ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/libgender/oct.C
Revision: 1.81
Committed: Fri Nov 26 03:48:40 2004 UTC (19 years, 6 months ago) by root
Content type: text/plain
Branch: MAIN
Changes since 1.80: +14 -5 lines
Log Message:
*** empty log message ***

File Contents

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