implemented Shadow Volume BSP based culling of lit surfaces, this is slightly better...
authorhavoc <havoc@d7cf8633-e32d-0410-b094-e92efae38249>
Sun, 28 Jan 2007 02:57:51 +0000 (02:57 +0000)
committerhavoc <havoc@d7cf8633-e32d-0410-b094-e92efae38249>
Sun, 28 Jan 2007 02:57:51 +0000 (02:57 +0000)
git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@6761 d7cf8633-e32d-0410-b094-e92efae38249

gl_rmain.c
gl_rsurf.c
makefile.inc
r_shadow.c
r_shadow.h
svbsp.c [new file with mode: 0644]
svbsp.h [new file with mode: 0644]

index b90a76a..c7e950a 100644 (file)
@@ -126,6 +126,9 @@ static struct r_bloomstate_s
 }
 r_bloomstate;
 
+// shadow volume bsp struct with automatically growing nodes buffer
+svbsp_t r_svbsp;
+
 rtexture_t *r_texture_blanknormalmap;
 rtexture_t *r_texture_white;
 rtexture_t *r_texture_black;
@@ -1067,10 +1070,14 @@ void gl_main_start(void)
        R_BuildFogTexture();
        memset(&r_bloomstate, 0, sizeof(r_bloomstate));
        memset(r_glsl_permutations, 0, sizeof(r_glsl_permutations));
+       memset(&r_svbsp, 0, sizeof (r_svbsp));
 }
 
 void gl_main_shutdown(void)
 {
+       if (r_svbsp.nodes)
+               Mem_Free(r_svbsp.nodes);
+       memset(&r_svbsp, 0, sizeof (r_svbsp));
        R_FreeTexturePool(&r_main_texturepool);
        r_texture_blanknormalmap = NULL;
        r_texture_white = NULL;
@@ -2621,11 +2628,13 @@ void R_UpdateTextureInfo(const entity_render_t *ent, texture_t *t)
        if (!(ent->flags & RENDER_LIGHT))
                t->currentmaterialflags |= MATERIALFLAG_FULLBRIGHT;
        if (ent->effects & EF_ADDITIVE)
-               t->currentmaterialflags |= MATERIALFLAG_ADD | MATERIALFLAG_BLENDED | MATERIALFLAG_TRANSPARENT;
+               t->currentmaterialflags |= MATERIALFLAG_ADD | MATERIALFLAG_BLENDED | MATERIALFLAG_TRANSPARENT | MATERIALFLAG_NOSHADOW;
        else if (t->currentalpha < 1)
-               t->currentmaterialflags |= MATERIALFLAG_ALPHA | MATERIALFLAG_BLENDED | MATERIALFLAG_TRANSPARENT;
+               t->currentmaterialflags |= MATERIALFLAG_ALPHA | MATERIALFLAG_BLENDED | MATERIALFLAG_TRANSPARENT | MATERIALFLAG_NOSHADOW;
+       if (ent->flags & RENDER_NOCULLFACE)
+               t->currentmaterialflags |= MATERIALFLAG_NOSHADOW;
        if (ent->effects & EF_NODEPTHTEST)
-               t->currentmaterialflags |= MATERIALFLAG_NODEPTHTEST;
+               t->currentmaterialflags |= MATERIALFLAG_NODEPTHTEST | MATERIALFLAG_NOSHADOW;
        if (t->currentmaterialflags & MATERIALFLAG_WATER && r_waterscroll.value != 0)
                t->currenttexmatrix = r_waterscrollmatrix;
        else
index 82b82b5..f11d41c 100644 (file)
@@ -522,12 +522,15 @@ typedef struct r_q1bsp_getlightinfo_s
        int outnumleafs;
        int *outsurfacelist;
        unsigned char *outsurfacepvs;
+       unsigned char *tempsurfacepvs;
        int outnumsurfaces;
        vec3_t outmins;
        vec3_t outmaxs;
        vec3_t lightmins;
        vec3_t lightmaxs;
        const unsigned char *pvs;
+       qboolean svbsp_active;
+       qboolean svbsp_insertoccluder;
 }
 r_q1bsp_getlightinfo_t;
 
@@ -548,8 +551,17 @@ void R_Q1BSP_RecursiveGetLightInfo(r_q1bsp_getlightinfo_t *info, mnode_t *node)
                        sides = BoxOnPlaneSide(info->lightmins, info->lightmaxs, plane);
                if (sides == 3)
                {
-                       R_Q1BSP_RecursiveGetLightInfo(info, node->children[0]);
-                       node = node->children[1];
+                       // recurse front side first because the svbsp building prefers it
+                       if (PlaneDist(info->relativelightorigin, plane) > 0)
+                       {
+                               R_Q1BSP_RecursiveGetLightInfo(info, node->children[0]);
+                               node = node->children[1];
+                       }
+                       else
+                       {
+                               R_Q1BSP_RecursiveGetLightInfo(info, node->children[1]);
+                               node = node->children[0];
+                       }
                }
                else if (sides == 0)
                        return; // ERROR: NAN bounding box!
