One of the questions that I have been asked lately

Imagine situation where we have a numbers from 1 to 100 all incrementing so we have 1,2,3, … ,99,100. Now we take one of them from this pool – randomly, then we are randomize order of rest of them.

Question: what is the best way of finding out which number has been taken, and what is complexity of your algorithm?


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

[cc lang=”c++”]

class Voxel {

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

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:
[cc lang=”c++”]
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);

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


[cc lang=”c++”]
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


All Right – Get back to work

No more excuses – this weekend’s aim:
OpenGL 4.0 + GLSL + GLM and math books!

Last couple weeks was really lazy.. well not lazy lazy.. I have done a lot.. well not game dev and I feel really bad with that.

Oh and I have discovered that Edinburgh is Rollerblades unfriendly city!