From 10523a94c80615aeccfa84c81bbffe11335ca4a7 Mon Sep 17 00:00:00 2001 From: havoc Date: Sun, 28 Jan 2007 02:57:51 +0000 Subject: [PATCH] implemented Shadow Volume BSP based culling of lit surfaces, this is slightly better than the existing portal culling code (or much better in the case of detail brush terrain in q3bsp where little culling was performed previously), and is now the only culling method used by rtlight compilation git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@6761 d7cf8633-e32d-0410-b094-e92efae38249 --- gl_rmain.c | 15 ++- gl_rsurf.c | 168 +++++++++++++++++++------- makefile.inc | 1 + r_shadow.c | 8 +- r_shadow.h | 3 +- svbsp.c | 324 +++++++++++++++++++++++++++++++++++++++++++++++++++ svbsp.h | 75 ++++++++++++ 7 files changed, 546 insertions(+), 48 deletions(-) create mode 100644 svbsp.c create mode 100644 svbsp.h diff --git a/gl_rmain.c b/gl_rmain.c index b90a76a0..c7e950aa 100644 --- a/gl_rmain.c +++ b/gl_rmain.c @@ -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 diff --git a/gl_rsurf.c b/gl_rsurf.c index 82b82b5f..f11d41c1 100644 --- a/gl_rsurf.c +++ b/gl_rsurf.c @@ -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; diff --git a/makefile.inc b/makefile.inc index a853c1d6..917dd3a4 100644 --- a/makefile.inc +++ b/makefile.inc @@ -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 \ diff --git a/r_shadow.c b/r_shadow.c index dce619c4..76ed116f 100644 --- a/r_shadow.c +++ b/r_shadow.c @@ -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; } diff --git a/r_shadow.h b/r_shadow.h index 92e2fdb4..c434b514 100644 --- a/r_shadow.h +++ b/r_shadow.h @@ -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 index 00000000..ad3fa38b --- /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 index 00000000..5d65ba31 --- /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 -- 2.39.2