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.79 by root, Tue Nov 23 18:32:39 2004 UTC

1#include <cstdlib> 1#include <cstdlib>
2 2
3#include <vector>
4using namespace std;
5
6#include "opengl.h"
7
3#include "oct.h" 8#include "oct.h"
9#include "view.h"
4#include "entity.h" 10#include "entity.h"
5 11
6octant world(0, 0); 12enum visibility_state { FULL, PARTIAL, SMALL, OCCLUDED, SUBTREE_OCCLUDED };
7 13
8octant::octant (octant *parent, int subindex) 14struct evis {
15 entity *e;
16 visibility_state state;
17 double last; // time of last check
18
19 void clear ()
20 {
21 last = 0.;
22 state = FULL;
23 }
24
25 evis ()
26 {
27 clear ();
28 }
29};
30
31struct oct_visibility : visibility_base
32{
33 vector<evis> vismap;
34
35 visibility_state state;
36
37 evis &get_visibility (int i, entity *e)
38 {
39 evis &evs = vismap [i];
40
41 if (evs.e != e)
42 {
43 evs.clear ();
44 evs.e = e;
45 }
46
47 return evs;
48 }
49
50 oct_visibility (octant &oct)
51 : state(FULL)
52 {
53 }
54};
55
56octant world(0, sector (0, 0, 0), MAXEXTENT);
57
58octant::octant (octant *parent, const sector &orig, uoffs extent)
9: parent(parent) 59: parent(parent)
60, orig(orig)
61, extent(extent)
10{ 62{
11 for (fill = 8; fill--; ) 63 for (fill = 8; fill--; )
12 sub[fill] = 0; 64 sub[fill] = 0;
65}
13 66
14 if (parent) 67visibility_base *octant::new_visibility ()
15 { 68{
16 extent = (parent->extent + 1) >> 1; 69 return new oct_visibility (*this);
17 orig = parent->orig; 70}
18 orig.offset (subindex, extent); 71
19 } 72void octant::clear_visibility (visibility_base *vs)
20 else 73{
21 { 74 ((oct_visibility *)vs)->vismap.clear ();
22 extent = MAXEXTENT; 75 ((oct_visibility *)vs)->state = FULL;
23 orig.x = orig.y = orig.z = SOFFS_MIN; 76 ((oct_visibility *)vs)->state = OCCLUDED;//D
24 }
25} 77}
26 78
27octant::~octant () 79octant::~octant ()
28{ 80{
29 for (fill = 8; fill--; ) 81 for (fill = 8; fill--; )
30 delete sub[fill]; 82 delete sub[fill];
31} 83}
32 84
33void octant::add (const sector &sec, entity_base *e) 85static bool overlap (const sector &orig, uoffs extent, const sector &a, const sector &b)
34{ 86{
35 sector orig2; 87 sector size = (b - a + 1) >> 1;
36 sector extent2; 88 sector center = a + size;
37 89
38 orig2.x = sec.x + (soffs)e->bbox.a.x; 90 return abs (orig - center) <= extent + size;
39 orig2.y = sec.y + (soffs)e->bbox.a.y; 91}
40 orig2.z = sec.z + (soffs)e->bbox.a.z;
41 92
42 extent2.x = sec.x + (soffs)e->bbox.b.x - orig2.x; 93static sector offset (const sector &s, int subindex, uoffs extent)
43 extent2.x = sec.y + (soffs)e->bbox.b.y - orig2.y; 94{
44 extent2.x = sec.z + (soffs)e->bbox.b.z - orig2.z; 95 return sector (
96 s.x + (subindex & 1 ? extent : -extent),
97 s.y + (subindex & 2 ? extent : -extent),
98 s.z + (subindex & 4 ? extent : -extent)
99 );
100}
45 101
102void octant::add (entity *e)
103{
104 const sector &a = e->a;
105 const sector &b = e->b;
106
107 if (overlap (orig, extent, a, b))
108 {
109 uoffs extent2 = extent >> 1;
110 uoffs size = max (abs (b - a));
111
112 if (size >= extent2)
113 {
46 push_back (e); 114 push_back (e);
47 e->o.push_back (this); 115 e->o.push_back (this);
48} 116 return;
117 }
49 118
119 for (int i = 8; i--; )
120 {
121 sector s = offset (orig, i, extent2);
122
123 if (overlap (s, extent2, a, b))
124 {
125 if (!sub[i])
126 {
127 sub[i] = new octant (this, s, extent2);
128 fill++;
129 }
130
131 sub[i]->add (e);
132 }
133 }
134 }
135}
136
50void octant::remove (entity_base *e) 137void octant::remove (entity *e)
51{ 138{
52} 139}
53 140
54void octant::draw (const draw_context &ctx) 141bool octant::detect_visibility (view &ctx)
55{ 142{
56 for (iterator i = end (); i-- != begin (); ) 143 ctx.stat1++;//D
144
145 sector centeri = orig - ctx.orig;
146 point centerf = point (centeri);
147
148 GLfloat rad = ctx.diagfact * extent;
149
150 if (!overlap (ctx.frustum.c, sphere (centerf, rad)))
151 return false;
152
153 oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);
154
155 if (max (abs (centeri)) <= extent)
156 vs.state = PARTIAL;
157 else
158 {
159 if (distance (ctx.frustum.t, centerf) < -rad) return false;
160 if (distance (ctx.frustum.b, centerf) < -rad) return false;
161 if (distance (ctx.frustum.l, centerf) < -rad) return false;
162 if (distance (ctx.frustum.r, centerf) < -rad) return false;
163 if (distance (ctx.frustum.n, centerf) < -rad) return false;
164
165#if 0
166 GLfloat fd = distance (ctx.frustum.f, centerf);
167
168 if (fd < -(ctx.c_far - ctx.z_far) -rad * 3.F)
169 return false;
170#endif
171 }
172
173 // very important, optimize?
174 GLfloat z = ctx.z_near + distance (ctx.frustum.n, centerf) + rad;
175 if (ctx.perspfact * extent / z < 1.) // very crude "too small to see" check
176 return false;
177
178#if 0
179 if (vs.state == PARTIAL || vs.state == FULL)
180 ctx.nc_far = max (ctx.nc_far, z);
181#endif
182
183 if (vs.state == SUBTREE_OCCLUDED)
184 {
185 ctx.vislist.push_back (this);
186 return false;
187 }
188
189 bool visible = size () && (vs.state == PARTIAL || vs.state == FULL);
190
191 // node to start with
192 unsigned char si = centeri.x > 0 ? 1 : 0
193 | centeri.y > 0 ? 2 : 0
194 | centeri.z > 0 ? 4 : 0;
195
196 // bit-toggle to find next child for front-to-back order
197 static unsigned char toggle[8+1]
198 = { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7, 0 };
199
200 unsigned char *next = toggle;
201 do
202 {
203 si ^= *next;
204
205 if (sub[si])
206 visible = visible | sub[si]->detect_visibility (ctx);
207 }
208 while (*++next);
209
210 if (visible)
211 {
212 if (size ())
213 ctx.vislist.push_back (this);
214 }
215 else
216 vs.state = SUBTREE_OCCLUDED;
217
218 return visible;
219}
220
221void octant::draw_depth (view &ctx)
222{
223 oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);
224
225 vs.vismap.resize (size ());
226
227 if (vs.state == OCCLUDED || vs.state == SUBTREE_OCCLUDED)
228 return;
229
230 for (int i = 0; i < size (); ++i)
231 {
232 entity *e = (*this)[i];
233 const evis &evs = vs.get_visibility (i, e);
234
235 if (evs.state != OCCLUDED)
236 {
237 if (!ctx.may_draw (e))
238 continue;
239
240 sector center = ((e->a + e->b) >> 1) - ctx.orig;
241 GLfloat z = length (vec3 (center));
242 ctx.pixfact = ctx.perspfact / z;
243
244 ctx.nz_far = max (ctx.nz_far, z + extent);
245 ctx.nz_near = min (ctx.nz_near, z - extent);
246
57 (*i)->draw (ctx); 247 e->draw (ctx);
248 }
249 }
58} 250}
59 251
252void octant::draw_postdepth (view &ctx)
253{
254 oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);
255
256 if (vs.state == OCCLUDED || vs.state == SUBTREE_OCCLUDED)
257 {
258 ctx.begin_occ_query (*this, 0);
259 sector s = orig - ctx.orig;
260 gl::draw_bbox (s - extent, s + extent);
261 ctx.end_occ_query ();
262 }
263 else
264 {
265 int nvis = 0;
266
267 for (int i = 0; i < size (); ++i)
268 {
269 entity *e = (*this)[i];
270 const evis &evs = vs.get_visibility (i, e);
271
272 if (evs.state == OCCLUDED)
273 {
274 if (!ctx.may_draw (e))
275 continue;
276
277 ctx.begin_occ_query (*this, e);
278 gl::draw_bbox (e->a - ctx.orig, e->b - ctx.orig);
279 ctx.end_occ_query ();
280 }
281 else
282 nvis++;
283 }
284
285 if (nvis == 0 && size ())
286 vs.state = OCCLUDED;
287 }
288}
289
290void octant::draw_lighted (view &ctx)
291{
292 oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);
293
294 if (vs.state == OCCLUDED || vs.state == SUBTREE_OCCLUDED)
295 return;
296
297 for (int i = 0; i < size (); ++i)
298 {
299 entity *e = (*this)[i];
300 evis &evs = vs.get_visibility (i, e);
301
302 if (evs.state != OCCLUDED)
303 {
304 if (!ctx.may_draw (e))
305 continue;
306
307 sector center = ((e->a + e->b) >> 1) - ctx.orig;
308 GLfloat z = length (vec3 (center));
309 ctx.pixfact = ctx.perspfact / z;
310
311 if (ctx.pass->type != LIGHTED
312 || !ctx.first_lighted
313 || evs.last + 0.1 > timer.now)
314 e->draw (ctx);
315 else
316 {
317 evs.last = timer.now;
318 ctx.begin_occ_query (*this, e);
319 e->draw (ctx);
320 ctx.end_occ_query ();
321 }
322 }
323 }
324}
325
326void octant::event (occ_query &ev)
327{
328 oct_visibility &vs = *(oct_visibility *)get_visibility (ev.ctx);
329 entity *e = (entity *)ev.id;
330
331 if (e)
332 {
333 for (vector<evis>::iterator i = vs.vismap.begin ();
334 i != vs.vismap.end ();
335 ++i)
336 if (i->e == e)
337 {
338 i->state = ev.count ? FULL : OCCLUDED;
339 return;
340 }
341 }
342 else
343 vs.state = ev.count ? FULL : OCCLUDED;
344}
345
346

Diff Legend

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