/* | |
Copyright (C) 1996-1997 Id Software, Inc. | |
This program is free software; you can redistribute it and/or | |
modify it under the terms of the GNU General Public License | |
as published by the Free Software Foundation; either version 2 | |
of the License, or (at your option) any later version. | |
This program is distributed in the hope that it will be useful, | |
but WITHOUT ANY WARRANTY; without even the implied warranty of | |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. | |
See the GNU General Public License for more details. | |
You should have received a copy of the GNU General Public License | |
along with this program; if not, write to the Free Software | |
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. | |
*/ | |
// r_bsp.c | |
#include "quakedef.h" | |
#include "r_local.h" | |
// | |
// current entity info | |
// | |
qboolean insubmodel; | |
entity_t *currententity; | |
vec3_t modelorg, base_modelorg; | |
// modelorg is the viewpoint reletive to | |
// the currently rendering entity | |
vec3_t r_entorigin; // the currently rendering entity in world | |
// coordinates | |
float entity_rotation[3][3]; | |
vec3_t r_worldmodelorg; | |
int r_currentbkey; | |
typedef enum {touchessolid, drawnode, nodrawnode} solidstate_t; | |
#define MAX_BMODEL_VERTS 500 // 6K | |
#define MAX_BMODEL_EDGES 1000 // 12K | |
static mvertex_t *pbverts; | |
static bedge_t *pbedges; | |
static int numbverts, numbedges; | |
static mvertex_t *pfrontenter, *pfrontexit; | |
static qboolean makeclippededge; | |
//=========================================================================== | |
/* | |
================ | |
R_EntityRotate | |
================ | |
*/ | |
void R_EntityRotate (vec3_t vec) | |
{ | |
vec3_t tvec; | |
VectorCopy (vec, tvec); | |
vec[0] = DotProduct (entity_rotation[0], tvec); | |
vec[1] = DotProduct (entity_rotation[1], tvec); | |
vec[2] = DotProduct (entity_rotation[2], tvec); | |
} | |
/* | |
================ | |
R_RotateBmodel | |
================ | |
*/ | |
void R_RotateBmodel (void) | |
{ | |
float angle, s, c, temp1[3][3], temp2[3][3], temp3[3][3]; | |
// TODO: should use a look-up table | |
// TODO: should really be stored with the entity instead of being reconstructed | |
// TODO: could cache lazily, stored in the entity | |
// TODO: share work with R_SetUpAliasTransform | |
// yaw | |
angle = currententity->angles[YAW]; | |
angle = angle * M_PI*2 / 360; | |
s = sin(angle); | |
c = cos(angle); | |
temp1[0][0] = c; | |
temp1[0][1] = s; | |
temp1[0][2] = 0; | |
temp1[1][0] = -s; | |
temp1[1][1] = c; | |
temp1[1][2] = 0; | |
temp1[2][0] = 0; | |
temp1[2][1] = 0; | |
temp1[2][2] = 1; | |
// pitch | |
angle = currententity->angles[PITCH]; | |
angle = angle * M_PI*2 / 360; | |
s = sin(angle); | |
c = cos(angle); | |
temp2[0][0] = c; | |
temp2[0][1] = 0; | |
temp2[0][2] = -s; | |
temp2[1][0] = 0; | |
temp2[1][1] = 1; | |
temp2[1][2] = 0; | |
temp2[2][0] = s; | |
temp2[2][1] = 0; | |
temp2[2][2] = c; | |
R_ConcatRotations (temp2, temp1, temp3); | |
// roll | |
angle = currententity->angles[ROLL]; | |
angle = angle * M_PI*2 / 360; | |
s = sin(angle); | |
c = cos(angle); | |
temp1[0][0] = 1; | |
temp1[0][1] = 0; | |
temp1[0][2] = 0; | |
temp1[1][0] = 0; | |
temp1[1][1] = c; | |
temp1[1][2] = s; | |
temp1[2][0] = 0; | |
temp1[2][1] = -s; | |
temp1[2][2] = c; | |
R_ConcatRotations (temp1, temp3, entity_rotation); | |
// | |
// rotate modelorg and the transformation matrix | |
// | |
R_EntityRotate (modelorg); | |
R_EntityRotate (vpn); | |
R_EntityRotate (vright); | |
R_EntityRotate (vup); | |
R_TransformFrustum (); | |
} | |
/* | |
================ | |
R_RecursiveClipBPoly | |
================ | |
*/ | |
void R_RecursiveClipBPoly (bedge_t *pedges, mnode_t *pnode, msurface_t *psurf) | |
{ | |
bedge_t *psideedges[2], *pnextedge, *ptedge; | |
int i, side, lastside; | |
float dist, frac, lastdist; | |
mplane_t *splitplane, tplane; | |
mvertex_t *pvert, *plastvert, *ptvert; | |
mnode_t *pn; | |
psideedges[0] = psideedges[1] = NULL; | |
makeclippededge = false; | |
// transform the BSP plane into model space | |
// FIXME: cache these? | |
splitplane = pnode->plane; | |
tplane.dist = splitplane->dist - | |
DotProduct(r_entorigin, splitplane->normal); | |
tplane.normal[0] = DotProduct (entity_rotation[0], splitplane->normal); | |
tplane.normal[1] = DotProduct (entity_rotation[1], splitplane->normal); | |
tplane.normal[2] = DotProduct (entity_rotation[2], splitplane->normal); | |
// clip edges to BSP plane | |
for ( ; pedges ; pedges = pnextedge) | |
{ | |
pnextedge = pedges->pnext; | |
// set the status for the last point as the previous point | |
// FIXME: cache this stuff somehow? | |
plastvert = pedges->v[0]; | |
lastdist = DotProduct (plastvert->position, tplane.normal) - | |
tplane.dist; | |
if (lastdist > 0) | |
lastside = 0; | |
else | |
lastside = 1; | |
pvert = pedges->v[1]; | |
dist = DotProduct (pvert->position, tplane.normal) - tplane.dist; | |
if (dist > 0) | |
side = 0; | |
else | |
side = 1; | |
if (side != lastside) | |
{ | |
// clipped | |
if (numbverts >= MAX_BMODEL_VERTS) | |
return; | |
// generate the clipped vertex | |
frac = lastdist / (lastdist - dist); | |
ptvert = &pbverts[numbverts++]; | |
ptvert->position[0] = plastvert->position[0] + | |
frac * (pvert->position[0] - | |
plastvert->position[0]); | |
ptvert->position[1] = plastvert->position[1] + | |
frac * (pvert->position[1] - | |
plastvert->position[1]); | |
ptvert->position[2] = plastvert->position[2] + | |
frac * (pvert->position[2] - | |
plastvert->position[2]); | |
// split into two edges, one on each side, and remember entering | |
// and exiting points | |
// FIXME: share the clip edge by having a winding direction flag? | |
if (numbedges >= (MAX_BMODEL_EDGES - 1)) | |
{ | |
Con_Printf ("Out of edges for bmodel\n"); | |
return; | |
} | |
ptedge = &pbedges[numbedges]; | |
ptedge->pnext = psideedges[lastside]; | |
psideedges[lastside] = ptedge; | |
ptedge->v[0] = plastvert; | |
ptedge->v[1] = ptvert; | |
ptedge = &pbedges[numbedges + 1]; | |
ptedge->pnext = psideedges[side]; | |
psideedges[side] = ptedge; | |
ptedge->v[0] = ptvert; | |
ptedge->v[1] = pvert; | |
numbedges += 2; | |
if (side == 0) | |
{ | |
// entering for front, exiting for back | |
pfrontenter = ptvert; | |
makeclippededge = true; | |
} | |
else | |
{ | |
pfrontexit = ptvert; | |
makeclippededge = true; | |
} | |
} | |
else | |
{ | |
// add the edge to the appropriate side | |
pedges->pnext = psideedges[side]; | |
psideedges[side] = pedges; | |
} | |
} | |
// if anything was clipped, reconstitute and add the edges along the clip | |
// plane to both sides (but in opposite directions) | |
if (makeclippededge) | |
{ | |
if (numbedges >= (MAX_BMODEL_EDGES - 2)) | |
{ | |
Con_Printf ("Out of edges for bmodel\n"); | |
return; | |
} | |
ptedge = &pbedges[numbedges]; | |
ptedge->pnext = psideedges[0]; | |
psideedges[0] = ptedge; | |
ptedge->v[0] = pfrontexit; | |
ptedge->v[1] = pfrontenter; | |
ptedge = &pbedges[numbedges + 1]; | |
ptedge->pnext = psideedges[1]; | |
psideedges[1] = ptedge; | |
ptedge->v[0] = pfrontenter; | |
ptedge->v[1] = pfrontexit; | |
numbedges += 2; | |
} | |
// draw or recurse further | |
for (i=0 ; i<2 ; i++) | |
{ | |
if (psideedges[i]) | |
{ | |
// draw if we've reached a non-solid leaf, done if all that's left is a | |
// solid leaf, and continue down the tree if it's not a leaf | |
pn = pnode->children[i]; | |
// we're done with this branch if the node or leaf isn't in the PVS | |
if (pn->visframe == r_visframecount) | |
{ | |
if (pn->contents < 0) | |
{ | |
if (pn->contents != CONTENTS_SOLID) | |
{ | |
r_currentbkey = ((mleaf_t *)pn)->key; | |
R_RenderBmodelFace (psideedges[i], psurf); | |
} | |
} | |
else | |
{ | |
R_RecursiveClipBPoly (psideedges[i], pnode->children[i], | |
psurf); | |
} | |
} | |
} | |
} | |
} | |
/* | |
================ | |
R_DrawSolidClippedSubmodelPolygons | |
================ | |
*/ | |
void R_DrawSolidClippedSubmodelPolygons (model_t *pmodel) | |
{ | |
int i, j, lindex; | |
vec_t dot; | |
msurface_t *psurf; | |
int numsurfaces; | |
mplane_t *pplane; | |
mvertex_t bverts[MAX_BMODEL_VERTS]; | |
bedge_t bedges[MAX_BMODEL_EDGES], *pbedge; | |
medge_t *pedge, *pedges; | |
// FIXME: use bounding-box-based frustum clipping info? | |
psurf = &pmodel->surfaces[pmodel->firstmodelsurface]; | |
numsurfaces = pmodel->nummodelsurfaces; | |
pedges = pmodel->edges; | |
for (i=0 ; i<numsurfaces ; i++, psurf++) | |
{ | |
// find which side of the node we are on | |
pplane = psurf->plane; | |
dot = DotProduct (modelorg, pplane->normal) - pplane->dist; | |
// draw the polygon | |
if (((psurf->flags & SURF_PLANEBACK) && (dot < -BACKFACE_EPSILON)) || | |
(!(psurf->flags & SURF_PLANEBACK) && (dot > BACKFACE_EPSILON))) | |
{ | |
// FIXME: use bounding-box-based frustum clipping info? | |
// copy the edges to bedges, flipping if necessary so always | |
// clockwise winding | |
// FIXME: if edges and vertices get caches, these assignments must move | |
// outside the loop, and overflow checking must be done here | |
pbverts = bverts; | |
pbedges = bedges; | |
numbverts = numbedges = 0; | |
if (psurf->numedges > 0) | |
{ | |
pbedge = &bedges[numbedges]; | |
numbedges += psurf->numedges; | |
for (j=0 ; j<psurf->numedges ; j++) | |
{ | |
lindex = pmodel->surfedges[psurf->firstedge+j]; | |
if (lindex > 0) | |
{ | |
pedge = &pedges[lindex]; | |
pbedge[j].v[0] = &r_pcurrentvertbase[pedge->v[0]]; | |
pbedge[j].v[1] = &r_pcurrentvertbase[pedge->v[1]]; | |
} | |
else | |
{ | |
lindex = -lindex; | |
pedge = &pedges[lindex]; | |
pbedge[j].v[0] = &r_pcurrentvertbase[pedge->v[1]]; | |
pbedge[j].v[1] = &r_pcurrentvertbase[pedge->v[0]]; | |
} | |
pbedge[j].pnext = &pbedge[j+1]; | |
} | |
pbedge[j-1].pnext = NULL; // mark end of edges | |
R_RecursiveClipBPoly (pbedge, currententity->topnode, psurf); | |
} | |
else | |
{ | |
Sys_Error ("no edges in bmodel"); | |
} | |
} | |
} | |
} | |
/* | |
================ | |
R_DrawSubmodelPolygons | |
================ | |
*/ | |
void R_DrawSubmodelPolygons (model_t *pmodel, int clipflags) | |
{ | |
int i; | |
vec_t dot; | |
msurface_t *psurf; | |
int numsurfaces; | |
mplane_t *pplane; | |
// FIXME: use bounding-box-based frustum clipping info? | |
psurf = &pmodel->surfaces[pmodel->firstmodelsurface]; | |
numsurfaces = pmodel->nummodelsurfaces; | |
for (i=0 ; i<numsurfaces ; i++, psurf++) | |
{ | |
// find which side of the node we are on | |
pplane = psurf->plane; | |
dot = DotProduct (modelorg, pplane->normal) - pplane->dist; | |
// draw the polygon | |
if (((psurf->flags & SURF_PLANEBACK) && (dot < -BACKFACE_EPSILON)) || | |
(!(psurf->flags & SURF_PLANEBACK) && (dot > BACKFACE_EPSILON))) | |
{ | |
r_currentkey = ((mleaf_t *)currententity->topnode)->key; | |
// FIXME: use bounding-box-based frustum clipping info? | |
R_RenderFace (psurf, clipflags); | |
} | |
} | |
} | |
/* | |
================ | |
R_RecursiveWorldNode | |
================ | |
*/ | |
void R_RecursiveWorldNode (mnode_t *node, int clipflags) | |
{ | |
int i, c, side, *pindex; | |
vec3_t acceptpt, rejectpt; | |
mplane_t *plane; | |
msurface_t *surf, **mark; | |
mleaf_t *pleaf; | |
double d, dot; | |
if (node->contents == CONTENTS_SOLID) | |
return; // solid | |
if (node->visframe != r_visframecount) | |
return; | |
// cull the clipping planes if not trivial accept | |
// FIXME: the compiler is doing a lousy job of optimizing here; it could be | |
// twice as fast in ASM | |
if (clipflags) | |
{ | |
for (i=0 ; i<4 ; i++) | |
{ | |
if (! (clipflags & (1<<i)) ) | |
continue; // don't need to clip against it | |
// generate accept and reject points | |
// FIXME: do with fast look-ups or integer tests based on the sign bit | |
// of the floating point values | |
pindex = pfrustum_indexes[i]; | |
rejectpt[0] = (float)node->minmaxs[pindex[0]]; | |
rejectpt[1] = (float)node->minmaxs[pindex[1]]; | |
rejectpt[2] = (float)node->minmaxs[pindex[2]]; | |
d = DotProduct (rejectpt, view_clipplanes[i].normal); | |
d -= view_clipplanes[i].dist; | |
if (d <= 0) | |
return; | |
acceptpt[0] = (float)node->minmaxs[pindex[3+0]]; | |
acceptpt[1] = (float)node->minmaxs[pindex[3+1]]; | |
acceptpt[2] = (float)node->minmaxs[pindex[3+2]]; | |
d = DotProduct (acceptpt, view_clipplanes[i].normal); | |
d -= view_clipplanes[i].dist; | |
if (d >= 0) | |
clipflags &= ~(1<<i); // node is entirely on screen | |
} | |
} | |
// if a leaf node, draw stuff | |
if (node->contents < 0) | |
{ | |
pleaf = (mleaf_t *)node; | |
mark = pleaf->firstmarksurface; | |
c = pleaf->nummarksurfaces; | |
if (c) | |
{ | |
do | |
{ | |
(*mark)->visframe = r_framecount; | |
mark++; | |
} while (--c); | |
} | |
// deal with model fragments in this leaf | |
if (pleaf->efrags) | |
{ | |
R_StoreEfrags (&pleaf->efrags); | |
} | |
pleaf->key = r_currentkey; | |
r_currentkey++; // all bmodels in a leaf share the same key | |
} | |
else | |
{ | |
// node is just a decision point, so go down the apropriate sides | |
// find which side of the node we are on | |
plane = node->plane; | |
switch (plane->type) | |
{ | |
case PLANE_X: | |
dot = modelorg[0] - plane->dist; | |
break; | |
case PLANE_Y: | |
dot = modelorg[1] - plane->dist; | |
break; | |
case PLANE_Z: | |
dot = modelorg[2] - plane->dist; | |
break; | |
default: | |
dot = DotProduct (modelorg, plane->normal) - plane->dist; | |
break; | |
} | |
if (dot >= 0) | |
side = 0; | |
else | |
side = 1; | |
// recurse down the children, front side first | |
R_RecursiveWorldNode (node->children[side], clipflags); | |
// draw stuff | |
c = node->numsurfaces; | |
if (c) | |
{ | |
surf = cl.worldmodel->surfaces + node->firstsurface; | |
if (dot < -BACKFACE_EPSILON) | |
{ | |
do | |
{ | |
if ((surf->flags & SURF_PLANEBACK) && | |
(surf->visframe == r_framecount)) | |
{ | |
if (r_drawpolys) | |
{ | |
if (r_worldpolysbacktofront) | |
{ | |
if (numbtofpolys < MAX_BTOFPOLYS) | |
{ | |
pbtofpolys[numbtofpolys].clipflags = | |
clipflags; | |
pbtofpolys[numbtofpolys].psurf = surf; | |
numbtofpolys++; | |
} | |
} | |
else | |
{ | |
R_RenderPoly (surf, clipflags); | |
} | |
} | |
else | |
{ | |
R_RenderFace (surf, clipflags); | |
} | |
} | |
surf++; | |
} while (--c); | |
} | |
else if (dot > BACKFACE_EPSILON) | |
{ | |
do | |
{ | |
if (!(surf->flags & SURF_PLANEBACK) && | |
(surf->visframe == r_framecount)) | |
{ | |
if (r_drawpolys) | |
{ | |
if (r_worldpolysbacktofront) | |
{ | |
if (numbtofpolys < MAX_BTOFPOLYS) | |
{ | |
pbtofpolys[numbtofpolys].clipflags = | |
clipflags; | |
pbtofpolys[numbtofpolys].psurf = surf; | |
numbtofpolys++; | |
} | |
} | |
else | |
{ | |
R_RenderPoly (surf, clipflags); | |
} | |
} | |
else | |
{ | |
R_RenderFace (surf, clipflags); | |
} | |
} | |
surf++; | |
} while (--c); | |
} | |
// all surfaces on the same node share the same sequence number | |
r_currentkey++; | |
} | |
// recurse down the back side | |
R_RecursiveWorldNode (node->children[!side], clipflags); | |
} | |
} | |
/* | |
================ | |
R_RenderWorld | |
================ | |
*/ | |
void R_RenderWorld (void) | |
{ | |
int i; | |
model_t *clmodel; | |
btofpoly_t btofpolys[MAX_BTOFPOLYS]; | |
pbtofpolys = btofpolys; | |
currententity = &cl_entities[0]; | |
VectorCopy (r_origin, modelorg); | |
clmodel = currententity->model; | |
r_pcurrentvertbase = clmodel->vertexes; | |
R_RecursiveWorldNode (clmodel->nodes, 15); | |
// if the driver wants the polygons back to front, play the visible ones back | |
// in that order | |
if (r_worldpolysbacktofront) | |
{ | |
for (i=numbtofpolys-1 ; i>=0 ; i--) | |
{ | |
R_RenderPoly (btofpolys[i].psurf, btofpolys[i].clipflags); | |
} | |
} | |
} | |