   BSP trees and line splitting
  I'm trying to implement the BSP tree for DOOM.Net. However one problem I'm having is how to split a polygon based on a nodes partition line. I start out with a four sided rectangular polygon that contains the whole level and the first nodes partition line.The partition line is defined by the 2D points PA and PB with the polygon consisting of A to D. What I need to know is IA and IB where the "extended" partition line would intersect with the polygon. However I have no idea how to extend it or figure out the intersection points.Also after being split in two I need to figure out which new polygon point S belongs in.Any help would be appreciated.   
  Perhaps you're looking for Sutherland-Hodgman?The algorithm is usually described with respect to 3D, but is applicable in 2D as well. Also be aware that many treatments of the algorithm gloss over robustness issues. You may or may not run into problems with this, but ask if you need further info.   ;Quote:Original post by jykPerhaps you're looking for Sutherland-Hodgman?Yeah, but how do I generate the clipping plane just from a normal line segment? And how do I get the normals and other things? I'm afraid you're going to have to "dumb it down" a little.   ;Quote:Original post by ScetYeah, but how do I generate the clipping plane just from a normal line segment? And how do I get the normals and other things? I'm afraid you're going to have to "dumb it down" a little.Sure :-) With both the 2D and 3D versions of the algorithm we're dealing with generalized hyperplanes. In 3D it's a plane and in 2D a line, but in both cases we represent it the same way; with a normal and a distance along that normal. Although it's not strictly necessary, it can be useful for the normal to be unit-length as well.Here's how to derive this information from a line segment represented by two points:vector3 direction = p2 - p1;vector3 normal;normal.x = -direction.y;normal.y = direction.x;normal.normalize();float distance = dot(p1, normal);In some references you'll find the distance value is negated (which can be a bit confusing).I have code for all this lying around; if it would be useful as a reference, I can clean it up a bit and post it for you.   ;  Thanks, I'll give it a try later. I have some plane-segment collision code someplace, hopefully it'll work.Quote:Original post by jykI have code for all this lying around; if it would be useful as a reference, I can clean it up a bit and post it for you.If it's not too much trouble that would be great.   ;Quote:Original post by ScetIf it's not too much trouble that would be great.Unfortunately, I now realize the code I mentioned is for polygon clipping rather than polygon splitting. The latter is just an extension of the former, more or less, but there are more cases involved. Anyway, I'll go ahead and post the clipping code; maybe it'll be of some use...enum {ON, BACK, FRONT, SPANNING};// Returns one of above values indicating point classification with respect// to input hyperplane.template <typename T, int N>int ClassifyPointToPlane(    const vector< T,fixed<N> >& point, // Point to test    const vector< T,fixed<N> >& normal, // Hyperplane normal (must be normalized)    T  distance, // Hyperplane distance    T& dist, // On completion, distance from point to hyperplane    T  epsilon) // 'Thick plane' epsilon{    dist = dot(point,normal)-distance;    return dist < -epsilon ? BACK : (dist > epsilon ? FRONT : ON);}    template <typename T, int N>bool PolygonToHPlane(    const vector< T,fixed<N> >* const inVerts, // Pointer to input verts    int numInVerts, // How many input verts    vector< T,fixed<N> >* const  outVerts, // Pointer to output vert array    int&numOutVerts, // On completion, how many verts were written    int maxNumOutVerts, // Capacity of output array    const vector< T,fixed<N> >&  normal, // Hyperplane normal (must be normalized)    T   distance, // Hyperplane distance    T   epsilon) // 'Thick plane' epsilon{    typedef vector< T,fixed<N> > vector_type;    vector_type p0 = inVerts[numInVerts-1];    T dist0;    int side0 = ClassifyPointToPlane(p0, normal, distance, dist0, epsilon);    numOutVerts = 0;    for (int i = 0; i < numInVerts; ++i) {   vector_type p1 = inVerts;   T dist1;   int side1 = ClassifyPointToPlane(p1, normal, distance, dist1, epsilon); if ((side0 | side1) == SPANNING) {  if (numOutVerts == maxNumOutVerts) { Log::Get()->Print("Max number of verts exceeded in Clipping::PolygonToHPlane()!"); numOutVerts = 0; return false;  }    outVerts[numOutVerts++] = p0+(dist0/(dist0-dist1))*(p1-p0);   }   if (side1 != BACK) {  if (numOutVerts == maxNumOutVerts) { Log::Get()->Print("Max number of verts exceeded in Clipping::PolygonToHPlane()!"); numOutVerts = 0; return false;  }  outVerts[numOutVerts++] = p1;   }   p0 = p1;   dist0 = dist1;   side0 = side1;    }   return numOutVerts > 0;}Feel free to ask if you have any questions.   ;  Thanks jyk for your help, but I think I'm going to give glBSP a shot. I've already got it partially working. This stuff is way over my head and there's no point in reinventing the wheel.   