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

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

Diff Legend

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