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

Comparing libgender/oct.C (file contents):
Revision 1.47 by root, Sun Oct 10 02:40:18 2004 UTC vs.
Revision 1.87 by root, Thu Jan 6 03:09:24 2005 UTC

1#include <cstdlib> 1#include <cstdlib>
2 2
3#include <vector> 3#include <vector>
4
5using namespace std; 4using namespace std;
6 5
7#include <GL/gl.h> 6#include "opengl.h"
8 7
9#include "oct.h" 8#include "oct.h"
10#include "view.h" 9#include "view.h"
11#include "entity.h" 10#include "entity.h"
12 11
13octant world(0, sector (SOFFS_MIN, SOFFS_MIN, SOFFS_MIN), MAXEXTENT); 12enum visibility_state { FULL, PARTIAL, OCCLUDED };
13
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);
14 57
15octant::octant (octant *parent, const sector &orig, uoffs extent) 58octant::octant (octant *parent, const sector &orig, uoffs extent)
16: parent(parent), orig(orig), extent(extent) 59: parent(parent)
60, orig(orig)
61, extent(extent)
17{ 62{
18 for (fill = 8; fill--; ) 63 for (fill = 8; fill--; )
19 sub[fill] = 0; 64 sub[fill] = 0;
20} 65}
21 66
67visibility_base *octant::new_visibility ()
68{
69 return new oct_visibility (*this);
70}
71
72void octant::clear_visibility (visibility_base *vs)
73{
74 ((oct_visibility *)vs)->vismap.clear ();
75 ((oct_visibility *)vs)->state = FULL;
76}
77
22octant::~octant () 78octant::~octant ()
23{ 79{
24 for (fill = 8; fill--; ) 80 for (fill = 8; fill--; )
25 delete sub[fill]; 81 delete sub[fill];
26} 82}
27 83
28static 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)
29{ 85{
30 ea /= 2;
31
32 sector center_1 = o1 + ea;
33 sector size_2 = b - a; 86 sector size = (b - a + 1) >> 1;
34 sector center_2 = a + size_2 / 2; 87 sector center = a + size;
35 88
36 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 );
37} 99}
38 100
39void octant::add (entity *e) 101void octant::add (entity *e)
40{ 102{
41 const sector &a = e->a; 103 const sector &a = e->a;
42 const sector &b = e->b; 104 const sector &b = e->b;
43 105
106 uoffs size = max (abs (b - a));
107
108 if (size >= extent >> 4)
109 {
44 if (overlap (orig, extent, a, b)) 110 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 { 111 {
51 push_back (e); 112 push_back (e);
52 e->o.push_back (this); 113 e->o.push_back (this);
53 return;
54 } 114 }
115 }
116 else
117 {
118 uoffs extent2 = extent >> 1;
55 119
56 for (int i = 8; i--; ) 120 for (int i = 8; i--; )
57 { 121 {
58 sector s = orig;
59 s.offset (i, extent2); 122 sector s = offset (orig, i, extent2);
60 123
61 if (overlap (s, extent2, a, b)) 124 if (overlap (s, extent2, a, b))
62 { 125 {
63 if (!sub[i]) 126 if (!sub[i])
127 {
64 sub[i] = new octant (this, s, extent2); 128 sub[i] = new octant (this, s, extent2);
129 fill++;
130 }
65 131
66 sub[i]->add (e); 132 sub[i]->add (e);
67 } 133 }
68 } 134 }
69 } 135 }
71 137
72void octant::remove (entity *e) 138void octant::remove (entity *e)
73{ 139{
74} 140}
75 141
76void octant::detect_visibility (view &ctx) 142bool octant::detect_visibility (view &ctx) //, bool fully_visible)
77{ 143{
78 visibility_state &vs = ctx.vismap[this]; 144 ctx.stat1++;//D
79 145
80 GLfloat extent2 = 0.5F * (GLfloat)extent; 146 sector centeri = orig - ctx.orig;
81 point center = point (orig + (extent >> 1) - ctx.orig); 147 point centerf = point (centeri);
82 if (extent & 1) center = center + 0.5F; 148
83 GLfloat rad = ctx.diagfact * extent2; 149 GLfloat rad = ctx.diagfact * extent;
84 150
85 if (vs.generation + 1 != ctx.generation) 151 if (!overlap (ctx.frustum.c, sphere (centerf, rad)))
86 vs.visibility = visibility_state::UNKNOWN; 152 return false;
87 153
88 vs.generation = ctx.generation; 154 oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);
89 155
90 if (orig <= ctx.orig && ctx.orig <= orig + extent) 156 //vs.state = FULL;//D
91 vs.visibility = visibility_state::PARTIAL; 157
158#if 0
159 if (max (abs (centeri)) <= extent)
160 ;
92 else 161 else
93 { 162 {
94 if (ctx.frustum.t.distance (center) < -rad) return; 163#endif
95 if (ctx.frustum.b.distance (center) < -rad) return;
96 if (ctx.frustum.l.distance (center) < -rad) return;
97 if (ctx.frustum.r.distance (center) < -rad) return;
98 if (ctx.frustum.n.distance (center) < -rad) return;
99 164
165 //if (distance (ctx.frustum.t, centerf) < -rad) return false;
166 //if (distance (ctx.frustum.b, centerf) < -rad) return false;
167 //if (distance (ctx.frustum.l, centerf) < -rad) return false;
168 //if (distance (ctx.frustum.r, centerf) < -rad) return false;
169 ////if (distance (ctx.frustum.n, centerf) < -rad) return false;
170
171#if 0
100 GLfloat fd = ctx.frustum.f.distance (center); 172 GLfloat fd = distance (ctx.frustum.f, centerf);
101 173
102 if (fd < -(ctx.c_far - ctx.z_far) -rad * 3.F) 174 if (fd < -(ctx.c_far - ctx.z_far) -rad * 3.F)
103 return; 175 return false;
104 }
105
106 if (vs.visibility == visibility_state::OCCLUDED
107 || vs.visibility == visibility_state::UNKNOWN)
108 {
109 ctx.farlist.push_back (this);
110 return;
111 }
112
113#if 0
114 if (vs.visibility == visibility_state::UNKNOWN)
115 vs.visibility = visibility_state::FULL;
116#endif 176#endif
117 177
118 GLfloat z = ctx.z_near + ctx.frustum.n.distance (center) + rad; 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
181 return false;
119 182
120 if (vs.visibility == visibility_state::FULL) 183#if 0
184 if (vs.state == PARTIAL || vs.state == FULL)
121 ctx.nc_far = max (ctx.nc_far, z); 185 ctx.nc_far = max (ctx.nc_far, z);
186#endif
122 187
123 if (size () 188 if (vs.state == OCCLUDED)
124 && (vs.visibility == visibility_state::PARTIAL
125 || vs.visibility == visibility_state::FULL))
126 { 189 {
127 ctx.nz_far = max (ctx.nz_far, z); 190#if 0
191 if (extent < ctx.z_far)
192 {
193#endif
128 ctx.vislist.push_back (this); 194 ctx.postdepthlist.push_back (this);
195 return false;
196#if 0
197 }
198 else
199 vs.state == PARTIAL;
200#endif
129 } 201 }
202
203 bool visible = size () && vs.state == FULL;
130 204
131 // node to start with 205 // node to start with
132 unsigned char si = ctx.d.x < 0 ? 1 : 0 206 unsigned char si = centeri.x > 0 ? 1 : 0
133 | ctx.d.y < 0 ? 2 : 0 207 | centeri.y > 0 ? 2 : 0
134 | ctx.d.z < 0 ? 4 : 0; 208 | centeri.z > 0 ? 4 : 0;
135 209
136 // bit-toggle to find next child for front-to-back order 210 // bit-toggle to find next child for front-to-back order
137 static unsigned char next[8] 211 static unsigned char toggle[8+1]
138 = { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7 }; 212 = { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7, 0 };
139 213
140 for (int i = 0; i < 8; i++) 214 unsigned char *next = toggle;
215 do
141 { 216 {
142 si ^= next[i]; 217 si ^= *next;
143 218
144 if (sub[si]) 219 if (sub[si])
145 sub[si]->detect_visibility (ctx); 220 visible = visible | sub[si]->detect_visibility (ctx);
221 }
222 while (*++next);
223
224 if (visible)
225 {
226 if (size ())
227 ctx.vislist.push_back (this);
228
229 ctx.postdepthlist.push_back (this);
230 }
231 else
232 {
233 //vs.state = OCCLUDED;
234 ctx.postdepthlist.push_back (this);
235 }
236
237 return visible;
238}
239
240void octant::draw_depth (view &ctx)
241{
242 oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);
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
254 if (evs.state != OCCLUDED)
255 {
256 if (!ctx.may_draw (e))
257 continue;
258
259 sector center = ((e->a + e->b) >> 1) - ctx.orig;
260 GLfloat z = length (vec3 (center));
261 ctx.pixfact = ctx.perspfact / z;
262
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)
292 {
293 if (!ctx.may_draw (e))
294 continue;
295
296 ctx.begin_occ_query (*this, e);
297 gl::draw_bbox (e->a - ctx.orig, e->b - ctx.orig);
298 ctx.end_occ_query ();
299 }
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
146 } 321 }
147} 322#endif
148 323
149void octant::display (view &ctx) 324 if (vs.state == PARTIAL || vs.state == OCCLUDED)
150{ 325 return;
326
151#if 0 327#if 0
152 glBegin (GL_LINES); 328 {
329 static vertex_buffer vb;
330 static index_buffer ib;
331
153 sector s = orig - ctx.orig; 332 sector s = orig - ctx.orig;
154 vec3 clr(0, 0.8, 0); 333 sector a = s - extent, b = s + extent;
155 glMaterialfv (GL_FRONT_AND_BACK, GL_DIFFUSE, (const GLfloat*)&clr);
156 334
157 for (int i = 8; i--; ) 335 vertex_v3f vd[] = {
158 for (int ji = 3; ji--; ) 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)
159 { 347 {
160 int j = i | (1 << ji); 348 static GLushort verts[4*6] = {
161 if (i != j) 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
387 {
388 evs.last = timer.now;
389 ctx.begin_occ_query (*this, e);
390 e->draw (ctx);
391 ctx.end_occ_query ();
392 }
393 }
394 }
395}
396
397void octant::event (occ_query &ev)
398{
399 oct_visibility &vs = *(oct_visibility *)get_visibility (ev.ctx);
400 entity *e = (entity *)ev.id;
401
402 if (e)
403 {
404 for (vector<evis>::iterator i = vs.vismap.begin ();
405 i != vs.vismap.end ();
406 ++i)
407 if (i->e == e)
162 { 408 {
163 glVertex3i (s.x + !!(i & 1) * extent, 409 i->state = ev.count ? FULL : OCCLUDED;
164 s.y + !!(i & 2) * extent, 410 return;
165 s.z + !!(i & 4) * extent);
166 glVertex3i (s.x + !!(j & 1) * extent,
167 s.y + !!(j & 2) * extent,
168 s.z + !!(j & 4) * extent);
169 } 411 }
170 } 412 }
171 413 else
172 glEnd (); 414 vs.state = ev.count ? (vs.state == PARTIAL ? PARTIAL : FULL) : OCCLUDED;
173#endif
174
175 for (iterator i = end (); i != begin (); )
176 (*--i)->display (ctx);
177} 415}
178 416
179void octant::draw_bbox (view &ctx)
180{
181 sector s = orig - ctx.orig;
182 417
183 gl::draw_box (ctx, s, s + extent);
184}
185
186void octant::event (occ_query &ev)
187{
188 visibility_state &vs = ev.v.vismap[this];
189
190 vs.last = timer.now;
191 vs.visibility = ev.r <= 0
192 ? visibility_state::OCCLUDED
193 : visibility_state::FULL;
194 //if (extent > 0x16)
195 //printf ("OCT(%x,%x,%x+%x) samples %d\n", orig.x, orig.y, orig.z, extent, ev.r);
196}
197

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines