5
each portal will have a list of all possible to see from first portal
7
if (!thread->portalmightsee[portalnum])
11
for p2 = all other portals in leaf
13
for all portals that might be seen by p2
14
mark as unseen if not present in seperating plane
15
flood fill a new mightsee
16
save as passagemightsee
19
void CalcMightSee (leaf_t *leaf,
22
int CountBits (byte *bits, int numbits)
28
for (i=0 ; i<numbits ; i++)
29
if (bits[i>>3] & (1<<(i&7)) )
36
int c_portalskip, c_leafskip;
37
int c_vistest, c_mighttest;
43
void CheckStack (leaf_t *leaf, threaddata_t *thread)
47
for (p=thread->pstack_head.next ; p ; p=p->next)
51
Error ("CheckStack: leaf recursion");
52
for (p2=thread->pstack_head.next ; p2 != p ; p2=p2->next)
53
if (p2->leaf == p->leaf)
54
Error ("CheckStack: late leaf recursion");
60
winding_t *AllocStackWinding (pstack_t *stack)
66
if (stack->freewindings[i])
68
stack->freewindings[i] = 0;
69
return &stack->windings[i];
73
Error ("AllocStackWinding: failed");
78
void FreeStackWinding (winding_t *w, pstack_t *stack)
82
i = w - stack->windings;
85
return; // not from local
87
if (stack->freewindings[i])
88
Error ("FreeStackWinding: allready free");
89
stack->freewindings[i] = 1;
98
winding_t *ChopWinding (winding_t *in, pstack_t *stack, plane_t *split)
109
counts[0] = counts[1] = counts[2] = 0;
111
// determine sides for each point
112
for (i=0 ; i<in->numpoints ; i++)
114
dot = DotProduct (in->points[i], split->normal);
117
if (dot > ON_EPSILON)
118
sides[i] = SIDE_FRONT;
119
else if (dot < -ON_EPSILON)
120
sides[i] = SIDE_BACK;
129
return in; // completely on front side
133
FreeStackWinding (in, stack);
140
neww = AllocStackWinding (stack);
144
for (i=0 ; i<in->numpoints ; i++)
148
if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
150
FreeStackWinding (neww, stack);
151
return in; // can't chop -- fall back to original
154
if (sides[i] == SIDE_ON)
156
VectorCopy (p1, neww->points[neww->numpoints]);
161
if (sides[i] == SIDE_FRONT)
163
VectorCopy (p1, neww->points[neww->numpoints]);
167
if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
170
if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
172
FreeStackWinding (neww, stack);
173
return in; // can't chop -- fall back to original
176
// generate a split point
177
p2 = in->points[(i+1)%in->numpoints];
179
dot = dists[i] / (dists[i]-dists[i+1]);
180
for (j=0 ; j<3 ; j++)
181
{ // avoid round off error when possible
182
if (split->normal[j] == 1)
183
mid[j] = split->dist;
184
else if (split->normal[j] == -1)
185
mid[j] = -split->dist;
187
mid[j] = p1[j] + dot*(p2[j]-p1[j]);
190
VectorCopy (mid, neww->points[neww->numpoints]);
194
// free the original winding
195
FreeStackWinding (in, stack);
205
Source, pass, and target are an ordering of portals.
207
Generates seperating planes canidates by taking two points from source and one
208
point from pass, and clips target by them.
210
If target is totally clipped away, that portal can not be seen through.
212
Normal clip keeps target on the same side as pass, which is correct if the
213
order goes source, pass, target. If the order goes pass, source, target then
214
flipclip should be set.
217
winding_t *ClipToSeperators (winding_t *source, winding_t *pass, winding_t *target, qboolean flipclip, pstack_t *stack)
227
// check all combinations
228
for (i=0 ; i<source->numpoints ; i++)
230
l = (i+1)%source->numpoints;
231
VectorSubtract (source->points[l] , source->points[i], v1);
233
// fing a vertex of pass that makes a plane that puts all of the
234
// vertexes of pass on the front side and all of the vertexes of
235
// source on the back side
236
for (j=0 ; j<pass->numpoints ; j++)
238
VectorSubtract (pass->points[j], source->points[i], v2);
240
plane.normal[0] = v1[1]*v2[2] - v1[2]*v2[1];
241
plane.normal[1] = v1[2]*v2[0] - v1[0]*v2[2];
242
plane.normal[2] = v1[0]*v2[1] - v1[1]*v2[0];
244
// if points don't make a valid plane, skip it
246
length = plane.normal[0] * plane.normal[0]
247
+ plane.normal[1] * plane.normal[1]
248
+ plane.normal[2] * plane.normal[2];
250
if (length < ON_EPSILON)
253
length = 1/sqrt(length);
255
plane.normal[0] *= length;
256
plane.normal[1] *= length;
257
plane.normal[2] *= length;
259
plane.dist = DotProduct (pass->points[j], plane.normal);
262
// find out which side of the generated seperating plane has the
267
for (k=0 ; k<source->numpoints ; k++)
269
if (k == i || k == l)
271
d = DotProduct (source->points[k], plane.normal) - plane.dist;
273
{ // source is on the negative side, so we want all
274
// pass and target on the positive side
278
else if (d > ON_EPSILON)
279
{ // source is on the positive side, so we want all
280
// pass and target on the negative side
285
if (k == source->numpoints)
286
continue; // planar with source portal
291
// flip the normal if the source portal is backwards
295
VectorSubtract (vec3_origin, plane.normal, plane.normal);
296
plane.dist = -plane.dist;
300
// if all of the pass portal points are now on the positive side,
301
// this is the seperating plane
303
counts[0] = counts[1] = counts[2] = 0;
304
for (k=0 ; k<pass->numpoints ; k++)
308
d = DotProduct (pass->points[k], plane.normal) - plane.dist;
311
else if (d > ON_EPSILON)
316
if (k != pass->numpoints)
317
continue; // points on negative side, not a seperating plane
320
continue; // planar with seperating plane
322
k = (j+1)%pass->numpoints;
323
d = DotProduct (pass->points[k], plane.normal) - plane.dist;
326
k = (j+pass->numpoints-1)%pass->numpoints;
327
d = DotProduct (pass->points[k], plane.normal) - plane.dist;
332
// flip the normal if we want the back side
336
VectorSubtract (vec3_origin, plane.normal, plane.normal);
337
plane.dist = -plane.dist;
341
// clip target by the seperating plane
343
target = ChopWinding (target, stack, &plane);
345
return NULL; // target is not visible
358
Flood fill through the leafs
359
If src_portal is NULL, this is the originating leaf
362
void RecursiveLeafFlow (int leafnum, threaddata_t *thread, pstack_t *prevstack)
369
long *test, *might, *vis, more;
374
leaf = &leafs[leafnum];
375
// CheckStack (leaf, thread);
377
prevstack->next = &stack;
383
might = (long *)stack.mightsee;
384
vis = (long *)thread->base->portalvis;
386
// check all portals for flowing into other leafs
387
for (i=0 ; i<leaf->numportals ; i++)
389
p = leaf->portals[i];
392
if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) )
394
continue; // can't possibly see it
397
// if the portal can't see anything we haven't allready seen, skip it
398
if (p->status == stat_done)
400
test = (long *)p->portalvis;
404
test = (long *)p->portalflood;
408
for (j=0 ; j<portallongs ; j++)
410
might[j] = ((long *)prevstack->mightsee)[j] & test[j];
411
more |= (might[j] & ~vis[j]);
415
(thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) )
416
{ // can't see anything new
420
// get plane of portal, point normal into the neighbor leaf
421
stack.portalplane = p->plane;
422
VectorSubtract (vec3_origin, p->plane.normal, backplane.normal);
423
backplane.dist = -p->plane.dist;
429
stack.freewindings[0] = 1;
430
stack.freewindings[1] = 1;
431
stack.freewindings[2] = 1;
437
d = DotProduct (p->origin, thread->pstack_head.portalplane.normal);
438
d -= thread->pstack_head.portalplane.dist;
443
else if (d > p->radius)
445
stack.pass = p->winding;
449
stack.pass = ChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
455
stack.pass = ChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
465
d = DotProduct (thread->base->origin, p->plane.normal);
467
if (d > thread->base->radius)
468
// if (d > p->radius)
472
// else if (d < -p->radius)
473
else if (d < -thread->base->radius)
475
stack.source = prevstack->source;
479
stack.source = ChopWinding (prevstack->source, &stack, &backplane);
485
stack.source = ChopWinding (prevstack->source, &stack, &backplane);
490
if (!prevstack->pass)
491
{ // the second leaf can only be blocked if coplanar
493
// mark the portal as visible
494
thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
496
RecursiveLeafFlow (p->leaf, thread, &stack);
500
stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, false, &stack);
504
stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, true, &stack);
508
// mark the portal as visible
509
thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
511
// flow through it for real
512
RecursiveLeafFlow (p->leaf, thread, &stack);
521
generates the portalvis bit vector
524
void PortalFlow (int portalnum)
531
p = sorted_portals[portalnum];
532
p->status = stat_working;
534
c_might = CountBits (p->portalflood, numportals*2);
536
memset (&data, 0, sizeof(data));
539
data.pstack_head.portal = p;
540
data.pstack_head.source = p->winding;
541
data.pstack_head.portalplane = p->plane;
542
for (i=0 ; i<portallongs ; i++)
543
((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];
544
RecursiveLeafFlow (p->leaf, &data, &data.pstack_head);
546
p->status = stat_done;
548
c_can = CountBits (p->portalvis, numportals*2);
550
qprintf ("portal:%4i mightsee:%4i cansee:%4i (%i chains)\n",
551
(int)(p - portals), c_might, c_can, data.c_chains);
556
===============================================================================
558
This is a rough first-order aproximation that is used to trivially reject some
559
of the final calculations.
562
Calculates portalfront and portalflood bit vectors
566
typedef struct passage_s
568
struct passage_s *next;
570
stryct sep_s *seperators;
574
typedef struct portal_s
576
struct passage_s *passages;
577
int leaf; // leaf portal faces into
585
calc portal visibility
591
for a portal to be visible to a passage, it must be on the front of
592
all seperating planes, and both portals must be behind the mew portal
594
===============================================================================
599
char test_leaf[MAX_MAP_LEAFS];
610
void SimpleFlood (portal_t *srcportal, int leafnum)
617
if(cullerror && !test_leaf[leafnum])
620
test_leaf[leafnum] = 0;
622
leaf = &leafs[leafnum];
624
for (i=0 ; i<leaf->numportals ; i++)
626
p = leaf->portals[i];
630
if ( ! (srcportal->portalfront[pnum>>3] & (1<<(pnum&7)) ) )
633
if (srcportal->portalflood[pnum>>3] & (1<<(pnum&7)) )
636
srcportal->portalflood[pnum>>3] |= (1<<(pnum&7));
638
SimpleFlood (srcportal, p->leaf);
646
void BasePortalVis (int portalnum)
652
vec3_t prenormal, normal;
653
float p_dot, tp_dot, p_rad, tp_rad;
655
p = portals+portalnum;
657
p->portalfront = malloc (portalbytes);
658
memset (p->portalfront, 0, portalbytes);
660
p->portalflood = malloc (portalbytes);
661
memset (p->portalflood, 0, portalbytes);
663
p->portalvis = malloc (portalbytes);
664
memset (p->portalvis, 0, portalbytes);
666
memset(test_leaf, 0, MAX_MAP_LEAFS);
668
for (j=0, tp = portals ; j<numportals*2 ; j++, tp++)
672
else if(cullerror && tp->leaf == p->owner_leaf)
675
test_leaf[tp->leaf] = 1;
679
for (k=0 ; k<w->numpoints ; k++)
681
d = DotProduct (w->points[k], p->plane.normal)
686
if (k == w->numpoints)
687
continue; // no points on front
690
for (k=0 ; k<w->numpoints ; k++)
692
d = DotProduct (w->points[k], tp->plane.normal)
698
if (k == w->numpoints)
699
continue; // no points on front (or in range if maxdist set)
703
// This approximation will consider 2 circles in 3d space with the centeer and radius of the
704
// polygons on the planes of the polygons.
706
prenormal[0] = p->origin[0] - tp->origin[0];
707
prenormal[1] = p->origin[1] - tp->origin[1];
708
prenormal[2] = p->origin[2] - tp->origin[2];
710
d = VectorNormalize(prenormal, normal);
712
p_dot = DotProduct(p->plane.normal, normal);
715
p_rad = -p_dot * p->radius;
717
p_rad = p_dot * p->radius;
719
tp_dot = DotProduct(tp->plane.normal, normal);
722
tp_rad = -tp_dot * tp->radius;
724
tp_rad = tp_dot * tp->radius;
726
if(d > (maxdist + tp_rad + p_rad))
730
p->portalfront[j>>3] |= (1<<(j&7));
733
SimpleFlood (p, p->leaf);
735
p->nummightsee = CountBits (p->portalflood, numportals*2);
736
// printf ("portal %i: %i mightsee\n", portalnum, p->nummightsee);
737
c_flood += p->nummightsee;
745
===============================================================================
747
This is a second order aproximation
749
Calculates portalvis bit vector
753
===============================================================================
762
void RecursiveLeafBitFlow (int leafnum, byte *mightsee, byte *cansee)
769
byte newmight[MAX_PORTALS/8];
771
leaf = &leafs[leafnum];
773
// check all portals for flowing into other leafs
774
for (i=0 ; i<leaf->numportals ; i++)
776
p = leaf->portals[i];
779
// if some previous portal can't see it, skip
780
if (! (mightsee[pnum>>3] & (1<<(pnum&7)) ) )
783
// if this portal can see some portals we mightsee, recurse
785
for (j=0 ; j<portallongs ; j++)
787
((long *)newmight)[j] = ((long *)mightsee)[j]
788
& ((long *)p->portalflood)[j];
789
more |= ((long *)newmight)[j] & ~((long *)cansee)[j];
793
continue; // can't see anything new
795
cansee[pnum>>3] |= (1<<(pnum&7));
797
RecursiveLeafBitFlow (p->leaf, newmight, cansee);
806
void BetterPortalVis (int portalnum)
810
p = portals+portalnum;
812
RecursiveLeafBitFlow (p->leaf, p->portalflood, p->portalvis);
814
// build leaf vis information
815
p->nummightsee = CountBits (p->portalvis, numportals*2);
816
c_vis += p->nummightsee;
added
removed
source/utils3/bsp/qvis3/flow.c
