Plane Bounded By AABB

[SmokingRope]

I am writing a program to visualize the diving planes of a BSP tree. I associate each node in the tree with an AABB. Every non-leaf node in the tree has a dividing plane. I find the four vertex on the dividing plane that intersect the AABB. I am having trouble with the winding of these four vertex. Planes with certain normals do not actually result in a quad, but rather a quad with an isosceles triangle cut-out (the quad is being flipped.) I have included a screenshot in case that wasn't clear.

http://img134.imageshack.us/img134/5003/quadcutoutyt4.th.jpg (http://img134.imageshack.us/my.php?image=quadcutoutyt4.jpg)

As a breakdown of what i'm doing:

I Construct An Array Consisting Of All 12 Lines Defining The AABB (l_aabbPts)
I find the intersection between each line and the plane
I render the first four intersection points found as a quad



GLfloat l_pts[4][3];
GLuint l_ptsIndex = 0;

GLfloat l_aabbPts[12][2][3] =
{
l_max[0],l_max[1],l_min[2], // Top Right Of The Quad (Top)
l_min[0],l_max[1],l_min[2], // Top Left Of The Quad (Top)

l_min[0],l_max[1],l_max[2], // Bottom Left Of The Quad (Top)
l_max[0],l_max[1],l_max[2], // Bottom Right Of The Quad (Top)

l_max[0],l_max[1],l_min[2], // Top Right Of The Quad (Top)
l_max[0],l_max[1],l_max[2], // Bottom Right Of The Quad (Top)

l_min[0],l_max[1],l_min[2], // Top Left Of The Quad (Top)
l_min[0],l_max[1],l_max[2], // Bottom Left Of The Quad (Top)

l_max[0],l_min[1],l_max[2], // Top Right Of The Quad (Bottom)
l_min[0],l_min[1],l_max[2], // Top Left Of The Quad (Bottom)

l_min[0],l_min[1],l_min[2], // Bottom Left Of The Quad (Bottom)
l_max[0],l_min[1],l_min[2], // Bottom Right Of The Quad (Bottom)

l_max[0],l_min[1],l_max[2], // Top Right Of The Quad (Bottom)
l_max[0],l_min[1],l_min[2], // Bottom Right Of The Quad (Bottom)

l_min[0],l_min[1],l_max[2], // Top Left Of The Quad (Bottom)
l_min[0],l_min[1],l_min[2], // Bottom Left Of The Quad (Bottom)

l_max[0],l_max[1],l_max[2], // Top Right Of The Quad (Front)
l_max[0],l_min[1],l_max[2], // Bottom Right Of The Quad (Front)

l_min[0],l_max[1],l_max[2], // Top Left Of The Quad (Front)
l_min[0],l_min[1],l_max[2], // Bottom Left Of The Quad (Front)

l_min[0],l_max[1],l_min[2], // Top Right Of The Quad (Back)
l_min[0],l_min[1],l_min[2], // Bottom Right Of The Quad (Back)

l_max[0],l_max[1],l_min[2], // Top Left Of The Quad (Back)
l_max[0],l_min[1],l_min[2] // Bottom Left Of The Quad (Back)
};

const GLfloat *l_normal = pBSP->Plane()->m_Normal;

for( int l_i = 0 ; l_i < 12 && l_ptsIndex < 4 ; l_i++ )
{
GLfloat l_a[3], l_b[3];

memcpy(l_a, l_aabbPts[l_i][0], 3*sizeof(GLfloat));
memcpy(l_b, l_aabbPts[l_i][1], 3*sizeof(GLfloat));

GLfloat l_ab[3];
GLfloat l_t;

// Vector Describing Line On AABB
l_ab[0] = l_b[0] - l_a[0];
l_ab[1] = l_b[1] - l_a[1];
l_ab[2] = l_b[2] - l_a[2];

// Distance along line that plane intersects
l_t = pBSP->Plane()->d() - l_normal[0]*l_a[0] -
l_normal[1]*l_a[1] -
l_normal[2]*l_a[2];
l_t /= l_normal[0]*l_ab[0] +
l_normal[1]*l_ab[1] +
l_normal[2]*l_ab[2];

if( l_t < 0.0f || l_t > 1.0f ) continue;

// Plug Distance Back Into Line Equation
l_pts[l_ptsIndex][0] = l_a[0] + l_t*l_ab[0];
l_pts[l_ptsIndex][1] = l_a[1] + l_t*l_ab[1];
l_pts[l_ptsIndex][2] = l_a[2] + l_t*l_ab[2];

++l_ptsIndex;
}

glBegin(GL_QUADS);
glVertex3fv(l_pts[0]);
glVertex3fv(l_pts[1]);
glVertex3fv(l_pts[2]);
glVertex3fv(l_pts[3]);
glEnd();


How can i get the quad vertex into the correct order?

Additionally, it seems this will break if the plane exactly intersects end-points, is there anything i should be doing to account for this?

[anubis]

For the winding problem check this thread :

http://www.devmaster.net/forums/showthread.php?t=12232

[anubis]

Additionally, it seems this will break if the plane exactly intersects end-points, is there anything i should be doing to account for this?

If you can't deal with the degenerate case, you could just set off the vertices a little.

[SmokingRope]

For the winding problem check this thread :

http://www.devmaster.net/forums/showthread.php?t=12232

That did the trick; however, i have not had to correct winding order in my previous experience. Is it common to do this? I'm just guessing, but it would seem (http://en.wikipedia.org/wiki/Code_smell) my algorithm for constructing the points of the plane isn't an optimal solution since this correction step is necessary.

In a 3d modelling application as an example, would a function to compute a consistent winding be commonly needed?

[anubis]

I haven't read your code but in general it depends on whether you are given the points in random order or if your algorithm can impose some order. In the random case you are left with little choice but to infer the an order using the method from the other post. I might have time to skim through your code later in the evening.

In a 3d modelling application as an example, would a function to compute a consistent winding be commonly needed?

I think it is quite common that you lose information about the order of the veritces during certain operations. CSG using BSPs being one of them for example, since in that case a model gets converted completely into a bounding plane representation (depending on the algorithm used) and I find it hard to imagine, that you could reconstruct faces from the planes, knowing an order of intersection of the planes in advance.

Thinking about it... If you clip a plane against an AABB, you should be able to gain some information from the normal of the plane. Think about how the plane is oriented in space. Obviously the order of intersection points you get will be determined by that. And since you take the intersection in their order of appearance, you end up with differently wound polygons. Maybe that helps.