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

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

Diff Legend

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