Power of well balanced octree

300 FPS when moves - Insane!

Small memory leak was driving me crazy; Debugging process was taking ages.. bored, frustrated and tired decided to play about with octrees depth and minimal/maximal number of elements in leaf.. Amazed by 300FPS discovered the stupid mistake of creating VBO each time the leaf is regenerated. Instant win; fix of memory leak and 10 times greater performance.

Who said that the mistakes are stupid?

Bonsai v0.2

256x256x256 8 - 9 FPS.. Need Optimisation already...

After hours spent on struggling with the VBO’s and GLSL I have managed to draw my first voxel based model.. the bonsai tree *fanfare*.
File loading time and processing takes about 20seconds, 8.3 FPS without culling or optimisation.. primitive brute force.. get all the points process them through marching cubes algorithm and then draw on the screen.. barbarity I know. but I had to start somehow.
Camera system allow to move around which is kind a nice..

Good night.

Voxel Engine – Idea Pitch

voxel (Volumetric Picture Element) is a volume element, representing a value on a regular grid in three dimensional space. – thank you wiki.

Voxel based engines are commonly used in medicine, simulations and gaming.

What the project will be about?

Main objective is to display world as set of voxels,

How will that happen?

Today I have started doing the research on how voxel data will be stored and how data structure will looks like. As the most simple solutions are almost always the best. I have decided to use image to storing voxel data. The idea is similar to hight map.. or maybe even better MRI screens – each image describes one level of brain, if we process atlas – the one you can see below; the output will be an array[][][] of Voxels. Very first application will processing arrays 16x16x16 – just to make sure if everything is working. I can see a problem with big arrays like 1024x1024x1024 but I will solve that later. As first approach I want to make it work.

Note: Instead of using images the solution with .raw files will be used.

I am planning to use Marching Cubes algorithm to display this volumetric data. The basic idea behind Marching Cubes algorithm is that “the algorithm proceeds through the scalar field, taking eight neighbor locations at a time (thus forming an imaginary cube), then determining the polygon(s) needed to represent the part of the isosurface that passes through this cube. The individual polygons are then fused into the desired surface.” – thank you wiki once again.

Voxel Class Prototype

class Voxel {

private:
glm::vec3 pos;
bool alive;
glColor3f color;

public:
Voxel();
~Voxel();
Draw();
Update(); //used in animations

}

This class eventually will be changed – I am pretty sure that will be one of the first things on “To Do” list.

At this moment I have fully working very simple application that displays empty window written in C++ and OpenGL4.0+GLSL 1.4 which will be used as a base for further development, by end of this week I should be ready to present working camera with first voxel primitives.

Where will I get dataset from?

I will use .raw files to storing objects dataset. Sample dataset can be found here.

What is .raw?

.raw is simple binary file that contains several values. In order to correct parse a raw file we need to know exact bit size of each value.

Will you give me a code?

Yes, I have found great method – sorry I can’t remember where – on how to parse the raw files that will be used in my engine.
The dataset use 8bit values and the method that will parse the file looks like:

uchar *** parseDataSet(char* filename, int sizeX, int sizeY, int sizeZ) {
uchar *** voxels = new uchar uchar**[sizeX];
FILE * file = fopen(filename, "rb");
if(file == NULL) {
printf("File not found: $s", filename);
exit(-1);
}

for(int x = 0; x< sizeX; x++)
{
voxels[x] = new uchar*[sizeY];
for(int y = 0; y< sizeY; y++){
voxels[x][y] = new uchar[sizeZ];
fread(voxels[x][y], sizeof(uchar), sizeZ, file);
}
}
return voxels;
}

What Marching Cubes is?

Marching cubes is a computer graphics algorithm, published in the 1987 Lorensen and Cline.

The algorithm uses precalculated array of 256 possible polygon configurations (28 = 256) within the cube, by treating each of the 8 scalar values as a bit in an 8-bit integer. If cube is inside the surface then the bit is set to one when outside it is set to zero. The final value after all 8 scalars are checked, is the actual index to the polygon indices array.

What I am going to use?

In research process my what I am going to use list is changing fairly frequently, lately I have discovered OpenCL which may improve performance of Voxel Engine.

The Edge Table

