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