// lower left, front
node->_octants[0] = new ZNode(minX, minY, mid._z, mid._x, mid._y, maxZ);
// lower right, front
node->_octants[1] = new ZNode(mid._x, minY, mid._z, maxX, mid._y, maxZ);
// lower left, back
node->_octants[2] = new ZNode(minX, minY, minZ, mid._x, mid._y, mid._z);
// lower right, back
node->_octants[3] = new ZNode(mid._x, minY, minZ, maxX, mid._y, mid._z);
// upper reft, front
node->_octants[4] = new ZNode(minX, mid._y, mid._z, mid._x, maxY, maxZ);
// upper right, front
node->_octants[5] = new ZNode(mid._x, mid._y, mid._z, maxX, maxY, maxZ);
// upper left, back
node->_octants[6] = new ZNode(minX, mid._y, minZ, mid._x, maxY, mid._z);
// upper right, back
node->_octants[7] = new ZNode(mid._x, mid._y, minZ, maxX, maxY, mid._z);
Octree Problem again...
Author
Hi, i have a problem with my octree again...
There are some "holes" in my polygon soup after it is partitioned by the octree, so some polys are just not added to any node since the poly - in AABB test fails.
Just to note, i split everything that spans the three cardinal planes.
But why does it not work?
Here are the calculated centers for my eight child nodes based on the center of the current node.
if the child AABBs are right, it''s probably the triangle/AABBtest, which looks suspicious.
as a first step, you can build a bounding box around the triangle, and test that box against the child boxes of the octree. Highly innacurate, but simple, and if it works, you''ll know the octree is sound and the tri/box collision is screwed up.
as for the tri/AABB test itself, I''d recommend a separation axis test. which is simple to implement, fast, and stable.
since I''ve done it many times, here is the code
''*'' is a dot product, ''^'' is a cross product.
as a first step, you can build a bounding box around the triangle, and test that box against the child boxes of the octree. Highly innacurate, but simple, and if it works, you''ll know the octree is sound and the tri/box collision is screwed up.
as for the tri/AABB test itself, I''d recommend a separation axis test. which is simple to implement, fast, and stable.
since I''ve done it many times, here is the code
void TriInterval(const Vector& Axis, const Vector* V, float& min, float& max){ float d = V[0] * Axis; min = max = d; d = V[1] * Axis; if (d < min) min = d; else if (d > max) max = d; d = V[2] * Axis; if (d < min) min = d; else if (d > max) max = d;}void BoxInterval(const Vector& Axis, const Vector& Cen, const Vector& Ext, const Vector* Dir, float& min, float& max){ float e = (float) fabs(Axis * Dir[0]) * Ext.x + (float) fabs(Axis * Dir[1]) * Ext.y + (float) fabs(Axis * Dir[2]) * Ext.z; float c = Axis * Cen; min = c - e; max = c + e; }bool TriBoxIntervalOverlap(const Vector& Axis, const Vector* V, const Vector& Cen, const Vector& Ext, const Vector* Dir){ float mint, maxt; float minb, maxb; TriInterval(Axis, V, mint, maxt); BoxInterval(Axis, Cen, Ext, Dir, minb, maxb); return !(minb > maxt || mint > maxb);}bool TriBoxIntersect(const Vector* V, const Vector& Min, const Vector& Max){ Vector Cen = (Max + Min) * 0.5f; Vector Ext = (Max - Min) * 0.5f; Vector Dir[3] = { Vector(1, 0, 0), Vector(0, 1, 0), Vector(0, 0, 1) }; // the box axis (which are axis aligned Vector E[3] = { V[1] - V[0], V[2] - V[1], V[0] - V[2] }; // the edges of teh triangle Vector N = E[0] ^ E[1]; // normal of the triangle Vector Axis; // separation axis to test Axis = N; if (!TriBoxIntervalOverlap(Axis, V, Cen, Ext, Dir)) return false; Axis = Dir[0]; if (!TriBoxIntervalOverlap(Axis, V, Cen, Ext, Dir)) return false; Axis = Dir[1]; if (!TriBoxIntervalOverlap(Axis, V, Cen, Ext, Dir)) return false; Axis = Dir[2]; if (!TriBoxIntervalOverlap(Axis, V, Cen, Ext, Dir)) return false; Axis = E[0] ^ Dir[0]; if (!TriBoxIntervalOverlap(Axis, V, Cen, Ext, Dir)) return false; Axis = E[0] ^ Dir[1]; if (!TriBoxIntervalOverlap(Axis, V, Cen, Ext, Dir)) return false; Axis = E[0] ^ Dir[2]; if (!TriBoxIntervalOverlap(Axis, V, Cen, Ext, Dir)) return false; Axis = E[1] ^ Dir[0]; if (!TriBoxIntervalOverlap(Axis, V, Cen, Ext, Dir)) return false; Axis = E[1] ^ Dir[1]; if (!TriBoxIntervalOverlap(Axis, V, Cen, Ext, Dir)) return false; Axis = E[1] ^ Dir[2]; if (!TriBoxIntervalOverlap(Axis, V, Cen, Ext, Dir)) return false; Axis = E[2] ^ Dir[0]; if (!TriBoxIntervalOverlap(Axis, V, Cen, Ext, Dir)) return false; Axis = E[2] ^ Dir[1]; if (!TriBoxIntervalOverlap(Axis, V, Cen, Ext, Dir)) return false; Axis = E[2] ^ Dir[2]; if (!TriBoxIntervalOverlap(Axis, V, Cen, Ext, Dir)) return false; return true;}''*'' is a dot product, ''^'' is a cross product.
When you test polygons against your node, you actually need to perform some type of clipping on them or perform a Seperating Axis Test as Oliii suggests. In fact, Oliii's code seems really nice and readable compared to the standard place of reference (www.realtimerendering.com/int - look for triangle/aabb test), so I'd have a good look at that.
Anyway, the reason for this seemingly large amount of work is that a polygon can span (i.e. cut-through) an entire node without any of its vertices actually lying inside the node.
Good luck getting it working,
T
edit: I'm a spelling idiot..
edit2: I'm a grammar idiot..
[edited by - Tessellator on April 22, 2004 8:02:29 AM]
Anyway, the reason for this seemingly large amount of work is that a polygon can span (i.e. cut-through) an entire node without any of its vertices actually lying inside the node.
Good luck getting it working,
T
edit: I'm a spelling idiot..
edit2: I'm a grammar idiot..
[edited by - Tessellator on April 22, 2004 8:02:29 AM]
Author
Thanks for your replies!
Hmm... i´m not completely sure wehteher i understand the concept, but i want to adhere that my polygons cannot span any child node´s AABB, since all my polygons in the current node are pre-clipped against these three planes before sending them to the childs:
partitionPlanes[0].set(1.0, 0.0, 0.0, -mid._x);
partitionPlanes[1].set(0.0, 1.0, 0.0, -mid._y);
partitionPlanes[2].set(0.0, 0.0, 1.0, -mid._z);
for (each plane p in partitionPlanes)
{
for (each poly poly in node´s list of polys)
split if spanning, delete the
original poly and add the two clipped polys to
the node´s poly list
}
[/source]
so this makes sure that each polygon are chopped off and fit into the child nodes.
Therefore, i need no intersection test, but a good working Triangle-Inside Box or Polygon-Inside box-test. I have searched the web, but i only find Intersection Tests...
[edited by - Gammastrahler on April 22, 2004 10:08:54 AM]
Hmm... i´m not completely sure wehteher i understand the concept, but i want to adhere that my polygons cannot span any child node´s AABB, since all my polygons in the current node are pre-clipped against these three planes before sending them to the childs:
partitionPlanes[0].set(1.0, 0.0, 0.0, -mid._x);
partitionPlanes[1].set(0.0, 1.0, 0.0, -mid._y);
partitionPlanes[2].set(0.0, 0.0, 1.0, -mid._z);
for (each plane p in partitionPlanes)
{
for (each poly poly in node´s list of polys)
split if spanning, delete the
original poly and add the two clipped polys to
the node´s poly list
}
[/source]
so this makes sure that each polygon are chopped off and fit into the child nodes.
Therefore, i need no intersection test, but a good working Triangle-Inside Box or Polygon-Inside box-test. I have searched the web, but i only find Intersection Tests...
[edited by - Gammastrahler on April 22, 2004 10:08:54 AM]
Author
I have slightly changed my code to avoid errors by testing against >= -EPSILON.
For example, for the x component:
if (v.x - min.x >= -EPSILON) then x is inside = true;
this works! is this correct?
thanks anyway
greets
Gammastrahler
For example, for the x component:
if (v.x - min.x >= -EPSILON) then x is inside = true;
this works! is this correct?
thanks anyway
greets
Gammastrahler
All my nodes in the ocree are expanded slightly by a small epsilon to do essentially the same thing as you. It seems to be a pretty regular exercise to avoid floating point precision problems.
T
T
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
