1 /*
2 sw32_r_bsp.c
3
4 (description)
5
6 Copyright (C) 1996-1997 Id Software, Inc.
7
8 This program is free software; you can redistribute it and/or
9 modify it under the terms of the GNU General Public License
10 as published by the Free Software Foundation; either version 2
11 of the License, or (at your option) any later version.
12
13 This program is distributed in the hope that it will be useful,
14 but 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
20 along with this program; if not, write to:
21
22 Free Software Foundation, Inc.
23 59 Temple Place - Suite 330
24 Boston, MA 02111-1307, USA
25
26 */
27 #ifdef HAVE_CONFIG_H
28 # include "config.h"
29 #endif
30
31 #define NH_DEFINE
32 #include "namehack.h"
33
34 #include <math.h>
35 #include <stdlib.h>
36
37 #include "qfalloca.h"
38
39 #include "QF/render.h"
40 #include "QF/sys.h"
41
42 #include "r_internal.h"
43
44 // current entity info
45 qboolean sw32_insubmodel;
46 vec3_t sw32_r_worldmodelorg;
47 static float entity_rotation[3][3];
48
49 int sw32_r_currentbkey;
50
51 typedef enum { touchessolid, drawnode, nodrawnode } solidstate_t;
52
53 #define MAX_BMODEL_VERTS 500 // 6K
54 #define MAX_BMODEL_EDGES 1000 // 12K
55
56 static mvertex_t *pbverts;
57 static bedge_t *pbedges;
58 static int numbverts, numbedges;
59
60 int sw32_numbtofpolys;
61 static btofpoly_t *pbtofpolys;
62
63 static mvertex_t *pfrontenter, *pfrontexit;
64
65 static qboolean makeclippededge;
66
67
68 static void
R_EntityRotate(vec3_t vec)69 R_EntityRotate (vec3_t vec)
70 {
71 vec3_t tvec;
72
73 VectorCopy (vec, tvec);
74 vec[0] = DotProduct (entity_rotation[0], tvec);
75 vec[1] = DotProduct (entity_rotation[1], tvec);
76 vec[2] = DotProduct (entity_rotation[2], tvec);
77 }
78
79
80 void
sw32_R_RotateBmodel(void)81 sw32_R_RotateBmodel (void)
82 {
83 VectorCopy (currententity->transform + 0, entity_rotation[0]);
84 VectorCopy (currententity->transform + 4, entity_rotation[1]);
85 VectorCopy (currententity->transform + 8, entity_rotation[2]);
86
87 // rotate modelorg and the transformation matrix
88 R_EntityRotate (modelorg);
89 R_EntityRotate (vpn);
90 R_EntityRotate (vright);
91 R_EntityRotate (vup);
92
93 sw32_R_TransformFrustum ();
94 }
95
96
97 static void
R_RecursiveClipBPoly(bedge_t * pedges,mnode_t * pnode,msurface_t * psurf)98 R_RecursiveClipBPoly (bedge_t *pedges, mnode_t *pnode, msurface_t *psurf)
99 {
100 bedge_t *psideedges[2], *pnextedge, *ptedge;
101 int i, side, lastside;
102 float dist, frac, lastdist;
103 plane_t *splitplane, tplane;
104 mvertex_t *pvert, *plastvert, *ptvert;
105 mnode_t *pn;
106
107 psideedges[0] = psideedges[1] = NULL;
108
109 makeclippededge = false;
110
111 // transform the BSP plane into model space
112 // FIXME: cache these?
113 splitplane = pnode->plane;
114 tplane.dist = splitplane->dist -
115 DotProduct (r_entorigin, splitplane->normal);
116 tplane.normal[0] = DotProduct (entity_rotation[0], splitplane->normal);
117 tplane.normal[1] = DotProduct (entity_rotation[1], splitplane->normal);
118 tplane.normal[2] = DotProduct (entity_rotation[2], splitplane->normal);
119
120 // clip edges to BSP plane
121 for (; pedges; pedges = pnextedge) {
122 pnextedge = pedges->pnext;
123
124 // set the status for the last point as the previous point
125 // FIXME: cache this stuff somehow?
126 plastvert = pedges->v[0];
127 lastdist = DotProduct (plastvert->position, tplane.normal) -
128 tplane.dist;
129
130 if (lastdist > 0)
131 lastside = 0;
132 else
133 lastside = 1;
134
135 pvert = pedges->v[1];
136
137 dist = DotProduct (pvert->position, tplane.normal) - tplane.dist;
138
139 if (dist > 0)
140 side = 0;
141 else
142 side = 1;
143
144 if (side != lastside) {
145 // clipped
146 if (numbverts >= MAX_BMODEL_VERTS)
147 return;
148
149 // generate the clipped vertex
150 frac = lastdist / (lastdist - dist);
151 ptvert = &pbverts[numbverts++];
152 ptvert->position[0] = plastvert->position[0] +
153 frac * (pvert->position[0] - plastvert->position[0]);
154 ptvert->position[1] = plastvert->position[1] +
155 frac * (pvert->position[1] - plastvert->position[1]);
156 ptvert->position[2] = plastvert->position[2] +
157 frac * (pvert->position[2] - plastvert->position[2]);
158
159 // split into two edges, one on each side, and remember entering
160 // and exiting points
161 // FIXME: share the clip edge by having a winding direction flag?
162 if (numbedges >= (MAX_BMODEL_EDGES - 1)) {
163 Sys_Printf ("Out of edges for bmodel\n");
164 return;
165 }
166
167 ptedge = &pbedges[numbedges];
168 ptedge->pnext = psideedges[lastside];
169 psideedges[lastside] = ptedge;
170 ptedge->v[0] = plastvert;
171 ptedge->v[1] = ptvert;
172
173 ptedge = &pbedges[numbedges + 1];
174 ptedge->pnext = psideedges[side];
175 psideedges[side] = ptedge;
176 ptedge->v[0] = ptvert;
177 ptedge->v[1] = pvert;
178
179 numbedges += 2;
180
181 if (side == 0) {
182 // entering for front, exiting for back
183 pfrontenter = ptvert;
184 makeclippededge = true;
185 } else {
186 pfrontexit = ptvert;
187 makeclippededge = true;
188 }
189 } else {
190 // add the edge to the appropriate side
191 pedges->pnext = psideedges[side];
192 psideedges[side] = pedges;
193 }
194 }
195
196 // if anything was clipped, reconstitute and add the edges along the clip
197 // plane to both sides (but in opposite directions)
198 if (makeclippededge) {
199 if (numbedges >= (MAX_BMODEL_EDGES - 2)) {
200 Sys_Printf ("Out of edges for bmodel\n");
201 return;
202 }
203
204 ptedge = &pbedges[numbedges];
205 ptedge->pnext = psideedges[0];
206 psideedges[0] = ptedge;
207 ptedge->v[0] = pfrontexit;
208 ptedge->v[1] = pfrontenter;
209
210 ptedge = &pbedges[numbedges + 1];
211 ptedge->pnext = psideedges[1];
212 psideedges[1] = ptedge;
213 ptedge->v[0] = pfrontenter;
214 ptedge->v[1] = pfrontexit;
215
216 numbedges += 2;
217 }
218 // draw or recurse further
219 for (i = 0; i < 2; i++) {
220 if (psideedges[i]) {
221 // draw if we've reached a non-solid leaf, done if all that's left
222 // is a solid leaf, and continue down the tree if it's not a leaf
223 pn = pnode->children[i];
224
225 // we're done with this branch if the node or leaf isn't in the PVS
226 if (pn->visframe == r_visframecount) {
227 if (pn->contents < 0) {
228 if (pn->contents != CONTENTS_SOLID) {
229 sw32_r_currentbkey = ((mleaf_t *) pn)->key;
230 sw32_R_RenderBmodelFace (psideedges[i], psurf);
231 }
232 } else {
233 R_RecursiveClipBPoly (psideedges[i], pnode->children[i],
234 psurf);
235 }
236 }
237 }
238 }
239 }
240
241
242 void
sw32_R_DrawSolidClippedSubmodelPolygons(model_t * pmodel)243 sw32_R_DrawSolidClippedSubmodelPolygons (model_t *pmodel)
244 {
245 int i, j, lindex;
246 vec_t dot;
247 msurface_t *psurf;
248 int numsurfaces;
249 plane_t *pplane;
250 mvertex_t bverts[MAX_BMODEL_VERTS];
251 bedge_t bedges[MAX_BMODEL_EDGES], *pbedge;
252 medge_t *pedge, *pedges;
253
254 // FIXME: use bounding-box-based frustum clipping info?
255
256 psurf = &pmodel->surfaces[pmodel->firstmodelsurface];
257 numsurfaces = pmodel->nummodelsurfaces;
258 pedges = pmodel->edges;
259
260 for (i = 0; i < numsurfaces; i++, psurf++) {
261 // find which side of the node we are on
262 pplane = psurf->plane;
263
264 dot = DotProduct (modelorg, pplane->normal) - pplane->dist;
265
266 // draw the polygon
267 if (((psurf->flags & SURF_PLANEBACK) && (dot < -BACKFACE_EPSILON)) ||
268 (!(psurf->flags & SURF_PLANEBACK) && (dot > BACKFACE_EPSILON))) {
269 // FIXME: use bounding-box-based frustum clipping info?
270
271 // copy the edges to bedges, flipping if necessary so always
272 // clockwise winding
273 // FIXME: if edges and vertices get caches, these assignments must
274 // move outside the loop, and overflow checking must be done here
275 pbverts = bverts;
276 pbedges = bedges;
277 numbverts = numbedges = 0;
278
279 if (psurf->numedges > 0) {
280 pbedge = &bedges[numbedges];
281 numbedges += psurf->numedges;
282
283 for (j = 0; j < psurf->numedges; j++) {
284 lindex = pmodel->surfedges[psurf->firstedge + j];
285
286 if (lindex > 0) {
287 pedge = &pedges[lindex];
288 pbedge[j].v[0] = &r_pcurrentvertbase[pedge->v[0]];
289 pbedge[j].v[1] = &r_pcurrentvertbase[pedge->v[1]];
290 } else {
291 lindex = -lindex;
292 pedge = &pedges[lindex];
293 pbedge[j].v[0] = &r_pcurrentvertbase[pedge->v[1]];
294 pbedge[j].v[1] = &r_pcurrentvertbase[pedge->v[0]];
295 }
296
297 pbedge[j].pnext = &pbedge[j + 1];
298 }
299
300 pbedge[j - 1].pnext = NULL; // mark end of edges
301
302 R_RecursiveClipBPoly (pbedge, currententity->topnode, psurf);
303 } else {
304 Sys_Error ("no edges in bmodel");
305 }
306 }
307 }
308 }
309
310
311 void
sw32_R_DrawSubmodelPolygons(model_t * pmodel,int clipflags)312 sw32_R_DrawSubmodelPolygons (model_t *pmodel, int clipflags)
313 {
314 int i;
315 vec_t dot;
316 msurface_t *psurf;
317 int numsurfaces;
318 plane_t *pplane;
319
320 // FIXME: use bounding-box-based frustum clipping info?
321
322 psurf = &pmodel->surfaces[pmodel->firstmodelsurface];
323 numsurfaces = pmodel->nummodelsurfaces;
324
325 for (i = 0; i < numsurfaces; i++, psurf++) {
326 // find which side of the node we are on
327 pplane = psurf->plane;
328
329 dot = DotProduct (modelorg, pplane->normal) - pplane->dist;
330
331 // draw the polygon
332 if (((psurf->flags & SURF_PLANEBACK) && (dot < -BACKFACE_EPSILON)) ||
333 (!(psurf->flags & SURF_PLANEBACK) && (dot > BACKFACE_EPSILON))) {
334 sw32_r_currentkey = ((mleaf_t *) currententity->topnode)->key;
335
336 // FIXME: use bounding-box-based frustum clipping info?
337 sw32_R_RenderFace (psurf, clipflags);
338 }
339 }
340 }
341
342 static inline void
visit_leaf(mleaf_t * leaf)343 visit_leaf (mleaf_t *leaf)
344 {
345 // deal with model fragments in this leaf
346 if (leaf->efrags)
347 R_StoreEfrags (leaf->efrags);
348 leaf->key = sw32_r_currentkey;
349 sw32_r_currentkey++; // all bmodels in a leaf share the same key
350 }
351
352 static inline int
get_side(mnode_t * node)353 get_side (mnode_t *node)
354 {
355 // find which side of the node we are on
356 plane_t *plane = node->plane;
357
358 if (plane->type < 3)
359 return (modelorg[plane->type] - plane->dist) < 0;
360 return (DotProduct (modelorg, plane->normal) - plane->dist) < 0;
361 }
362
363 static void
visit_node(mnode_t * node,int side,int clipflags)364 visit_node (mnode_t *node, int side, int clipflags)
365 {
366 int c;
367 msurface_t *surf;
368
369 // sneaky hack for side = side ? SURF_PLANEBACK : 0;
370 side = (~side + 1) & SURF_PLANEBACK;
371 // draw stuff
372 if ((c = node->numsurfaces)) {
373 surf = r_worldentity.model->surfaces + node->firstsurface;
374 for (; c; c--, surf++) {
375 if (surf->visframe != r_visframecount)
376 continue;
377
378 // side is either 0 or SURF_PLANEBACK
379 if (side ^ (surf->flags & SURF_PLANEBACK))
380 continue; // wrong side
381
382 if (sw32_r_drawpolys) {
383 if (sw32_r_worldpolysbacktofront) {
384 if (sw32_numbtofpolys < MAX_BTOFPOLYS) {
385 pbtofpolys[sw32_numbtofpolys].clipflags = clipflags;
386 pbtofpolys[sw32_numbtofpolys].psurf = surf;
387 sw32_numbtofpolys++;
388 }
389 } else {
390 sw32_R_RenderPoly (surf, clipflags);
391 }
392 } else {
393 sw32_R_RenderFace (surf, clipflags);
394 }
395 }
396 // all surfaces on the same node share the same sequence number
397 sw32_r_currentkey++;
398 }
399 }
400
401 static inline int
test_node(mnode_t * node,int * clipflags)402 test_node (mnode_t *node, int *clipflags)
403 {
404 int i, *pindex;
405 vec3_t acceptpt, rejectpt;
406 double d;
407
408 if (node->contents < 0)
409 return 0;
410 if (node->visframe != r_visframecount)
411 return 0;
412 // cull the clipping planes if not trivial accept
413 // FIXME: the compiler is doing a lousy job of optimizing here; it could be
414 // twice as fast in ASM
415 if (*clipflags) {
416 for (i = 0; i < 4; i++) {
417 if (!(*clipflags & (1 << i)))
418 continue; // don't need to clip against it
419
420 // generate accept and reject points
421 // FIXME: do with fast look-ups or integer tests based on the
422 // sign bit of the floating point values
423
424 pindex = sw32_pfrustum_indexes[i];
425
426 rejectpt[0] = (float) node->minmaxs[pindex[0]];
427 rejectpt[1] = (float) node->minmaxs[pindex[1]];
428 rejectpt[2] = (float) node->minmaxs[pindex[2]];
429
430 d = DotProduct (rejectpt, sw32_view_clipplanes[i].normal);
431 d -= sw32_view_clipplanes[i].dist;
432
433 if (d <= 0)
434 return 0;
435
436 acceptpt[0] = (float) node->minmaxs[pindex[3 + 0]];
437 acceptpt[1] = (float) node->minmaxs[pindex[3 + 1]];
438 acceptpt[2] = (float) node->minmaxs[pindex[3 + 2]];
439
440 d = DotProduct (acceptpt, sw32_view_clipplanes[i].normal);
441 d -= sw32_view_clipplanes[i].dist;
442 if (d >= 0)
443 *clipflags &= ~(1 << i); // node is entirely on screen
444 }
445 }
446 return 1;
447 }
448
449 static void
R_VisitWorldNodes(model_t * model,int clipflags)450 R_VisitWorldNodes (model_t *model, int clipflags)
451 {
452 typedef struct {
453 mnode_t *node;
454 int side, clipflags;
455 } rstack_t;
456 rstack_t *node_ptr;
457 rstack_t *node_stack;
458 mnode_t *node;
459 mnode_t *front;
460 int side, cf;
461
462 node = model->nodes;
463 // +2 for paranoia
464 node_stack = alloca ((model->depth + 2) * sizeof (rstack_t));
465 node_ptr = node_stack;
466
467 cf = clipflags;
468 while (1) {
469 while (test_node (node, &cf)) {
470 cf = clipflags;
471 side = get_side (node);
472 front = node->children[side];
473 if (test_node (front, &cf)) {
474 node_ptr->node = node;
475 node_ptr->side = side;
476 node_ptr->clipflags = clipflags;
477 node_ptr++;
478 clipflags = cf;
479 node = front;
480 continue;
481 }
482 if (front->contents < 0 && front->contents != CONTENTS_SOLID)
483 visit_leaf ((mleaf_t *) front);
484 visit_node (node, side, clipflags);
485 node = node->children[!side];
486 }
487 if (node->contents < 0 && node->contents != CONTENTS_SOLID)
488 visit_leaf ((mleaf_t *) node);
489 if (node_ptr != node_stack) {
490 node_ptr--;
491 node = node_ptr->node;
492 side = node_ptr->side;
493 clipflags = node_ptr->clipflags;
494 visit_node (node, side, clipflags);
495 node = node->children[!side];
496 continue;
497 }
498 break;
499 }
500 if (node->contents < 0 && node->contents != CONTENTS_SOLID)
501 visit_leaf ((mleaf_t *) node);
502 }
503
504 void
sw32_R_RenderWorld(void)505 sw32_R_RenderWorld (void)
506 {
507 int i;
508 model_t *clmodel;
509 btofpoly_t btofpolys[MAX_BTOFPOLYS];
510
511 pbtofpolys = btofpolys;
512
513 currententity = &r_worldentity;
514 VectorCopy (r_origin, modelorg);
515 clmodel = currententity->model;
516 r_pcurrentvertbase = clmodel->vertexes;
517
518 R_VisitWorldNodes (clmodel, 15);
519
520 // if the driver wants the polygons back to front, play the visible ones
521 // back in that order
522 if (sw32_r_worldpolysbacktofront) {
523 for (i = sw32_numbtofpolys - 1; i >= 0; i--) {
524 sw32_R_RenderPoly (btofpolys[i].psurf, btofpolys[i].clipflags);
525 }
526 }
527 }
528