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

Comparing libgender/oct.C (file contents):
Revision 1.71 by root, Sun Nov 7 02:28:18 2004 UTC vs.
Revision 1.76 by root, Tue Nov 9 22:33:18 2004 UTC

… …
7 7
8#include "oct.h" 8#include "oct.h"
9#include "view.h" 9#include "view.h"
10#include "entity.h" 10#include "entity.h"
11 11
12enum visibility_state { FULL, PARTIAL, SMALL, OCCLUDED }; 12enum visibility_state { FULL, PARTIAL, SMALL, OCCLUDED, SUBTREE_OCCLUDED };
13 13
14struct evis { 14struct evis {
15 visibility_state state; 15 visibility_state state;
16 double last; // time of last check 16 double last; // time of last check
17 evis () : last(0.), state(FULL) { }; 17 evis () : last(0.), state(FULL) { };
… …
28 : state(FULL) 28 : state(FULL)
29 { 29 {
30 } 30 }
31}; 31};
32 32
33octant world(0, sector (SOFFS_MIN, SOFFS_MIN, SOFFS_MIN), MAXEXTENT); 33octant world(0, sector (0, 0, 0), MAXEXTENT);
34 34
35octant::octant (octant *parent, const sector &orig, uoffs extent) 35octant::octant (octant *parent, const sector &orig, uoffs extent)
36: parent(parent) 36: parent(parent)
37, orig(orig) 37, orig(orig)
38, extent(extent) 38, extent(extent)
… …
47} 47}
48 48
49void octant::clear_visibility (visibility_base *vs) 49void octant::clear_visibility (visibility_base *vs)
50{ 50{
51 ((oct_visibility *)vs)->vismap.clear (); 51 ((oct_visibility *)vs)->vismap.clear ();
52 ((oct_visibility *)vs)->state = FULL;
52} 53}
53 54
54octant::~octant () 55octant::~octant ()
55{ 56{
56 for (fill = 8; fill--; ) 57 for (fill = 8; fill--; )
57 delete sub[fill]; 58 delete sub[fill];
58} 59}
59 60
60static bool overlap (const sector &o1, uoffs ea, const sector &a, const sector &b) 61static bool overlap (const sector &orig, uoffs extent, const sector &a, const sector &b)
61{ 62{
62 ea /= 2; 63 sector size = (b - a + 1) >> 1;
63
64 sector center_1 = o1 + ea; 64 sector center = a + size;
65 sector size_2 = b - a;
66 sector center_2 = a + (size_2 >> 1);
67 65
68 return abs (center_1 - center_2) <= ea + size_2; 66 return abs (orig - center) <= extent + size;
67}
68
69static sector offset (const sector &s, int subindex, uoffs extent)
70{
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 );
69} 76}
70 77
71void octant::add (entity *e) 78void octant::add (entity *e)
72{ 79{
73 const sector &a = e->a; 80 const sector &a = e->a;
… …
76 if (overlap (orig, extent, a, b)) 83 if (overlap (orig, extent, a, b))
77 { 84 {
78 uoffs extent2 = extent >> 1; 85 uoffs extent2 = extent >> 1;
79 uoffs size = max (abs (b - a)); 86 uoffs size = max (abs (b - a));
80 87
81 if (size >= extent2 >> 1) 88 if (size >= extent2)
82 { 89 {
83 push_back (e); 90 push_back (e);
84 e->o.push_back (this); 91 e->o.push_back (this);
85 return; 92 return;
86 } 93 }
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 {
… …
108{ 114{
109} 115}
110 116
111bool octant::detect_visibility (view &ctx) 117bool octant::detect_visibility (view &ctx)
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 (abs (centeri)) <= extent)
125 vs.state = PARTIAL; 130 vs.state = PARTIAL;
126 else 131 else
127 { 132 {
128 if (distance (ctx.frustum.t, centerf) < -rad) return false; 133 if (distance (ctx.frustum.t, centerf) < -rad) return false;
129 if (distance (ctx.frustum.b, centerf) < -rad) return false; 134 if (distance (ctx.frustum.b, centerf) < -rad) return false;
… …
137 if (fd < -(ctx.c_far - ctx.z_far) -rad * 3.F) 142 if (fd < -(ctx.c_far - ctx.z_far) -rad * 3.F)
138 return false; 143 return false;
139#endif 144#endif
140 } 145 }
141 146
142#if 0 147 // very important, optimize?
143 if (vs.state == OCCLUDED && size ())
144 {
145 if (size ())
146 ctx.vislist.push_back (this);
147 return false;
148 }
149#endif
150
151 GLfloat z = ctx.z_near + distance (ctx.frustum.n, centerf) + rad; 148 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 149 if (ctx.perspfact * extent / z < 1.) // very crude "too small to see" check
153 return false; 150 return false;
154 //printf ("z %f, perspfact %f, z*p %f\n", z, ctx.perspfact, ctx.perspfact / z);
155 151
156#if 0 152#if 0
157 if (vs.state == PARTIAL || vs.state == FULL) 153 if (vs.state == PARTIAL || vs.state == FULL)
158 ctx.nc_far = max (ctx.nc_far, z); 154 ctx.nc_far = max (ctx.nc_far, z);
159#endif 155#endif
160 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
161 // node to start with 165 // node to start with
162 unsigned char si = centeri.x > 0 ? 1 : 0 166 unsigned char si = centeri.x > 0 ? 1 : 0
163 | centeri.y > 0 ? 2 : 0 167 | centeri.y > 0 ? 2 : 0
164 | centeri.z > 0 ? 4 : 0; 168 | centeri.z > 0 ? 4 : 0;
165 169
166 // bit-toggle to find next child for front-to-back order 170 // bit-toggle to find next child for front-to-back order
167 static unsigned char toggle[8+1] 171 static unsigned char toggle[8+1]
168 = { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7, 0 }; 172 = { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7, 0 };
169 173
170 bool visible = vs.state == PARTIAL || vs.state == FULL;
171
172 unsigned char *next = toggle; 174 unsigned char *next = toggle;
173 do 175 do
174 { 176 {
175 si ^= *next; 177 si ^= *next;
176 178
… …
184 if (size ()) 186 if (size ())
185 ctx.vislist.push_back (this); 187 ctx.vislist.push_back (this);
186 } 188 }
187 else 189 else
188 { 190 {
189 vs.state = OCCLUDED; 191 vs.state = SUBTREE_OCCLUDED;
190 ctx.vislist.push_back (this); 192 ctx.vislist.push_back (this);
191 } 193 }
192 194
193 return visible; 195 return visible;
194} 196}
195 197
196void octant::display (view &ctx) 198void octant::draw_depth (view &ctx)
197{ 199{
198 oct_visibility &vs = *(oct_visibility *)get_visibility (ctx); 200 oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);
199 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
200 if (vs.state == OCCLUDED) 211 if (evs.state != OCCLUDED)
201 { 212 {
202 if (ctx.pass_type == view::POSTDEPTH) 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);
203 { 224 }
225 }
226}
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 {
204 ctx.begin_occ_query (*this, 0); 234 ctx.begin_occ_query (*this, 0);
205 sector s = orig - ctx.orig; 235 sector s = orig - ctx.orig;
206 gl::draw_bbox (s, s + extent); 236 gl::draw_bbox (s - extent, s + extent);
207 ctx.end_occ_query (); 237 ctx.end_occ_query ();
208 }
209 } 238 }
210 else 239 else
211 { 240 {
212 int nvis = 0; 241 int nvis = 0;
213 242
… …
215 { 244 {
216 entity *e = *i++; 245 entity *e = *i++;
217 246
218 evis &evs = vs.vismap[e]; 247 evis &evs = vs.vismap[e];
219 248
220 if (ctx.pass_type == view::POSTDEPTH) 249 if (evs.state == OCCLUDED)
221 { 250 {
222 if (evs.state == OCCLUDED) 251 if (!ctx.may_draw (e))
223 { 252 continue;
253
224 ctx.begin_occ_query (*this, e); 254 ctx.begin_occ_query (*this, e);
225 gl::draw_bbox (e->a - ctx.orig, e->b - ctx.orig); 255 gl::draw_bbox (e->a - ctx.orig, e->b - ctx.orig);
226 ctx.end_occ_query (); 256 ctx.end_occ_query ();
227 }
228 else
229 nvis++;
230 } 257 }
231 else 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)
232 { 281 {
233 if (!ctx.may_draw (e)) 282 if (!ctx.may_draw (e))
234 continue; 283 continue;
235 284
236
237 if (evs.state != OCCLUDED)
238 {
239 sector center = ((e->a + e->b) >> 1) - ctx.orig; 285 sector center = ((e->a + e->b) >> 1) - ctx.orig;
240 GLfloat z = length (vec3 (center)); 286 GLfloat z = length (vec3 (center));
241 ctx.pixfact = ctx.perspfact / z; 287 ctx.pixfact = ctx.perspfact / z;
242 288
243 ctx.nz_far = max (ctx.nz_far, z + extent); 289 if (ctx.pass->type != LIGHTED
244 ctx.nz_near = min (ctx.nz_near, z - extent); 290 || !ctx.first_lighted
245 291 || evs.last + 0.1 > timer.now)
246 if (ctx.pass_type == view::DEPTH || evs.last + 0.3 > timer.now)
247 e->draw (ctx); 292 e->draw (ctx);
248 else 293 else
249 { 294 {
250 evs.last = timer.now; 295 evs.last = timer.now;
251 ctx.begin_occ_query (*this, e); 296 ctx.begin_occ_query (*this, e);
252 e->draw (ctx); 297 e->draw (ctx);
253 ctx.end_occ_query (); 298 ctx.end_occ_query ();
254 }
255 }
256 } 299 }
257 } 300 }
258
259#if 1
260 if (ctx.pass_type == view::POSTDEPTH && nvis == 0 && size ())
261 vs.state = OCCLUDED;
262#endif
263 } 301 }
264} 302}
265 303
266void octant::event (occ_query &ev) 304void octant::event (occ_query &ev)
267{ 305{

Diff Legend

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