From 0b8126c02a213706a84d7ead72ef52e7c3c26c0c Mon Sep 17 00:00:00 2001 From: havoc Date: Thu, 24 Dec 2009 21:42:49 +0000 Subject: [PATCH] changed svbsp code to use floats instead of doubles optimized the parent node checks in svbsp occluder insertion git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@9681 d7cf8633-e32d-0410-b094-e92efae38249 --- gl_rsurf.c | 6 ++-- model_shared.c | 4 +-- svbsp.c | 88 +++++++++++++++++++++++++++++++++++--------------- svbsp.h | 8 ++--- 4 files changed, 71 insertions(+), 35 deletions(-) diff --git a/gl_rsurf.c b/gl_rsurf.c index f5fe469a..a85e9c5a 100644 --- a/gl_rsurf.c +++ b/gl_rsurf.c @@ -724,7 +724,7 @@ static void R_Q1BSP_RecursiveGetLightInfo(r_q1bsp_getlightinfo_t *info, mnode_t { int i; mportal_t *portal; - static double points[128][3]; + static float points[128][3]; for (portal = leaf->portals;portal;portal = portal->next) { for (i = 0;i < portal->numpoints;i++) @@ -768,7 +768,7 @@ static void R_Q1BSP_RecursiveGetLightInfo(r_q1bsp_getlightinfo_t *info, mnode_t msurface_t *surface; const int *e; const vec_t *v[3]; - double v2[3][3]; + float v2[3][3]; for (leafsurfaceindex = 0;leafsurfaceindex < leaf->numleafsurfaces;leafsurfaceindex++) { surfaceindex = leaf->firstleafsurface[leafsurfaceindex]; @@ -857,7 +857,7 @@ static void R_Q1BSP_CallRecursiveGetLightInfo(r_q1bsp_getlightinfo_t *info, qboo { if (use_svbsp) { - double origin[3]; + float origin[3]; VectorCopy(info->relativelightorigin, origin); if (!r_svbsp.nodes) { diff --git a/model_shared.c b/model_shared.c index 02f50da3..84bcd67a 100644 --- a/model_shared.c +++ b/model_shared.c @@ -3076,7 +3076,7 @@ static void Mod_GenerateLightmaps_CreateLights_ComputeSVBSP_InsertSurfaces(const const float *vertex3f = model->surfmesh.data_vertex3f; const int *element3i = model->surfmesh.data_element3i; const int *e; - double v2[3][3]; + float v2[3][3]; for (surfaceindex = 0, surface = model->data_surfaces;surfaceindex < model->nummodelsurfaces;surfaceindex++, surface++) { if (!BoxesOverlap(surface->mins, surface->maxs, mins, maxs)) @@ -3097,7 +3097,7 @@ static void Mod_GenerateLightmaps_CreateLights_ComputeSVBSP(dp_model_t *model, l { int maxnodes = 1<<14; svbsp_node_t *nodes; - double origin[3]; + float origin[3]; float mins[3]; float maxs[3]; svbsp_t svbsp; diff --git a/svbsp.c b/svbsp.c index 4184378f..725da08c 100644 --- a/svbsp.c +++ b/svbsp.c @@ -12,9 +12,9 @@ #define SVBSP_DotProduct(a,b) ((a)[0]*(b)[0]+(a)[1]*(b)[1]+(a)[2]*(b)[2]) -static void SVBSP_PlaneFromPoints(double *plane4f, const double *p1, const double *p2, const double *p3) +static void SVBSP_PlaneFromPoints(float *plane4f, const float *p1, const float *p2, const float *p3) { - double ilength; + float ilength; // calculate unnormalized plane plane4f[0] = (p1[1] - p2[1]) * (p3[2] - p2[2]) - (p1[2] - p2[2]) * (p3[1] - p2[1]); plane4f[1] = (p1[2] - p2[2]) * (p3[0] - p2[0]) - (p1[0] - p2[0]) * (p3[2] - p2[2]); @@ -30,7 +30,7 @@ static void SVBSP_PlaneFromPoints(double *plane4f, const double *p1, const doubl plane4f[3] *= ilength; } -void SVBSP_Init(svbsp_t *b, const double *origin, int maxnodes, svbsp_node_t *nodes) +void SVBSP_Init(svbsp_t *b, const float *origin, int maxnodes, svbsp_node_t *nodes) { memset(b, 0, sizeof(*b)); b->origin[0] = origin[0]; @@ -88,12 +88,15 @@ void SVBSP_Init(svbsp_t *b, const double *origin, int maxnodes, svbsp_node_t *no b->nodes[2].children[1] = -1; } -static void SVBSP_InsertOccluderPolygonNodes(svbsp_t *b, int *parentnodenumpointer, int parentnodenum, int numpoints, const double *points, void (*fragmentcallback)(void *fragmentcallback_pointer1, int fragmentcallback_number1, svbsp_t *b, int numpoints, const double *points), void *fragmentcallback_pointer1, int fragmentcallback_number1) +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) { // 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 1 + unsigned int sideflags[(MAX_SVBSP_POLYGONPOINTS+31)>>5]; +#endif // if there aren't enough nodes remaining, skip it if (b->numnodes + numpoints + 1 >= b->maxnodes) @@ -118,29 +121,55 @@ static void SVBSP_InsertOccluderPolygonNodes(svbsp_t *b, int *parentnodenumpoint // line which is done last to allow multithreaded queries during an // insertion basenum = b->numnodes; - for (i = 0, p = numpoints - 1;i < numpoints;p = i, i++) - { #if 1 - // see if a parent plane describes this side - for (j = parentnodenum;j >= 0;j = b->nodes[j].parent) + // 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 + memset(sideflags, 0, sizeof(sideflags[0])*((numpoints+31)>>5)); + for (j = parentnodenum;j >= 0;j = b->nodes[j].parent) + { + float *parentnodeplane = b->nodes[j].plane; + float plane[4] = {parentnodeplane[0], parentnodeplane[1], parentnodeplane[2], parentnodeplane[3]}; + float mindist = plane[3] - SVBSP_CLIP_EPSILON; + float maxdist = plane[3] + SVBSP_CLIP_EPSILON; + float d; + int i, p, n; + // 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 + d = SVBSP_DotProduct(b->origin , plane); + if (d < mindist || d > maxdist) + continue; + // 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; + d = SVBSP_DotProduct(points + i * 3, plane); + p = d >= mindist && d <= maxdist; + for (i = 0;i < numpoints;i++) { - double *parentnodeplane = b->nodes[j].plane; - if (fabs(SVBSP_DotProduct(b->origin , parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON - && fabs(SVBSP_DotProduct(points + p * 3, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON - && fabs(SVBSP_DotProduct(points + i * 3, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON) - break; + d = SVBSP_DotProduct(points + i * 3, plane); + n = d >= mindist && d <= maxdist; + if (p && n) + sideflags[i>>5] |= 1<<(i&31); + p = n; } - if (j >= 0) - continue; // already have a matching parent plane #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))) + continue; +#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); // 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 double sided) + // (in this way this code treats all polygons as float sided) // // because speed is important this stops as soon as it finds proof // that the orientation is right or wrong @@ -149,7 +178,7 @@ static void SVBSP_InsertOccluderPolygonNodes(svbsp_t *b, int *parentnodenumpoint // sufficient) for (j = 0;j < numpoints;j++) { - double d = SVBSP_DotProduct(points + j * 3, node->plane) - node->plane[3]; + float d = SVBSP_DotProduct(points + j * 3, node->plane) - node->plane[3]; if (d < -SVBSP_CLIP_EPSILON) break; if (d > SVBSP_CLIP_EPSILON) @@ -174,7 +203,7 @@ static void SVBSP_InsertOccluderPolygonNodes(svbsp_t *b, int *parentnodenumpoint // see if a parent plane describes the face plane for (j = parentnodenum;j >= 0;j = b->nodes[j].parent) { - double *parentnodeplane = b->nodes[j].plane; + 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) @@ -205,11 +234,13 @@ static void SVBSP_InsertOccluderPolygonNodes(svbsp_t *b, int *parentnodenumpoint } } -static int SVBSP_AddPolygonNode(svbsp_t *b, int *parentnodenumpointer, int parentnodenum, int numpoints, const double *points, int insertoccluder, void (*fragmentcallback)(void *fragmentcallback_pointer1, int fragmentcallback_number1, svbsp_t *b, int numpoints, const double *points), void *fragmentcallback_pointer1, int fragmentcallback_number1) +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) { int i; int frontnumpoints, backnumpoints; - double frontpoints[MAX_SVBSP_POLYGONPOINTS * 3], backpoints[MAX_SVBSP_POLYGONPOINTS * 3]; + float plane[4]; + float frontpoints[MAX_SVBSP_POLYGONPOINTS * 3], backpoints[MAX_SVBSP_POLYGONPOINTS * 3]; + float d; if (numpoints < 3) return 0; // recurse through plane nodes @@ -219,9 +250,14 @@ static int SVBSP_AddPolygonNode(svbsp_t *b, int *parentnodenumpointer, int paren svbsp_node_t *node = b->nodes + *parentnodenumpointer; parentnodenum = *parentnodenumpointer; #if 1 - if (SVBSP_DotProduct(points, node->plane) >= node->plane[3] + SVBSP_CLIP_EPSILON) + 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) { - for (i = 1;i < numpoints && SVBSP_DotProduct(points + i * 3, node->plane) >= node->plane[3] + SVBSP_CLIP_EPSILON;i++); + for (i = 1;i < numpoints && SVBSP_DotProduct(points + i * 3, plane) - plane[3] >= SVBSP_CLIP_EPSILON;i++); if (i == numpoints) { // no need to split, just go to one side @@ -229,9 +265,9 @@ static int SVBSP_AddPolygonNode(svbsp_t *b, int *parentnodenumpointer, int paren continue; } } - else if (SVBSP_DotProduct(points, node->plane) <= node->plane[3] - SVBSP_CLIP_EPSILON) + else if (d <= -SVBSP_CLIP_EPSILON) { - for (i = 1;i < numpoints && SVBSP_DotProduct(points + i * 3, node->plane) <= node->plane[3] - SVBSP_CLIP_EPSILON;i++); + for (i = 1;i < numpoints && SVBSP_DotProduct(points + i * 3, plane) - plane[3] <= -SVBSP_CLIP_EPSILON;i++); if (i == numpoints) { // no need to split, just go to one side @@ -241,7 +277,7 @@ static int SVBSP_AddPolygonNode(svbsp_t *b, int *parentnodenumpointer, int paren } #endif // at this point we know it crosses the plane, so we need to split it - PolygonD_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); + 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) @@ -301,7 +337,7 @@ static int SVBSP_AddPolygonNode(svbsp_t *b, int *parentnodenumpointer, int paren return 1; } -int SVBSP_AddPolygon(svbsp_t *b, int numpoints, const double *points, int insertoccluder, void (*fragmentcallback)(void *fragmentcallback_pointer1, int fragmentcallback_number1, svbsp_t *b, int numpoints, const double *points), void *fragmentcallback_pointer1, int fragmentcallback_number1) +int SVBSP_AddPolygon(svbsp_t *b, 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) { int i; int nodenum; diff --git a/svbsp.h b/svbsp.h index 5d65ba31..ca87f0d9 100644 --- a/svbsp.h +++ b/svbsp.h @@ -14,14 +14,14 @@ typedef struct svbsp_node_s // parent can be -1 if this is the root node, >= 0 is a node int parent, children[2], padding; // node plane, splits space - double plane[4]; + float plane[4]; } svbsp_node_t; typedef struct svbsp_s { // lightsource or view origin - double origin[3]; + float origin[3]; // current number of nodes in the svbsp int numnodes; // how big the nodes array is @@ -53,7 +53,7 @@ svbsp_t; // // as a rule of thumb the minimum nodes needed for a polygon set is // numpolygons * (averagepolygonvertices + 1) -void SVBSP_Init(svbsp_t *b, const double *origin, int maxnodes, svbsp_node_t *nodes); +void SVBSP_Init(svbsp_t *b, const float *origin, int maxnodes, svbsp_node_t *nodes); // this function tests if any part of a polygon is not in shadow, and returns // non-zero if the polygon is not completely shadowed @@ -70,6 +70,6 @@ void SVBSP_Init(svbsp_t *b, const double *origin, int maxnodes, svbsp_node_t *no // (beware that polygons often get split heavily, even if entirely unshadowed) // // thread-safety notes: do not multi-thread insertions! -int SVBSP_AddPolygon(svbsp_t *b, int numpoints, const double *points, int insertoccluder, void (*fragmentcallback)(void *fragmentcallback_pointer1, int fragmentcallback_number1, svbsp_t *b, int numpoints, const double *points), void *fragmentcallback_pointer1, int fragmentcallback_number1); +int SVBSP_AddPolygon(svbsp_t *b, 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); #endif -- 2.39.2