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

Comparing libgender/oct.C (file contents):
Revision 1.67 by root, Thu Oct 28 22:29:29 2004 UTC vs.
Revision 1.89 by root, Mon Jul 18 01:40:01 2005 UTC

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

Diff Legend

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