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