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

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

Diff Legend

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