m_update = RM_BEGIN { Out RM_DECL(color); // color output In RM_DECL(tex); // (x,y) coordinate input Value3f test = 0; Value1ui hitpoint = 0; // variables that determines whether we've hit something Value1ui zbit = 0, z = 0; // depth bitpacking variables Value3ui block; Value3f vox; // current voxel color = Value3f(0,0,0); // sets the default color output to black ////////// origin and direction calculation Value3f origin = m_gpu_origin; // reads the origin from the device memory Value3f direction = m_gpu_p1 + m_gpu_dx*tex[0] + m_gpu_dy*tex[1]; direction = direction - origin; // gets the correct direction from device memory direction = normalize(direction); // calculates the normalized direction vector ////////// ////////// 3d-dda grid traversal initialisation Value3f smin = Value3f(0,0,0); // scene minimum boundary Value3f cellStep = sign(direction); // returns the sign of the distance (-1 negative | 0 | positive 1) Value3f cellI = (cellStep == Value3f(1,1,1)); Value3i voxelid = 0; // determines the starting voxel id (using the camera origin) Value3i voxelid_next; // contains the next voxel id Value3f t = 0, tstep; // vector t determines the distance (in each iteration) to the nearest boundary on each axis Value3f world; // contains the world coordinates of a voxel Value1ui safe = 0; // safeguard to prevent endless loops and Bad Things (debugging purpose) ////////// ////////// voxel grid traversal code RM_WHILE( rapidmind::min(voxelid) >= 0 && rapidmind::max(voxelid) <= 8 && voxelid[1] < 1 // just some scene boundaries (stay within 0,0,0 and 8,5,8) && safe <= (Value1ui)32 // as long as our safeguard check is within reasonable bounds && hitpoint == (Value1ui)0 // and we haven't hit anything ) { // calculate the voxel according to the current t vector along the ray voxelid = (Value3i)(origin + t*direction); // calculate the voxel that is the next to hit our ray voxelid_next = voxelid + cellI; tstep = (voxelid_next - origin)/direction + (Value1f)0.00001f; // calculate the world coordinates of the voxel world = voxelid - smin; // use t to calculate the exact (entry) hit point and subtract the world coordinates // of the voxel so we get the entry point relative to the box (instead of the entry point in the world) Value3f hit_entry = ((t-(Value1f)0.00002f)*direction + origin) - world; // calculate the distance (in each iteration) to the nearest boundary on each axis t = rapidmind::min(tstep); // the t above gives us the distance (along the ray) to the entry point of our next voxel, // which is the exit point of our current voxel, so calculate the exact (exit) hit point // and subtract the world coordinates of the voxel so we get the local exit point Value3f hit_exit = ((t-(Value1f)0.00002f)*direction + origin) - world; ////////// HACK: swap the y and z axes and reverse the x axis (perhaps a proper fix would be to turn the world and the camera) Value1f temp; temp = hit_entry[2]; hit_entry[2] = hit_entry[1]; hit_entry[1] = temp; temp = hit_exit[2]; hit_exit[2] = hit_exit[1]; hit_exit[1] = temp; ////////// ////////// HACK: boundary check (prevents the caster from traversing blocks outside the scene) RM_IF(rapidmind::min(voxelid) < 0 || rapidmind::max(voxelid) > 8 || voxelid[1] >= (Value1ui)1){ hitpoint = 1; }RM_ENDIF; ////////// ////////// bresenham traversal initialisation Value3f steps, delta; Value1ui asteps_max, len; Value3ui asteps_cmb, asteps_neg; Value3i asteps; // calculate the data offsets for the horizontally aligned textures Value1ui off_volume = (voxelid[0]+voxelid[2]*8) * (Value1ui)RES; Value1ui off_lod = off_volume / (Value1ui)LOD_SIZE; //////////////////////////////// // scale the entry and exit points according to the box resolution hit_entry *= (Value1f)RES-(Value1f)1; hit_exit *= (Value1f)RES-(Value1f)1; // determine the bresenham traversal derivatives according to the entry and exit points steps = (hit_exit - hit_entry); asteps = abs(steps); // these instructions return delta (Value3) with "delta[biggest axis]=1.0*sign(steps[biggest axis])" and "delta[x]=(steps[x]/asteps[biggest axis])" asteps_max = rapidmind::max(asteps); // gets the maximum value for abs(steps) asteps_cmb = (asteps(0,1,2) == asteps_max(0,0,0)); // returns 1 for the maximum value, otherwise 0 asteps_neg = (asteps_cmb == Value3ui(0,0,0)); // returns 1 for everything except the maximum value (which returns 0) delta = asteps_cmb*sign(steps) + (asteps_neg * (steps/asteps_max)); // creates delta out of an addition of: // 1.0 or -1.0 (depending on the value's sign) for the biggest axis (and 0.0 elsewhere) // steps/asteps_max everywhere except for the biggest axis (which is 0.0) Value3i sgn = dot(asteps_cmb,sign(steps)); // determine the length of the traversal path len = asteps_max; // HACK: set a boundary safeguard, in case something went wrong (to prevent GPU freezing) RM_IF(len>=(Value1ui)300){ len = 0; }RM_ENDIF; // initialize the depth (z) value z = 0; ////////// ////////// bresenham traversal code vox = hit_entry; Value1ui i; // critical loop! this loop consumes most power so should be optimized down to the bare metal RM_FOR(i = 0, i < (Value1ui)len && hitpoint==(Value1ui)0, i+=1) { ////////// lod empty space skipping block = vox / (Value1ui)LOD_SIZE; // calculate the current block Value3ui block_next = (block + (Value1ui)1) * (Value1ui)LOD_SIZE; // determine the voxel position of the next block // optimize! Value3i delta_s = sign(delta); delta_s = (delta_s(0,1,2) == Value3i(-1,-1,-1)); // 1 for 0,1 --- 0 for -1 Value3ui block_dist = (block_next-(delta_s*(Value1ui)LOD_SIZE) - vox)/delta; // distance between the current voxel and the next block Value1ui boundary = rapidmind::min(block_dist); // find the smallest multiple of delta for which we cross a block boundary test = vox; Value1ub l = m_lod[Value2ub(off_lod+block[0],block[1])]; // get the lod data zbit = (Value1ui)1 << block[2]; // calculate the z-value Value1ui empty = sign(l & zbit); // empty: 1 for empty voxel, 0 for full voxel ////////// i += boundary*empty; Value4ui v = m_volume[Value2ub(off_volume+vox[0],vox[1])]; // get the volume data ////////// bitwise decoding z = vox[2]; // gets the z value from the traversal point zbit = (Value1ui)1 << (z & (Value1ui)31); // convert the z value into a bitvector with 1 on the location of z Value4ui div = floor( (z/(Value1ui)32) + (Value1f)0.5f ); // floor/+0.5f is a hack to work around rapidmind's native integer issues Value4ui mask = (div(0,0,0,0) == Value4ui(0,1,2,3)); // returns 1 for the corresponding index if div is 0, 1, 2 or 3 (e.g. if div is 2, mask is [0,0,1,0]) hitpoint = rapidmind::max(v*mask) & zbit; // gets the appropriate value from v, according to the mask generated by div, by using the bitvector zbit ////////// // increment the traversal point vox += delta; vox += (delta*boundary*empty); }RM_ENDFOR; ////////// ////////// HACK: safeguard to prevent Bad Things like endless loops safe += (Value1ui)1; ////////// }RM_ENDWHILE; ////////// ////////// HACK: output some debug colors Value1ui siz = (Value1f)RES; //color = vox/siz; color = test/siz; RM_IF(hitpoint){ // if we hit something Value1f d = z / siz; // calculate the color according to the depth //color = Value3f(d, d, d); }RM_ENDIF; ////////// } RM_END;