I have written a BSP compiler that consistently puts polygons in the wrong order.
Drawing front to back or reverse is always in correct because some polygons are in the wrong order. However my program follows my algorithm correctly, therefore I am not understanding how you decide which polygon is in front or back.
What is required for some arbitrary polygon to be in front of or behind a splitting plane?
I am getting old and my brain is starting to go.
Thanks for the help
[This message has been edited by hkyProgrammer88 (edited 08-02-2002).]
If you’re not using the Z buffer, then you have to split the polygon along the plane and consider each part separately; one is in front; the other is behind.
Ya, I got the spliting working, its just that I don’t know how to pick what order to put polygons in. My BSP compiler sorts the polygons in a way that no matter how the tree is walked (front/back) there will always be a polygon in the wrong order.
I believe this function in my program is the error (function performs exactly as I intend, its just that I don’t know what I am doing):
// Params: Splitting plane, poly to test
// NOTE: ALL poly’s passed are either in front, behind, or planar (none will span)
char onWhichSideOfPlane( const rgPlane &plane, const bspPolyGon *poly)
{
char result = BSP_POLY_IS_PLANAR; // Assume planar
float dProduct;
rgVector edgeTestVector;
int i_vert;
bool stopChecking = false;
for( i_vert = 0; i_vert < poly->vertCount; i_vert++) { // Determine if not planar
edgeTestVector = poly->v[i_vert] - plane.p;
dProduct = rgDotProduct( plane.n, edgeTestVector);
if( dProduct < 0.0f) { // Poly is on opposite side of plane normals direction
// Polygon has been conclusively proven that it is behind the plane.
result = BSP_POLY_IS_BEHIND_PLANE;
stopChecking = true;
} else if( dProduct > 0.0f) { // Poly is on same side as plane normal direction
// Polygon has been conclusively proven that it is in front of the plane.
result = BSP_POLY_IS_INFRONT_OF_PLANE;
stopChecking = true;
}
if( stopChecking) break;
}
return result;
}
[This message has been edited by hkyProgrammer88 (edited 08-03-2002).]
BTW, the common ways to describe a plane is n,d (not n,p as you seem to be describing it) - d stands for ‘distance’. It’s not important, but you may find other peoples code confusing if you don’t adhere to the standard.
[This message has been edited by knackered (edited 08-03-2002).]
I also did this stuff once. In your code you do everything with the normals and the dotproduct. I see nowhere that you test on which side the vertices are.
However maybe you do this somewhere else.
If plane.p isn’t a point on the plane but the distance to the plane you have to do what knackered says!
Are you sure all of the polygon’s points are on one side of the plane? If they are, this should work correctly.
Plane.p is a point on the plane (usually vertex 0 of poly (poly->v[0]). Plane.n is a normalized plane normal.
All polygons passed to function have been split by plane, therefore simply finding a point that is not planar will indicate which side the poly is of the plane.
The big problem is that I am not understanding how to sort polygons after partitioning. I have already compiled my simple map by hand and came up with the same tree my program generates.
The sort order is incorrect but I follow all the rules (pick spliting plane, use plane normal to put poly’s in front or back and repeat).
For a simple cube (with double sided polygons) would the correct BSP tree for this cube be:
(All cube polygons have their normals facing outward, select partition polys in this order A, B, C and D).
Right child → back
Left child → front
A
A ±-------+
/ \ | |
B D | | B
/ \ | |
C ±-------+
/ \ C
D
However this order is not correct, I think it should be (ADBC or DABC or ADCB or DACB).
I figured it out, the problem was that I was sorting them wrong. Out of all the information I read about BSP trees, none of them made it “clear” that you sort based on the first polygon you choose as the root. It appears that a polygon is in front only if it is on the same side as the root polygon when tested from the splitting plane.