1 /*
2 * r_bsp.c
3 * $Id: r_bsp.c,v 1.7 2008-04-22 13:06:06 sezero Exp $
4 *
5 * Copyright (C) 1996-1997 Id Software, Inc.
6 * Copyright (C) 1997-1998 Raven Software Corp.
7 *
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or (at
11 * your option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
16 *
17 * See the GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License along
20 * with this program; if not, write to the Free Software Foundation, Inc.,
21 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
22 */
23
24 #include "quakedef.h"
25 #include "r_local.h"
26
27 //
28 // current entity info
29 //
30 qboolean insubmodel;
31 entity_t *currententity;
32 vec3_t modelorg, base_modelorg;
33 // modelorg is the viewpoint reletive to
34 // the currently rendering entity
35
36 vec3_t r_entorigin;
37 // the currently rendering entity in world
38 // coordinates
39
40 float entity_rotation[3][3];
41
42 int r_currentbkey;
43
44 typedef enum
45 {
46 touchessolid,
47 drawnode,
48 nodrawnode
49 } solidstate_t;
50
51 #define MAX_BMODEL_VERTS 500 // 6K
52 #define MAX_BMODEL_EDGES 1000 // 12K
53
54 static mvertex_t *pbverts;
55 static bedge_t *pbedges;
56 static int numbverts, numbedges;
57
58 static mvertex_t *pfrontenter, *pfrontexit;
59
60 static qboolean makeclippededge;
61
62
63 //===========================================================================
64
65 /*
66 ================
67 R_EntityRotate
68 ================
69 */
R_EntityRotate(vec3_t vec)70 static void R_EntityRotate (vec3_t vec)
71 {
72 vec3_t tvec;
73
74 VectorCopy (vec, tvec);
75 vec[0] = DotProduct (entity_rotation[0], tvec);
76 vec[1] = DotProduct (entity_rotation[1], tvec);
77 vec[2] = DotProduct (entity_rotation[2], tvec);
78 }
79
80
81 /*
82 ================
83 R_RotateBmodel
84 ================
85 */
R_RotateBmodel(void)86 void R_RotateBmodel (void)
87 {
88 float angle, s, c, temp1[3][3], temp2[3][3], temp3[3][3];
89
90 // TODO: should use a look-up table
91 // TODO: should really be stored with the entity instead of being reconstructed
92 // TODO: could cache lazily, stored in the entity
93 // TODO: share work with R_SetUpAliasTransform
94
95 // yaw
96 angle = currententity->angles[YAW];
97 angle = angle * M_PI*2 / 360;
98 s = sin(angle);
99 c = cos(angle);
100
101 temp1[0][0] = c;
102 temp1[0][1] = s;
103 temp1[0][2] = 0;
104 temp1[1][0] = -s;
105 temp1[1][1] = c;
106 temp1[1][2] = 0;
107 temp1[2][0] = 0;
108 temp1[2][1] = 0;
109 temp1[2][2] = 1;
110
111 // pitch
112 angle = currententity->angles[PITCH];
113 angle = angle * M_PI*2 / 360;
114 s = sin(angle);
115 c = cos(angle);
116
117 temp2[0][0] = c;
118 temp2[0][1] = 0;
119 temp2[0][2] = -s;
120 temp2[1][0] = 0;
121 temp2[1][1] = 1;
122 temp2[1][2] = 0;
123 temp2[2][0] = s;
124 temp2[2][1] = 0;
125 temp2[2][2] = c;
126
127 R_ConcatRotations (temp2, temp1, temp3);
128
129 // roll
130 angle = currententity->angles[ROLL];
131 angle = angle * M_PI*2 / 360;
132 s = sin(angle);
133 c = cos(angle);
134
135 temp1[0][0] = 1;
136 temp1[0][1] = 0;
137 temp1[0][2] = 0;
138 temp1[1][0] = 0;
139 temp1[1][1] = c;
140 temp1[1][2] = s;
141 temp1[2][0] = 0;
142 temp1[2][1] = -s;
143 temp1[2][2] = c;
144
145 R_ConcatRotations (temp1, temp3, entity_rotation);
146
147 //
148 // rotate modelorg and the transformation matrix
149 //
150 R_EntityRotate (modelorg);
151 R_EntityRotate (vpn);
152 R_EntityRotate (vright);
153 R_EntityRotate (vup);
154
155 R_TransformFrustum ();
156 }
157
158
159 /*
160 ================
161 R_RecursiveClipBPoly
162 ================
163 */
R_RecursiveClipBPoly(bedge_t * pedges,mnode_t * pnode,msurface_t * psurf)164 static void R_RecursiveClipBPoly (bedge_t *pedges, mnode_t *pnode, msurface_t *psurf)
165 {
166 bedge_t *psideedges[2], *pnextedge, *ptedge;
167 int i, side, lastside;
168 float dist, frac, lastdist;
169 mplane_t *splitplane, tplane;
170 mvertex_t *pvert, *plastvert, *ptvert;
171 mnode_t *pn;
172
173 psideedges[0] = psideedges[1] = NULL;
174
175 makeclippededge = false;
176
177 // transform the BSP plane into model space
178 // FIXME: cache these?
179 splitplane = pnode->plane;
180 tplane.dist = splitplane->dist -
181 DotProduct(r_entorigin, splitplane->normal);
182 tplane.normal[0] = DotProduct (entity_rotation[0], splitplane->normal);
183 tplane.normal[1] = DotProduct (entity_rotation[1], splitplane->normal);
184 tplane.normal[2] = DotProduct (entity_rotation[2], splitplane->normal);
185
186 // clip edges to BSP plane
187 for ( ; pedges ; pedges = pnextedge)
188 {
189 pnextedge = pedges->pnext;
190
191 // set the status for the last point as the previous point
192 // FIXME: cache this stuff somehow?
193 plastvert = pedges->v[0];
194 lastdist = DotProduct (plastvert->position, tplane.normal) - tplane.dist;
195
196 if (lastdist > 0)
197 lastside = 0;
198 else
199 lastside = 1;
200
201 pvert = pedges->v[1];
202
203 dist = DotProduct (pvert->position, tplane.normal) - tplane.dist;
204
205 if (dist > 0)
206 side = 0;
207 else
208 side = 1;
209
210 if (side != lastside)
211 {
212 // clipped
213 if (numbverts >= MAX_BMODEL_VERTS)
214 return;
215
216 // generate the clipped vertex
217 frac = lastdist / (lastdist - dist);
218 ptvert = &pbverts[numbverts++];
219 ptvert->position[0] = plastvert->position[0] +
220 frac * (pvert->position[0] -
221 plastvert->position[0]);
222 ptvert->position[1] = plastvert->position[1] +
223 frac * (pvert->position[1] -
224 plastvert->position[1]);
225 ptvert->position[2] = plastvert->position[2] +
226 frac * (pvert->position[2] -
227 plastvert->position[2]);
228
229 // split into two edges, one on each side, and remember entering
230 // and exiting points
231 // FIXME: share the clip edge by having a winding direction flag?
232 if (numbedges >= (MAX_BMODEL_EDGES - 1))
233 {
234 Con_Printf ("Out of edges for bmodel\n");
235 return;
236 }
237
238 ptedge = &pbedges[numbedges];
239 ptedge->pnext = psideedges[lastside];
240 psideedges[lastside] = ptedge;
241 ptedge->v[0] = plastvert;
242 ptedge->v[1] = ptvert;
243
244 ptedge = &pbedges[numbedges + 1];
245 ptedge->pnext = psideedges[side];
246 psideedges[side] = ptedge;
247 ptedge->v[0] = ptvert;
248 ptedge->v[1] = pvert;
249
250 numbedges += 2;
251
252 if (side == 0)
253 {
254 // entering for front, exiting for back
255 pfrontenter = ptvert;
256 makeclippededge = true;
257 }
258 else
259 {
260 pfrontexit = ptvert;
261 makeclippededge = true;
262 }
263 }
264 else
265 {
266 // add the edge to the appropriate side
267 pedges->pnext = psideedges[side];
268 psideedges[side] = pedges;
269 }
270 }
271
272 // if anything was clipped, reconstitute and add the edges along the clip
273 // plane to both sides (but in opposite directions)
274 if (makeclippededge)
275 {
276 if (numbedges >= (MAX_BMODEL_EDGES - 2))
277 {
278 Con_Printf ("Out of edges for bmodel\n");
279 return;
280 }
281
282 ptedge = &pbedges[numbedges];
283 ptedge->pnext = psideedges[0];
284 psideedges[0] = ptedge;
285 ptedge->v[0] = pfrontexit;
286 ptedge->v[1] = pfrontenter;
287
288 ptedge = &pbedges[numbedges + 1];
289 ptedge->pnext = psideedges[1];
290 psideedges[1] = ptedge;
291 ptedge->v[0] = pfrontenter;
292 ptedge->v[1] = pfrontexit;
293
294 numbedges += 2;
295 }
296
297 // draw or recurse further
298 for (i = 0 ; i < 2 ; i++)
299 {
300 if (psideedges[i])
301 {
302 // draw if we've reached a non-solid leaf, done if all
303 // that's left is a solid leaf, and continue down the
304 // tree if it's not a leaf
305 pn = pnode->children[i];
306
307 // we're done with this branch if the node or leaf isn't
308 // in the PVS
309 if (pn->visframe == r_visframecount)
310 {
311 if (pn->contents < 0)
312 {
313 if (pn->contents != CONTENTS_SOLID)
314 {
315 r_currentbkey = ((mleaf_t *)pn)->key;
316 R_RenderBmodelFace (psideedges[i], psurf);
317 }
318 }
319 else
320 {
321 R_RecursiveClipBPoly (psideedges[i], pnode->children[i], psurf);
322 }
323 }
324 }
325 }
326 }
327
328
329 /*
330 ================
331 R_DrawSolidClippedSubmodelPolygons
332 ================
333 */
R_DrawSolidClippedSubmodelPolygons(qmodel_t * pmodel)334 void R_DrawSolidClippedSubmodelPolygons (qmodel_t *pmodel)
335 {
336 int i, j, lindex;
337 vec_t dot;
338 msurface_t *psurf;
339 int numsurfaces;
340 mplane_t *pplane;
341 mvertex_t bverts[MAX_BMODEL_VERTS];
342 bedge_t bedges[MAX_BMODEL_EDGES], *pbedge;
343 medge_t *pedge, *pedges;
344
345 // FIXME: use bounding-box-based frustum clipping info?
346
347 psurf = &pmodel->surfaces[pmodel->firstmodelsurface];
348 numsurfaces = pmodel->nummodelsurfaces;
349 pedges = pmodel->edges;
350
351 for (i = 0 ; i < numsurfaces ; i++, psurf++)
352 {
353 // find which side of the node we are on
354 pplane = psurf->plane;
355
356 dot = DotProduct (modelorg, pplane->normal) - pplane->dist;
357
358 // draw the polygon
359 if ( ((psurf->flags & SURF_PLANEBACK) && (dot < -BACKFACE_EPSILON)) ||
360 (!(psurf->flags & SURF_PLANEBACK) && (dot > BACKFACE_EPSILON)) )
361 {
362 // FIXME: use bounding-box-based frustum clipping info?
363
364 // copy the edges to bedges, flipping if necessary
365 // so always clockwise winding
366 // FIXME: if edges and vertices get caches, these
367 // assignments must move outside the loop,
368 // and overflow checking must be done here
369 pbverts = bverts;
370 pbedges = bedges;
371 numbverts = numbedges = 0;
372
373 if (psurf->numedges > 0)
374 {
375 pbedge = &bedges[numbedges];
376 numbedges += psurf->numedges;
377
378 for (j = 0 ; j < psurf->numedges ; j++)
379 {
380 lindex = pmodel->surfedges[psurf->firstedge+j];
381
382 if (lindex > 0)
383 {
384 pedge = &pedges[lindex];
385 pbedge[j].v[0] = &r_pcurrentvertbase[pedge->v[0]];
386 pbedge[j].v[1] = &r_pcurrentvertbase[pedge->v[1]];
387 }
388 else
389 {
390 lindex = -lindex;
391 pedge = &pedges[lindex];
392 pbedge[j].v[0] = &r_pcurrentvertbase[pedge->v[1]];
393 pbedge[j].v[1] = &r_pcurrentvertbase[pedge->v[0]];
394 }
395
396 pbedge[j].pnext = &pbedge[j+1];
397 }
398
399 pbedge[j-1].pnext = NULL; // mark end of edges
400
401 R_RecursiveClipBPoly (pbedge, currententity->topnode, psurf);
402 }
403 else
404 {
405 Sys_Error ("no edges in bmodel");
406 }
407 }
408 }
409 }
410
411
412 /*
413 ================
414 R_DrawSubmodelPolygons
415 ================
416 */
R_DrawSubmodelPolygons(qmodel_t * pmodel,int clipflags)417 void R_DrawSubmodelPolygons (qmodel_t *pmodel, int clipflags)
418 {
419 int i;
420 vec_t dot;
421 msurface_t *psurf;
422 int numsurfaces;
423 mplane_t *pplane;
424
425 // FIXME: use bounding-box-based frustum clipping info?
426
427 psurf = &pmodel->surfaces[pmodel->firstmodelsurface];
428 numsurfaces = pmodel->nummodelsurfaces;
429
430 for (i = 0 ; i < numsurfaces ; i++, psurf++)
431 {
432 // find which side of the node we are on
433 pplane = psurf->plane;
434
435 dot = DotProduct (modelorg, pplane->normal) - pplane->dist;
436
437 // draw the polygon
438 if ( ((psurf->flags & SURF_PLANEBACK) && (dot < -BACKFACE_EPSILON)) ||
439 (!(psurf->flags & SURF_PLANEBACK) && (dot > BACKFACE_EPSILON)) )
440 {
441 r_currentkey = ((mleaf_t *)currententity->topnode)->key;
442
443 // FIXME: use bounding-box-based frustum clipping info?
444 R_RenderFace (psurf, clipflags);
445 }
446 }
447 }
448
449
450 /*
451 ================
452 R_RecursiveWorldNode
453 ================
454 */
R_RecursiveWorldNode(mnode_t * node,int clipflags)455 static void R_RecursiveWorldNode (mnode_t *node, int clipflags)
456 {
457 int i, c, side, *pindex;
458 vec3_t acceptpt, rejectpt;
459 mplane_t *plane;
460 msurface_t *surf, **mark;
461 mleaf_t *pleaf;
462 double d, dot;
463
464 if (node->contents == CONTENTS_SOLID)
465 return; // solid
466
467 if (node->visframe != r_visframecount)
468 return;
469
470 // cull the clipping planes if not trivial accept
471 // FIXME: the compiler is doing a lousy job of optimizing
472 // here; it could be twice as fast in ASM
473 if (clipflags)
474 {
475 for (i = 0 ; i < 4 ; i++)
476 {
477 if (! (clipflags & (1<<i)) )
478 continue; // don't need to clip against it
479
480 // generate accept and reject points
481 // FIXME: do with fast look-ups or integer tests based
482 // on the sign bit of the floating point values
483
484 pindex = pfrustum_indexes[i];
485
486 rejectpt[0] = (float)node->minmaxs[pindex[0]];
487 rejectpt[1] = (float)node->minmaxs[pindex[1]];
488 rejectpt[2] = (float)node->minmaxs[pindex[2]];
489
490 d = DotProduct (rejectpt, view_clipplanes[i].normal);
491 d -= view_clipplanes[i].dist;
492
493 if (d <= 0)
494 return;
495
496 acceptpt[0] = (float)node->minmaxs[pindex[3+0]];
497 acceptpt[1] = (float)node->minmaxs[pindex[3+1]];
498 acceptpt[2] = (float)node->minmaxs[pindex[3+2]];
499
500 d = DotProduct (acceptpt, view_clipplanes[i].normal);
501 d -= view_clipplanes[i].dist;
502
503 if (d >= 0)
504 clipflags &= ~(1<<i); // node is entirely on screen
505 }
506 }
507
508 // if a leaf node, draw stuff
509 if (node->contents < 0)
510 {
511 pleaf = (mleaf_t *)node;
512
513 mark = pleaf->firstmarksurface;
514 c = pleaf->nummarksurfaces;
515
516 if (c)
517 {
518 do
519 {
520 (*mark)->visframe = r_framecount;
521 mark++;
522 } while (--c);
523 }
524
525 // deal with model fragments in this leaf
526 if (pleaf->efrags)
527 {
528 R_StoreEfrags (&pleaf->efrags);
529 }
530
531 pleaf->key = r_currentkey;
532 r_currentkey++; // all bmodels in a leaf share the same key
533 }
534 else
535 {
536 // node is just a decision point, so go down the apropriate sides
537 // find which side of the node we are on
538 plane = node->plane;
539
540 switch (plane->type)
541 {
542 case PLANE_X:
543 dot = modelorg[0] - plane->dist;
544 break;
545 case PLANE_Y:
546 dot = modelorg[1] - plane->dist;
547 break;
548 case PLANE_Z:
549 dot = modelorg[2] - plane->dist;
550 break;
551 default:
552 dot = DotProduct (modelorg, plane->normal) - plane->dist;
553 break;
554 }
555
556 if (dot >= 0)
557 side = 0;
558 else
559 side = 1;
560
561 // recurse down the children, front side first
562 R_RecursiveWorldNode (node->children[side], clipflags);
563
564 // draw stuff
565 c = node->numsurfaces;
566
567 if (c)
568 {
569 surf = cl.worldmodel->surfaces + node->firstsurface;
570
571 if (dot < -BACKFACE_EPSILON)
572 {
573 do
574 {
575 if ((surf->flags & SURF_PLANEBACK) &&
576 (surf->visframe == r_framecount))
577 {
578 if (r_drawpolys)
579 {
580 if (r_worldpolysbacktofront)
581 {
582 if (numbtofpolys < MAX_BTOFPOLYS)
583 {
584 pbtofpolys[numbtofpolys].clipflags = clipflags;
585 pbtofpolys[numbtofpolys].psurf = surf;
586 numbtofpolys++;
587 }
588 }
589 else
590 {
591 R_RenderPoly (surf, clipflags);
592 }
593 }
594 else
595 {
596 R_RenderFace (surf, clipflags);
597 }
598 }
599
600 surf++;
601 } while (--c);
602 }
603 else if (dot > BACKFACE_EPSILON)
604 {
605 do
606 {
607 if (!(surf->flags & SURF_PLANEBACK) &&
608 (surf->visframe == r_framecount))
609 {
610 if (r_drawpolys)
611 {
612 if (r_worldpolysbacktofront)
613 {
614 if (numbtofpolys < MAX_BTOFPOLYS)
615 {
616 pbtofpolys[numbtofpolys].clipflags = clipflags;
617 pbtofpolys[numbtofpolys].psurf = surf;
618 numbtofpolys++;
619 }
620 }
621 else
622 {
623 R_RenderPoly (surf, clipflags);
624 }
625 }
626 else
627 {
628 R_RenderFace (surf, clipflags);
629 }
630 }
631
632 surf++;
633 } while (--c);
634 }
635
636 // all surfaces on the same node share the same sequence number
637 r_currentkey++;
638 }
639
640 // recurse down the back side
641 R_RecursiveWorldNode (node->children[!side], clipflags);
642 }
643 }
644
645
646 /*
647 ================
648 R_RenderWorld
649 ================
650 */
R_RenderWorld(void)651 void R_RenderWorld (void)
652 {
653 int i;
654 qmodel_t *clmodel;
655 btofpoly_t btofpolys[MAX_BTOFPOLYS];
656
657 pbtofpolys = btofpolys;
658
659 currententity = &r_worldentity;
660 VectorCopy (r_origin, modelorg);
661 clmodel = currententity->model;
662 r_pcurrentvertbase = clmodel->vertexes;
663
664 R_RecursiveWorldNode (clmodel->nodes, 15);
665
666 // if the driver wants the polygons back to front,
667 // play the visible ones back in that order
668 if (r_worldpolysbacktofront)
669 {
670 for (i = numbtofpolys-1 ; i >= 0 ; i--)
671 {
672 R_RenderPoly (btofpolys[i].psurf, btofpolys[i].clipflags);
673 }
674 }
675 }
676
677