0,0 → 1,674 |
/* |
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); |
} |
} |
} |
|
|