improved performance of SVBSP code
authorhavoc <havoc@d7cf8633-e32d-0410-b094-e92efae38249>
Fri, 25 Dec 2009 13:53:26 +0000 (13:53 +0000)
committerhavoc <havoc@d7cf8633-e32d-0410-b094-e92efae38249>
Fri, 25 Dec 2009 13:53:26 +0000 (13:53 +0000)
git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@9689 d7cf8633-e32d-0410-b094-e92efae38249

svbsp.c

diff --git a/svbsp.c b/svbsp.c
index 83064e1..de2ab86 100644 (file)
--- a/svbsp.c
+++ b/svbsp.c
@@ -1,6 +1,7 @@
 
 // Shadow Volume BSP code written by Forest "LordHavoc" Hale on 2003-11-06 and placed into public domain.
 // Modified by LordHavoc (to make it work and other nice things like that) on 2007-01-24 and 2007-01-25
+// Optimized by LordHavoc on 2009-12-24 and 2009-12-25
 
 #include <math.h>
 #include <string.h>
 
 #define SVBSP_DotProduct(a,b) ((a)[0]*(b)[0]+(a)[1]*(b)[1]+(a)[2]*(b)[2])
 
+typedef struct svbsp_polygon_s
+{
+       float points[MAX_SVBSP_POLYGONPOINTS][3];
+       //unsigned char splitflags[MAX_SVBSP_POLYGONPOINTS];
+       int facesplitflag;
+       int numpoints;
+}
+svbsp_polygon_t;
+
 static void SVBSP_PlaneFromPoints(float *plane4f, const float *p1, const float *p2, const float *p3)
 {
        float ilength;
@@ -30,6 +40,72 @@ static void SVBSP_PlaneFromPoints(float *plane4f, const float *p1, const float *
        plane4f[3] *= ilength;
 }
 
+static void SVBSP_DividePolygon(int innumpoints, const float *inpoints, float planenormalx, float planenormaly, float planenormalz, float planedist, float epsilon, int outfrontmaxpoints, float *outfrontpoints, int *neededfrontpoints, int outbackmaxpoints, float *outbackpoints, int *neededbackpoints, int *oncountpointer)
+{
+       int i, frontcount = 0, backcount = 0, oncount = 0;
+       const float *n, *p;
+       float frac, pdist, ndist;
+       if (innumpoints)
+       {
+               n = inpoints;
+               ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
+               for(i = 0;i < innumpoints;i++)
+               {
+                       p = n;
+                       pdist = ndist;
+                       n = inpoints + ((i + 1) < innumpoints ? (i + 1) : 0) * 3;
+                       ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
+                       if (pdist >= -epsilon)
+                       {
+                               if (pdist <= epsilon)
+                                       oncount++;
+                               if (frontcount < outfrontmaxpoints)
+                               {
+                                       *outfrontpoints++ = p[0];
+                                       *outfrontpoints++ = p[1];
+                                       *outfrontpoints++ = p[2];
+                               }
+                               frontcount++;
+                       }
+                       if (pdist <= epsilon)
+                       {
+                               if (backcount < outbackmaxpoints)
+                               {
+                                       *outbackpoints++ = p[0];
+                                       *outbackpoints++ = p[1];
+                                       *outbackpoints++ = p[2];
+                               }
+                               backcount++;
+                       }
+                       if ((pdist > epsilon && ndist < -epsilon) || (pdist < -epsilon && ndist > epsilon))
+                       {
+                               oncount++;
+                               frac = pdist / (pdist - ndist);
+                               if (frontcount < outfrontmaxpoints)
+                               {
+                                       *outfrontpoints++ = p[0] + frac * (n[0] - p[0]);
+                                       *outfrontpoints++ = p[1] + frac * (n[1] - p[1]);
+                                       *outfrontpoints++ = p[2] + frac * (n[2] - p[2]);
+                               }
+                               frontcount++;
+                               if (backcount < outbackmaxpoints)
+                               {
+                                       *outbackpoints++ = p[0] + frac * (n[0] - p[0]);
+                                       *outbackpoints++ = p[1] + frac * (n[1] - p[1]);
+                                       *outbackpoints++ = p[2] + frac * (n[2] - p[2]);
+                               }
+                               backcount++;
+                       }
+               }
+       }
+       if (neededfrontpoints)
+               *neededfrontpoints = frontcount;
+       if (neededbackpoints)
+               *neededbackpoints = backcount;
+       if (oncountpointer)
+               *oncountpointer = oncount;
+}
+
 void SVBSP_Init(svbsp_t *b, const float *origin, int maxnodes, svbsp_node_t *nodes)
 {
        memset(b, 0, sizeof(*b));
@@ -88,26 +164,15 @@ void SVBSP_Init(svbsp_t *b, const float *origin, int maxnodes, svbsp_node_t *nod
        b->nodes[2].children[1] = -1;
 }
 
-static void SVBSP_InsertOccluderPolygonNodes(svbsp_t *b, int *parentnodenumpointer, int parentnodenum, int numpoints, const float *points, void (*fragmentcallback)(void *fragmentcallback_pointer1, int fragmentcallback_number1, svbsp_t *b, int numpoints, const float *points), void *fragmentcallback_pointer1, int fragmentcallback_number1)
+static void SVBSP_InsertOccluderPolygonNodes(svbsp_t *b, int *parentnodenumpointer, int parentnodenum, const svbsp_polygon_t *poly, void (*fragmentcallback)(void *fragmentcallback_pointer1, int fragmentcallback_number1, svbsp_t *b, int numpoints, const float *points), void *fragmentcallback_pointer1, int fragmentcallback_number1)
 {
        // now we need to create up to numpoints + 1 new nodes, forming a BSP tree
        // describing the occluder polygon's shadow volume
        int i, j, p, basenum;
        svbsp_node_t *node;
-#if 0
-       unsigned int sideflags[(MAX_SVBSP_POLYGONPOINTS+31)>>5];
-       float *parentnodeplane;
-       float plane[4];
-#if 0
-       float mindist;
-       float maxdist;
-       float d;
-#endif
-       int n;
-#endif
 
        // if there aren't enough nodes remaining, skip it
-       if (b->numnodes + numpoints + 1 >= b->maxnodes)
+       if (b->numnodes + poly->numpoints + 1 >= b->maxnodes)
        {
                b->ranoutofnodes = 1;
                return;
@@ -129,93 +194,30 @@ static void SVBSP_InsertOccluderPolygonNodes(svbsp_t *b, int *parentnodenumpoint
        // line which is done last to allow multithreaded queries during an
        // insertion
        basenum = b->numnodes;
-#if 1
-       for (i = 0, p = numpoints - 1;i < numpoints;p = i, i++)
+       for (i = 0, p = poly->numpoints - 1;i < poly->numpoints;p = i, i++)
        {
 #if 1
                // see if a parent plane describes this side
                for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
                {
                        float *parentnodeplane = b->nodes[j].plane;
-               //      float v[3];
-               //      v[0] = SVBSP_DotProduct(b->origin     , parentnodeplane) - parentnodeplane[3];
-               //      v[1] = SVBSP_DotProduct(points + p * 3, parentnodeplane) - parentnodeplane[3];
-               //      v[2] = SVBSP_DotProduct(points + i * 3, parentnodeplane) - parentnodeplane[3];
-               //      if (SVBSP_DotProduct(v,v) < (SVBSP_CLIP_EPSILON*SVBSP_CLIP_EPSILON))
-                       if (fabs(SVBSP_DotProduct(points + p * 3, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
-                        && fabs(SVBSP_DotProduct(points + i * 3, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
-                        && fabs(SVBSP_DotProduct(b->origin     , parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON)
+                       if (fabs(SVBSP_DotProduct(poly->points[p], parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
+                        && fabs(SVBSP_DotProduct(poly->points[i], parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
+                        && fabs(SVBSP_DotProduct(b->origin      , parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON)
                                break;
                }
                if (j >= 0)
                        continue; // already have a matching parent plane
 #endif
-
-#else
-#if 1
-       // iterate parent planes and check if any sides of the polygon lie on their plane - if so the polygon can not contribute a new node for that side
-       for (i = 0;i < (int)(sizeof(sideflags)/sizeof(sideflags[0]));i++)
-               sideflags[i] = 0;
-       for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
-       {
-               parentnodeplane = b->nodes[j].plane;
-               plane[0] = parentnodeplane[0];
-               plane[1] = parentnodeplane[1];
-               plane[2] = parentnodeplane[2];
-               plane[3] = parentnodeplane[3];
 #if 0
-               mindist = plane[3] - SVBSP_CLIP_EPSILON;
-               maxdist = plane[3] + SVBSP_CLIP_EPSILON;
-#endif
-               // if a parent plane crosses the origin, it is a side plane
-               // if it does not cross the origin, it is a face plane, and thus will
-               // not match any side planes we could add
-#if 1
-               if (fabs(SVBSP_DotProduct(b->origin, plane) - plane[3]) > SVBSP_CLIP_EPSILON)
-                       continue;
-#else
-               d = SVBSP_DotProduct(b->origin     , plane);
-               if (d < mindist || d > maxdist)
-                       continue;
-#endif
-               // classify each side as belonging to this parent plane or not
-               // do a distance check on the last point of the polygon first, and
-               // then one distance check per point, reusing the previous point
-               // distance check to classify this side as being on or off the plane
-               i = numpoints-1;
-#if 1
-               p = fabs(SVBSP_DotProduct(points + i * 3, plane) - plane[3]) <= SVBSP_CLIP_EPSILON;
-#else
-               d = SVBSP_DotProduct(points + i * 3, plane);
-               p = d >= mindist && d <= maxdist;
-#endif
-               for (i = 0;i < numpoints;i++)
-               {
-#if 1
-                       n = fabs(SVBSP_DotProduct(points + i * 3, plane) - plane[3]) <= SVBSP_CLIP_EPSILON;
-#else
-                       d = SVBSP_DotProduct(points + i * 3, plane);
-                       n = d >= mindist && d <= maxdist;
-#endif
-                       if (p && n)
-                               sideflags[i>>5] |= 1<<(i&31);
-                       p = n;
-               }
-#endif
-       }
-
-       for (i = 0, p = numpoints - 1;i < numpoints;p = i, i++)
-       {
-#if 1
                // skip any sides that were classified as belonging to a parent plane
-               if (sideflags[i>>5] & (1<<(i&31)))
+               if (poly->splitflags[i])
                        continue;
-#endif
 #endif
                // create a side plane
                // anything infront of this is not inside the shadow volume
                node = b->nodes + b->numnodes++;
-               SVBSP_PlaneFromPoints(node->plane, b->origin, points + p * 3, points + i * 3);
+               SVBSP_PlaneFromPoints(node->plane, b->origin, poly->points[p], poly->points[i]);
                // we need to flip the plane if it puts any part of the polygon on the
                // wrong side
                // (in this way this code treats all polygons as float sided)
@@ -225,9 +227,9 @@ static void SVBSP_InsertOccluderPolygonNodes(svbsp_t *b, int *parentnodenumpoint
                // (we know that the plane is on one edge of the polygon, so there is
                // never a case where points lie on both sides, so the first hint is
                // sufficient)
-               for (j = 0;j < numpoints;j++)
+               for (j = 0;j < poly->numpoints;j++)
                {
-                       float d = SVBSP_DotProduct(points + j * 3, node->plane) - node->plane[3];
+                       float d = SVBSP_DotProduct(poly->points[j], node->plane) - node->plane[3];
                        if (d < -SVBSP_CLIP_EPSILON)
                                break;
                        if (d > SVBSP_CLIP_EPSILON)
@@ -249,22 +251,14 @@ static void SVBSP_InsertOccluderPolygonNodes(svbsp_t *b, int *parentnodenumpoint
        }
 
 #if 1
-       // see if a parent plane describes the face plane
-       for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
-       {
-               float *parentnodeplane = b->nodes[j].plane;
-               if (fabs(SVBSP_DotProduct(points    , parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
-                && fabs(SVBSP_DotProduct(points + 3, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
-                && fabs(SVBSP_DotProduct(points + 6, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON)
-                       break;
-       }
-       if (j < 0)
+       // skip the face plane if it lies on a parent plane
+       if (!poly->facesplitflag)
 #endif
        {
                // add the face-plane node
                // infront is empty, behind is shadow
                node = b->nodes + b->numnodes++;
-               SVBSP_PlaneFromPoints(node->plane, points, points + 3, points + 6);
+               SVBSP_PlaneFromPoints(node->plane, poly->points[0], poly->points[1], poly->points[2]);
                // this is a flip check similar to the one above
                // this one checks if the plane faces the origin, if not, flip it
                if (SVBSP_DotProduct(b->origin, node->plane) - node->plane[3] < -SVBSP_CLIP_EPSILON)
@@ -283,60 +277,143 @@ static void SVBSP_InsertOccluderPolygonNodes(svbsp_t *b, int *parentnodenumpoint
        }
 }
 
-static int SVBSP_AddPolygonNode(svbsp_t *b, int *parentnodenumpointer, int parentnodenum, int numpoints, const float *points, int insertoccluder, void (*fragmentcallback)(void *fragmentcallback_pointer1, int fragmentcallback_number1, svbsp_t *b, int numpoints, const float *points), void *fragmentcallback_pointer1, int fragmentcallback_number1)
+static int SVBSP_AddPolygonNode(svbsp_t *b, int *parentnodenumpointer, int parentnodenum, const svbsp_polygon_t *poly, int insertoccluder, void (*fragmentcallback)(void *fragmentcallback_pointer1, int fragmentcallback_number1, svbsp_t *b, int numpoints, const float *points), void *fragmentcallback_pointer1, int fragmentcallback_number1)
 {
        int i;
-       int frontnumpoints, backnumpoints;
+       int countonpoints;
+       int facesplitflag = poly->facesplitflag;
        float plane[4];
-       float frontpoints[MAX_SVBSP_POLYGONPOINTS * 3], backpoints[MAX_SVBSP_POLYGONPOINTS * 3];
-       float d;
-       if (numpoints < 3)
+       svbsp_polygon_t front;
+       svbsp_polygon_t back;
+       svbsp_node_t *node;
+       if (poly->numpoints < 1)
                return 0;
        // recurse through plane nodes
        while (*parentnodenumpointer >= 0)
        {
                // do a quick check to see if there is any need to split the polygon
-               svbsp_node_t *node = b->nodes + *parentnodenumpointer;
+               node = b->nodes + *parentnodenumpointer;
                parentnodenum = *parentnodenumpointer;
-#if 1
                plane[0] = node->plane[0];
                plane[1] = node->plane[1];
                plane[2] = node->plane[2];
                plane[3] = node->plane[3];
-               d = SVBSP_DotProduct(points, plane) - plane[3];
-               if (d >= SVBSP_CLIP_EPSILON)
+#if 1
                {
-                       for (i = 1;i < numpoints && SVBSP_DotProduct(points + i * 3, plane) - plane[3] >= SVBSP_CLIP_EPSILON;i++);
-                       if (i == numpoints)
+                       int onback;
+                       int onfront;
+                       float d;
+                       onback = 0;
+                       onfront = 0;
+                       for (i = 0;i < poly->numpoints;i++)
+                       {
+                               d = SVBSP_DotProduct(poly->points[i], plane) - plane[3];
+                               if (d <= -SVBSP_CLIP_EPSILON)
+                                       onback = 1;
+                               if (d >= SVBSP_CLIP_EPSILON)
+                                       onfront = 1;
+                       }
+                       if (onfront)
+                       {
+                               if (!onback)
+                               {
+                                       // no need to split, just go to one side
+                                       parentnodenumpointer = &node->children[0];
+                                       continue;
+                               }
+                       }
+                       else if (onback)
                        {
                                // no need to split, just go to one side
+                               parentnodenumpointer = &node->children[1];
+                               continue;
+                       }
+                       else
+                       {
+                               // no need to split, this polygon is on the plane
+                               // this case only occurs for polygons on the face plane, usually
+                               // the same polygon (inserted twice - once as occluder, once as
+                               // tester)
+                               // if this is an occluder, it is redundant
+                               if (insertoccluder)
+                                       return 1; // occluded
+                               // if this is a tester, test the front side, because it is
+                               // probably the same polygon that created this node...
+                               facesplitflag = 1;
                                parentnodenumpointer = &node->children[0];
                                continue;
                        }
                }
-               else if (d <= -SVBSP_CLIP_EPSILON)
+               // at this point we know it crosses the plane, so we need to split it
+               SVBSP_DividePolygon(poly->numpoints, poly->points[0], plane[0], plane[1], plane[2], plane[3], SVBSP_CLIP_EPSILON, MAX_SVBSP_POLYGONPOINTS, front.points[0], &front.numpoints, MAX_SVBSP_POLYGONPOINTS, back.points[0], &back.numpoints, &countonpoints);
+#else
+               // at this point we know it crosses the plane, so we need to split it
+               SVBSP_DividePolygon(poly->numpoints, poly->points[0], plane[0], plane[1], plane[2], plane[3], SVBSP_CLIP_EPSILON, MAX_SVBSP_POLYGONPOINTS, front.points[0], &front.numpoints, MAX_SVBSP_POLYGONPOINTS, back.points[0], &back.numpoints, &countonpoints);
+               if (countonpoints == poly->numpoints)
                {
-                       for (i = 1;i < numpoints && SVBSP_DotProduct(points + i * 3, plane) - plane[3] <= -SVBSP_CLIP_EPSILON;i++);
-                       if (i == numpoints)
+                       // polygon lies on plane - this only occurs on face planes
+                       // if it is an occluder, it is redundant
+                       if (insertoccluder)
+                               return 1; // occluded
+                       // if it is a tester, it should take the front side only
+                       facesplitflag = 1;
+                       parentnodenumpointer = &node->children[0];
+                       continue;
+               }
+#endif
+               if (front.numpoints > MAX_SVBSP_POLYGONPOINTS)
+                       front.numpoints = MAX_SVBSP_POLYGONPOINTS;
+               front.facesplitflag = facesplitflag;
+               if (back.numpoints > MAX_SVBSP_POLYGONPOINTS)
+                       back.numpoints = MAX_SVBSP_POLYGONPOINTS;
+               back.facesplitflag = facesplitflag;
+#if 0
+               if (insertoccluder)
+               {
+                       int pnum;
+                       int f;
+                       int pf;
+                       svbsp_node_t *pnode;
+                       // set splitflags based on this node and parent nodes
+                       for (i = 0;i < front.numpoints;i++)
+                               front.splitflags[i] = 0;
+                       for (i = 0;i < front.numpoints;i++)
+                               back.splitflags[i] = 0;
+                       pnum = *parentnodenumpointer;
+                       while (pnum >= 0)
                        {
-                               // no need to split, just go to one side
-                               parentnodenumpointer = &node->children[1];
-                               continue;
+                               pnode = b->nodes + pnum;
+                               plane[0] = pnode->plane[0];
+                               plane[1] = pnode->plane[1];
+                               plane[2] = pnode->plane[2];
+                               plane[3] = pnode->plane[3];
+                               if (front.numpoints)
+                               {
+                                       i = front.numpoints-1;
+                                       pf = fabs(SVBSP_DotProduct(front.points[i], plane) - plane[3]) <= SVBSP_CLIP_EPSILON;
+                                       for (i = 0;i < front.numpoints;pf = f, i++)
+                                       {
+                                               f = fabs(SVBSP_DotProduct(front.points[i], plane) - plane[3]) <= SVBSP_CLIP_EPSILON;
+                                               front.splitflags[i] |= (f & pf);
+                                       }
+                               }
+                               if (back.numpoints)
+                               {
+                                       i = back.numpoints-1;
+                                       pf = fabs(SVBSP_DotProduct(back.points[i], plane) - plane[3]) <= SVBSP_CLIP_EPSILON;
+                                       for (i = 0;i < back.numpoints;pf = f, i++)
+                                       {
+                                               f = fabs(SVBSP_DotProduct(back.points[i], plane) - plane[3]) <= SVBSP_CLIP_EPSILON;
+                                               back.splitflags[i] |= (f & pf);
+                                       }
+                               }
+                               pnum = pnode->parent;
                        }
                }
 #endif
-               // at this point we know it crosses the plane, so we need to split it
-               PolygonF_Divide(numpoints, points, node->plane[0], node->plane[1], node->plane[2], node->plane[3], SVBSP_CLIP_EPSILON, MAX_SVBSP_POLYGONPOINTS, frontpoints, &frontnumpoints, MAX_SVBSP_POLYGONPOINTS, backpoints, &backnumpoints, NULL);
-               if (frontnumpoints > MAX_SVBSP_POLYGONPOINTS)
-                       frontnumpoints = MAX_SVBSP_POLYGONPOINTS;
-               if (backnumpoints > MAX_SVBSP_POLYGONPOINTS)
-                       backnumpoints = MAX_SVBSP_POLYGONPOINTS;
-               // recurse the sides and return the resulting bit flags
-               i = 0;
-               if (frontnumpoints >= 3)
-                       i |= SVBSP_AddPolygonNode(b, &node->children[0], (int)(node - b->nodes), frontnumpoints, frontpoints, insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
-               if (backnumpoints >= 3)
-                       i |= SVBSP_AddPolygonNode(b, &node->children[1], (int)(node - b->nodes), backnumpoints , backpoints , insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
+               // recurse the sides and return the resulting occlusion flags
+               i  = SVBSP_AddPolygonNode(b, &node->children[0], *parentnodenumpointer, &front, insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
+               i |= SVBSP_AddPolygonNode(b, &node->children[1], *parentnodenumpointer, &back , insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
                return i;
        }
        // leaf node
@@ -345,24 +422,24 @@ static int SVBSP_AddPolygonNode(svbsp_t *b, int *parentnodenumpointer, int paren
                // empty leaf node; and some geometry survived
                // if inserting an occluder, replace this empty leaf with a shadow volume
 #if 0
-               for (i = 0;i < numpoints-2;i++)
+               for (i = 0;i < poly->numpoints-2;i++)
                {
                        Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE);
-                       Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0.25, 0, 0, 1);
-                       Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0.25, 0, 0, 1);
-                       Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0.25, 0, 0, 1);
+                       Debug_PolygonVertex(poly->points[  0][0], poly->points[  0][1], poly->points[  0][2], 0.0f, 0.0f, 0.25f, 0.0f, 0.0f, 1.0f);
+                       Debug_PolygonVertex(poly->points[i+1][0], poly->points[i+1][1], poly->points[i+1][2], 0.0f, 0.0f, 0.25f, 0.0f, 0.0f, 1.0f);
+                       Debug_PolygonVertex(poly->points[i+2][0], poly->points[i+2][1], poly->points[i+2][2], 0.0f, 0.0f, 0.25f, 0.0f, 0.0f, 1.0f);
                        Debug_PolygonEnd();
                }
 #endif
                if (insertoccluder)
                {
                        b->stat_occluders_fragments_accepted++;
-                       SVBSP_InsertOccluderPolygonNodes(b, parentnodenumpointer, parentnodenum, numpoints, points, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
+                       SVBSP_InsertOccluderPolygonNodes(b, parentnodenumpointer, parentnodenum, poly, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
                }
                else
                        b->stat_queries_fragments_accepted++;
                if (fragmentcallback)
-                       fragmentcallback(fragmentcallback_pointer1, fragmentcallback_number1, b, numpoints, points);
+                       fragmentcallback(fragmentcallback_pointer1, fragmentcallback_number1, b, poly->numpoints, poly->points[0]);
                return 2;
        }
        else
@@ -373,12 +450,12 @@ static int SVBSP_AddPolygonNode(svbsp_t *b, int *parentnodenumpointer, int paren
                else
                        b->stat_queries_fragments_rejected++;
 #if 0
-               for (i = 0;i < numpoints-2;i++)
+               for (i = 0;i < poly->numpoints-2;i++)
                {
                        Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE);
-                       Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0, 0, 0.25, 1);
-                       Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0, 0, 0.25, 1);
-                       Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0, 0, 0.25, 1);
+                       Debug_PolygonVertex(poly->points[  0][0], poly->points[  0][1], poly->points[  0][2], 0.0f, 0.0f, 0.0f, 0.0f, 0.25f, 1.0f);
+                       Debug_PolygonVertex(poly->points[i+1][0], poly->points[i+1][1], poly->points[i+1][2], 0.0f, 0.0f, 0.0f, 0.0f, 0.25f, 1.0f);
+                       Debug_PolygonVertex(poly->points[i+2][0], poly->points[i+2][1], poly->points[i+2][2], 0.0f, 0.0f, 0.0f, 0.0f, 0.25f, 1.0f);
                        Debug_PolygonEnd();
                }
 #endif
@@ -390,22 +467,33 @@ int SVBSP_AddPolygon(svbsp_t *b, int numpoints, const float *points, int inserto
 {
        int i;
        int nodenum;
+       svbsp_polygon_t poly;
        // don't even consider an empty polygon
-       if (numpoints < 3)
+       // note we still allow points and lines to be tested...
+       if (numpoints < 1)
                return 0;
+       poly.numpoints = numpoints;
+       for (i = 0;i < numpoints;i++)
+       {
+               poly.points[i][0] = points[i*3+0];
+               poly.points[i][1] = points[i*3+1];
+               poly.points[i][2] = points[i*3+2];
+               //poly.splitflags[i] = 0; // this edge is a valid BSP splitter - clipped edges are not (because they lie on a bsp plane)
+               poly.facesplitflag = 0; // this face is a valid BSP Splitter - if it lies on a bsp plane it is not
+       }
 #if 0
 //if (insertoccluder)
-       for (i = 0;i < numpoints-2;i++)
+       for (i = 0;i < poly.numpoints-2;i++)
        {
                Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE);
-               Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0, 0.25, 0, 1);
-               Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0, 0.25, 0, 1);
-               Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0, 0.25, 0, 1);
+               Debug_PolygonVertex(poly.points[  0][0], poly.points[  0][1], poly.points[  0][2], 0.0f, 0.0f, 0.0f, 0.25f, 0.0f, 1.0f);
+               Debug_PolygonVertex(poly.points[i+1][0], poly.points[i+1][1], poly.points[i+1][2], 0.0f, 0.0f, 0.0f, 0.25f, 0.0f, 1.0f);
+               Debug_PolygonVertex(poly.points[i+2][0], poly.points[i+2][1], poly.points[i+2][2], 0.0f, 0.0f, 0.0f, 0.25f, 0.0f, 1.0f);
                Debug_PolygonEnd();
        }
 #endif
        nodenum = 0;
-       i = SVBSP_AddPolygonNode(b, &nodenum, -1, numpoints, points, insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
+       i = SVBSP_AddPolygonNode(b, &nodenum, -1, &poly, insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
        if (insertoccluder)
        {
                if (i & 2)