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.95 by root, Thu Aug 11 20:42:19 2005 UTC

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

Diff Legend

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