ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/libgender/oct.C
(Generate patch)

Comparing libgender/oct.C (file contents):
Revision 1.3 by root, Sun Oct 3 03:51:51 2004 UTC vs.
Revision 1.39 by root, Sat Oct 9 16:37:31 2004 UTC

1#include <cstdlib> 1#include <cstdlib>
2 2
3#include <vector>
4
5using namespace std;
6
7#include <GL/gl.h>
8
3#include "oct.h" 9#include "oct.h"
10#include "view.h"
4#include "entity.h" 11#include "entity.h"
5 12
6octant world(0, 0); 13octant world(0, sector (SOFFS_MIN, SOFFS_MIN, SOFFS_MIN), MAXEXTENT);
7 14
8octant::octant (octant *parent, int subindex) 15octant::octant (octant *parent, const sector &orig, uoffs extent)
9: parent(parent) 16: parent(parent), orig(orig), extent(extent)
10{ 17{
11 for (fill = 8; fill--; ) 18 for (fill = 8; fill--; )
12 sub[fill] = 0; 19 sub[fill] = 0;
13
14 if (parent)
15 {
16 extent = (parent->extent + 1) >> 1;
17 orig = parent->orig;
18 orig.offset (subindex, extent);
19 }
20 else
21 {
22 extent = MAXEXTENT;
23 orig.x = orig.y = orig.z = SOFFS_MIN;
24 }
25} 20}
26 21
27octant::~octant () 22octant::~octant ()
28{ 23{
29 for (fill = 8; fill--; ) 24 for (fill = 8; fill--; )
30 delete sub[fill]; 25 delete sub[fill];
31} 26}
32 27
33void octant::add (const sector &sec, entity_base *e) 28static bool overlap (const sector &o1, uoffs ea, const sector &a, const sector &b)
34{ 29{
35 sector orig2; 30 ea /= 2;
36 sector extent2;
37 31
38 orig2.x = sec.x + (soffs)e->bbox.a.x; 32 sector center_1 = o1 + ea;
39 orig2.y = sec.y + (soffs)e->bbox.a.y; 33 sector size_2 = b - a;
40 orig2.z = sec.z + (soffs)e->bbox.a.z; 34 sector center_2 = a + size_2 / 2;
41 35
42 extent2.x = sec.x + (soffs)e->bbox.b.x - orig2.x; 36 return abs (center_1 - center_2) <= ea + size_2;
43 extent2.x = sec.y + (soffs)e->bbox.b.y - orig2.y;
44 extent2.x = sec.z + (soffs)e->bbox.b.z - orig2.z;
45
46 push_back (e);
47 e->o.push_back (this);
48} 37}
49 38
39void octant::add (entity *e)
40{
41 const sector &a = e->a;
42 const sector &b = e->b;
43
44 if (overlap (orig, extent, a, b))
45 {
46 uoffs extent2 = extent / 2;
47 uoffs size = max (abs (b - a));
48
49 if (size > extent2 || !extent2)
50 {
51 push_back (e);
52 e->o.push_back (this);
53 return;
54 }
55
56 for (int i = 8; i--; )
57 {
58 sector s = orig;
59 s.offset (i, extent2);
60
61 if (overlap (s, extent2, a, b))
62 {
63 if (!sub[i])
64 sub[i] = new octant (this, s, extent2);
65
66 sub[i]->add (e);
67 }
68 }
69 }
70}
71
50void octant::remove (entity_base *e) 72void octant::remove (entity *e)
51{ 73{
52} 74}
53 75
54void octant::draw (const draw_context &ctx) 76void octant::detect_visibility (view &ctx)
55{ 77{
56 for (iterator i = end (); i-- != begin (); ) 78 visibility_state &vs = ctx.vismap[this];
57 (*i)->draw (ctx); 79
80 if (vs.generation != ctx.generation)
81 vs.visibility = visibility_state::UNKNOWN;
82
83 if (orig <= ctx.orig && ctx.orig <= orig + extent)
84 {
85 vs.visibility = visibility_state::PARTIAL;
86 vs.generation = ctx.generation;
87 }
88 else
89 {
90 GLfloat extent2 = 0.5F * (GLfloat)extent;
91 point center = point (orig) + extent2 - point (ctx.orig);
92
93 GLfloat rad = ctx.diagfact * extent2;
94
95 if (ctx.frustum.t.distance (center) < -rad) return;
96 if (ctx.frustum.b.distance (center) < -rad) return;
97 if (ctx.frustum.l.distance (center) < -rad) return;
98 if (ctx.frustum.r.distance (center) < -rad) return;
99 if (ctx.frustum.n.distance (center) < -rad) return;
100
101 GLfloat fd = ctx.frustum.f.distance (center);
102
103 if (fd < -rad)
104 {
105 if (fd < -rad * 3.F)
106 return;
107
108 ctx.farlist.push_back (this);
109 return;
110 }
111 }
112
113 if (vs.visibility == visibility_state::UNKNOWN)
114 vs.visibility = visibility_state::FULL;
115
116 if (size ())
117 ctx.vislist.push_back (this);
118
119 // node to start with
120 unsigned char si = ctx.d.x < 0 ? 1 : 0
121 | ctx.d.y < 0 ? 2 : 0
122 | ctx.d.z < 0 ? 4 : 0;
123
124 // bit-toggle to find next child for front-to-back order
125 static unsigned char next[8]
126 = { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7 };
127
128 for (int i = 0; i < 8; i++)
129 {
130 si ^= next[i];
131
132 if (sub[si])
133 sub[si]->detect_visibility (ctx);
134 }
135
136 vs.generation = ctx.generation;
58} 137}
59 138
139void octant::display (view &ctx)
140{
141#if 0
142 glBegin (GL_LINES);
143 sector s = orig - ctx.orig;
144 vec3 clr(0, 0.8, 0);
145 glMaterialfv (GL_FRONT_AND_BACK, GL_DIFFUSE, (const GLfloat*)&clr);
146
147 for (int i = 8; i--; )
148 for (int ji = 3; ji--; )
149 {
150 int j = i | (1 << ji);
151 if (i != j)
152 {
153 glVertex3i (s.x + !!(i & 1) * extent,
154 s.y + !!(i & 2) * extent,
155 s.z + !!(i & 4) * extent);
156 glVertex3i (s.x + !!(j & 1) * extent,
157 s.y + !!(j & 2) * extent,
158 s.z + !!(j & 4) * extent);
159 }
160 }
161
162 glEnd ();
163#endif
164
165 for (iterator i = end (); i != begin (); )
166 (*--i)->display (ctx);
167}
168
169void octant::draw_bbox (view &ctx)
170{
171 sector s = orig - ctx.orig;
172
173 gl::draw_box (ctx, s, s + extent);
174}
175
176void octant::event (occ_query &ev)
177{
178 if (ev.r <= 5)
179 return;
180
181 //ev.v.vismap[this].visibility = visibility_state::FULL;
182 ev.v.far = ev.v.near + ev.v.frustum.n.distance (orig);
183 printf ("OCT(%x,%x,%x+%x) samples %d\n", orig.x, orig.y, orig.z, extent, ev.r);
184}
185

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines