#### Archived

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

# Octree Problem again...

This topic is 5229 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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 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 on other sites

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 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 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 on other sites
I misunderstood. Then yes, you need to expand the node slightly, just to ''make sure''.

1. 1
2. 2
frob
17
3. 3
4. 4
5. 5

• 20
• 13
• 14
• 76
• 22
• ### Forum Statistics

• Total Topics
632140
• Total Posts
3004373

×