# Uniform Spatial Subdivision

Hi I’m trying to implement the Uniform Spatial subdivision for a ray tracing class and trying to implement it using the algorithm given in Fundamentals of Computer Graphics by Peter Shirley. I’m trying to understand how voxels are created in C++. Trying to define the gird here but I’m stuck at constructing or rather defining the grid n divide them into cells.

``````struct Bound

{

Float3 minBound;

Float3 maxBound;

Float3 center;

float dia;

}B;

int nbox;

typedef struct:  public Bound {

int nx,ny,nz;

int Ghit(Ray ray,int hitrec);//Bound *box,,

void BuildGrid();

triangle tri;

}Grid;

Grid G;

std::vector<Grid> cell;
``````

I was trying to trace the cells along the ray and store it in an array and then call it in another function and check whether it has the triangles also intersects the them. This what I have done so far.

``````int Grid::Ghit(Ray ray,	int hitrec, Bound *box)//,

{

int I_inc, I_stop, J_inc, J_stop, K_inc, K_stop;

I_inc = J_inc = K_inc = 0;

I_stop = G.nx - 1;  J_stop = G.ny - 1;  K_stop = G.nz - 1;

float dtX,dtY,dtZ;

float tXnext, tYnext, tZnext , tlast;

Float3 pointOnRay = ray.ray_o + Scale(ray.ray_d, ray.tMax);

if(ray.ray_d.X >= 0.0f )

{

txmin = (box->minBound.X - ray.ray_o.X)/ray.ray_d.X;

I_inc += 1;

I_stop = nx;

}

else

{

txmin = (box->maxBound.X - ray.ray_o.X)/ray.ray_d.X;

txmax = (box->minBound.X - ray.ray_o.X)/ray.ray_d.X;

I_inc -= 1;

I_stop = -1;

}

if(ray.ray_d.Y >= 0.0f)

{

tymin = (box->minBound.Y - ray.ray_o.Y)/ray.ray_d.Y;

tymax = (box->maxBound.Y - ray.ray_o.Y)/ray.ray_d.Y;

J_inc += 1;

J_stop = ny;

}

else

{

tymin = (box->maxBound.Y - ray.ray_o.Y)/ray.ray_d.Y;

tymax = (box->minBound.Y - ray.ray_o.Y)/ray.ray_d.Y;

J_inc -= 1;

J_stop = -1;

}

if(txmin > tymax || tymin > txmax) return false;

if(ray.ray_d.Z >= 0.0f)

{

tzmin = (box->minBound.Z - ray.ray_o.Z)/ray.ray_d.Z;

tzmax = (box->maxBound.Z - ray.ray_o.Z)/ray.ray_d.Z;

K_inc += 1;

K_stop = nz;

}

else

{

tzmin = (box->maxBound.Z - ray.ray_o.Z)/ray.ray_d.Z;

tzmax = (box->minBound.Z - ray.ray_o.Z)/ray.ray_d.Z;

K_inc -= 1;

K_stop = -1;

}

if(tzmin > txmax || txmin > tzmax) return false;

if(tzmin > tymax || tymin > tzmax) return false;

dtX = (txmax - txmin)/nx;

dtY = (tymax - tymin)/ny;

dtZ = (tzmax - tzmin)/nz;

int  I, J, K;

// if a point on the ray is inside the grid

if(ray.tMin >= box->minBound.X)

{

I = floor(nx*(pointOnRay.X - box->minBound.X)/(box->maxBound.X - box->minBound.X));

if(I < 0) I = 0;

if(I > nx - 1) I = nx - 1;

J = floor(ny*(pointOnRay.Y- box->minBound.Y)/(box->maxBound.Y - box->minBound.Y));

if(J < 0) J = 0;

if(J > ny-1) J = ny - 1;

K = floor(nz*(pointOnRay.Z - box->minBound.Z)/(box->maxBound.Z - box->minBound.Z));

if(K < 0 ) K = 0;

if(K > nz-1) K = nz - 1;

tXnext = txmin + (I + (I_inc + 1)/2)*dtX;

tYnext = tymin + (J + (J_inc + 1)/2)*dtY;

tZnext = tzmin + (K + (I_inc + 1)/2)*dtZ;

tlast = ray.tMin;

}

else if (txmin > tymin && txmin > tzmin)

{

I = I_stop - I_inc;

pointOnRay.Y = ray.ray_o.Y + ray.tMin;//txminyd;

J = floor(ny*(pointOnRay.Y - box->minBound.Y)/(box->maxBound.Y- box->minBound.Y));

if(J < 0) J = 0;

if(J > ny-1) J = ny-1;

pointOnRay.Z = ray.ray_o.Z + ray.tMin; //tyminZd;

K = floor(nz*(pointOnRay.Z - box->minBound.Z)/(box->maxBound.Z- box->minBound.Z));

if(K < 0 ) K = 0;

if(K > nz-1) K = nz-1;

tXnext = txmin + dtX;

tYnext = tymin + (J + (J_inc + 1)/2)*dtY;

tZnext = tzmin + (K + (K_inc + 1)/2)*dtZ;

tlast = txmin;

}

else if(tymin > tzmin)

{

J = J_stop - J_inc;

pointOnRay.X = ray.ray_o.X + ray.tMin; //tyminxd

I = floor(nx*(pointOnRay.X - box->minBound.X)/(box->maxBound.X - box->minBound.X));

if(I < 0) I = 0;

if(I > nx-1) I = nx-1;

pointOnRay.Z = ray.ray_o.Z + ray.tMin; //tyminzd

K = floor(nz*(pointOnRay.Z - box->minBound.Z)/(box->maxBound.Z- box->minBound.Z));

if(K < 0 ) K = 0;

if(K > nz -1) K = nz -1;

tYnext = tymin + dtY;

tXnext = txmin + (I + (I_inc + 1)/2)*dtX;

tZnext = tzmin + (K + (K_inc + 1)/2)*dtZ;

tlast = tymin;

}

else K = K_stop - K_inc;

pointOnRay.X = ray.ray_o.X + ray.tMin;//tzminxd

I = floor(nx*(pointOnRay.X - box->minBound.X)/(box->maxBound.X- box->minBound.X));

if (I < 0 ) I = 0;

if (I > nx - 1) I = nx - 1;

pointOnRay.Y = ray.ray_o.Y + ray.tMin; //tzminyd

J = floor(nx*(pointOnRay.Y - box->minBound.Y)/(box->maxBound.Y- box->minBound.Y));

if(J < 0) J=0;

if(J > ny-1) J = ny-1;

tZnext = tzmin + dtZ;

tXnext = txmin + (I + (I_inc + 1)/2)*dtX;

tYnext = tymin + (J + (J_inc + 1)/2)*dtZ;

tlast = tzmin;

if(tlast > ray.tMax) return false;

while(true)

{

if(tXnext < tYnext && tXnext < tZnext)

{

if(cell[I,J].Ghit(ray, hitrec) && hitrec < ray.tMax) //box //ray,tlast,tXnext,rec

return true;

tlast = tXnext;

tXnext += dtX;

I += I_inc;

if(I==I_stop) return false;

}

else if(tYnext < tZnext)

{

if(cell[I,J].Ghit(ray, hitrec) && hitrec < ray.tMax) //box //ray,tlast,tXnext,rec

return true;

tlast = tYnext;

tYnext += dtY;

J += J_inc;

if(J==J_stop) return false;

}

else

{

if(cell[I,J].Ghit(ray,hitrec) && hitrec < ray.tMax) //box //ray,tlast,tXnext,rec

return true;

tlast = tZnext;

tZnext += dtZ;

K += K_inc;

if(K==K_stop) return false;

}

}

}

bool ray_uss_intersection(Ray ray, Grid *G, float *ray_t, float *t_beta, float *t_gamma )

{

int USS_hitID = -1;

bool USS_hit = G->Ghit(ray, USS_hitID);

int M, N;

if(USS_hit)

{

while (&cell!= NULL)

{

int Tri_hitID = ray_trianglelist_intersection(ray, &cell[M,N].tri, ray_t, t_beta, t_gamma);

if (Tri_hitID >= 0 )//&& the point is inside the cell

{

//grid = cell[USS_hit];

return Tri_hitID;

}

}

}

return -1;

}

int ray_scene_intersection(Ray ray, Grid *G, Bound *B, float *ray_t, float *t_beta, float *t_gamma)

{

// Step I: Do bounding box test

if (ray_box_intersection(ray, *B))

return ray_trianglelist_intersection(ray, T, ray_t, t_beta, t_gamma);

//return ray_uss_intersection(ray, G, ray_t, t_beta, t_gamma);

else return -1;

//

// Step II:  Do bounding box test

// if (ray_box_intersection(ray, *B))

//    //return ray_uss_intersection(ray, G);

////

//return ray_trianglelist_intersection(ray, T, ray_t, t_beta, t_gamma);

}
``````

Does anyone know a simple way to create the voxels n the grid.

Thanks

Posted the same question and found the answer in the meantime.

If you follow the ray from origin to a hitpoint: you always travel from low cell numbers to high cell numbers even if you enter in for example cell[nx-1][ny-1][nz-1] (So those cell numbers need to be converted.) Secondly, the first cell you enter when you increment cells is the lowest cell number and the first cell you enter when you decrement cells is the highest cell (so not the other way arround as in the book).

http://stackoverflow.com/questions/20302119/3d-regular-grid-acceleration-structure-for-a-ray-tracer-algorithm-bug/20311591#20311591

Greetz.