Skip to main content
gamedev.net
🔒 Locked

BSP Splitting errors

Started by Sfpiano Oct 18, 2005 at 9:03 PM 12 replies 1k views
Original Post
Sfpiano
Sfpiano
I've tried about 4 different versions from unique sources, and all of them give me the same error when trying to split a polygon with a plane. I have the plane and polygon intersecting perpendicularly. The way all of the algorithms work is that they compare the current vertex to the one before it and find the distance between them where that lien crosses the plane. The problem is that the point where they cross is not where the vertex of the new polygon should be. If I have a plane that spans along the X-axis and I have a line that spans the Z-axis and runs through it, the point of intersection will be something like (0, .67, 0); however the point where the polygon's vertex should be in that situation is (0, 0, 0) - the x and z values remain the same, but the y value needs to be lowered in this case. Here's the code I have now from codesampler.com: 

POLY poly, POLY plane;
for(i++<poly.numVerts) {

Vec direction = poly - poly[(i+1)%poly.numVerts];
float linelength = D3DXVec3Dot(&direction, &plane.normal);

Vec L1 = plane[0] - poly;
float dist_from_plane = D3DXVec3Dot(&L1, &plane.normal);

float percentage = dist_from_plane / linelength; 
Vec intersection = poly + (direction * percentage);

}
Everything works correctly except for when poly and poly[i+1] forms a diagnoal line. [Edited by - Sfpiano on October 18, 2005 10:03:37 PM]
//------------------------------------------------------------------------------------------------------The great logician Bertrand Russell once claimed that he could prove anything if given that 1+1=1. So one day, some fool asked him, "Ok. Prove that you're the Pope." He thought for a while and proclaimed, "I am one. The Pope is one. Therefore, the Pope and I are one."
Zakwayda
Zakwayda
I see a couple of things in the code you posted. First, poly[i+1] should probably be poly[(i+1)%numVerts]. Second, in the last line poly[0] should be poly.
Sfpiano
Sfpiano
Right, I had those things, I guess I just copied them incorrectly when I shortened the names.
//------------------------------------------------------------------------------------------------------The great logician Bertrand Russell once claimed that he could prove anything if given that 1+1=1. So one day, some fool asked him, "Ok. Prove that you're the Pope." He thought for a while and proclaimed, "I am one. The Pope is one. Therefore, the Pope and I are one."
Zakwayda
Zakwayda
Quote:
Right, I had those things, I guess I just copied them incorrectly when I shortened the names.
So I take it it still doesn't work?
Sfpiano
Sfpiano
No, I still have problems with diagonals.
//------------------------------------------------------------------------------------------------------The great logician Bertrand Russell once claimed that he could prove anything if given that 1+1=1. So one day, some fool asked him, "Ok. Prove that you're the Pope." He thought for a while and proclaimed, "I am one. The Pope is one. Therefore, the Pope and I are one."
Zakwayda
Zakwayda
Quote:
No, I still have problems with diagonals.
Can you repost the code and just paste it from your source file? (That way we won't confuse typos with actual errors.)
Sfpiano
Sfpiano 
for(i=0; i<poly.numPoints; i++) {	int m = (i + 1)%poly.numPoints;	bool bIgnore = false;	switch(classPos) {		case INFRONT: {			front.ppVertices.push_back(poly.ppVertices);			front.numPoints++;			break;		case BEHIND:			back.ppVertices.push_back(poly.ppVertices);			back.numPoints++;			break;		case COINCIDING:			front.ppVertices.push_back(poly.ppVertices);			back.ppVertices.push_back(poly.ppVertices);			front.numPoints++;			back.numPoints++;			continue;		}if( classPos == COINCIDING && classPos[m] != COINCIDING ) {	bIgnore = true;}else if( classPos[m] == COINCIDING && classPos != COINCIDING ) {	bIgnore = true;}if( !bIgnore && (classPos != classPos[m]) ) {getIntersect(poly.ppVertices->vPos,				poly.ppVertices[m]->vPos,				divider.ppVertices[0]->vPos,				divider.vNormal, IntersectPoint, percent);}///////////////////////////////////////////////////////////////////bool getIntersect( D3DXVECTOR3 linestart, D3DXVECTOR3 lineend, 				  D3DXVECTOR3 vertex, D3DXVECTOR3 normal, 				  D3DXVECTOR3 &intersection, float &percentage ){	D3DXVECTOR3 direction;	D3DXVECTOR3 L1;	float       linelength;	float       dist_from_plane;	direction = lineend - linestart;	linelength = D3DXVec3Dot(&direction, &normal);	if( fabsf( linelength ) < EPSILON ) 		return false;	L1 = vertex - linestart;	dist_from_plane = D3DXVec3Dot(&L1, &normal);	percentage = dist_from_plane / linelength; 	intersection = linestart + (direction * percentage);  	return true;}
//------------------------------------------------------------------------------------------------------The great logician Bertrand Russell once claimed that he could prove anything if given that 1+1=1. So one day, some fool asked him, "Ok. Prove that you're the Pope." He thought for a while and proclaimed, "I am one. The Pope is one. Therefore, the Pope and I are one."
Zakwayda
Zakwayda
It would take a little work to go through that code, so I'm just going to punt and post some of my own:

void SplitPolygon(    const std::vector<Vector3>& p,  // Input polygon    std::vector<Vector3>& pf,       // Front poly after split    std::vector<Vector3>& pb,       // Back poly after split    const Vector3& n,               // Plane normal    float d,                        // Plane distance (p.n = d)    float epsilon)                  // Tolerance for point-on-plane{    if (p.empty()) {        return;    }        std::vector<float> dist(p.size());    std::vector<int> side(p.size());    int numFront = 0;    int numBack = 0;        enum {ON, FRONT, BACK, SPANNING};        for (int i = 0; i < p.size(); ++i) {        dist = p.Dot(n) - d;        if (dist > epsilon) {            side = FRONT;            ++numFront;        } else if (dist < -epsilon) {            side = BACK;            ++numBack;        } else {            side = ON;        }    }    pf.clear();    pb.clear();    if (!numBack) {        pf = p;    } else if (!numFront) {        pb = p;    } else {        for (int i = 0; i < p.size(); ++i) {            if (!(side & BACK)) {                pf.push_back(p);            }            if (!(side & FRONT)) {                pb.push_back(p);            }                int j = (i + 1) % p.size();            if ((side | side[j]) == SPANNING) {                float t = dist / (dist - dist[j]);                Vector3 v = (1.0f - t) * p + t * p[j];                pf.push_back(v);                pb.push_back(v);            }        }    }}

I think I moved some brackets around since the last time I tested this code, so I suppose I could have screwed something up there (nothing you couldn't fix though). Other than that, I think it's been tested successfully and works as advertised. You can use it as is, or use it as a reference for fixing your own code.

Oh, and one more thing. You mentioned in your first post that you'd tried several different versions and gotten the same results each time. If you try the above code and get the same results, it may be that something is wrong with your input.
Sfpiano
Sfpiano
Here is the problem as I understand it:



That black dot (0,1,0) is the actual intersection between the diagonal line and the other plane. However, that is not where the vertex of the split plane should be. There should be two on that line - one above the point at (0,2,0) and the other below at (0,0,0).

[Edited by - Sfpiano on October 27, 2005 9:08:05 PM]
//------------------------------------------------------------------------------------------------------The great logician Bertrand Russell once claimed that he could prove anything if given that 1+1=1. So one day, some fool asked him, "Ok. Prove that you're the Pope." He thought for a while and proclaimed, "I am one. The Pope is one. Therefore, the Pope and I are one."
Sfpiano
Sfpiano
Anyone?
//------------------------------------------------------------------------------------------------------The great logician Bertrand Russell once claimed that he could prove anything if given that 1+1=1. So one day, some fool asked him, "Ok. Prove that you're the Pope." He thought for a while and proclaimed, "I am one. The Pope is one. Therefore, the Pope and I are one."
Sfpiano
Sfpiano
Let's ignore my code and look at jyk's because it's more consise and I get better results. (You were right, that INFRONT { was a copying error, and I do store the split vertex, but I left that part out)

Anyway, how can I not include the diagonal line if I iterate through all of the vertices of the input polygon? The vertices are arranged as so:
1/4-------5|	  || 	  ||	  |0-------2/3


So when i=1 and i+1=2, the line that will be compared with the plane will be the diagonal from vertex 1 to vertex 2.

When I run the function, here are the vertices I get for the back split:
{ x=0 y=2 z=2 }{ x=0 y=2 z=0 }{ x=0 y=1 z=0 }{ x=0 y=0 z=2 }{ x=0 y=0 z=2 }{ x=0 y=1 z=0 }{ x=0 y=1 z=0 }


As you can see, they're not in order, there's too many of them, and the (0,1,0) should be (0,0,0)
//------------------------------------------------------------------------------------------------------The great logician Bertrand Russell once claimed that he could prove anything if given that 1+1=1. So one day, some fool asked him, "Ok. Prove that you're the Pope." He thought for a while and proclaimed, "I am one. The Pope is one. Therefore, the Pope and I are one."
Zakwayda
Zakwayda
I'm still confused about the problem. If you're splitting, say, a polygon with 4 sides, you shouldn't be considering the diagonal at all. There are four edges; you split each of them to the plane and use the results to create the resulting front and back polygons (which is what my code does).

Ok, looking at your diagrams, it looks like you're considering the quad as 2 triangles, i.e. 6 verts (or 4 if the verts are shared) and 6 edges? The algorithm isn't set up to process the polygon in that form. It should just be a sequence of vertices, wound either clockwise or counterclockwise around the polygon, that implicitly defines the edges of the polygon. For a quad, that would be 4 verts only.

Anyway, I may be confused about what you're doing, but maybe the above will get you moving in the right direction...

Topic Locked

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

Sign in to reply to this topic.