From 9e12e94923d6998872c0ea7312ac721b0fe4bba4 Mon Sep 17 00:00:00 2001 From: havoc Date: Thu, 20 Feb 2003 09:12:25 +0000 Subject: [PATCH] optional portal based determination of lit surfaces (good speed gain, enough to make dpdm2 somewhat playable, on by default) git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@2766 d7cf8633-e32d-0410-b094-e92efae38249 --- portals.c | 172 ++++++++++++++++++++++++++++++++++++++++++++++++++++- portals.h | 1 + quakedef.h | 2 - r_shadow.c | 101 ++++++++++++++++++++++--------- 4 files changed, 244 insertions(+), 32 deletions(-) diff --git a/portals.c b/portals.c index 554177ad..18e17b79 100644 --- a/portals.c +++ b/portals.c @@ -5,7 +5,6 @@ #define MAXRECURSIVEPORTALS 256 static tinyplane_t portalplanes[MAXRECURSIVEPORTALPLANES]; -static int portalplanecount; static int ranoutofportalplanes; static int ranoutofportals; static float portaltemppoints[2][256][3]; @@ -84,7 +83,7 @@ int Portal_PortalThroughPortalPlanes(tinyplane_t *clipplanes, int clipnumplanes, } if (numpoints > maxpoints) return -1; - memcpy(out, &portaltemppoints[1][0][0], numpoints * 3 * sizeof(float)); + memcpy(out, &portaltemppoints[0][0][0], numpoints * 3 * sizeof(float)); return numpoints; } @@ -220,7 +219,6 @@ int Portal_CheckPolygon(model_t *model, vec3_t eye, float *polypoints, int numpo } } - portalplanecount = 0; ranoutofportalplanes = false; ranoutofportals = false; @@ -319,3 +317,171 @@ int Portal_CheckBox(model_t *model, vec3_t eye, vec3_t a, vec3_t b) return false; } +vec3_t trianglepoints[3]; + +typedef struct portalrecursioninfo_s +{ + int exact; + float nradius; + qbyte *surfacemark; + qbyte *leafmark; + model_t *model; + vec3_t eye; +} +portalrecursioninfo_t; + +void Portal_RecursiveFlow_ExactMarkSurfaces(portalrecursioninfo_t *info, int *mark, int nummarksurfaces, int firstclipplane, int numclipplanes) +{ + int i, j, *elements; + msurface_t *surf; + surfmesh_t *surfmesh; + for (i = 0;i < nummarksurfaces;i++, mark++) + { + if (!info->surfacemark[*mark]) + { + surf = info->model->surfaces + *mark; + if (surf->poly_numverts) + { + if (surf->flags & SURF_PLANEBACK) + { + if (DotProduct(info->eye, surf->plane->normal) > surf->plane->dist) + continue; + } + else + { + if (DotProduct(info->eye, surf->plane->normal) < surf->plane->dist) + continue; + } + if (Portal_PortalThroughPortalPlanes(&portalplanes[firstclipplane], numclipplanes, surf->poly_verts, surf->poly_numverts, &portaltemppoints2[0][0], 256) < 3) + continue; + } + else + { + for (surfmesh = surf->mesh;surfmesh;surfmesh = surfmesh->chain) + { + for (j = 0, elements = surfmesh->index;j < surfmesh->numtriangles;j++, elements += 3) + { + VectorCopy((surfmesh->verts + elements[0] * 4), trianglepoints[0]); + VectorCopy((surfmesh->verts + elements[1] * 4), trianglepoints[1]); + VectorCopy((surfmesh->verts + elements[2] * 4), trianglepoints[2]); + if ((info->eye[0] - trianglepoints[0][0]) * ((trianglepoints[0][1] - trianglepoints[1][1]) * (trianglepoints[2][2] - trianglepoints[1][2]) - (trianglepoints[0][2] - trianglepoints[1][2]) * (trianglepoints[2][1] - trianglepoints[1][1])) + + (info->eye[1] - trianglepoints[0][1]) * ((trianglepoints[0][2] - trianglepoints[1][2]) * (trianglepoints[2][0] - trianglepoints[1][0]) - (trianglepoints[0][0] - trianglepoints[1][0]) * (trianglepoints[2][2] - trianglepoints[1][2])) + + (info->eye[2] - trianglepoints[0][2]) * ((trianglepoints[0][0] - trianglepoints[1][0]) * (trianglepoints[2][1] - trianglepoints[1][1]) - (trianglepoints[0][1] - trianglepoints[1][1]) * (trianglepoints[2][0] - trianglepoints[1][0])) > 0 + && Portal_PortalThroughPortalPlanes(&portalplanes[firstclipplane], numclipplanes, trianglepoints[0], 3, &portaltemppoints2[0][0], 256) >= 3) + break; + } + if (j < surfmesh->numtriangles) + break; + } + if (surfmesh == NULL) + continue; + } + info->surfacemark[*mark] = true; + } + } +} + +void Portal_RecursiveFlow (portalrecursioninfo_t *info, mleaf_t *leaf, int firstclipplane, int numclipplanes) +{ + mportal_t *p; + int newpoints, i, prev; + float dist; + vec3_t center, v1, v2; + tinyplane_t *newplanes; + + if (info->leafmark) + info->leafmark[leaf - info->model->leafs] = true; + + // mark surfaces in leaf that can be seen through portal + if (leaf->nummarksurfaces && info->surfacemark) + { + if (info->exact) + Portal_RecursiveFlow_ExactMarkSurfaces(info, leaf->firstmarksurface, leaf->nummarksurfaces, firstclipplane, numclipplanes); + else + for (i = 0;i < leaf->nummarksurfaces;i++) + info->surfacemark[leaf->firstmarksurface[i]] = true; + } + + // follow portals into other leafs + for (p = leaf->portals;p;p = p->next) + { + // only flow through portals facing away from the viewer + dist = PlaneDiff(info->eye, (&p->plane)); + if (dist < 0 && dist >= info->nradius) + { + newpoints = Portal_PortalThroughPortalPlanes(&portalplanes[firstclipplane], numclipplanes, (float *) p->points, p->numpoints, &portaltemppoints2[0][0], 256); + if (newpoints < 3) + continue; + else if (firstclipplane + numclipplanes + newpoints > MAXRECURSIVEPORTALPLANES) + ranoutofportalplanes = true; + else + { + // find the center by averaging + VectorClear(center); + for (i = 0;i < newpoints;i++) + VectorAdd(center, portaltemppoints2[i], center); + // ixtable is a 1.0f / N table + VectorScale(center, ixtable[newpoints], center); + // calculate the planes, and make sure the polygon can see it's own center + newplanes = &portalplanes[firstclipplane + numclipplanes]; + for (prev = newpoints - 1, i = 0;i < newpoints;prev = i, i++) + { + VectorSubtract(info->eye, portaltemppoints2[i], v1); + VectorSubtract(portaltemppoints2[prev], portaltemppoints2[i], v2); + CrossProduct(v1, v2, newplanes[i].normal); + VectorNormalizeFast(newplanes[i].normal); + newplanes[i].dist = DotProduct(info->eye, newplanes[i].normal); + if (DotProduct(newplanes[i].normal, center) <= newplanes[i].dist) + { + // polygon can't see it's own center, discard and use parent portal + break; + } + } + if (i == newpoints) + Portal_RecursiveFlow(info, p->past, firstclipplane + numclipplanes, newpoints); + else + Portal_RecursiveFlow(info, p->past, firstclipplane, numclipplanes); + } + } + } +} + +void Portal_Visibility(model_t *model, const vec3_t eye, qbyte *leafmark, qbyte *surfacemark, const mplane_t *frustumplanes, int numfrustumplanes, int exact, float radius) +{ + int i; + portalrecursioninfo_t info; + + // if there is no model, it can not block visibility + if (model == NULL) + Host_Error("Portal_Visibility: NULL model\n"); + + Mod_CheckLoaded(model); + + if (model->type != mod_brush) + Host_Error("Portal_Visibility: not a brush model\n"); + + // put frustum planes (if any) into tinyplane format at start of buffer + for (i = 0;i < numfrustumplanes;i++) + { + VectorCopy(frustumplanes[i].normal, portalplanes[i].normal); + portalplanes[i].dist = frustumplanes[i].dist; + } + + ranoutofportalplanes = false; + ranoutofportals = false; + + info.nradius = -radius; + info.exact = exact; + info.surfacemark = surfacemark; + info.leafmark = leafmark; + info.model = model; + VectorCopy(eye, info.eye); + + Portal_RecursiveFlow(&info, Mod_PointInLeaf(eye, model), 0, numfrustumplanes); + + if (ranoutofportalplanes) + Con_Printf("Portal_RecursiveFlow: ran out of %d plane stack when recursing through portals\n", MAXRECURSIVEPORTALPLANES); + if (ranoutofportals) + Con_Printf("Portal_RecursiveFlow: ran out of %d portal stack when recursing through portals\n", MAXRECURSIVEPORTALS); +} + diff --git a/portals.h b/portals.h index 02e7642c..25d8d3ce 100644 --- a/portals.h +++ b/portals.h @@ -4,6 +4,7 @@ int Portal_CheckPolygon(model_t *model, vec3_t eye, float *polypoints, int numpoints); int Portal_CheckBox(model_t *model, vec3_t eye, vec3_t a, vec3_t b); +void Portal_Visibility(model_t *model, const vec3_t eye, qbyte *leafmark, qbyte *surfacemark, const mplane_t *frustumplanes, int numfrustumplanes, int exact, float radius); #endif diff --git a/quakedef.h b/quakedef.h index 360b4b0d..f1d6d5ed 100644 --- a/quakedef.h +++ b/quakedef.h @@ -192,8 +192,6 @@ extern char *buildstring; #include "ui.h" -#include "portals.h" - extern qboolean noclip_anglehack; // diff --git a/r_shadow.c b/r_shadow.c index d1f00634..e2964deb 100644 --- a/r_shadow.c +++ b/r_shadow.c @@ -2,6 +2,7 @@ #include "quakedef.h" #include "r_shadow.h" #include "cl_collision.h" +#include "portals.h" extern void R_Shadow_EditLights_Init(void); @@ -39,6 +40,7 @@ cvar_t r_shadow_scissor = {0, "r_shadow_scissor", "1"}; cvar_t r_shadow_bumpscale_bumpmap = {0, "r_shadow_bumpscale_bumpmap", "4"}; cvar_t r_shadow_bumpscale_basetexture = {0, "r_shadow_bumpscale_basetexture", "0"}; cvar_t r_shadow_shadownudge = {0, "r_shadow_shadownudge", "1"}; +cvar_t r_shadow_portallight = {0, "r_shadow_portallight", "1"}; int c_rt_lights, c_rt_clears, c_rt_scissored; int c_rt_shadowmeshes, c_rt_shadowtris, c_rt_lightmeshes, c_rt_lighttris; @@ -103,6 +105,7 @@ void R_Shadow_Init(void) Cvar_RegisterVariable(&r_shadow_bumpscale_bumpmap); Cvar_RegisterVariable(&r_shadow_bumpscale_basetexture); Cvar_RegisterVariable(&r_shadow_shadownudge); + Cvar_RegisterVariable(&r_shadow_portallight); R_Shadow_EditLights_Init(); R_RegisterModule("R_Shadow", r_shadow_start, r_shadow_shutdown, r_shadow_newmap); } @@ -1051,7 +1054,7 @@ void R_Shadow_NewWorldLight(vec3_t origin, float radius, vec3_t color, int style e->style = style; if (e->style < 0 || e->style >= MAX_LIGHTSTYLES) { - Con_Printf("R_Shadow_NewWorldLight: invalid light style number %i, must be > = 0 and < %i\n", e->style, MAX_LIGHTSTYLES); + Con_Printf("R_Shadow_NewWorldLight: invalid light style number %i, must be >= 0 and < %i\n", e->style, MAX_LIGHTSTYLES); e->style = 0; } e->castshadows = castshadow; @@ -1075,38 +1078,82 @@ void R_Shadow_NewWorldLight(vec3_t origin, float radius, vec3_t color, int style if (cl.worldmodel) { castshadowcount++; - leaf = Mod_PointInLeaf(origin, cl.worldmodel); - pvs = Mod_LeafPVS(leaf, cl.worldmodel); - for (i = 0, leaf = cl.worldmodel->leafs + 1;i < cl.worldmodel->numleafs;i++, leaf++) + if (r_shadow_portallight.integer) + { + qbyte *byteleafpvs; + qbyte *bytesurfacepvs; + byteleafpvs = Mem_Alloc(tempmempool, cl.worldmodel->numleafs + 1); + bytesurfacepvs = Mem_Alloc(tempmempool, cl.worldmodel->numsurfaces); + Portal_Visibility(cl.worldmodel, e->origin, byteleafpvs, bytesurfacepvs, NULL, 0, true, e->lightradius); + + for (i = 0, leaf = cl.worldmodel->leafs + 1;i < cl.worldmodel->numleafs;i++, leaf++) + { + if (byteleafpvs[i+1]) + { + temp[0] = bound(leaf->mins[0], e->origin[0], leaf->maxs[0]) - e->origin[0]; + temp[1] = bound(leaf->mins[1], e->origin[1], leaf->maxs[1]) - e->origin[1]; + temp[2] = bound(leaf->mins[2], e->origin[2], leaf->maxs[2]) - e->origin[2]; + if (DotProduct(temp, temp) < e->lightradius * e->lightradius) + leaf->worldnodeframe = castshadowcount; + } + } + + for (i = 0, surf = cl.worldmodel->surfaces;i < cl.worldmodel->numsurfaces;i++, surf++) + { + if (bytesurfacepvs[i]) + { + f = DotProduct(e->origin, surf->plane->normal) - surf->plane->dist; + if (surf->flags & SURF_PLANEBACK) + f = -f; + if (f > 0 && f < e->lightradius) + { + temp[0] = bound(surf->poly_mins[0], e->origin[0], surf->poly_maxs[0]) - e->origin[0]; + temp[1] = bound(surf->poly_mins[1], e->origin[1], surf->poly_maxs[1]) - e->origin[1]; + temp[2] = bound(surf->poly_mins[2], e->origin[2], surf->poly_maxs[2]) - e->origin[2]; + if (DotProduct(temp, temp) < e->lightradius * e->lightradius) + surf->castshadow = castshadowcount; + } + } + } + + Mem_Free(byteleafpvs); + Mem_Free(bytesurfacepvs); + } + else { - if (pvs[i >> 3] & (1 << (i & 7))) + leaf = Mod_PointInLeaf(origin, cl.worldmodel); + pvs = Mod_LeafPVS(leaf, cl.worldmodel); + for (i = 0, leaf = cl.worldmodel->leafs + 1;i < cl.worldmodel->numleafs;i++, leaf++) { - VectorCopy(origin, temp); - if (temp[0] < leaf->mins[0]) temp[0] = leaf->mins[0]; - if (temp[0] > leaf->maxs[0]) temp[0] = leaf->maxs[0]; - if (temp[1] < leaf->mins[1]) temp[1] = leaf->mins[1]; - if (temp[1] > leaf->maxs[1]) temp[1] = leaf->maxs[1]; - if (temp[2] < leaf->mins[2]) temp[2] = leaf->mins[2]; - if (temp[2] > leaf->maxs[2]) temp[2] = leaf->maxs[2]; - VectorSubtract(temp, origin, temp); - if (DotProduct(temp, temp) < e->lightradius * e->lightradius) + if (pvs[i >> 3] & (1 << (i & 7))) { - leaf->worldnodeframe = castshadowcount; - for (j = 0, mark = leaf->firstmarksurface;j < leaf->nummarksurfaces;j++, mark++) + VectorCopy(origin, temp); + if (temp[0] < leaf->mins[0]) temp[0] = leaf->mins[0]; + if (temp[0] > leaf->maxs[0]) temp[0] = leaf->maxs[0]; + if (temp[1] < leaf->mins[1]) temp[1] = leaf->mins[1]; + if (temp[1] > leaf->maxs[1]) temp[1] = leaf->maxs[1]; + if (temp[2] < leaf->mins[2]) temp[2] = leaf->mins[2]; + if (temp[2] > leaf->maxs[2]) temp[2] = leaf->maxs[2]; + VectorSubtract(temp, origin, temp); + if (DotProduct(temp, temp) < e->lightradius * e->lightradius) { - surf = cl.worldmodel->surfaces + *mark; - if (surf->castshadow != castshadowcount) + leaf->worldnodeframe = castshadowcount; + for (j = 0, mark = leaf->firstmarksurface;j < leaf->nummarksurfaces;j++, mark++) { - f = DotProduct(e->origin, surf->plane->normal) - surf->plane->dist; - if (surf->flags & SURF_PLANEBACK) - f = -f; - if (f > 0 && f < e->lightradius) + surf = cl.worldmodel->surfaces + *mark; + if (surf->castshadow != castshadowcount) { - temp[0] = bound(surf->poly_mins[0], e->origin[0], surf->poly_maxs[0]) - e->origin[0]; - temp[1] = bound(surf->poly_mins[1], e->origin[1], surf->poly_maxs[1]) - e->origin[1]; - temp[2] = bound(surf->poly_mins[2], e->origin[2], surf->poly_maxs[2]) - e->origin[2]; - if (DotProduct(temp, temp) < e->lightradius * e->lightradius) - surf->castshadow = castshadowcount; + f = DotProduct(e->origin, surf->plane->normal) - surf->plane->dist; + if (surf->flags & SURF_PLANEBACK) + f = -f; + if (f > 0 && f < e->lightradius) + { + temp[0] = bound(surf->poly_mins[0], e->origin[0], surf->poly_maxs[0]) - e->origin[0]; + temp[1] = bound(surf->poly_mins[1], e->origin[1], surf->poly_maxs[1]) - e->origin[1]; + temp[2] = bound(surf->poly_mins[2], e->origin[2], surf->poly_maxs[2]) - e->origin[2]; + if (DotProduct(temp, temp) < e->lightradius * e->lightradius) + surf->castshadow = castshadowcount; + } } } } -- 2.39.2