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