# 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.

## 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.

Anyone?

##### Share on other sites
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 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 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 on other sites
Thanks for your time. I would like to see some clip code to compare.

##### 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 on other sites
Thanks pal. You helped me a lot. Things are clear now and I was able to get things working right.

• 10
• 17
• 9
• 13
• 41