So there's the progress on the GUI so far. As I plan on making it the usual, here is the branch on GitHub.
There's nothing particularly fancy to report, it's yet another GUI framework for OpenGL, but this has the almost unique distinction of being written in C99. It's all WIP, so if you use it, don't be surprised when the next version breaks everything.
Showing posts with label C. Show all posts
Showing posts with label C. Show all posts
Sunday, June 2, 2013
GUI progress
So there's the progress on the GUI so far. As I plan on making it the usual, here is the branch on GitHub.
There's nothing particularly fancy to report, it's yet another GUI framework for OpenGL, but this has the almost unique distinction of being written in C99. It's all WIP, so if you use it, don't be surprised when the next version breaks everything.
Thursday, November 22, 2012
One Shiny Dragon + Source
This is viewing a hollow shell of the XYZ RGB Asian Dragon at 1024^3, using what I've written so far of my attempt to implement Cyril Crassin's GigaVoxel method.
At the moment it would be optimistic to say I have partly implemented a quarter of it, but it's capable of drawing shiny dragons, and I'd like to share them :-)
The original dragon has a tad more detail than 2048^3 can store, which I intend to address in the next phase of the method, mip-mapping. In the mean time, I for one always get sad when I read a blog post about something really cool, and I can't play with it myself.
GitHub - Win32 Binaries - zlib licensed.
This should build with minimal fiddling on your favourite linux distro. I use Debian, but it only depends on X and zlib, so should be easy to build. It also loves clang. It's written in pure C99, at least that's what I tell the compiler.
To all yee who explore the source code, fair warning, it's a hatchet job. With that in mind I hope it should make a kind of sense. The first thing you'll want to look at is the
A 1024^3 cube is big. That's out of the box we're talking about a Gigabyte of data if we're only using a single byte per voxel, but I'm using 4 floats. This means we don't have enough video memory. Well, it's sparse, which brings it down to 900Mb. The texture data is zipped up with zlib, which brings the data file down to a much more reasonable 17Mb. It's still extracting to 900Mb of RAM though.Due to ?!?!?, the current Nvidia drivers don't like me allocating 900Mb of texture memory on Windows 7, so the drivers convert it to 16bit floats, bringing it down to 450Mb, which it's quite happy with. This doesn't seem to affect performance in this instance, as I'm already abusing the video card in plenty of other ways. 64bit executables solve this problem, I've updated the binary and now it does allocate the full 900Mb.
The idea is
This is where we find the initialisation, the texture block is decompressed with zlib, and loaded into a vanilla old OpenGL 3D floating point texture. The Node Pool is loaded into the format that Nvidia requires when you're planning on breaking the legs of the GLSL standard, like I am doing here. The main brains of the program is located in the fragment shader, which this file dutifully loads and compiles it ready for the GPU to use. The final text in this file is a few lines that update variables for the shader, such as the camera position, and then render a single flat polygon covering the whole screen. As all of the work is done in the fragment shader, it will be called once per pixel on the screen (unless you're using antialiasing, then this will run horribly slow, and at no visual benefit at all, this rendering method is aliasing free to begin with). OpenGL experts will marvel at how primitively I'm drawing the quad, and possibly be driven to self harm. Pressing the R key will reload the shader from disk, useful for debugging.
To understand this code you'll really have to read Cyril Crassin's PhD, which can be found here. The quick version is that for each pixel it traces a path through the Sparse Voxel Octtree that was built by
GitHub - Win32 Binaries - zlib licensed.
This should build with minimal fiddling on your favourite linux distro. I use Debian, but it only depends on X and zlib, so should be easy to build. It also loves clang. It's written in pure C99, at least that's what I tell the compiler.
Going Deeper...
To all yee who explore the source code, fair warning, it's a hatchet job. With that in mind I hope it should make a kind of sense. The first thing you'll want to look at is the
Makefile. convert and convertoct convert simple Wavefront OBJ files, as output by Blender, into a format suitable for throwing at a video card. Worth grabbing the win32 binaries for the included data file, it's not in the git repo.
convert and polyview
convert turns the OBJ file into the format that polyview expects for a VBO. polyview loads the file into memory, tells OpenGL where it is in memory and how it's formatted, and runs a simple display loop. It's not terribly clever, but it does push all of the load onto the video card, leaving the CPU idle in my tests.
convertoct and octview
convertoct produces a Sparse Voxel Octtree by discarding the polygons of a mesh file produced by convert, and throwing the points (and their normals) into a buffer. Hatchet Job. So this will only work with models that have a uniform vertex density, mostly 3D scanned objects (like the dragon, and the bunny).
The Data
A 1024^3 cube is big. That's out of the box we're talking about a Gigabyte of data if we're only using a single byte per voxel, but I'm using 4 floats. This means we don't have enough video memory. Well, it's sparse, which brings it down to 900Mb. The texture data is zipped up with zlib, which brings the data file down to a much more reasonable 17Mb. It's still extracting to 900Mb of RAM though.
The Build System & Porting
The idea is
win32.c and x11.c are "shivs", all platform dependant things are in there, they obey their respective OS's rules, and they toggle fullscreen when pressing F11. They call main_* functions in polyview.c or octview.c depending which one is linked. polyview.c has almost no intelligence at all, it's just a test mesh displayer. octview.c is marginally better, providing simple FPS controls, and handballing off to voxel.c. Making a osx.c shiv should be pretty easy, and I'm fairly sure I already have one laying around from an older project.
voxel.c
This is where we find the initialisation, the texture block is decompressed with zlib, and loaded into a vanilla old OpenGL 3D floating point texture. The Node Pool is loaded into the format that Nvidia requires when you're planning on breaking the legs of the GLSL standard, like I am doing here. The main brains of the program is located in the fragment shader, which this file dutifully loads and compiles it ready for the GPU to use. The final text in this file is a few lines that update variables for the shader, such as the camera position, and then render a single flat polygon covering the whole screen. As all of the work is done in the fragment shader, it will be called once per pixel on the screen (unless you're using antialiasing, then this will run horribly slow, and at no visual benefit at all, this rendering method is aliasing free to begin with). OpenGL experts will marvel at how primitively I'm drawing the quad, and possibly be driven to self harm. Pressing the R key will reload the shader from disk, useful for debugging.
render.frag
To understand this code you'll really have to read Cyril Crassin's PhD, which can be found here. The quick version is that for each pixel it traces a path through the Sparse Voxel Octtree that was built by
convertoct. There's nothing more complicated than that going on, so there's currently no point comparing it to Gigavoxels. Also it does it in GLSL, as opposed to a real GPU compute language, so mine is an amusing abuse of GPU power, at best. For now...
Sunday, February 19, 2012
OpenCL Compilation Tool
I wrote a simple OpenCL compiler interface tool, partially to sink my teeth into OpenCL, partially because I wanted it. Also it seems I'm one of the few who's tackling OpenCL from a pure C angle, so this code may be useful to other folks going down that path.
If compilation works, it tells you how many bytes the binary is. If it fails, it outputs the compiler messages. That's it. It's a single C file, the linked archive includes a Makefile for Mingw, and a binary for windows. It's so simple you should have *no* problems building it on anything. Compiles with gcc and clang with -Wall with no warnings. What more could you want? Features? Use clcc.
It should be noted, that there is already a tool that does this, clcc, which supports... well... options. All of them it seems. It's written in C++, uses Boost, etc. I encourage folks to use that one instead of mine, it's much better. But if you're a fan of KISS, then you might want to check out mine. But clcc is better. On with the show...
Invoking it displays it's usage...
D:\code\opencl\ocl>ocl
OpenCL Compiler Test Tool
(c) 2012 Daniel Burke - dan.p.burke@gmail.com
USAGE:
ocl
display arguments and devices
ocl filename
compile filename with first device
ocl N filename
compile filename with Nth device
The Device list is...
-----------------------
AMD Accelerated Parallel Processing
0 ATI RV770
1 ATI RV770
2 Intel(R) Core(TM)2 Duo CPU E8600 @ 3.33GHz
Intel(R) OpenCL
3 Intel(R) Core(TM)2 Duo CPU E8600 @ 3.33GHz
If compilation works, it tells you how many bytes the binary is. If it fails, it outputs the compiler messages. That's it. It's a single C file, the linked archive includes a Makefile for Mingw, and a binary for windows. It's so simple you should have *no* problems building it on anything. Compiles with gcc and clang with -Wall with no warnings. What more could you want? Features? Use clcc.
Wednesday, January 5, 2011
Octtree's for Two
Next time you're out having dinner with that special someone, why not strike up a romantic conversation about Octtrees? For just such an occasion, here is what I've figured out about the subject.
An octtree can be thought of as a 3 dimensional binary tree. Typically in a tree the OO mentality would suggest that we create objects for each node, with pointers to the child nodes. But we're using C, and want to avoid all of that hassle. If only there was a clever way to avoid all of that setup. With an array.
First of all, we want to malloc() some memory for this. Each node in an octtree has 8 child nodes, so for an Octtree with 1 layer, there are 9 nodes (1 for the root, and 8 children). For 2 layers there are 73 nodes, and for 3 layers 585. But we're playing with Octtrees, surely there is a trick for figuring out these numbers. If we look at those numbers in Octal, things become clearer. $9_{10}$ in octal is $11_8$. $73_{10}$ in octal is $111_8$, $585_{10}$ in octal is $1111_8$. So we can safely say a $6_{10}$ layer octtree has $1111111_8$ nodes in it. One octal number takes 3 bits to represent, so we can cheat.
Unfortunately we have imposed a limit on ourselves with this function, of having octtree's with no more than 10 layers in them. But if you really need an Octtree with more than 1,227,133,513 nodes in it, you'll be able to adjust the function yourself.
If we create a 4 layer octtree, and want the offset in the array of the first element of the 4th layer,
$8^4 = 2^4 \times 2^4 \times 2^4$
or
$4096 = 16 \times 16 \times16$
Now we have allocated our octtree, we want to start populating it with data. So we need a uniform method of mapping space to a branch in the tree. This borders into Space filling curves, but we can do something easier than that. As mentioned earlier, an octal digit takes 3 bits to store, one for each spatial dimension. We can use Morton Numbers for this. Here is a pair of functions that will do the job
So if our octtree is covering 1000.0f units of space (and is an even cube for simlicity), and is 4 layers deep, then each cell on the leaf node layer is $\dfrac{1000}{2^4} = 62.5$ units along each edge. So to find the node into which to insert our point of data (p), we do this
Now before you go and index into your array, don't forget you need to add the offset of the current layer to that.
Now you're probably wondering why I'm keeping the layer offset and the cell offset in separate variables. Here's why...
As I've been harping on about, octal numbers take 3 bits. And I've rather conspicuously avoided talking about tree traversal. That is because we are going to traverse the tree from bottom to top. So that node we've just populated with data, we want to find it's parent node, couldn't be easier.
Want to find the neighboring nodes of the leaf we were just looking at?
These techniques apply to n-dimensional binary trees. Want a Quad-Tree? Morton numbers with 2 variables is the canonical example. A Binary tree? Morton numbers with 1 variable are just the same number. Enjoy!
Hors d'œuvres
An octtree can be thought of as a 3 dimensional binary tree. Typically in a tree the OO mentality would suggest that we create objects for each node, with pointers to the child nodes. But we're using C, and want to avoid all of that hassle. If only there was a clever way to avoid all of that setup. With an array.
First of all, we want to malloc() some memory for this. Each node in an octtree has 8 child nodes, so for an Octtree with 1 layer, there are 9 nodes (1 for the root, and 8 children). For 2 layers there are 73 nodes, and for 3 layers 585. But we're playing with Octtrees, surely there is a trick for figuring out these numbers. If we look at those numbers in Octal, things become clearer. $9_{10}$ in octal is $11_8$. $73_{10}$ in octal is $111_8$, $585_{10}$ in octal is $1111_8$. So we can safely say a $6_{10}$ layer octtree has $1111111_8$ nodes in it. One octal number takes 3 bits to represent, so we can cheat.
int ot_size(int depth)
{
return 011111111111 & (0xFFFFFFFF >> (32-(depth*3 + 1)));
}
Code Explanation
Prefixing a zero is how you write in Octal in C. We're trimming down the 0xFFF's down to the length we want, so we can get enough octal 1's for the size octtree we want. (Depth * 3) is because each octal digit is 3 bits long.Wait a minute...
Why the plus one? Lets take a tree, With a root layer, 1 node, first layer, 8 nodes and second layer, 64 nodes. For calculating the size of the node, it works best to describe this as a 3 layer octtree because we need 3 octal digits to count the number of nodes. Like the good C programmers we are, our layers are indexed starting from 0. So while the root node technically is a layer, it's a very special case. Later when I'm saying a "3 layer tree", you can pretend I'm saying "3 layers plus a root node".Unfortunately we have imposed a limit on ourselves with this function, of having octtree's with no more than 10 layers in them. But if you really need an Octtree with more than 1,227,133,513 nodes in it, you'll be able to adjust the function yourself.
If we create a 4 layer octtree, and want the offset in the array of the first element of the 4th layer,
ot_size(3);will give it to us. Incidentally, the leaf layer contains 8 to the 4th power nodes, and in each dimension there is 2 to the 4th power of nodes. We can prove this as
$8^4 = 2^4 \times 2^4 \times 2^4$
or
$4096 = 16 \times 16 \times16$
Main Course
Now we have allocated our octtree, we want to start populating it with data. So we need a uniform method of mapping space to a branch in the tree. This borders into Space filling curves, but we can do something easier than that. As mentioned earlier, an octal digit takes 3 bits to store, one for each spatial dimension. We can use Morton Numbers for this. Here is a pair of functions that will do the job
int spread_bits(int x)
{
x = (x | (x << 16)) & 0x030000FF;
x = (x | (x << 8)) & 0x0300F00F;
x = (x | (x << 4)) & 0x030C30C3;
x = (x | (x << 2)) & 0x09249249;
return x;
}
int cell_offset(int x, int y, int z)
{
return spread_bits(x)
| spread_bits(y) << 1
| spread_bits(z) << 2;
}
So if our octtree is covering 1000.0f units of space (and is an even cube for simlicity), and is 4 layers deep, then each cell on the leaf node layer is $\dfrac{1000}{2^4} = 62.5$ units along each edge. So to find the node into which to insert our point of data (p), we do this
int x,y,z, offset;
x = (int)(p.x / 62.5f);
y = (int)(p.y / 62.5f);
z = (int)(p.z / 62.5f);
offset = cell_offset(x,y,z);
Now before you go and index into your array, don't forget you need to add the offset of the current layer to that.
int layer = ot_size(3);
int target = layer + offset;
Now you're probably wondering why I'm keeping the layer offset and the cell offset in separate variables. Here's why...
Dessert
As I've been harping on about, octal numbers take 3 bits. And I've rather conspicuously avoided talking about tree traversal. That is because we are going to traverse the tree from bottom to top. So that node we've just populated with data, we want to find it's parent node, couldn't be easier.
layer = layer >> 3;
offset = offset >> 3;
target = layer+offset;
Want to find the neighboring nodes of the leaf we were just looking at?
offset = layer+cell_offset(x+1, y, z);
After Dinner Mint
These techniques apply to n-dimensional binary trees. Want a Quad-Tree? Morton numbers with 2 variables is the canonical example. A Binary tree? Morton numbers with 1 variable are just the same number. Enjoy!
Fluid Simulation Goodness
Just got the fluid simulation code I've been working on to the point where it works correctly. Until I get something more impressive, enjoy this video of a dot vortex!
If you're interested in playing with this yourself, check out the excellent articles by Dr Michael Gourlay over at the Intel Software site.
I should note, this simulation has 27000 particles in it, and runs at 60fps while using about 60% of one of my cores (on a 3.33Ghz c2d). That's without any optimisation, and full debug symbols compiled in.
Subscribe to:
Posts (Atom)