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

Diff Legend

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