Archived

This topic is now archived and is closed to further replies.

Gammastrahler

Octree Problem again...

Recommended Posts

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.
// 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);
And I use this test to test a poly against a child node´s AABB Pseudo code: set nodeMin = min of child node´s AABB set nodeMax = max of child node´s AABB for (each poly in parent node) { set nInside to 0 for (each vertex in poly) { if ((v.x >= nodeMin.x) && (v.x <= nodeMax.x) && (v.y >= nodeMin.y) && (v.y <= nodeMax.y) && (v.z >= nodeMin.z) && (v.z <= nodeMax.z)) nInside++; } end vertex loop if nInside == number of verts in poly then add poly to this child node } could you see what is wrong? i didn´t find the error, since my AABB´s seem to get calculated right. thanks in advance Gammastrahler [edited by - Gammastrahler on April 22, 2004 6:15:28 AM]

Share this post


Link to post
Share on other sites
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


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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites