Jump to content
  • Advertisement
Sign in to follow this  
playa_151

BSP Tree problems

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am making a BSP tree in OpenGL. Everything works fine except when I split polygons the texture coordinates don't split right for some polygons. I am so getting sick of this so can someone help me by telling me a formula you used to split the texture coords. All I am looking for is a code snippet showing how to calculate the right texture coordinates for split polygons. Thanks.

Share this post


Link to post
Share on other sites
Advertisement
Can you show us how you're currently calculating the texture coordinates at the split points? And perhaps you could also tell us how the resulting texture coordinates are wrong.

Share this post


Link to post
Share on other sites
Basically I am using this to get the tex coords

float tu = texCoords[current].tu - texCoords.tu;
float tv = texCoords[current].tv - texCoords.tv;

tu = texCoords.tu + (tu * dist);
tv = texCoords.tv + (tv * dist);

With dist being the scalar used to split the polygon. What makes the tex coords wrong is the output I am getting. I have a room with 4 walls, a floor, and a ceiling as well as another wall in the middle left of the room. If I don't render using the BSP I can clearly see all of the polygon data and tex coords are correct. The problem lines in the polygon split function. Here is the entire splitting function. Keep in mind I was hacking at this for a few days so there might be some unused variables and things might be a little sloppy.


void CPolygon::ClipPolygon(CPlane &plane, CPolygon *fP, CPolygon *bP)
{
int frontCount = 0, backCount = 0, current = 0, f = 0, b = 0;
int resultIndex[10];
CVector4 frontList[10];
CTexCoord tCFList[10];
CVector4 backList[10];
CTexCoord tCBList[10];
CVector4 p1, p2, pHit;

if(!fP && !bP) return;

for(int i = 0; i < 3; i++)
{
resultIndex = plane.ClassifyPoint(vertices);

switch(resultIndex)
{
case FRONT_PLANE:
f++;
break;

case BEHIND_PLANE:
b++;
break;

default:
break;
}
}

if(!f)
{
backCount = 3;
backList[0] = vertices[0];
backList[1] = vertices[1];
backList[2] = vertices[2];
}

if(!b)
{
frontCount = 3;
frontList[0] = vertices[0];
frontList[1] = vertices[1];
frontList[2] = vertices[2];
}

tCFList[0] = texCoords[0];
tCFList[1] = texCoords[1];
tCFList[2] = texCoords[2];
tCBList[0] = texCoords[0];
tCBList[1] = texCoords[1];
tCBList[2] = texCoords[2];

if(f && b)
{
for(int i = 0; i < 3; i++)
{
current = (i + 1) % 3;

switch(resultIndex)
{
case FRONT_PLANE:
frontList[frontCount++] = vertices;
break;

case ON_PLANE:
case CLIPPED_PLANE:
frontList[frontCount++] = vertices;
backList[backCount++] = vertices;
continue;
break;

default:
backList[backCount++] = vertices;
break;
}

if(resultIndex[current] == ON_PLANE ||
resultIndex[current] == resultIndex) continue;

CVector4 v1(vertices.x, vertices.y, vertices.z, 1);
CVector4 v2(vertices[current].x, vertices[current].y, vertices[current].z, 1);
CVector4 v3(vertices[0].x, vertices[0].y, vertices[0].z, 1);

CVector4 dir = v2 - v1;
CVector4 dir2 = v3 - v1;
CVector4 pNormal(plane.a, plane.b, plane.c, plane.d);
int result = 1;
float dist = 0;
float dp2 = 0;

float dp = pNormal.DotProduct3(dir);
if(fabs(dp) < 0.001f) result = 0;
else
{
dp2 = pNormal.DotProduct3(dir2);
dist = dp2 / dp;

if(dist < 0 || dist > 1) result = 0;
else
{
pHit = v1 + dir * dist;
}
}

dist = (pHit - v1).GetLength() / dp;

frontList[frontCount] = pHit;
backList[backCount] = pHit;

float tu = texCoords[current].tu - texCoords.tu;
float tv = texCoords[current].tv - texCoords.tv;

tu = texCoords.tu + (tu * dist);
tv = texCoords.tv + (tv * dist);

tCFList[frontCount].tu = tu;
tCFList[frontCount].tv = tv;
tCBList[backCount].tu = tu;
tCBList[backCount].tv = tv;

frontCount++;
backCount++;
}
}

if(fP)
{
fP->vertices[0] = frontList[0];
fP->vertices[1] = frontList[1];
fP->vertices[2] = frontList[2];
fP->flag = flag;
fP->normal = normal;
fP->texCoords[0] = tCFList[0];
fP->texCoords[1] = tCFList[1];
fP->texCoords[2] = tCFList[2];
}

if(bP)
{
bP->vertices[0] = backList[0];
bP->vertices[1] = backList[1];
bP->vertices[2] = backList[2];
bP->flag = flag;
bP->normal = normal;
bP->texCoords[0] = tCBList[0];
bP->texCoords[1] = tCBList[1];
bP->texCoords[2] = tCBList[2];
}
}

Share this post


Link to post
Share on other sites
Ok, had a quick look through your code. I can't quite tell what you're doing towards the middle there, where you find the intersection point. I didn't look at it too carefully, but at first glance the code doesn't look right, and may be the source of your problems. In any case, whether or not it's correct, I think you're working too hard there - the intersection points can be found with considerably less effort.

The first thing to consider is that your ClassifyPoint() function most likely finds the signed distance from the point to the plane, and then returns a constant based on the sign of the result, e.g. a positive distance is 'in front', a negative distance is 'behind', and so on.

The fact is, these signed distances give you all the information you need to find the points of intersection, but you're just throwing the information away. Then, later, you're doing a bunch of additional work to try to re-create the point of intersection.

Here's how I do it in my clipping code. Instead of calling a ClassifyPoint() function, I call a DistanceToPlane() function, and keep the result in an array. I also have a frontCount and backCount, like you do, and increment them as appropriate based on the distance to the plane for each vertex.

If and when it comes time to clip the polygon, the distances from the vertices to the planes (which you saved from your distance tests) tell you a) if an edge spans the plane and needs to be clipped, and b) where the parametric point of intersection is.

Anyway, that's it for me for tonight, but if you're still struggling with this tomorrow I'll be glad to post some code.

Share this post


Link to post
Share on other sites
Here is some sample code for you to look at:


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 (may need to be negated first)
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 tested it and it seems to work fine. I didn't include texture coordinates, but you should be able to interpolate them using 't' the same way the vertices are interpolated.

If anything isn't clear, feel free to ask.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!