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