int edgeTable[256]={
0x0  , 0x109, 0x203, 0x30a, 0x406, 0x50f, 0x605, 0x70c,
0x80c, 0x905, 0xa0f, 0xb06, 0xc0a, 0xd03, 0xe09, 0xf00,
0x190, 0x99 , 0x393, 0x29a, 0x596, 0x49f, 0x795, 0x69c,
0x99c, 0x895, 0xb9f, 0xa96, 0xd9a, 0xc93, 0xf99, 0xe90,
0x230, 0x339, 0x33 , 0x13a, 0x636, 0x73f, 0x435, 0x53c,
0xa3c, 0xb35, 0x83f, 0x936, 0xe3a, 0xf33, 0xc39, 0xd30,
0x3a0, 0x2a9, 0x1a3, 0xaa , 0x7a6, 0x6af, 0x5a5, 0x4ac,
0xbac, 0xaa5, 0x9af, 0x8a6, 0xfaa, 0xea3, 0xda9, 0xca0,
0x460, 0x569, 0x663, 0x76a, 0x66 , 0x16f, 0x265, 0x36c,
0xc6c, 0xd65, 0xe6f, 0xf66, 0x86a, 0x963, 0xa69, 0xb60,
0x5f0, 0x4f9, 0x7f3, 0x6fa, 0x1f6, 0xff , 0x3f5, 0x2fc,
0xdfc, 0xcf5, 0xfff, 0xef6, 0x9fa, 0x8f3, 0xbf9, 0xaf0,
0x650, 0x759, 0x453, 0x55a, 0x256, 0x35f, 0x55 , 0x15c,
0xe5c, 0xf55, 0xc5f, 0xd56, 0xa5a, 0xb53, 0x859, 0x950,
0x7c0, 0x6c9, 0x5c3, 0x4ca, 0x3c6, 0x2cf, 0x1c5, 0xcc ,
0xfcc, 0xec5, 0xdcf, 0xcc6, 0xbca, 0xac3, 0x9c9, 0x8c0,
0x8c0, 0x9c9, 0xac3, 0xbca, 0xcc6, 0xdcf, 0xec5, 0xfcc,
0xcc , 0x1c5, 0x2cf, 0x3c6, 0x4ca, 0x5c3, 0x6c9, 0x7c0,
0x950, 0x859, 0xb53, 0xa5a, 0xd56, 0xc5f, 0xf55, 0xe5c,
0x15c, 0x55 , 0x35f, 0x256, 0x55a, 0x453, 0x759, 0x650,
0xaf0, 0xbf9, 0x8f3, 0x9fa, 0xef6, 0xfff, 0xcf5, 0xdfc,
0x2fc, 0x3f5, 0xff , 0x1f6, 0x6fa, 0x7f3, 0x4f9, 0x5f0,
0xb60, 0xa69, 0x963, 0x86a, 0xf66, 0xe6f, 0xd65, 0xc6c,
0x36c, 0x265, 0x16f, 0x66 , 0x76a, 0x663, 0x569, 0x460,
0xca0, 0xda9, 0xea3, 0xfaa, 0x8a6, 0x9af, 0xaa5, 0xbac,
0x4ac, 0x5a5, 0x6af, 0x7a6, 0xaa , 0x1a3, 0x2a9, 0x3a0,
0xd30, 0xc39, 0xf33, 0xe3a, 0x936, 0x83f, 0xb35, 0xa3c,
0x53c, 0x435, 0x73f, 0x636, 0x13a, 0x33 , 0x339, 0x230,
0xe90, 0xf99, 0xc93, 0xd9a, 0xa96, 0xb9f, 0x895, 0x99c,
0x69c, 0x795, 0x49f, 0x596, 0x29a, 0x393, 0x99 , 0x190,
0xf00, 0xe09, 0xd03, 0xc0a, 0xb06, 0xa0f, 0x905, 0x80c,
0x70c, 0x605, 0x50f, 0x406, 0x30a, 0x203, 0x109, 0x0   };

OpenCL 1.1

Need to do more research but as far as I know:
“OpenCL gives any application access to the Graphics Processing Unit for non-graphical computing. Thus, OpenCL extends the power of the Graphics Processing Unit beyond graphics ”
which sounds pretty awesome!

Current list:

  • C++
  • OpenGL 4.0
  • OpenCL 1.1
  • GLEW
  • GLUT
  • GLM
  • GLSL 1.4
  • .raw
  • Marching Cubes