@@ -557,7 +569,28 @@ void R_Q1BSP_RecursiveGetLightInfo(r_q1bsp_getlightinfo_t *info, mnode_t *node)
                        node = node->children[sides - 1];
        }
        leaf = (mleaf_t *)node;
-       if (info->pvs == NULL || CHECKPVSBIT(info->pvs, leaf->clusterindex))
+       if (info->svbsp_active)
+       {
+               int i;
+               mportal_t *portal;
+               double points[128][3];
+               for (portal = leaf->portals;portal;portal = portal->next)
+               {
+                       for (i = 0;i < portal->numpoints;i++)
+                               VectorCopy(portal->points[i].position, points[i]);
+                       if (SVBSP_AddPolygon(&r_svbsp, portal->numpoints, points[0], false, NULL, NULL, 0) & 2)
+                               break;
+               }
+               if (portal == NULL)
+                       return; // no portals of this leaf visible
+       }
+       else
+       {
+               if (info->pvs != NULL && !CHECKPVSBIT(info->pvs, leaf->clusterindex))
+                       return;
+       }
+       // inserting occluders does not alter the light info
+       if (!info->svbsp_insertoccluder)
        {
                info->outmins[0] = min(info->outmins[0], leaf->mins[0]);
                info->outmins[1] = min(info->outmins[1], leaf->mins[1]);
@@ -574,31 +607,49 @@ void R_Q1BSP_RecursiveGetLightInfo(r_q1bsp_getlightinfo_t *info, mnode_t *node)
                                info->outleaflist[info->outnumleafs++] = leafindex;
                        }
                }
