StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>For the record, this is my implementation of the Revelles paper I ended up using:</p> <pre><code>#include "octree_traversal.h" using namespace std; unsigned char a; // because an unsigned char is 8 bits int first_node(double tx0, double ty0, double tz0, double txm, double tym, double tzm){ unsigned char answer = 0; // initialize to 00000000 // select the entry plane and set bits if(tx0 > ty0){ if(tx0 > tz0){ // PLANE YZ if(tym < tx0) answer|=2; // set bit at position 1 if(tzm < tx0) answer|=1; // set bit at position 0 return (int) answer; } } else { if(ty0 > tz0){ // PLANE XZ if(txm < ty0) answer|=4; // set bit at position 2 if(tzm < ty0) answer|=1; // set bit at position 0 return (int) answer; } } // PLANE XY if(txm < tz0) answer|=4; // set bit at position 2 if(tym < tz0) answer|=2; // set bit at position 1 return (int) answer; } int new_node(double txm, int x, double tym, int y, double tzm, int z){ if(txm < tym){ if(txm < tzm){return x;} // YZ plane } else{ if(tym < tzm){return y;} // XZ plane } return z; // XY plane; } void proc_subtree (double tx0, double ty0, double tz0, double tx1, double ty1, double tz1, Node* node){ float txm, tym, tzm; int currNode; if(tx1 < 0 || ty1 < 0 || tz1 < 0) return; if(node->terminal){ cout << "Reached leaf node " << node->debug_ID << endl; return; } else{ cout << "Reached node " << node->debug_ID << endl;} txm = 0.5*(tx0 + tx1); tym = 0.5*(ty0 + ty1); tzm = 0.5*(tz0 + tz1); currNode = first_node(tx0,ty0,tz0,txm,tym,tzm); do{ switch (currNode) { case 0: { proc_subtree(tx0,ty0,tz0,txm,tym,tzm,node->children[a]); currNode = new_node(txm,4,tym,2,tzm,1); break;} case 1: { proc_subtree(tx0,ty0,tzm,txm,tym,tz1,node->children[1^a]); currNode = new_node(txm,5,tym,3,tz1,8); break;} case 2: { proc_subtree(tx0,tym,tz0,txm,ty1,tzm,node->children[2^a]); currNode = new_node(txm,6,ty1,8,tzm,3); break;} case 3: { proc_subtree(tx0,tym,tzm,txm,ty1,tz1,node->children[3^a]); currNode = new_node(txm,7,ty1,8,tz1,8); break;} case 4: { proc_subtree(txm,ty0,tz0,tx1,tym,tzm,node->children[4^a]); currNode = new_node(tx1,8,tym,6,tzm,5); break;} case 5: { proc_subtree(txm,ty0,tzm,tx1,tym,tz1,node->children[5^a]); currNode = new_node(tx1,8,tym,7,tz1,8); break;} case 6: { proc_subtree(txm,tym,tz0,tx1,ty1,tzm,node->children[6^a]); currNode = new_node(tx1,8,ty1,8,tzm,7); break;} case 7: { proc_subtree(txm,tym,tzm,tx1,ty1,tz1,node->children[7^a]); currNode = 8; break;} } } while (currNode<8); } void ray_octree_traversal(Octree* octree, Ray ray){ a = 0; // fixes for rays with negative direction if(ray.direction[0] < 0){ ray.origin[0] = octree->size[0] - ray.origin[0]; ray.direction[0] = - ray.direction[0]; a |= 4 ; //bitwise OR (latest bits are XYZ) } if(ray.direction[1] < 0){ ray.origin[1] = octree->size[1] - ray.origin[1]; ray.direction[1] = - ray.direction[1]; a |= 2 ; } if(ray.direction[2] < 0){ ray.origin[2] = octree->size[2] - ray.origin[2]; ray.direction[2] = - ray.direction[2]; a |= 1 ; } double divx = 1 / ray.direction[0]; // IEEE stability fix double divy = 1 / ray.direction[1]; double divz = 1 / ray.direction[2]; double tx0 = (octree->min[0] - ray.origin[0]) * divx; double tx1 = (octree->max[0] - ray.origin[0]) * divx; double ty0 = (octree->min[1] - ray.origin[1]) * divy; double ty1 = (octree->max[1] - ray.origin[1]) * divy; double tz0 = (octree->min[2] - ray.origin[2]) * divz; double tz1 = (octree->max[2] - ray.origin[2]) * divz; if( max(max(tx0,ty0),tz0) < min(min(tx1,ty1),tz1) ){ proc_subtree(tx0,ty0,tz0,tx1,ty1,tz1,octree->root); } } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload