Skip to main content
gamedev.net
🔒 Locked

Octree Problem again...

Started by Gammastrahler Apr 22, 2004 at 5:12 AM 5 replies 850+ views
Original Post
Gammastrahler
Gammastrahler
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]
oliii
oliii
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.
Everything is better with Metal.
Tessellator
Tessellator
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]
Gammastrahler
Gammastrahler
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]
Gammastrahler
Gammastrahler
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
Tessellator
Tessellator
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
oliii
oliii
I misunderstood. Then yes, you need to expand the node slightly, just to ''make sure''.
Everything is better with Metal.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.