implemented shadow caster culling by creating a frustum plane set that includes the...

git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@6945 d7cf8633-e32d-0410-b094-e92efae38249

diff --git a/client.h b/client.h
index 5e9df7ded5479e1bda54879fb580813c3e3fca5b..b0edf5201f5d316a5c1dbde30a67294ed303eb38 100644 (file)
--- 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 361012e3f02ac04b445383fc56e2fb9569f427b9..4b26e4f4f670d4df8a10190f025de3d0a584abd4 100644 (file)
--- 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 d8e16f95364fe8be3d7c70606c6261b1df65c78d..30d6c6788aa46d54796f127cd5b32fb01aa9a823 100644 (file)
--- 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 98b21ee63e05edaf51a6576db3054b185099c3b1..352dc74acbf1b45878cdf28868edf3b868734dc9 100644 (file)
--- 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 1c4aeb2ebb8be27a9ce0d8ad4b39463d5027ade9..07a6846666f6ee0fb2acf728ffe7374ca616dcbe 100644 (file)
--- 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 5010a752361826af37a176313e35cce48faa68fb..852a25b93589701511672047f895265404af9369 100644 (file)
--- 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"