-               if (info->outsurfacepvs)
+       }
+       if (info->outsurfacepvs)
+       {
+               int leafsurfaceindex;
+               int surfaceindex;
+               int triangleindex, t;
+               msurface_t *surface;
+               const int *e;
+               const vec_t *v[3];
+               double v2[3][3];
+               for (leafsurfaceindex = 0;leafsurfaceindex < leaf->numleafsurfaces;leafsurfaceindex++)
                {
-                       int leafsurfaceindex;
-                       for (leafsurfaceindex = 0;leafsurfaceindex < leaf->numleafsurfaces;leafsurfaceindex++)
+                       surfaceindex = leaf->firstleafsurface[leafsurfaceindex];
+                       if (!CHECKPVSBIT(info->outsurfacepvs, surfaceindex))
                        {
-                               int surfaceindex = leaf->firstleafsurface[leafsurfaceindex];
-                               if (!CHECKPVSBIT(info->outsurfacepvs, surfaceindex))
+                               surface = info->model->data_surfaces + surfaceindex;
+                               if (BoxesOverlap(info->lightmins, info->lightmaxs, surface->mins, surface->maxs)
+                                && (!info->svbsp_insertoccluder || !(surface->texture->currentframe->currentmaterialflags & MATERIALFLAG_NOSHADOW)))
                                {
-                                       msurface_t *surface = info->model->data_surfaces + surfaceindex;
-                                       if (BoxesOverlap(info->lightmins, info->lightmaxs, surface->mins, surface->maxs))
+                                       for (triangleindex = 0, t = surface->num_firstshadowmeshtriangle, e = info->model->brush.shadowmesh->element3i + t * 3;triangleindex < surface->num_triangles;triangleindex++, t++, e += 3)
                                        {
-                                               int triangleindex, t;
-                                               const int *e;
-                                               const vec_t *v[3];
-                                               for (triangleindex = 0, t = surface->num_firstshadowmeshtriangle, e = info->model->brush.shadowmesh->element3i + t * 3;triangleindex < surface->num_triangles;triangleindex++, t++, e += 3)
+                                               v[0] = info->model->brush.shadowmesh->vertex3f + e[0] * 3;
+                                               v[1] = info->model->brush.shadowmesh->vertex3f + e[1] * 3;
+                                               v[2] = info->model->brush.shadowmesh->vertex3f + e[2] * 3;
+                                               if (PointInfrontOfTriangle(info->relativelightorigin, v[0], v[1], v[2])
+                                                && info->lightmaxs[0] > min(v[0][0], min(v[1][0], v[2][0]))
+                                                && info->lightmins[0] < max(v[0][0], max(v[1][0], v[2][0]))
+                                                && info->lightmaxs[1] > min(v[0][1], min(v[1][1], v[2][1]))
+                                                && info->lightmins[1] < max(v[0][1], max(v[1][1], v[2][1]))
+                                                && info->lightmaxs[2] > min(v[0][2], min(v[1][2], v[2][2]))
+                                                && info->lightmins[2] < max(v[0][2], max(v[1][2], v[2][2])))
                                                {
-                                                       v[0] = info->model->brush.shadowmesh->vertex3f + e[0] * 3;
-                                                       v[1] = info->model->brush.shadowmesh->vertex3f + e[1] * 3;
-                                                       v[2] = info->model->brush.shadowmesh->vertex3f + e[2] * 3;
-                                                       if (PointInfrontOfTriangle(info->relativelightorigin, v[0], v[1], v[2]) && info->lightmaxs[0] > min(v[0][0], min(v[1][0], v[2][0])) && info->lightmins[0] < max(v[0][0], max(v[1][0], v[2][0])) && info->lightmaxs[1] > min(v[0][1], min(v[1][1], v[2][1])) && info->lightmins[1] < max(v[0][1], max(v[1][1], v[2][1])) && info->lightmaxs[2] > min(v[0][2], min(v[1][2], v[2][2])) && info->lightmins[2] < max(v[0][2], max(v[1][2], v[2][2])))
+                                                       if (info->svbsp_active)
                                                        {
-                                                               SETPVSBIT(info->outsurfacepvs, surfaceindex);
-                                                               info->outsurfacelist[info->outnumsurfaces++] = surfaceindex;
-                                                               break;
+                                                               VectorCopy(v[0], v2[0]);
+                                                               VectorCopy(v[1], v2[1]);
+                                                               VectorCopy(v[2], v2[2]);
+                                                               if (!(SVBSP_AddPolygon(&r_svbsp, 3, v2[0], info->svbsp_insertoccluder, NULL, NULL, 0) & 2))
+                                                                       continue;
                                                        }
+                                                       SETPVSBIT(info->outsurfacepvs, surfaceindex);
+                                                       info->outsurfacelist[info->outnumsurfaces++] = surfaceindex;
+                                                       break;
                                                }
                                        }
                                }
@@ -607,6 +658,52 @@ void R_Q1BSP_RecursiveGetLightInfo(r_q1bsp_getlightinfo_t *info, mnode_t *node)
        }
 }
 
+void R_Q1BSP_CallRecursiveGetLightInfo(r_q1bsp_getlightinfo_t *info, qboolean use_svbsp)
+{
+       if (use_svbsp)
+       {
+               double origin[3];
+               VectorCopy(info->relativelightorigin, origin);
+               if (!r_svbsp.nodes)
+               {
+                       r_svbsp.maxnodes = max(r_svbsp.maxnodes, 1<<18);
+                       r_svbsp.nodes = Mem_Alloc(r_main_mempool, r_svbsp.maxnodes * sizeof(svbsp_node_t));
+               }
+               info->svbsp_active = true;
+               info->svbsp_insertoccluder = true;
+               for (;;)
+               {
+                       SVBSP_Init(&r_svbsp, origin, r_svbsp.maxnodes, r_svbsp.nodes);
+                       R_Q1BSP_RecursiveGetLightInfo(info, info->model->brush.data_nodes);
+                       // if that failed, retry with more nodes
+                       if (r_svbsp.ranoutofnodes)
+                       {
+                               // an upper limit is imposed
+                               if (r_svbsp.maxnodes >= 2<<22)
+                                       break;
+                               Mem_Free(r_svbsp.nodes);
+                               r_svbsp.maxnodes *= 2;
+                               r_svbsp.nodes = Mem_Alloc(tempmempool, r_svbsp.maxnodes * sizeof(svbsp_node_t));
+                       }
+                       else
+                               break;
+               }
+               // now clear the surfacepvs array because we need to redo it
+               memset(info->outsurfacepvs, 0, (info->model->nummodelsurfaces + 7) >> 3);
+               info->outnumsurfaces = 0;
+       }
+       else
+               info->svbsp_active = false;
+       info->svbsp_insertoccluder = false;
+       R_Q1BSP_RecursiveGetLightInfo(info, info->model->brush.data_nodes);
+       if (developer.integer >= 100 && use_svbsp)
+       {
+               Con_Printf("GetLightInfo: svbsp built with %i nodes, polygon stats:\n", r_svbsp.numnodes);
+               Con_Printf("occluders: %i accepted, %i rejected, %i fragments accepted, %i fragments rejected.\n", r_svbsp.stat_occluders_accepted, r_svbsp.stat_occluders_rejected, r_svbsp.stat_occluders_fragments_accepted, r_svbsp.stat_occluders_fragments_rejected);
+               Con_Printf("queries  : %i accepted, %i rejected, %i fragments accepted, %i fragments rejected.\n", r_svbsp.stat_queries_accepted, r_svbsp.stat_queries_rejected, r_svbsp.stat_queries_fragments_accepted, r_svbsp.stat_queries_fragments_rejected);
+       }
+}
+
 void R_Q1BSP_GetLightInfo(entity_render_t *ent, vec3_t relativelightorigin, float lightradius, vec3_t outmins, vec3_t outmaxs, int *outleaflist, unsigned char *outleafpvs, int *outnumleafspointer, int *outsurfacelist, unsigned char *outsurfacepvs, int *outnumsurfacespointer)
 {
        r_q1bsp_getlightinfo_t info;
@@ -642,21 +739,12 @@ void R_Q1BSP_GetLightInfo(entity_render_t *ent, vec3_t relativelightorigin, floa
        else
                info.pvs = NULL;
        R_UpdateAllTextureInfo(ent);
-       if (r_shadow_compilingrtlight)
-       {
-               // use portal recursion for exact light volume culling, and exact surface checking
-               Portal_Visibility(info.model, info.relativelightorigin, info.outleaflist, info.outleafpvs, &info.outnumleafs, info.outsurfacelist, info.outsurfacepvs, &info.outnumsurfaces, NULL, 0, true, info.lightmins, info.lightmaxs, info.outmins, info.outmaxs);
-       }
-       else if (r_shadow_realtime_dlight_portalculling.integer)
-       {
-               // use portal recursion for exact light volume culling, but not the expensive exact surface checking
-               Portal_Visibility(info.model, info.relativelightorigin, info.outleaflist, info.outleafpvs, &info.outnumleafs, info.outsurfacelist, info.outsurfacepvs, &info.outnumsurfaces, NULL, 0, r_shadow_realtime_dlight_portalculling.integer >= 2, info.lightmins, info.lightmaxs, info.outmins, info.outmaxs);
-       }
-       else
-       {
-               // use BSP recursion as lights are often small
-               R_Q1BSP_RecursiveGetLightInfo(&info, info.model->brush.data_nodes);
-       }
+
+       // recurse the bsp tree, checking leafs and surfaces for visibility
+       // optionally using svbsp for exact culling of compiled lights
+       // (or if the user enables dlight svbsp culling, which is mostly for
+       //  debugging not actual use)
+       R_Q1BSP_CallRecursiveGetLightInfo(&info, r_shadow_compilingrtlight ? r_shadow_realtime_world_compilesvbsp.integer : r_shadow_realtime_dlight_svbspculling.integer);
 
        // limit combined leaf box to light boundaries
        outmins[0] = max(info.outmins[0] - 1, info.lightmins[0]);
@@ -683,7 +771,7 @@ void R_Q1BSP_CompileShadowVolume(entity_render_t *ent, vec3_t relativelightorigi
        {
                surface = model->data_surfaces + surfacelist[surfacelistindex];
                texture = surface->texture;
-               if ((texture->basematerialflags & (MATERIALFLAG_NODRAW | MATERIALFLAG_TRANSPARENT | MATERIALFLAG_WALL)) != MATERIALFLAG_WALL)
+               if (texture->basematerialflags & MATERIALFLAG_NOSHADOW)
                        continue;
                if ((texture->textureflags & (Q3TEXTUREFLAG_TWOSIDED | Q3TEXTUREFLAG_AUTOSPRITE | Q3TEXTUREFLAG_AUTOSPRITE2)) || (ent->flags & RENDER_NOCULLFACE))
                        continue;
@@ -726,9 +814,7 @@ void R_Q1BSP_DrawShadowVolume(entity_render_t *ent, vec3_t relativelightorigin,
                {
                        surface = model->data_surfaces + modelsurfacelist[modelsurfacelistindex];
                        t = surface->texture->currentframe;
-                       if ((t->currentmaterialflags & (MATERIALFLAG_NODRAW | MATERIALFLAG_TRANSPARENT | MATERIALFLAG_WALL)) != MATERIALFLAG_WALL)
-                               continue;
-                       if ((t->textureflags & (Q3TEXTUREFLAG_TWOSIDED | Q3TEXTUREFLAG_AUTOSPRITE | Q3TEXTUREFLAG_AUTOSPRITE2)) || (ent->flags & RENDER_NOCULLFACE))
+                       if (t->currentmaterialflags & MATERIALFLAG_NOSHADOW)
                                continue;
                        R_Shadow_MarkVolumeFromBox(surface->num_firstshadowmeshtriangle, surface->num_triangles, model->brush.shadowmesh->vertex3f, model->brush.shadowmesh->element3i, relativelightorigin, relativelightdirection, lightmins, lightmaxs, surface->mins, surface->maxs);
                }
@@ -752,7 +838,7 @@ void R_Q1BSP_DrawShadowVolume(entity_render_t *ent, vec3_t relativelightorigin,
                                }
                                t = surface->texture;
                                rsurface_texture = t->currentframe;
-                               f = (rsurface_texture->currentmaterialflags & (MATERIALFLAG_NODRAW | MATERIALFLAG_TRANSPARENT | MATERIALFLAG_WALL)) == MATERIALFLAG_WALL;
+                               f = rsurface_texture->currentmaterialflags & MATERIALFLAG_NOSHADOW;
                        }
                        if (f && surface->num_triangles)
                                surfacelist[numsurfacelist++] = surface;
index a853c1d..917dd3a 100644 (file)
@@ -121,6 +121,7 @@ OBJ_COMMON= \
        sv_move.o \
        sv_phys.o \
        sv_user.o \
+       svbsp.o \
        svvm_cmds.o \
        sys_shared.o \
        vid_shared.o \
index dce619c..76ed116 100644 (file)
@@ -213,13 +213,14 @@ cvar_t r_shadow_portallight = {0, "r_shadow_portallight", "1", "use portal culli
 cvar_t r_shadow_projectdistance = {0, "r_shadow_projectdistance", "1000000", "how far to cast shadows"};
 cvar_t r_shadow_realtime_dlight = {CVAR_SAVE, "r_shadow_realtime_dlight", "1", "enables rendering of dynamic lights such as explosions and rocket light"};
 cvar_t r_shadow_realtime_dlight_shadows = {CVAR_SAVE, "r_shadow_realtime_dlight_shadows", "1", "enables rendering of shadows from dynamic lights"};
-cvar_t r_shadow_realtime_dlight_portalculling = {0, "r_shadow_realtime_dlight_portalculling", "0", "enables portal culling optimizations on dynamic lights (slow!  you probably don't want this!)"};
+cvar_t r_shadow_realtime_dlight_svbspculling = {0, "r_shadow_realtime_dlight_svbspculling", "0", "enables svbsp optimization on dynamic lights (very slow!)"};
 cvar_t r_shadow_realtime_world = {CVAR_SAVE, "r_shadow_realtime_world", "0", "enables rendering of full world lighting (whether loaded from the map, or a .rtlights file, or a .ent file, or a .lights file produced by hlight)"};
 cvar_t r_shadow_realtime_world_dlightshadows = {CVAR_SAVE, "r_shadow_realtime_world_dlightshadows", "1", "enables shadows from dynamic lights when using full world lighting"};
 cvar_t r_shadow_realtime_world_lightmaps = {CVAR_SAVE, "r_shadow_realtime_world_lightmaps", "0", "brightness to render lightmaps when using full world lighting, try 0.5 for a tenebrae-like appearance"};
 cvar_t r_shadow_realtime_world_shadows = {CVAR_SAVE, "r_shadow_realtime_world_shadows", "1", "enables rendering of shadows from world lights"};
 cvar_t r_shadow_realtime_world_compile = {0, "r_shadow_realtime_world_compile", "1", "enables compilation of world lights for higher performance rendering"};
 cvar_t r_shadow_realtime_world_compileshadow = {0, "r_shadow_realtime_world_compileshadow", "1", "enables compilation of shadows from world lights for higher performance rendering"};
+cvar_t r_shadow_realtime_world_compilesvbsp = {0, "r_shadow_realtime_world_compilesvbsp", "1", "enables svbsp optimization during compilation"};
 cvar_t r_shadow_scissor = {0, "r_shadow_scissor", "1", "use scissor optimization of light rendering (restricts rendering to the portion of the screen affected by the light)"};
 cvar_t r_shadow_shadow_polygonfactor = {0, "r_shadow_shadow_polygonfactor", "0", "how much to enlarge shadow volume polygons when rendering (should be 0!)"};
 cvar_t r_shadow_shadow_polygonoffset = {0, "r_shadow_shadow_polygonoffset", "1", "how much to push shadow volumes into the distance when rendering, to reduce chances of zfighting artifacts (should not be less than 0)"};
@@ -366,7 +367,6 @@ void R_Shadow_Help_f(void)
 "r_shadow_projectdistance : shadow volume projection distance\n"
 "r_shadow_realtime_dlight : use high quality dynamic lights in normal mode\n"
 "r_shadow_realtime_dlight_shadows : cast shadows from dlights\n"
-"r_shadow_realtime_dlight_portalculling : work hard to reduce graphics work\n"
 "r_shadow_realtime_world : use high quality world lighting mode\n"
 "r_shadow_realtime_world_dlightshadows : cast shadows from dlights\n"
 "r_shadow_realtime_world_lightmaps : use lightmaps in addition to lights\n"
@@ -400,13 +400,14 @@ void R_Shadow_Init(void)
        Cvar_RegisterVariable(&r_shadow_projectdistance);
        Cvar_RegisterVariable(&r_shadow_realtime_dlight);
        Cvar_RegisterVariable(&r_shadow_realtime_dlight_shadows);
-       Cvar_RegisterVariable(&r_shadow_realtime_dlight_portalculling);
+       Cvar_RegisterVariable(&r_shadow_realtime_dlight_svbspculling);
        Cvar_RegisterVariable(&r_shadow_realtime_world);
        Cvar_RegisterVariable(&r_shadow_realtime_world_dlightshadows);
        Cvar_RegisterVariable(&r_shadow_realtime_world_lightmaps);
        Cvar_RegisterVariable(&r_shadow_realtime_world_shadows);
        Cvar_RegisterVariable(&r_shadow_realtime_world_compile);
        Cvar_RegisterVariable(&r_shadow_realtime_world_compileshadow);
+       Cvar_RegisterVariable(&r_shadow_realtime_world_compilesvbsp);
        Cvar_RegisterVariable(&r_shadow_scissor);
        Cvar_RegisterVariable(&r_shadow_shadow_polygonfactor);
        Cvar_RegisterVariable(&r_shadow_shadow_polygonoffset);
@@ -1041,6 +1042,7 @@ void R_Shadow_RenderMode_VisibleLighting(qboolean stenciltest, qboolean transpar
        if (stenciltest)
        {
                qglEnable(GL_STENCIL_TEST);CHECKGLERROR
+               qglStencilFunc(GL_EQUAL, 128, ~0);CHECKGLERROR
        }
        r_shadow_rendermode = R_SHADOW_RENDERMODE_VISIBLELIGHTING;
 }
index 92e2fdb..c434b51 100644 (file)
@@ -16,13 +16,14 @@ extern cvar_t r_shadow_portallight;
 extern cvar_t r_shadow_projectdistance;
 extern cvar_t r_shadow_realtime_dlight;
 extern cvar_t r_shadow_realtime_dlight_shadows;
-extern cvar_t r_shadow_realtime_dlight_portalculling;
+extern cvar_t r_shadow_realtime_dlight_svbspculling;
 extern cvar_t r_shadow_realtime_world;
 extern cvar_t r_shadow_realtime_world_dlightshadows;
 extern cvar_t r_shadow_realtime_world_lightmaps;
 extern cvar_t r_shadow_realtime_world_shadows;
 extern cvar_t r_shadow_realtime_world_compile;
 extern cvar_t r_shadow_realtime_world_compileshadow;
+extern cvar_t r_shadow_realtime_world_compilesvbsp;
 extern cvar_t r_shadow_scissor;
 extern cvar_t r_shadow_shadow_polygonfactor;
 extern cvar_t r_shadow_shadow_polygonoffset;
diff --git a/svbsp.c b/svbsp.c
new file mode 100644 (file)
index 0000000..ad3fa38
--- /dev/null
+++ b/svbsp.c
@@ -0,0 +1,324 @@
+
+// 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
+
+#ifdef USEMALLOC
+#include "string.h"
+#define Mem_Alloc(p,s) malloc(s)
+#define Mem_Free free
+#else
+#include "quakedef.h"
+#endif
+#include "polygon.h"
+#include "svbsp.h"
+
+#define MAX_SVBSP_POLYGONPOINTS 64
+#define SVBSP_CLIP_EPSILON (1.0 / 1024.0)
+
+void SVBSP_Init(svbsp_t *b, const double *origin, int maxnodes, svbsp_node_t *nodes)
+{
+       memset(b, 0, sizeof(*b));
+       b->origin[0] = origin[0];
+       b->origin[1] = origin[1];
+       b->origin[2] = origin[2];
+       b->numnodes = 3;
+       b->maxnodes = maxnodes;
+       b->nodes = nodes;
+       b->ranoutofnodes = 0;
+       b->stat_occluders_rejected = 0;
+       b->stat_occluders_accepted = 0;
+       b->stat_occluders_fragments_accepted = 0;
+       b->stat_occluders_fragments_rejected = 0;
+       b->stat_queries_rejected = 0;
+       b->stat_queries_accepted = 0;
+       b->stat_queries_fragments_accepted = 0;
+       b->stat_queries_fragments_rejected = 0;
+
+       // the bsp tree must be initialized to have two perpendicular splits axes
+       // through origin, otherwise the polygon insertions would affect the
+       // opposite side of the tree, which would be disasterous.
+       //
+       // so this code has to make 3 nodes and 4 leafs, and since the leafs are
+       // represented by empty/solid state numbers in this system rather than
+       // actual structs, we only need to make the 3 nodes.
+
+       // root node
+       // this one splits the world into +X and -X sides
+       b->nodes[0].plane[0] = 1;
+       b->nodes[0].plane[1] = 0;
+       b->nodes[0].plane[2] = 0;
+       b->nodes[0].plane[3] = origin[0];
+       b->nodes[0].parent = -1;
+       b->nodes[0].children[0] = 1;
+       b->nodes[0].children[1] = 2;
+
+       // +X side node
+       // this one splits the +X half of the world into +Y and -Y
+       b->nodes[1].plane[0] = 0;
+       b->nodes[1].plane[1] = 1;
+       b->nodes[1].plane[2] = 0;
+       b->nodes[1].plane[3] = origin[1];
+       b->nodes[1].parent = 0;
+       b->nodes[1].children[0] = -1;
+       b->nodes[1].children[1] = -1;
+
+       // -X side node
+       // this one splits the -X half of the world into +Y and -Y
+       b->nodes[2].plane[0] = 0;
+       b->nodes[2].plane[1] = 1;
+       b->nodes[2].plane[2] = 0;
+       b->nodes[2].plane[3] = origin[1];
+       b->nodes[2].parent = 0;
+       b->nodes[2].children[0] = -1;
+       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)
+{
+       // 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 there aren't enough nodes remaining, skip it
+       if (b->numnodes + numpoints + 1 >= b->maxnodes)
+       {
+               b->ranoutofnodes = 1;
+               return;
+       }
+
+       // add one node per side, then the actual occluding face node
+
+       // thread safety notes:
+       // DO NOT multithread insertion, it could be made 'safe' but the results
+       // would be inconsistent.
+       //
+       // it is completely safe to multithread queries in all cases.
+       //
+       // if an insertion is occurring the query will give intermediate results,
+       // being blocked by some volumes but not others, which is perfectly okay
+       // for visibility culling intended only to reduce rendering work
+
+       // note down the first available nodenum for the *parentnodenumpointer
+       // 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++)
+       {
+               // see if a parent plane describes this side
+               for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
+               {
+                       svbsp_node_t *parentnode = b->nodes + j;
+                       if (fabs(DotProduct(b->origin     , parentnode->plane) - parentnode->plane[3]) < SVBSP_CLIP_EPSILON
+                        && fabs(DotProduct(points + p * 3, parentnode->plane) - parentnode->plane[3]) < SVBSP_CLIP_EPSILON
+                        && fabs(DotProduct(points + i * 3, parentnode->plane) - parentnode->plane[3]) < SVBSP_CLIP_EPSILON)
+                               break;
+               }
+               if (j >= 0)
+                       continue; // already have a matching parent plane
+
+               // create a side plane
+               // anything infront of this is not inside the shadow volume
+               node = b->nodes + b->numnodes++;
+               TriangleNormal(b->origin, points + p * 3, points + i * 3, node->plane);
+               VectorNormalize(node->plane);
+               node->plane[3] = DotProduct(node->plane, b->origin);
+               // 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)
+               //
+               // because speed is important this stops as soon as it finds proof
+               // that the orientation is right or wrong
+               // (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++)
+               {
+                       double d = DotProduct(points + j * 3, node->plane) - node->plane[3];
+                       if (d < -SVBSP_CLIP_EPSILON)
+                               break;
+                       if (d > SVBSP_CLIP_EPSILON)
+                       {
+                               node->plane[0] *= -1;
+                               node->plane[1] *= -1;
+                               node->plane[2] *= -1;
+                               node->plane[3] *= -1;
+                               break;
+                       }
+               }
+               node->parent = parentnodenum;
+               node->children[0] = -1; // empty
+               node->children[1] = -1; // empty
+               // link this child into the tree
+               *parentnodenumpointer = parentnodenum = (int)(node - b->nodes);
+               // now point to the child pointer for the next node to update later
+               parentnodenumpointer = &node->children[1];
+       }
+
+       // see if a parent plane describes the face plane
+       for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
+       {
+               svbsp_node_t *parentnode = b->nodes + j;
+               if (fabs(DotProduct(points    , parentnode->plane) - parentnode->plane[3]) < SVBSP_CLIP_EPSILON
+                && fabs(DotProduct(points + 3, parentnode->plane) - parentnode->plane[3]) < SVBSP_CLIP_EPSILON
+                && fabs(DotProduct(points + 6, parentnode->plane) - parentnode->plane[3]) < SVBSP_CLIP_EPSILON)
+                       break;
+       }
+       if (j < 0)
+       {
+               // add the face-plane node
+               // infront is empty, behind is shadow
+               node = b->nodes + b->numnodes++;
+               TriangleNormal(points, points + 3, points + 6, node->plane);
+               VectorNormalize(node->plane);
+               node->plane[3] = DotProduct(node->plane, points);
+               // this is a flip check similar to the one above
+               // this one checks if the plane faces the origin, if not, flip it
+               if (DotProduct(b->origin, node->plane) - node->plane[3] < -SVBSP_CLIP_EPSILON)
+               {
+                       node->plane[0] *= -1;
+                       node->plane[1] *= -1;
+                       node->plane[2] *= -1;
+                       node->plane[3] *= -1;
+               }
+               node->parent = parentnodenum;
+               node->children[0] = -1; // empty
+               node->children[1] = -2; // shadow
+               // link this child into the tree
+               // (with the addition of this node, queries will now culled by it)
+               *parentnodenumpointer = (int)(node - b->nodes);
+       }
+}
+
+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)
+{
+       int i;
+       int frontnumpoints, backnumpoints;
+       double frontpoints[MAX_SVBSP_POLYGONPOINTS * 3], backpoints[MAX_SVBSP_POLYGONPOINTS * 3];
+       if (numpoints < 3)
+               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;
+               parentnodenum = *parentnodenumpointer;
+#if 1
+               if (DotProduct(points, node->plane) >= node->plane[3] + SVBSP_CLIP_EPSILON)
+               {
+                       for (i = 1;i < numpoints && DotProduct(points + i * 3, node->plane) >= node->plane[3] + SVBSP_CLIP_EPSILON;i++);
+                       if (i == numpoints)
+                       {
+                               // no need to split, just go to one side
+                               parentnodenumpointer = &node->children[0];
+                               continue;
+                       }
+               }
+               else if (DotProduct(points, node->plane) <= node->plane[3] - SVBSP_CLIP_EPSILON)
+               {
+                       for (i = 1;i < numpoints && DotProduct(points + i * 3, node->plane) <= node->plane[3] - SVBSP_CLIP_EPSILON;i++);
+                       if (i == numpoints)
+                       {
+                               // no need to split, just go to one side
+                               parentnodenumpointer = &node->children[1];
+                               continue;
+                       }
+               }
+#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);
+               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);
+               return i;
+       }
+       // leaf node
+       if (*parentnodenumpointer == -1)
+       {
+               // 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++)
+               {
+                       Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE, false, 0);
+                       Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 1, 0, 0, 0.25);
+                       Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 1, 0, 0, 0.25);
+                       Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 1, 0, 0, 0.25);
+                       Debug_PolygonEnd();
+               }
+#endif
+               if (insertoccluder)
+               {
+                       b->stat_occluders_fragments_accepted++;
+                       SVBSP_InsertOccluderPolygonNodes(b, parentnodenumpointer, parentnodenum, numpoints, points, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
+               }
+               else
+                       b->stat_queries_fragments_accepted++;
+               if (fragmentcallback)
+                       fragmentcallback(fragmentcallback_pointer1, fragmentcallback_number1, b, numpoints, points);
+               return 2;
+       }
+       else
+       {
+               // otherwise it's a solid leaf which destroys all polygons inside it
+               if (insertoccluder)
+                       b->stat_occluders_fragments_rejected++;
+               else
+                       b->stat_queries_fragments_rejected++;
+#if 0
+               for (i = 0;i < numpoints-2;i++)
+               {
+                       Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE, false, 0);
+                       Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0, 0, 1, 0.25);
+                       Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0, 0, 1, 0.25);
+                       Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0, 0, 1, 0.25);
+                       Debug_PolygonEnd();
+               }
+#endif
+       }
+       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 i;
+       int nodenum;
+       // don't even consider an empty polygon
+       if (numpoints < 3)
+               return 0;
+#if 0
+       for (i = 0;i < numpoints-2;i++)
+       {
+               Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE, false, 0);
+               Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0, 1, 0, 0.25);
+               Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0, 1, 0, 0.25);
+               Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0, 1, 0, 0.25);
+               Debug_PolygonEnd();
+       }
+#endif
+       nodenum = 0;
+       i = SVBSP_AddPolygonNode(b, &nodenum, -1, numpoints, points, insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
+       if (insertoccluder)
+       {
+               if (i & 2)
+                       b->stat_occluders_accepted++;
+               else
+                       b->stat_occluders_rejected++;
+       }
+       else
+       {
+               if (i & 2)
+                       b->stat_queries_accepted++;
+               else
+                       b->stat_queries_rejected++;
+       }
+       return i;
+}
+
diff --git a/svbsp.h b/svbsp.h
new file mode 100644 (file)
index 0000000..5d65ba3
--- /dev/null
+++ b/svbsp.h
@@ -0,0 +1,75 @@
+
+// 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
+
+#ifndef SVBSP_H
+#define SVBSP_H
+
+typedef struct svbsp_node_s
+{
+       // notes:
+       // leaf nodes are not stored, these are always structural nodes
+       // (they always have a plane and two children)
+       // children[] can be -1 for empty leaf or -2 for shadow leaf, >= 0 is node
+       // 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];
+}
+svbsp_node_t;
+
+typedef struct svbsp_s
+{
+       // lightsource or view origin
+       double origin[3];
+       // current number of nodes in the svbsp
+       int numnodes;
+       // how big the nodes array is
+       int maxnodes;
+       // first node is the root node
+       svbsp_node_t *nodes;
+       // non-zero indicates that an insertion failed because of lack of nodes
+       int ranoutofnodes;
+       // tree statistics
+       // note: do not use multithreading when gathering statistics!
+       // (the code updating these counters is not thread-safe, increments may
+       //  sometimes fail when multithreaded)
+       int stat_occluders_rejected;
+       int stat_occluders_accepted;
+       int stat_occluders_fragments_rejected;
+       int stat_occluders_fragments_accepted;
+       int stat_queries_rejected;
+       int stat_queries_accepted;
+       int stat_queries_fragments_rejected;
+       int stat_queries_fragments_accepted;
+}
+svbsp_t;
+
+// this function initializes a tree to prepare for polygon insertions
+//
+// the maxnodes needed for a given polygon set can vary wildly, if there are
+// not enough maxnodes then later polygons will not be inserted and the field
+// svbsp_t->ranoutofnodes will be non-zero
+//
+// 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);
+
+// this function tests if any part of a polygon is not in shadow, and returns
+// non-zero if the polygon is not completely shadowed
+//
+// returns 0 if the polygon was rejected (not facing origin or no points)
+// returns 1 if all of the polygon is in shadow
+// returns 2 if all of the polygon is unshadowed
+// returns 3 if some of the polygon is shadowed and some unshadowed
+//
+// it also can add a new shadow volume (insertoccluder parameter)
+//
+// additionally it calls your fragmentcallback on each unshadowed clipped
+// part of the polygon
+// (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);
+
+#endif