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

Comparing libgender/oct.C (file contents):
Revision 1.60 by root, Mon Oct 18 12:24:29 2004 UTC vs.
Revision 1.87 by root, Thu Jan 6 03:09:24 2005 UTC

… …
7 7
8#include "oct.h" 8#include "oct.h"
9#include "view.h" 9#include "view.h"
10#include "entity.h" 10#include "entity.h"
11 11
12enum visibility_state { FULL, PARTIAL, SMALL, OCCLUDED }; 12enum visibility_state { FULL, PARTIAL, OCCLUDED };
13 13
14struct evis { 14struct evis {
15 entity *e;
15 visibility_state state; 16 visibility_state state;
16 double last; // time of last check 17 double last; // time of last check
17 evis () : last(0.), state(FULL) { }; 18
19 void clear ()
20 {
21 last = 0.;
22 state = FULL;
23 }
24
25 evis ()
26 {
27 clear ();
28 }
18}; 29};
19 30
20struct oct_visibility : visibility_base 31struct oct_visibility : visibility_base
21{ 32{
22 typedef map<entity *, evis> evismap; 33 vector<evis> vismap;
23 evismap vismap;
24 34
25 visibility_state state; 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 }
26 49
27 oct_visibility (octant &oct) 50 oct_visibility (octant &oct)
28 : state(FULL) 51 : state(FULL)
29 { 52 {
30 } 53 }
31}; 54};
32 55
33octant world(0, sector (SOFFS_MIN, SOFFS_MIN, SOFFS_MIN), MAXEXTENT); 56octant world(0, sector (0, 0, 0), MAXEXTENT);
34 57
35octant::octant (octant *parent, const sector &orig, uoffs extent) 58octant::octant (octant *parent, const sector &orig, uoffs extent)
36: parent(parent) 59: parent(parent)
37, orig(orig) 60, orig(orig)
38, extent(extent) 61, extent(extent)
… …
47} 70}
48 71
49void octant::clear_visibility (visibility_base *vs) 72void octant::clear_visibility (visibility_base *vs)
50{ 73{
51 ((oct_visibility *)vs)->vismap.clear (); 74 ((oct_visibility *)vs)->vismap.clear ();
75 ((oct_visibility *)vs)->state = FULL;
52} 76}
77
53octant::~octant () 78octant::~octant ()
54{ 79{
55 for (fill = 8; fill--; ) 80 for (fill = 8; fill--; )
56 delete sub[fill]; 81 delete sub[fill];
57} 82}
58 83
59static bool overlap (const sector &o1, uoffs ea, const sector &a, const sector &b) 84static bool overlap (const sector &orig, uoffs extent, const sector &a, const sector &b)
60{ 85{
61 ea /= 2; 86 sector size = (b - a + 1) >> 1;
62
63 sector center_1 = o1 + ea; 87 sector center = a + size;
64 sector size_2 = b - a;
65 sector center_2 = a + (size_2 >> 1);
66 88
67 return abs (center_1 - center_2) <= ea + size_2; 89 return abs (orig - center) <= extent + size;
90}
91
92static sector offset (const sector &s, int subindex, uoffs extent)
93{
94 return sector (
95 s.x + (subindex & 1 ? extent : -extent),
96 s.y + (subindex & 2 ? extent : -extent),
97 s.z + (subindex & 4 ? extent : -extent)
98 );
68} 99}
69 100
70void octant::add (entity *e) 101void octant::add (entity *e)
71{ 102{
72 const sector &a = e->a; 103 const sector &a = e->a;
73 const sector &b = e->b; 104 const sector &b = e->b;
74 105
106 uoffs size = max (abs (b - a));
107
108 if (size >= extent >> 4)
109 {
75 if (overlap (orig, extent, a, b)) 110 if (overlap (orig, extent, a, b))
76 {
77 uoffs extent2 = extent >> 1;
78 uoffs size = max (abs (b - a));
79
80 if (size >= extent2 >> 1)
81 { 111 {
82 push_back (e); 112 push_back (e);
83 e->o.push_back (this); 113 e->o.push_back (this);
84 return;
85 } 114 }
115 }
116 else
117 {
118 uoffs extent2 = extent >> 1;
86 119
87 for (int i = 8; i--; ) 120 for (int i = 8; i--; )
88 { 121 {
89 sector s = orig;
90 s.offset (i, extent2); 122 sector s = offset (orig, i, extent2);
91 123
92 if (overlap (s, extent2, a, b)) 124 if (overlap (s, extent2, a, b))
93 { 125 {
94 if (!sub[i]) 126 if (!sub[i])
95 { 127 {
… …
105 137
106void octant::remove (entity *e) 138void octant::remove (entity *e)
107{ 139{
108} 140}
109 141
110bool octant::depth_pass (view &ctx) 142bool octant::detect_visibility (view &ctx) //, bool fully_visible)
111{ 143{
112 oct_visibility &vs = *(oct_visibility *)get_visibility (ctx); 144 ctx.stat1++;//D
113 145
114 GLfloat extent2 = 0.5F * (GLfloat)extent;
115 sector centeri = orig + (extent >> 1) - ctx.orig; 146 sector centeri = orig - ctx.orig;
116 point centerf = point (centeri) + ((extent & 1) ? 0.5F : 0.F); 147 point centerf = point (centeri);
117 148
118 GLfloat rad = ctx.diagfact * extent2; 149 GLfloat rad = ctx.diagfact * extent;
119 150
120 if (!overlap (ctx.frustum.c, sphere (centerf, rad))) 151 if (!overlap (ctx.frustum.c, sphere (centerf, rad)))
121 return false; 152 return false;
122 153
123 if (orig <= ctx.orig && ctx.orig <= orig + extent) 154 oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);
124 vs.state = PARTIAL; 155
156 //vs.state = FULL;//D
157
158#if 0
159 if (max (abs (centeri)) <= extent)
160 ;
125 else 161 else
126 { 162 {
163#endif
164
127 if (distance (ctx.frustum.t, centerf) < -rad) return false; 165 //if (distance (ctx.frustum.t, centerf) < -rad) return false;
128 if (distance (ctx.frustum.b, centerf) < -rad) return false; 166 //if (distance (ctx.frustum.b, centerf) < -rad) return false;
129 if (distance (ctx.frustum.l, centerf) < -rad) return false; 167 //if (distance (ctx.frustum.l, centerf) < -rad) return false;
130 if (distance (ctx.frustum.r, centerf) < -rad) return false; 168 //if (distance (ctx.frustum.r, centerf) < -rad) return false;
131 if (distance (ctx.frustum.n, centerf) < -rad) return false; 169 ////if (distance (ctx.frustum.n, centerf) < -rad) return false;
132 170
133#if 0 171#if 0
134 GLfloat fd = distance (ctx.frustum.f, centerf); 172 GLfloat fd = distance (ctx.frustum.f, centerf);
135 173
136 if (fd < -(ctx.c_far - ctx.z_far) -rad * 3.F) 174 if (fd < -(ctx.c_far - ctx.z_far) -rad * 3.F)
137 return false; 175 return false;
138#endif 176#endif
139 }
140 177
141 if (vs.state == OCCLUDED) 178 // very important, optimize?
179 GLfloat z = length (ctx.p - centerf) + rad;
180 if (z < 0.F || ctx.perspfact * extent / z < 10.) // very crude "too small to see" check
142 return false; 181 return false;
143
144 GLfloat z = ctx.z_near + distance (ctx.frustum.n, centerf) + rad;
145 if (ctx.perspfact * extent / z < 1.) // very crude "too small to see" check
146 return false;
147 //printf ("z %f, perspfact %f, z*p %f\n", z, ctx.perspfact, ctx.perspfact / z);
148 182
149#if 0 183#if 0
150 if (vs.state == PARTIAL || vs.state == FULL) 184 if (vs.state == PARTIAL || vs.state == FULL)
151 ctx.nc_far = max (ctx.nc_far, z); 185 ctx.nc_far = max (ctx.nc_far, z);
152#endif 186#endif
187
188 if (vs.state == OCCLUDED)
189 {
190#if 0
191 if (extent < ctx.z_far)
192 {
193#endif
194 ctx.postdepthlist.push_back (this);
195 return false;
196#if 0
197 }
198 else
199 vs.state == PARTIAL;
200#endif
201 }
202
203 bool visible = size () && vs.state == FULL;
153 204
154 // node to start with 205 // node to start with
155 unsigned char si = centeri.x > 0 ? 1 : 0 206 unsigned char si = centeri.x > 0 ? 1 : 0
156 | centeri.y > 0 ? 2 : 0 207 | centeri.y > 0 ? 2 : 0
157 | centeri.z > 0 ? 4 : 0; 208 | centeri.z > 0 ? 4 : 0;
158 209
159 //printf ("si %d C %Ld,%Ld,%Ld\n", si, centeri.x, centeri.y, centeri.z);
160
161 // bit-toggle to find next child for front-to-back order 210 // bit-toggle to find next child for front-to-back order
162 static unsigned char toggle[8+1] 211 static unsigned char toggle[8+1]
163 = { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7, 0 }; 212 = { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7, 0 };
164 213
165 unsigned char *next = toggle; 214 unsigned char *next = toggle;
166 do 215 do
167 { 216 {
168 si ^= *next; 217 si ^= *next;
169 218
170 if (sub[si]) 219 if (sub[si])
171 sub[si]->depth_pass (ctx); 220 visible = visible | sub[si]->detect_visibility (ctx);
172 } 221 }
173 while (*++next); 222 while (*++next);
174 223
224 if (visible)
225 {
175 if (size () 226 if (size ())
176 && (vs.state == PARTIAL || vs.state == FULL))
177 {
178 display (ctx);
179 ctx.vislist.push_back (this); 227 ctx.vislist.push_back (this);
180 }
181 228
182 return true; 229 ctx.postdepthlist.push_back (this);
183}
184
185void octant::display (view &ctx)
186{
187#if 0
188 sector s = orig - ctx.orig;
189
190 glBegin (GL_LINES);
191 vec3 clr(0, 0.8, 0);
192 glMaterialfv (GL_FRONT_AND_BACK, GL_DIFFUSE, (const GLfloat*)&clr);
193
194 for (int i = 8; i--; )
195 for (int ji = 3; ji--; )
196 {
197 int j = i | (1 << ji);
198 if (i < j)
199 {
200 glVertex3i (s.x + !!(i & 1) * extent,
201 s.y + !!(i & 2) * extent,
202 s.z + !!(i & 4) * extent);
203 glVertex3i (s.x + !!(j & 1) * extent,
204 s.y + !!(j & 2) * extent,
205 s.z + !!(j & 4) * extent);
206 }
207 } 230 }
208 231 else
209 glEnd (); 232 {
210#endif 233 //vs.state = OCCLUDED;
234 ctx.postdepthlist.push_back (this);
235 }
236
237 return visible;
238}
239
240void octant::draw_depth (view &ctx)
241{
211 oct_visibility &vs = *(oct_visibility *)get_visibility (ctx); 242 oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);
212 243
244 vs.vismap.resize (size ());
245
246 if (vs.state == PARTIAL || vs.state == OCCLUDED)
247 return;
248
249 for (int i = 0; i < size (); ++i)
250 {
251 entity *e = (*this)[i];
252 const evis &evs = vs.get_visibility (i, e);
253
213 if (vs.state == OCCLUDED) 254 if (evs.state != OCCLUDED)
214 {
215 abort ();
216 if (ctx.pass == view::POSTDEPTH)
217 {
218 ctx.begin_occ_query (*this, 0);
219 sector s = orig - ctx.orig;
220 gl::draw_bbox (vb_bbox, s, s + extent);
221 ctx.end_occ_query ();
222 } 255 {
223 }
224 else
225 {
226 for (iterator i = begin (); i != end (); )
227 {
228 entity *e = *i++;
229
230 if (!ctx.may_draw (e)) 256 if (!ctx.may_draw (e))
231 continue; 257 continue;
232 258
233 evis &evs = vs.vismap[e]; 259 sector center = ((e->a + e->b) >> 1) - ctx.orig;
260 GLfloat z = length (vec3 (center));
261 ctx.pixfact = ctx.perspfact / z;
234 262
235 if (ctx.pass == view::POSTDEPTH) 263 ctx.nz_far = max (ctx.nz_far, z + extent);
264 ctx.nz_near = min (ctx.nz_near, z - extent);
265
266 e->draw (ctx);
267 }
268 }
269}
270
271void octant::draw_postdepth (view &ctx)
272{
273 oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);
274
275 if (vs.state == PARTIAL || vs.state == OCCLUDED)
276 {
277 ctx.begin_occ_query (*this, 0);
278 sector s = orig - ctx.orig;
279 gl::draw_bbox (s - extent, s + extent);
280 ctx.end_occ_query ();
281 }
282 else
283 {
284 int nvis = 0;
285
286 for (int i = 0; i < size (); ++i)
287 {
288 entity *e = (*this)[i];
289 const evis &evs = vs.get_visibility (i, e);
290
291 if (evs.state == OCCLUDED)
236 { 292 {
237 if (evs.state == OCCLUDED) 293 if (!ctx.may_draw (e))
238 { 294 continue;
295
239 ctx.begin_occ_query (*this, e); 296 ctx.begin_occ_query (*this, e);
240 gl::draw_bbox (vb_bbox, e->a - ctx.orig, e->b - ctx.orig); 297 gl::draw_bbox (e->a - ctx.orig, e->b - ctx.orig);
241 ctx.end_occ_query (); 298 ctx.end_occ_query ();
242 }
243 } 299 }
244 else 300 else
301 nvis++;
302 }
303
304#if 0
305 if (nvis == 0 && size ())
306 vs.state = PARTIAL;
307#endif
308 }
309}
310
311void octant::draw_lighted (view &ctx)
312{
313 oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);
314
315#if 0
316 if (vs.state == PARTIAL || vs.state == OCCLUDED)
317 {
318 sector s = orig - ctx.orig;
319 gl::draw_bbox (s - extent, s + extent);
320 printf ("DLP %p\n", this);//D
321 }
322#endif
323
324 if (vs.state == PARTIAL || vs.state == OCCLUDED)
325 return;
326
327#if 0
328 {
329 static vertex_buffer vb;
330 static index_buffer ib;
331
332 sector s = orig - ctx.orig;
333 sector a = s - extent, b = s + extent;
334
335 vertex_v3f vd[] = {
336 point (a.x, a.y, a.z),
337 point (b.x, a.y, a.z),
338 point (a.x, b.y, a.z),
339 point (b.x, b.y, a.z),
340 point (a.x, a.y, b.z),
341 point (b.x, a.y, b.z),
342 point (a.x, b.y, b.z),
343 point (b.x, b.y, b.z),
344 };
345
346 if (!ib)
347 {
348 static GLushort verts[4*6] = {
349 0, 4, 6, 2, // -x
350 1, 3, 7, 5, // +x
351 0, 1, 5, 4, // -y
352 7, 3, 2, 6, // +y
353 0, 2, 3, 1, // -z
354 4, 5, 7, 6, // +z
355 };
356
357 ib.set (verts, 4*6, GL_STATIC_DRAW_ARB);
358 }
359
360 vb.set (vd, 8, GL_STREAM_DRAW_ARB);
361 vb.bind ();
362 for (int i = 0; i < 6; i++)
363 ib.draw (GL_LINE_LOOP, i*4, 4);
364
365 }
366#endif
367
368 for (int i = 0; i < size (); ++i)
369 {
370 entity *e = (*this)[i];
371 evis &evs = vs.get_visibility (i, e);
372
373 if (evs.state != OCCLUDED)
374 {
375 if (!ctx.may_draw (e))
376 continue;
377
378 sector center = ((e->a + e->b) >> 1) - ctx.orig;
379 GLfloat z = length (vec3 (center));
380 ctx.pixfact = ctx.perspfact / z;
381
382 if (ctx.pass->type != LIGHTED
383 || !ctx.first_lighted
384 || evs.last + 1. > timer.now)
385 e->draw (ctx);
386 else
245 { 387 {
246 if (evs.state != OCCLUDED)
247 {
248 sector center = ((e->a + e->b) >> 1) - ctx.orig;
249 GLfloat z = length (vec3 (center));
250 ctx.pixfact = ctx.perspfact / z;
251
252 ctx.nz_far = max (ctx.nz_far, z + extent);
253 ctx.nz_near = min (ctx.nz_near, z - extent);
254
255 if (ctx.pass == view::DEPTH || evs.last + 1. > timer.now)
256 e->draw (ctx);
257 else
258 {
259 evs.last = timer.now; 388 evs.last = timer.now;
260 ctx.begin_occ_query (*this, e); 389 ctx.begin_occ_query (*this, e);
261 e->draw (ctx); 390 e->draw (ctx);
262 ctx.end_occ_query (); 391 ctx.end_occ_query ();
263 }
264 }
265 } 392 }
266 } 393 }
267 } 394 }
268} 395}
269
270#if 0
271void octant::draw_bbox (view &ctx)
272{
273 sector s = orig - ctx.orig;
274
275 gl::draw_bbox (ctx, s, s + extent);
276}
277#endif
278 396
279void octant::event (occ_query &ev) 397void octant::event (occ_query &ev)
280{ 398{
281 oct_visibility &vs = *(oct_visibility *)get_visibility (ev.ctx); 399 oct_visibility &vs = *(oct_visibility *)get_visibility (ev.ctx);
282 entity *e = (entity *)ev.id; 400 entity *e = (entity *)ev.id;
283 401
284 if (e) 402 if (e)
285 { 403 {
286 evis &evs = vs.vismap[e]; 404 for (vector<evis>::iterator i = vs.vismap.begin ();
405 i != vs.vismap.end ();
406 ++i)
407 if (i->e == e)
408 {
287 evs.state = ev.count ? FULL : OCCLUDED; 409 i->state = ev.count ? FULL : OCCLUDED;
410 return;
411 }
288 } 412 }
289 else 413 else
290 { 414 vs.state = ev.count ? (vs.state == PARTIAL ? PARTIAL : FULL) : OCCLUDED;
291 //vs.state = ev.count ? FULL : OCCLUDED;
292 }
293
294#if 0
295 visibility_state &vs = ev.v.vismap[this];
296
297 vs.last = timer.now;
298 vs.state = ev.r <= 0
299 ? visibility_state::OCCLUDED
300 : visibility_state::FULL;
301#endif
302} 415}
303 416
304 417

Diff Legend

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