From d32dfce0ff2d67ae7fa6665c62b3261b0d8582b7 Mon Sep 17 00:00:00 2001 From: havoc Date: Thu, 8 Mar 2007 23:50:28 +0000 Subject: [PATCH] implemented shadow caster culling by creating a frustum plane set that includes the light origin, any object that is not within this frustum (which encloses the screen and a triangular-shaped volume extending to the light origin) can not possibly cast a shadow onto the visible geometry, this reduces cpu work in a few cases (off-screen explosion with several entities further off-screen) git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@6945 d7cf8633-e32d-0410-b094-e92efae38249 --- client.h | 3 + gl_rmain.c | 65 +++++++++++++++++++-- gl_rsurf.c | 2 + r_shadow.c | 163 +++++++++++++++++++++++++++++++++++++++++++++++++++++ r_shadow.h | 7 +++ render.h | 1 + 6 files changed, 237 insertions(+), 4 deletions(-) diff --git a/client.h b/client.h index 5e9df7de..b0edf520 100644 --- a/client.h +++ b/client.h @@ -69,6 +69,8 @@ typedef struct rtlight_s // note that the world to light matrices are inversely scaled (divided) by lightradius // core properties + // matrix for transforming light filter coordinates to world coordinates + matrix4x4_t matrix_lighttoworld; // matrix for transforming world coordinates to light filter coordinates matrix4x4_t matrix_worldtolight; // typically 1 1 1, can be lower (dim) or higher (overbright) @@ -1338,6 +1340,7 @@ typedef struct r_view_s vec3_t up; mplane_t frustum[5]; float frustum_x, frustum_y; + vec3_t frustumcorner[4]; // screen area to render in int x; diff --git a/gl_rmain.c b/gl_rmain.c index 361012e3..4b26e4f4 100644 --- a/gl_rmain.c +++ b/gl_rmain.c @@ -1276,6 +1276,53 @@ int R_CullBox(const vec3_t mins, const vec3_t maxs) return false; } +int R_CullBoxCustomPlanes(const vec3_t mins, const vec3_t maxs, int numplanes, const mplane_t *planes) +{ + int i; + const mplane_t *p; + for (i = 0;i < numplanes;i++) + { + p = planes + i; + switch(p->signbits) + { + default: + case 0: + if (p->normal[0]*maxs[0] + p->normal[1]*maxs[1] + p->normal[2]*maxs[2] < p->dist) + return true; + break; + case 1: + if (p->normal[0]*mins[0] + p->normal[1]*maxs[1] + p->normal[2]*maxs[2] < p->dist) + return true; + break; + case 2: + if (p->normal[0]*maxs[0] + p->normal[1]*mins[1] + p->normal[2]*maxs[2] < p->dist) + return true; + break; + case 3: + if (p->normal[0]*mins[0] + p->normal[1]*mins[1] + p->normal[2]*maxs[2] < p->dist) + return true; + break; + case 4: + if (p->normal[0]*maxs[0] + p->normal[1]*maxs[1] + p->normal[2]*mins[2] < p->dist) + return true; + break; + case 5: + if (p->normal[0]*mins[0] + p->normal[1]*maxs[1] + p->normal[2]*mins[2] < p->dist) + return true; + break; + case 6: + if (p->normal[0]*maxs[0] + p->normal[1]*mins[1] + p->normal[2]*mins[2] < p->dist) + return true; + break; + case 7: + if (p->normal[0]*mins[0] + p->normal[1]*mins[1] + p->normal[2]*mins[2] < p->dist) + return true; + break; + } + } + return false; +} + //================================================================================== static void R_UpdateEntityLighting(entity_render_t *ent) @@ -1402,6 +1449,8 @@ void R_DrawModels(void) static void R_View_SetFrustum(void) { + double slopex, slopey; + // break apart the view matrix into vectors for various purposes Matrix4x4_ToVectors(&r_view.matrix, r_view.forward, r_view.left, r_view.up, r_view.origin); VectorNegate(r_view.left, r_view.right); @@ -1470,10 +1519,12 @@ static void R_View_SetFrustum(void) - VectorMAM(1, r_view.forward, 1.0 / -r_view.frustum_x, r_view.left, r_view.frustum[0].normal); - VectorMAM(1, r_view.forward, 1.0 / r_view.frustum_x, r_view.left, r_view.frustum[1].normal); - VectorMAM(1, r_view.forward, 1.0 / -r_view.frustum_y, r_view.up, r_view.frustum[2].normal); - VectorMAM(1, r_view.forward, 1.0 / r_view.frustum_y, r_view.up, r_view.frustum[3].normal); + slopex = 1.0 / r_view.frustum_x; + slopey = 1.0 / r_view.frustum_y; + VectorMA(r_view.forward, -slopex, r_view.left, r_view.frustum[0].normal); + VectorMA(r_view.forward, slopex, r_view.left, r_view.frustum[1].normal); + VectorMA(r_view.forward, -slopey, r_view.up , r_view.frustum[2].normal); + VectorMA(r_view.forward, slopey, r_view.up , r_view.frustum[3].normal); VectorCopy(r_view.forward, r_view.frustum[4].normal); VectorNormalize(r_view.frustum[0].normal); VectorNormalize(r_view.frustum[1].normal); @@ -1490,6 +1541,12 @@ static void R_View_SetFrustum(void) PlaneClassify(&r_view.frustum[3]); PlaneClassify(&r_view.frustum[4]); + // calculate frustum corners, which are used to calculate deformed frustum planes for shadow caster culling + VectorMAMAMAM(1, r_view.origin, 1024, r_view.forward, -1024 * slopex, r_view.left, -1024 * slopey, r_view.up, r_view.frustumcorner[0]); + VectorMAMAMAM(1, r_view.origin, 1024, r_view.forward, 1024 * slopex, r_view.left, -1024 * slopey, r_view.up, r_view.frustumcorner[1]); + VectorMAMAMAM(1, r_view.origin, 1024, r_view.forward, -1024 * slopex, r_view.left, 1024 * slopey, r_view.up, r_view.frustumcorner[2]); + VectorMAMAMAM(1, r_view.origin, 1024, r_view.forward, 1024 * slopex, r_view.left, 1024 * slopey, r_view.up, r_view.frustumcorner[3]); + // LordHavoc: note to all quake engine coders, Quake had a special case // for 90 degrees which assumed a square view (wrong), so I removed it, // Quake2 has it disabled as well. diff --git a/gl_rsurf.c b/gl_rsurf.c index d8e16f95..30d6c678 100644 --- a/gl_rsurf.c +++ b/gl_rsurf.c @@ -559,6 +559,8 @@ void R_Q1BSP_RecursiveGetLightInfo(r_q1bsp_getlightinfo_t *info, mnode_t *node) // return; if (!plane) break; + //if (!r_shadow_compilingrtlight && R_CullBoxCustomPlanes(node->mins, node->maxs, r_shadow_rtlight_numfrustumplanes, r_shadow_rtlight_frustumplanes)) + // return; if (plane->type < 3) { if (info->lightmins[plane->type] > plane->dist) diff --git a/r_shadow.c b/r_shadow.c index 98b21ee6..352dc74a 100644 --- a/r_shadow.c +++ b/r_shadow.c @@ -193,6 +193,9 @@ unsigned char *r_shadow_buffer_lighttrispvs; // current light's cull box (copied out of an rtlight or calculated by GetLightInfo) vec3_t r_shadow_rtlight_cullmins; vec3_t r_shadow_rtlight_cullmaxs; +// current light's culling planes +int r_shadow_rtlight_numfrustumplanes; +mplane_t r_shadow_rtlight_frustumplanes[12+6+6]; // see R_Shadow_ComputeShadowCasterCullingPlanes rtexturepool_t *r_shadow_texturepool; rtexture_t *r_shadow_attenuation2dtexture; @@ -2124,6 +2127,7 @@ void R_RTLight_Update(rtlight_t *rtlight, int isstatic, matrix4x4_t *matrix, vec memset(rtlight, 0, sizeof(*rtlight)); // copy the properties + rtlight->matrix_lighttoworld = tempmatrix; Matrix4x4_Invert_Simple(&rtlight->matrix_worldtolight, &tempmatrix); Matrix4x4_OriginFromMatrix(&tempmatrix, rtlight->shadoworigin); rtlight->radius = Matrix4x4_ScaleFromMatrix(&tempmatrix); @@ -2278,6 +2282,159 @@ void R_Shadow_UncompileWorldLights(void) R_RTLight_Uncompile(&light->rtlight); } +void R_Shadow_ComputeShadowCasterCullingPlanes(rtlight_t *rtlight) +{ + int i, j; + mplane_t plane; + // reset the count of frustum planes + // see r_shadow_rtlight_frustumplanes definition for how much this array + // can hold + r_shadow_rtlight_numfrustumplanes = 0; + +#if 1 + // generate a deformed frustum that includes the light origin, this is + // used to cull shadow casting surfaces that can not possibly cast a + // shadow onto the visible light-receiving surfaces, which can be a + // performance gain + // + // if the light origin is onscreen the result will be 4 planes exactly + // if the light origin is offscreen on only one axis the result will + // be exactly 5 planes (split-side case) + // if the light origin is offscreen on two axes the result will be + // exactly 4 planes (stretched corner case) + for (i = 0;i < 4;i++) + { + // quickly reject standard frustum planes that put the light + // origin outside the frustum + if (PlaneDiff(rtlight->shadoworigin, &r_view.frustum[i]) < -0.03125) + continue; + // copy the plane + r_shadow_rtlight_frustumplanes[r_shadow_rtlight_numfrustumplanes++] = r_view.frustum[i]; + } + // if all the standard frustum planes were accepted, the light is onscreen + // otherwise we need to generate some more planes below... + if (r_shadow_rtlight_numfrustumplanes < 4) + { + // at least one of the stock frustum planes failed, so we need to + // create one or two custom planes to enclose the light origin + for (i = 0;i < 4;i++) + { + // create a plane using the view origin and light origin, and a + // single point from the frustum corner set + TriangleNormal(r_view.origin, r_view.frustumcorner[i], rtlight->shadoworigin, plane.normal); + VectorNormalize(plane.normal); + plane.dist = DotProduct(r_view.origin, plane.normal); + // see if this plane is backwards and flip it if so + for (j = 0;j < 4;j++) + if (j != i && DotProduct(r_view.frustumcorner[j], plane.normal) - plane.dist < -0.03125) + break; + if (j < 4) + { + VectorNegate(plane.normal, plane.normal); + plane.dist *= -1; + // flipped plane, test again to see if it is now valid + for (j = 0;j < 4;j++) + if (j != i && DotProduct(r_view.frustumcorner[j], plane.normal) - plane.dist < -0.03125) + break; + // if the plane is still not valid, then it is dividing the + // frustum and has to be rejected + if (j < 4) + continue; + } + // we have created a valid plane, compute extra info + PlaneClassify(&plane); + // copy the plane + r_shadow_rtlight_frustumplanes[r_shadow_rtlight_numfrustumplanes++] = plane; +#if 1 + // if we've found 5 frustum planes then we have constructed a + // proper split-side case and do not need to keep searching for + // planes to enclose the light origin + if (r_shadow_rtlight_numfrustumplanes == 5) + break; +#endif + } + } +#endif + +#if 0 + for (i = 0;i < r_shadow_rtlight_numfrustumplanes;i++) + { + plane = r_shadow_rtlight_frustumplanes[i]; + Con_Printf("light %p plane #%i %f %f %f : %f (%f %f %f %f %f)\n", rtlight, i, plane.normal[0], plane.normal[1], plane.normal[2], plane.dist, PlaneDiff(r_view.frustumcorner[0], &plane), PlaneDiff(r_view.frustumcorner[1], &plane), PlaneDiff(r_view.frustumcorner[2], &plane), PlaneDiff(r_view.frustumcorner[3], &plane), PlaneDiff(rtlight->shadoworigin, &plane)); + } +#endif + +#if 0 + // now add the light-space box planes if the light box is rotated, as any + // caster outside the oriented light box is irrelevant (even if it passed + // the worldspace light box, which is axial) + if (rtlight->matrix_lighttoworld.m[0][0] != 1 || rtlight->matrix_lighttoworld.m[1][1] != 1 || rtlight->matrix_lighttoworld.m[2][2] != 1) + { + for (i = 0;i < 6;i++) + { + vec3_t v; + VectorClear(v); + v[i >> 1] = (i & 1) ? -1 : 1; + Matrix4x4_Transform(&rtlight->matrix_lighttoworld, v, plane.normal); + VectorSubtract(plane.normal, rtlight->shadoworigin, plane.normal); + plane.dist = VectorNormalizeLength(plane.normal); + plane.dist += DotProduct(plane.normal, rtlight->shadoworigin); + r_shadow_rtlight_frustumplanes[r_shadow_rtlight_numfrustumplanes++] = plane; + } + } +#endif + +#if 0 + // add the world-space reduced box planes + for (i = 0;i < 6;i++) + { + VectorClear(plane.normal); + plane.normal[i >> 1] = (i & 1) ? -1 : 1; + plane.dist = (i & 1) ? -r_shadow_rtlight_cullmaxs[i >> 1] : r_shadow_rtlight_cullmins[i >> 1]; + r_shadow_rtlight_frustumplanes[r_shadow_rtlight_numfrustumplanes++] = plane; + } +#endif + +#if 0 + { + int j, oldnum; + vec3_t points[8]; + vec_t bestdist; + // reduce all plane distances to tightly fit the rtlight cull box, which + // is in worldspace + VectorSet(points[0], r_shadow_rtlight_cullmins[0], r_shadow_rtlight_cullmins[1], r_shadow_rtlight_cullmins[2]); + VectorSet(points[1], r_shadow_rtlight_cullmaxs[0], r_shadow_rtlight_cullmins[1], r_shadow_rtlight_cullmins[2]); + VectorSet(points[2], r_shadow_rtlight_cullmins[0], r_shadow_rtlight_cullmaxs[1], r_shadow_rtlight_cullmins[2]); + VectorSet(points[3], r_shadow_rtlight_cullmaxs[0], r_shadow_rtlight_cullmaxs[1], r_shadow_rtlight_cullmins[2]); + VectorSet(points[4], r_shadow_rtlight_cullmins[0], r_shadow_rtlight_cullmins[1], r_shadow_rtlight_cullmaxs[2]); + VectorSet(points[5], r_shadow_rtlight_cullmaxs[0], r_shadow_rtlight_cullmins[1], r_shadow_rtlight_cullmaxs[2]); + VectorSet(points[6], r_shadow_rtlight_cullmins[0], r_shadow_rtlight_cullmaxs[1], r_shadow_rtlight_cullmaxs[2]); + VectorSet(points[7], r_shadow_rtlight_cullmaxs[0], r_shadow_rtlight_cullmaxs[1], r_shadow_rtlight_cullmaxs[2]); + oldnum = r_shadow_rtlight_numfrustumplanes; + r_shadow_rtlight_numfrustumplanes = 0; + for (j = 0;j < oldnum;j++) + { + // find the nearest point on the box to this plane + bestdist = DotProduct(r_shadow_rtlight_frustumplanes[j].normal, points[0]); + for (i = 1;i < 8;i++) + { + dist = DotProduct(r_shadow_rtlight_frustumplanes[j].normal, points[i]); + if (bestdist > dist) + bestdist = dist; + } + Con_Printf("light %p %splane #%i %f %f %f : %f < %f\n", rtlight, r_shadow_rtlight_frustumplanes[j].dist < bestdist + 0.03125 ? "^2" : "^1", j, r_shadow_rtlight_frustumplanes[j].normal[0], r_shadow_rtlight_frustumplanes[j].normal[1], r_shadow_rtlight_frustumplanes[j].normal[2], r_shadow_rtlight_frustumplanes[j].dist, bestdist); + // if the nearest point is near or behind the plane, we want this + // plane, otherwise the plane is useless as it won't cull anything + if (r_shadow_rtlight_frustumplanes[j].dist < bestdist + 0.03125) + { + PlaneClassify(&r_shadow_rtlight_frustumplanes[j]); + r_shadow_rtlight_frustumplanes[r_shadow_rtlight_numfrustumplanes++] = r_shadow_rtlight_frustumplanes[j]; + } + } + } +#endif +} + void R_Shadow_DrawWorldShadow(int numsurfaces, int *surfacelist, const unsigned char *trispvs) { RSurf_ActiveWorldEntity(); @@ -2479,6 +2636,8 @@ void R_DrawRTLight(rtlight_t *rtlight, qboolean visible) if (R_Shadow_ScissorForBBox(r_shadow_rtlight_cullmins, r_shadow_rtlight_cullmaxs)) return; + R_Shadow_ComputeShadowCasterCullingPlanes(rtlight); + // make a list of lit entities and shadow casting entities numlightentities = 0; numshadowentities = 0; @@ -2492,6 +2651,10 @@ void R_DrawRTLight(rtlight_t *rtlight, qboolean visible) vec3_t org; if (!BoxesOverlap(ent->mins, ent->maxs, r_shadow_rtlight_cullmins, r_shadow_rtlight_cullmaxs)) continue; + // skip the object entirely if it is not within the valid + // shadow-casting region (which includes the lit region) + if (R_CullBoxCustomPlanes(ent->mins, ent->maxs, r_shadow_rtlight_numfrustumplanes, r_shadow_rtlight_frustumplanes)) + continue; if (!(model = ent->model)) continue; if (r_viewcache.entityvisible[i] && model->DrawLight && (ent->flags & RENDER_LIGHT)) diff --git a/r_shadow.h b/r_shadow.h index 1c4aeb2e..07a68466 100644 --- a/r_shadow.h +++ b/r_shadow.h @@ -65,6 +65,13 @@ extern matrix4x4_t r_shadow_entitytoattenuationxyz; // this transforms only the Z to S, and T is always 0.5 extern matrix4x4_t r_shadow_entitytoattenuationz; +// current light's cull box (copied out of an rtlight or calculated by GetLightInfo) +extern vec3_t r_shadow_rtlight_cullmins; +extern vec3_t r_shadow_rtlight_cullmaxs; +// current light's culling planes +extern int r_shadow_rtlight_numfrustumplanes; +extern mplane_t r_shadow_rtlight_frustumplanes[12+6+6]; // see R_Shadow_ComputeShadowCasterCullingPlanes + void R_Shadow_RenderVolume(int numvertices, int numtriangles, const float *vertex3f, const int *element3i); qboolean R_Shadow_ScissorForBBox(const float *mins, const float *maxs); diff --git a/render.h b/render.h index 5010a752..852a25b9 100644 --- a/render.h +++ b/render.h @@ -136,6 +136,7 @@ void R_DrawExplosions(void); #define gl_alpha_format 4 int R_CullBox(const vec3_t mins, const vec3_t maxs); +int R_CullBoxCustomPlanes(const vec3_t mins, const vec3_t maxs, int numplanes, const mplane_t *planes); #include "r_modules.h" -- 2.39.2