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.65 by root, Sat Oct 23 02:27:51 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 };
7 13
8octant::octant (octant *parent, int subindex) 14struct evis {
15 visibility_state state;
16 double last; // time of last check
17 evis () : last(0.), state(FULL) { };
18};
19
20struct oct_visibility : visibility_base
21{
22 typedef map<entity *, evis> evismap;
23 evismap vismap;
24
25 visibility_state state;
26
27 oct_visibility (octant &oct)
28 : state(FULL)
29 {
30 }
31};
32
33octant world(0, sector (SOFFS_MIN, SOFFS_MIN, SOFFS_MIN), MAXEXTENT);
34
35octant::octant (octant *parent, const sector &orig, uoffs extent)
9: parent(parent) 36: parent(parent)
37, orig(orig)
38, extent(extent)
10{ 39{
11 for (fill = 8; fill--; ) 40 for (fill = 8; fill--; )
12 sub[fill] = 0; 41 sub[fill] = 0;
42}
13 43
14 if (parent) 44visibility_base *octant::new_visibility ()
15 { 45{
16 extent = (parent->extent + 1) >> 1; 46 return new oct_visibility (*this);
17 orig = parent->orig; 47}
18 orig.offset (subindex, extent); 48
19 } 49void octant::clear_visibility (visibility_base *vs)
20 else 50{
21 { 51 ((oct_visibility *)vs)->vismap.clear ();
22 extent = MAXEXTENT;
23 orig.x = orig.y = orig.z = SOFFS_MIN;
24 }
25} 52}
26 53
27octant::~octant () 54octant::~octant ()
28{ 55{
29 for (fill = 8; fill--; ) 56 for (fill = 8; fill--; )
30 delete sub[fill]; 57 delete sub[fill];
31} 58}
32 59
33void octant::add (const sector &sec, entity_base *e) 60static bool overlap (const sector &o1, uoffs ea, const sector &a, const sector &b)
34{ 61{
35 sector orig2; 62 ea /= 2;
36 sector extent2;
37 63
38 orig2.x = sec.x + (soffs)e->bbox.a.x; 64 sector center_1 = o1 + ea;
39 orig2.y = sec.y + (soffs)e->bbox.a.y; 65 sector size_2 = b - a;
40 orig2.z = sec.z + (soffs)e->bbox.a.z; 66 sector center_2 = a + (size_2 >> 1);
41 67
42 extent2.x = sec.x + (soffs)e->bbox.b.x - orig2.x; 68 return abs (center_1 - center_2) <= ea + size_2;
43 extent2.x = sec.y + (soffs)e->bbox.b.y - orig2.y; 69}
44 extent2.x = sec.z + (soffs)e->bbox.b.z - orig2.z;
45 70
71void octant::add (entity *e)
72{
73 const sector &a = e->a;
74 const sector &b = e->b;
75
76 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 {
46 push_back (e); 83 push_back (e);
47 e->o.push_back (this); 84 e->o.push_back (this);
48} 85 return;
86 }
49 87
88 for (int i = 8; i--; )
89 {
90 sector s = orig;
91 s.offset (i, extent2);
92
93 if (overlap (s, extent2, a, b))
94 {
95 if (!sub[i])
96 {
97 sub[i] = new octant (this, s, extent2);
98 fill++;
99 }
100
101 sub[i]->add (e);
102 }
103 }
104 }
105}
106
50void octant::remove (entity_base *e) 107void octant::remove (entity *e)
51{ 108{
52} 109}
53 110
54void octant::draw (const draw_context &ctx) 111bool octant::detect_visibility (view &ctx)
55{ 112{
56 for (iterator i = end (); i-- != begin (); ) 113 GLfloat extent2 = 0.5F * (GLfloat)extent;
57 (*i)->draw (ctx); 114 sector centeri = orig + (extent >> 1) - ctx.orig;
58} 115 point centerf = point (centeri) + ((extent & 1) ? 0.5F : 0.F);
59 116
117 GLfloat rad = ctx.diagfact * extent2;
118
119 if (!overlap (ctx.frustum.c, sphere (centerf, rad)))
120 return false;
121
122 oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);
123
124 if (orig <= ctx.orig && ctx.orig <= orig + extent)
125 vs.state = PARTIAL;
126 else
127 {
128 if (distance (ctx.frustum.t, centerf) < -rad) return false;
129 if (distance (ctx.frustum.b, centerf) < -rad) return false;
130 if (distance (ctx.frustum.l, centerf) < -rad) return false;
131 if (distance (ctx.frustum.r, centerf) < -rad) return false;
132 if (distance (ctx.frustum.n, centerf) < -rad) return false;
133
134#if 0
135 GLfloat fd = distance (ctx.frustum.f, centerf);
136
137 if (fd < -(ctx.c_far - ctx.z_far) -rad * 3.F)
138 return false;
139#endif
140 }
141
142 if (vs.state == OCCLUDED)
143 {
144 if (size ())
145 ctx.vislist.push_back (this);
146 return false;
147 }
148
149 GLfloat z = ctx.z_near + distance (ctx.frustum.n, centerf) + rad;
150 if (ctx.perspfact * extent / z < 1.) // very crude "too small to see" check
151 return false;
152 //printf ("z %f, perspfact %f, z*p %f\n", z, ctx.perspfact, ctx.perspfact / z);
153
154#if 0
155 if (vs.state == PARTIAL || vs.state == FULL)
156 ctx.nc_far = max (ctx.nc_far, z);
157#endif
158
159 // node to start with
160 unsigned char si = centeri.x > 0 ? 1 : 0
161 | centeri.y > 0 ? 2 : 0
162 | centeri.z > 0 ? 4 : 0;
163
164 //printf ("si %d C %Ld,%Ld,%Ld\n", si, centeri.x, centeri.y, centeri.z);
165
166 // bit-toggle to find next child for front-to-back order
167 static unsigned char toggle[8+1]
168 = { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7, 0 };
169
170 unsigned char *next = toggle;
171 do
172 {
173 si ^= *next;
174
175 if (sub[si])
176 sub[si]->detect_visibility (ctx);
177 }
178 while (*++next);
179
180 if (size ()
181 && (vs.state == PARTIAL || vs.state == FULL))
182 ctx.vislist.push_back (this);
183
184 return true;
185}
186
187void octant::display (view &ctx)
188{
189#if 0
190 sector s = orig - ctx.orig;
191
192 glBegin (GL_LINES);
193 vec3 clr(0, 0.8, 0);
194 glMaterialfv (GL_FRONT_AND_BACK, GL_DIFFUSE, (const GLfloat*)&clr);
195
196 for (int i = 8; i--; )
197 for (int ji = 3; ji--; )
198 {
199 int j = i | (1 << ji);
200 if (i < j)
201 {
202 glVertex3i (s.x + !!(i & 1) * extent,
203 s.y + !!(i & 2) * extent,
204 s.z + !!(i & 4) * extent);
205 glVertex3i (s.x + !!(j & 1) * extent,
206 s.y + !!(j & 2) * extent,
207 s.z + !!(j & 4) * extent);
208 }
209 }
210
211 glEnd ();
212#endif
213 oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);
214
215 if (vs.state == OCCLUDED)
216 {
217 if (ctx.pass == view::POSTDEPTH)
218 {
219 ctx.begin_occ_query (*this, 0);
220 sector s = orig - ctx.orig;
221 gl::draw_bbox (s, s + extent);
222 printf ("bbox %Ld,%ld,%Ld\n", s.x, s.y, s.z);
223 ctx.end_occ_query ();
224 }
225 }
226 else
227 {
228 int nvis = 0;
229
230 for (iterator i = begin (); i != end (); )
231 {
232 entity *e = *i++;
233
234 if (!ctx.may_draw (e))
235 continue;
236
237 evis &evs = vs.vismap[e];
238
239 if (ctx.pass == view::POSTDEPTH)
240 {
241 if (evs.state == OCCLUDED)
242 {
243 ctx.begin_occ_query (*this, e);
244 gl::draw_bbox (e->a - ctx.orig, e->b - ctx.orig);
245 ctx.end_occ_query ();
246 }
247 else
248 nvis++;
249 }
250 else
251 {
252 if (evs.state != OCCLUDED)
253 {
254 sector center = ((e->a + e->b) >> 1) - ctx.orig;
255 GLfloat z = length (vec3 (center));
256 ctx.pixfact = ctx.perspfact / z;
257
258 ctx.nz_far = max (ctx.nz_far, z + extent);
259 ctx.nz_near = min (ctx.nz_near, z - extent);
260
261 if (ctx.pass == view::DEPTH || evs.last + 0.3 > timer.now)
262 e->draw (ctx);
263 else
264 {
265 evs.last = timer.now;
266 ctx.begin_occ_query (*this, e);
267 e->draw (ctx);
268 ctx.end_occ_query ();
269 }
270 }
271 }
272 }
273
274#if 0
275 if (ctx.pass == view::POSTDEPTH && nvis == 0 && size ())
276 vs.state = OCCLUDED;
277#endif
278 }
279}
280
281void octant::event (occ_query &ev)
282{
283 oct_visibility &vs = *(oct_visibility *)get_visibility (ev.ctx);
284 entity *e = (entity *)ev.id;
285
286 if (e)
287 {
288 evis &evs = vs.vismap[e];
289 evs.state = ev.count ? FULL : OCCLUDED;
290 }
291 else
292 vs.state = ev.count ? FULL : OCCLUDED;
293}
294
295

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines