octree traversal problems
3ddes...@gmx.de
I am using the octree traversal algorithm described in the paper "An
Efficient Parametric Algorithm for Octree Traversal" by J. Revelles, C.
Urena, M. Lastra
http://cg.cs.uni-bonn.de/docs/teaching/2004/WS/photo/documents/Octree%20Traversal,%20WSCG.pdf
but I have problems making it work correctly.
I have my octree nodes in the same order as described in the paper, but
it doesn´t find the leaf nodes somehow. I must have a bug in there
somewhere.
Maybe someone could have a look at it.
Thanks in advance.
Here is the code:
void proc_subtree(Real tx0,Real ty0,Real tz0,
Real tx1,Real ty1,Real tz1,
InstOctree *n,std::vector<InstOctree>* nodes,Vector origin)
{
if(!n || !n->IsValid()) return;
Real txm,tym,tzm;
int currNode;
if(tx1<0 || ty1<0.0 || tz1<0.0)
return;
if(n->IsLast())
{
//Add this node
nodes->push_back(*n);
return;
}
txm = txm = 0.5 * (tx0 + tx1);
tym = tym = 0.5 * (ty0 + ty1);
tzm = 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,
n->GetChild(a),nodes,origin);
currNode = next_node(txm, 4, tym, 2, tzm, 1);
break;
case 1:
proc_subtree(tx0, ty0, tzm, txm, tym, tz1,
n->GetChild(1^a),nodes,origin);
currNode = next_node(txm, 5, tym, 3, tz1, 8);
break;
case 2:
proc_subtree(tx0, tym, tz0, txm, ty1, tzm,
n->GetChild(2^a),nodes,origin);
currNode = next_node(txm, 6, ty1, 8, tzm, 3);
break;
case 3:
proc_subtree(tx0, tym, tzm, txm, ty1, tz1,
n->GetChild(3^a),nodes,origin);
currNode = next_node(txm, 7, ty1, 8, tz1, 8);
break;
case 4:
proc_subtree(txm, ty0, tz0, tx1, tym, tzm,
n->GetChild(4^a),nodes,origin);
currNode = next_node(tx1, 8, tym, 6, tzm, 5);
break;
case 5:
proc_subtree(txm, ty0, tzm, tx1, tym, tz1,
n->GetChild(5^a),nodes,origin);
currNode = next_node(tx1, 8, tym, 7, tz1, 8);
break;
case 6:
proc_subtree(txm, tym, tz0, tx1, ty1, tzm,
n->GetChild(6^a),nodes,origin);
currNode = next_node(tx1, 8, ty1, 8, tzm, 7);
break;
case 7:
proc_subtree(txm, tym, tzm, tx1, ty1, tz1,
n->GetChild(7^a),nodes,origin);
currNode = 8;
break;
}
}
while(currNode < 8);
}
void InstOctree::BrowseOctree(InstOctree *pNode, Ray*
r,std::vector<InstOctree>* nodes)
{
if(!pNode || !pNode->IsValid()) return;
Ray ray = *r;
Vector center = pNode->GetCenter();
Vector size = pNode->GetWidth();
a = 0;
if(ray.v.x<0.0)
{
ray.p.x = size.x-ray.p.x;
ray.v.x = -ray.v.x;
a |= 4;
}
if(ray.v.y<0.0)
{
ray.p.y = size.y-ray.p.y;
ray.v.y = -ray.v.y;
a |= 2;
}
if(ray.v.z<0.0)
{
ray.p.z = size.z-ray.p.z;
ray.v.z = -ray.v.z;
a |= 1;
}
Vector min = Vector(center.x - size.x, center.y - size.y, center.z -
size.z);
Vector max = Vector(center.x + size.x, center.y + size.y, center.z +
size.z);
Real tx0 = (min.x - ray.p.x)/ray.v.x;
Real tx1 = (max.x - ray.p.x)/ray.v.x;
Real ty0 = (min.y - ray.p.x)/ray.v.y;
Real ty1 = (max.y - ray.p.x)/ray.v.y;
Real tz0 = (min.z - ray.p.x)/ray.v.z;
Real tz1 = (max.z - ray.p.x)/ray.v.z;
Real tmax = FMax(tx0,FMax(ty0,tz0));
Real tmin = FMin(tx1,FMin(ty1,tz1));
if(tmax < tmin && (tmin > 0.0))
proc_subtree (tx0,ty0,tz0,tx1,ty1,tz1,pNode,nodes,ray.p);
}
Matt Pharr
3ddes...@gmx.de writes:
> I am using the octree traversal algorithm described in the paper "An
> Efficient Parametric Algorithm for Octree Traversal" by J. Revelles, C.
> Urena, M. Lastra
>
> http://cg.cs.uni-bonn.de/docs/teaching/2004/WS/photo/documents/Octree%20Traversal,%20WSCG.pdf
>
> but I have problems making it work correctly.
One thing that immediately sticks out is:
Real tx0 = (min.x - ray.p.x)/ray.v.x;
Real tx1 = (max.x - ray.p.x)/ray.v.x;
Real ty0 = (min.y - ray.p.x)/ray.v.y; // you probably want ray.p.y not p.x
Real ty1 = (max.y - ray.p.x)/ray.v.y; // same problem
Real tz0 = (min.z - ray.p.x)/ray.v.z; // ray.p.z not ray.p.x
Real tz1 = (max.z - ray.p.x)/ray.v.z; // likewise
More generally, this sort of thing is always tricky to debug. If you know
OpenGL or D3D, it's worth the time to write a little program to help you
see which nodes are visited by rays in what order as they traverse the
tree. A little time invested in that should more than pay off by making
debugging a bit easier.
-matt
--
Matt Pharr ma...@pharr.org <URL:http://graphics.stanford.edu/~mmp>
=======================================================================
In a cruel and evil world, being cynical can allow you to get some
entertainment out of it. --Daniel Waters
Kalle Rutanen
>
> I am using the octree traversal algorithm described in the paper "An
> Efficient Parametric Algorithm for Octree Traversal" by J. Revelles, C.
> Urena, M. Lastra
>
> http://cg.cs.uni-bonn.de/docs/teaching/2004/WS/photo/documents/Octree%20Traversal,%20WSCG.pdf
>
> but I have problems making it work correctly.
At least in the version of the paper that I got, there was an error in
the paper in the section "Obtaining the first crossed node"
The table 1 in page 4 says the following:
// XY
// txm < tz0 -> 0
// tym < tz0 -> 1
// XZ
// txm < ty0 -> 0
// tzm < ty0 -> 2
// YZ
// tym < tx0 -> 1
// tzm < tx0 -> 2
The right table is here (x and z bits have been swapped, 2->0 and 0->2):
// XY
// txm < tz0 -> 2
// tym < tz0 -> 1
// XZ
// txm < ty0 -> 2
// tzm < ty0 -> 0
// YZ
// tym < tx0 -> 1
// tzm < tx0 -> 0
3ddes...@gmx.de
ouch! that hurts. :) Yes, such errors are most of the time silent
buggers hard to debug. Thanks for the advice too, although I am not
very proficient in OpenGL.
3ddes...@gmx.de
thanks to you too. I didn´t know about the swapping. Anyway, it still
doesn´t seem to work for me. Might also be a problem of other code. I
will have a deeper look first before damning the algorithm. ;-)
Thanks
3ddes...@gmx.de
implementation of the first_node function?
int first_node(float tx0, float ty0, float tz0, float txm, float tym,
float tzm)
{
int b = 0;
if (tx0 > ty0 && tx0 > tz0) //YZ PLANE
{
if (tym < tx0) b |= 1;
if (tzm < tx0) b |= 0;
}
else if (ty0 > tz0) //XZ PLANE
{
if (txm < ty0) b |= 2;
if (tzm < ty0) b |= 0;
}
else
{
if (txm < tz0) b |= 2; //XY PLANE
if (tym < tz0) b |= 1;
}
return b;
}
Thank you!
Kalle Rutanen
> Hmm, I still cannot make it work. Am I doing something wrong in my
> implementation of the first_node function?
Yes you are:)
Turning on bit 0 means to OR with 1. Likewise
bit 1 -> OR with 2
bit 2 -> OR with 4
(Note
1 << 0 = 1
1 << 1 = 2
1 << 2 = 4)
For example:
> if (tym < tx0) b |= 1;
> if (tzm < tx0) b |= 0;
Replace with
if (tym < tx0) b |= 2;
if (tzm < tx0) b |= 1;
Kalle Rutanen
> Hmm, I still cannot make it work. Am I doing something wrong in my
> implementation of the first_node function?
Also it seems that the logic to find out the entry plane is erroneous.
Logic for YZ plane is ok, but logics for XZ and XY planes are not. Maybe
this clip helps..
udword Octree::rayFirstNode(real tx0, real ty0, real tz0, real txm, real
tym, real tzm)
{
udword node = 0;
if (ty0 < tx0)
{
if (tz0 < tx0)
{
// ty0 < tx0 && tz0 < tx0
// YZ plane
if (tym < tx0) node |= 2;
if (tzm < tx0) node |= 1;
return node;
}
}
else
{
if (tz0 < ty0)
{
// tx0 <= ty0 && tz0 < ty0
// XZ plane
if (txm < ty0) node |= 4;
if (tzm < ty0) node |= 1;
return node;
}
}
// XY plane
if (txm < tz0) node |= 4;
if (tym < tz0) node |= 2;
return node;
}
Kalle Rutanen
The logic is fine. Sorry for too quick a look.
3ddes...@gmx.de
clear. :)
It still doesn´t work correctly but once again I will need to look
deeper. (Recursing linearly thru the octree finds all leaf nodes, which
tells me the octree itself is correct, so it must be another small
bugger).
argh, I hate this. :)
Thanks for your patience
Kalle Rutanen
>
> Thanks for your patience
No problem.. Been there, done that:)