123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638 |
- /*
- Copyright (C) 1997-2001 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 "r_local.h"
- //
- // current entity info
- //
- qboolean insubmodel;
- entity_t *currententity;
- vec3_t 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];
- 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
- Clip a bmodel poly down the world bsp tree
- ================
- */
- 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;
- int area;
- 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))
- {
- ri.Con_Printf (PRINT_ALL,"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))
- {
- ri.Con_Printf (PRINT_ALL,"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 != CONTENTS_NODE)
- {
- if (pn->contents != CONTENTS_SOLID)
- {
- if (r_newrefdef.areabits)
- {
- area = ((mleaf_t *)pn)->area;
- if (! (r_newrefdef.areabits[area>>3] & (1<<(area&7)) ) )
- continue; // not visible
- }
- r_currentbkey = ((mleaf_t *)pn)->key;
- R_RenderBmodelFace (psideedges[i], psurf);
- }
- }
- else
- {
- R_RecursiveClipBPoly (psideedges[i], pnode->children[i],
- psurf);
- }
- }
- }
- }
- }
- /*
- ================
- R_DrawSolidClippedSubmodelPolygons
- Bmodel crosses multiple leafs
- ================
- */
- void R_DrawSolidClippedSubmodelPolygons (model_t *pmodel, mnode_t *topnode)
- {
- 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)))
- continue;
- // 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;
- 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
- if ( !( psurf->texinfo->flags & ( SURF_TRANS66 | SURF_TRANS33 ) ) )
- R_RecursiveClipBPoly (pbedge, topnode, psurf);
- else
- R_RenderBmodelFace( pbedge, psurf );
- }
- }
- /*
- ================
- R_DrawSubmodelPolygons
- All in one leaf
- ================
- */
- void R_DrawSubmodelPolygons (model_t *pmodel, int clipflags, mnode_t *topnode)
- {
- 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 *)topnode)->key;
- // FIXME: use bounding-box-based frustum clipping info?
- R_RenderFace (psurf, clipflags);
- }
- }
- }
- int c_drawnode;
- /*
- ================
- 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;
- float d, dot;
- mleaf_t *pleaf;
- 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
- }
- }
- c_drawnode++;
- // if a leaf node, draw stuff
- if (node->contents != -1)
- {
- pleaf = (mleaf_t *)node;
- // check for door connected areas
- if (r_newrefdef.areabits)
- {
- if (! (r_newrefdef.areabits[pleaf->area>>3] & (1<<(pleaf->area&7)) ) )
- return; // not visible
- }
- mark = pleaf->firstmarksurface;
- c = pleaf->nummarksurfaces;
- if (c)
- {
- do
- {
- (*mark)->visframe = r_framecount;
- mark++;
- } while (--c);
- }
- 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 = r_worldmodel->surfaces + node->firstsurface;
- if (dot < -BACKFACE_EPSILON)
- {
- do
- {
- if ((surf->flags & SURF_PLANEBACK) &&
- (surf->visframe == r_framecount))
- {
- R_RenderFace (surf, clipflags);
- }
- surf++;
- } while (--c);
- }
- else if (dot > BACKFACE_EPSILON)
- {
- do
- {
- if (!(surf->flags & SURF_PLANEBACK) &&
- (surf->visframe == r_framecount))
- {
- 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)
- {
- if (!r_drawworld->value)
- return;
- if ( r_newrefdef.rdflags & RDF_NOWORLDMODEL )
- return;
- c_drawnode=0;
- // auto cycle the world frame for texture animation
- r_worldentity.frame = (int)(r_newrefdef.time*2);
- currententity = &r_worldentity;
- VectorCopy (r_origin, modelorg);
- currentmodel = r_worldmodel;
- r_pcurrentvertbase = currentmodel->vertexes;
- R_RecursiveWorldNode (currentmodel->nodes, 15);
- }
|