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

Comparing libgender/oct.C (file contents):
Revision 1.36 by root, Sat Oct 9 02:08:29 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#define GL_GLEXT_PROTOTYPES 6#include "opengl.h"
8#include <GL/gl.h>
9#include <GL/glext.h>
10 7
11#include "oct.h" 8#include "oct.h"
12#include "view.h" 9#include "view.h"
13#include "entity.h" 10#include "entity.h"
14 11
15vector<GLuint> occ_query_objects; 12enum visibility_state { FULL, PARTIAL, SMALL, OCCLUDED };
16 13
17static GLuint begin_occ_query () 14struct evis {
18{ 15 visibility_state state;
19 GLuint id; 16 double last; // time of last check
17 evis () : last(0.), state(FULL) { };
18};
20 19
21 if (occ_query_objects.size ()) 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)
22 { 29 {
23 id = *(occ_query_objects.end () - 1);
24 occ_query_objects.pop_back ();
25 } 30 }
26 else 31};
27 glGenQueriesARB (1, &id);
28
29 glBeginQueryARB (GL_SAMPLES_PASSED, id);
30 return id;
31}
32
33#define end_occ_query() glEndQueryARB (GL_SAMPLES_PASSED)
34
35GLuint occ_query_result (GLuint id)
36{
37 GLuint count;
38
39 glGetQueryObjectuivARB (id, GL_QUERY_RESULT, &count);
40 occ_query_objects.push_back (id);
41
42 return count;
43}
44 32
45octant world(0, sector (SOFFS_MIN, SOFFS_MIN, SOFFS_MIN), MAXEXTENT); 33octant world(0, sector (SOFFS_MIN, SOFFS_MIN, SOFFS_MIN), MAXEXTENT);
46 34
47octant::octant (octant *parent, const sector &orig, uoffs extent) 35octant::octant (octant *parent, const sector &orig, uoffs extent)
48: parent(parent), orig(orig), extent(extent) 36: parent(parent)
37, orig(orig)
38, extent(extent)
49{ 39{
50 for (fill = 8; fill--; ) 40 for (fill = 8; fill--; )
51 sub[fill] = 0; 41 sub[fill] = 0;
52} 42}
53 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
54octant::~octant () 54octant::~octant ()
55{ 55{
56 for (fill = 8; fill--; ) 56 for (fill = 8; fill--; )
57 delete sub[fill]; 57 delete sub[fill];
58} 58}
… …
61{ 61{
62 ea /= 2; 62 ea /= 2;
63 63
64 sector center_1 = o1 + ea; 64 sector center_1 = o1 + ea;
65 sector size_2 = b - a; 65 sector size_2 = b - a;
66 sector center_2 = a + size_2 / 2; 66 sector center_2 = a + (size_2 >> 1);
67 67
68 return abs (center_1 - center_2) <= ea + size_2; 68 return abs (center_1 - center_2) <= ea + size_2;
69} 69}
70 70
71void octant::add (entity *e) 71void octant::add (entity *e)
… …
73 const sector &a = e->a; 73 const sector &a = e->a;
74 const sector &b = e->b; 74 const sector &b = e->b;
75 75
76 if (overlap (orig, extent, a, b)) 76 if (overlap (orig, extent, a, b))
77 { 77 {
78 uoffs extent2 = extent / 2; 78 uoffs extent2 = extent >> 1;
79 uoffs size = max (abs (b - a)); 79 uoffs size = max (abs (b - a));
80 80
81 if (size > extent2 || !extent2) 81 if (size >= extent2 >> 1)
82 { 82 {
83 push_back (e); 83 push_back (e);
84 e->o.push_back (this); 84 e->o.push_back (this);
85 return; 85 return;
86 } 86 }
… …
91 s.offset (i, extent2); 91 s.offset (i, extent2);
92 92
93 if (overlap (s, extent2, a, b)) 93 if (overlap (s, extent2, a, b))
94 { 94 {
95 if (!sub[i]) 95 if (!sub[i])
96 {
96 sub[i] = new octant (this, s, extent2); 97 sub[i] = new octant (this, s, extent2);
98 fill++;
99 }
97 100
98 sub[i]->add (e); 101 sub[i]->add (e);
99 } 102 }
100 } 103 }
101 } 104 }
… …
103 106
104void octant::remove (entity *e) 107void octant::remove (entity *e)
105{ 108{
106} 109}
107 110
108void octant::detect_visibility (view &ctx) 111bool octant::detect_visibility (view &ctx)
109{ 112{
110 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);
111 116
112 if (vs.generation != ctx.generation) 117 GLfloat rad = ctx.diagfact * extent2;
113 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);
114 123
115 if (orig <= ctx.orig && ctx.orig <= orig + extent) 124 if (orig <= ctx.orig && ctx.orig <= orig + extent)
116 { 125 vs.state = PARTIAL;
117 vs.visibility = visibility_state::PARTIAL; 126 else
118 vs.generation = ctx.generation;
119 } 127 {
120 else 128 if (distance (ctx.frustum.t, centerf) < -rad) return false;
129 if (distance (ctx.frustum.b, centerf) < -rad) return false;
130 if (distance (ctx.frustum.l, centerf) < -rad) return false;
131 if (distance (ctx.frustum.r, centerf) < -rad) return false;
132 if (distance (ctx.frustum.n, centerf) < -rad) return false;
133
134#if 0
135 GLfloat fd = distance (ctx.frustum.f, centerf);
136
137 if (fd < -(ctx.c_far - ctx.z_far) -rad * 3.F)
138 return false;
139#endif
121 { 140 }
122 sector center_s (orig + extent / 2 - ctx.orig);
123 point center (center_s.x, center_s.y, center_s.z);
124 141
125 GLfloat dia = sqrtf (3) * (GLfloat)extent; 142#if 0
126 143 if (vs.state == OCCLUDED && size ())
127 if (ctx.frustum.t.distance (center) < -dia) return;
128 if (ctx.frustum.b.distance (center) < -dia) return;
129 if (ctx.frustum.l.distance (center) < -dia) return;
130 if (ctx.frustum.r.distance (center) < -dia) return;
131 if (ctx.frustum.n.distance (center) < -dia) return;
132
133 GLfloat fd = ctx.frustum.f.distance (center);
134
135 if (fd < -dia)
136 {
137 if (fd < -dia * 2)
138 return;
139
140 ctx.farlist.push_back (this);
141 return;
142 }
143 } 144 {
144
145 if (vs.visibility == visibility_state::UNKNOWN)
146 vs.visibility = visibility_state::FULL;
147
148 if (size ()) 145 if (size ())
149 ctx.vislist.push_back (this); 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;
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
150 160
151 // node to start with 161 // node to start with
152 unsigned char si = ctx.d.x < 0 ? 1 : 0 162 unsigned char si = centeri.x > 0 ? 1 : 0
153 | ctx.d.y < 0 ? 2 : 0 163 | centeri.y > 0 ? 2 : 0
154 | ctx.d.z < 0 ? 4 : 0; 164 | centeri.z > 0 ? 4 : 0;
155 165
156 // bit-toggle to find next child for front-to-back order 166 // bit-toggle to find next child for front-to-back order
157 static unsigned char next[8] 167 static unsigned char toggle[8+1]
158 = { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7 }; 168 = { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7, 0 };
159 169
160 for (int i = 0; i < 8; i++) 170 bool visible = vs.state == PARTIAL || vs.state == FULL;
171
172 unsigned char *next = toggle;
173 do
161 { 174 {
162 si ^= next[i]; 175 si ^= *next;
163 176
164 if (sub[si]) 177 if (sub[si])
165 sub[si]->detect_visibility (ctx); 178 visible = visible | sub[si]->detect_visibility (ctx);
179 }
180 while (*++next);
181
182 if (visible)
166 } 183 {
184 if (size ())
185 ctx.vislist.push_back (this);
186 }
187 else
188 {
189 vs.state = OCCLUDED;
190 ctx.vislist.push_back (this);
191 }
167 192
168 vs.generation = ctx.generation; 193 return visible;
169} 194}
170 195
171void octant::display (view &ctx) 196void octant::display (view &ctx)
172{ 197{
173#if 0 198 oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);
174 glBegin (GL_LINES); 199
200 if (vs.state == OCCLUDED)
201 {
202 if (ctx.pass_type == view::POSTDEPTH)
203 {
204 ctx.begin_occ_query (*this, 0);
175 sector s = orig - ctx.orig; 205 sector s = orig - ctx.orig;
176 vec3 clr(0, 0.8, 0); 206 gl::draw_bbox (s, s + extent);
177 glMaterialfv (GL_FRONT_AND_BACK, GL_DIFFUSE, (const GLfloat*)&clr); 207 ctx.end_occ_query ();
208 }
209 }
210 else
211 {
212 int nvis = 0;
178 213
179 for (int i = 8; i--; ) 214 for (iterator i = begin (); i != end (); )
180 for (int ji = 3; ji--; )
181 { 215 {
182 int j = i | (1 << ji); 216 entity *e = *i++;
183 if (i != j) 217
218 evis &evs = vs.vismap[e];
219
220 if (ctx.pass_type == view::POSTDEPTH)
184 { 221 {
185 glVertex3i (s.x + !!(i & 1) * extent, 222 if (evs.state == OCCLUDED)
186 s.y + !!(i & 2) * extent, 223 {
187 s.z + !!(i & 4) * extent); 224 ctx.begin_occ_query (*this, e);
188 glVertex3i (s.x + !!(j & 1) * extent, 225 gl::draw_bbox (e->a - ctx.orig, e->b - ctx.orig);
189 s.y + !!(j & 2) * extent, 226 ctx.end_occ_query ();
190 s.z + !!(j & 4) * extent); 227 }
228 else
229 nvis++;
191 } 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 }
192 } 257 }
193
194 glEnd ();
195 glDisable(GL_COLOR_MATERIAL);
196#endif
197 258
198 for (iterator i = end (); i != begin (); ) 259#if 1
199 (*--i)->display (ctx); 260 if (ctx.pass_type == view::POSTDEPTH && nvis == 0 && size ())
200} 261 vs.state = OCCLUDED;
201 262#endif
202void
203octant::draw_bbox (view &ctx)
204{
205 sector s = orig - ctx.orig;
206 int i;
207 GLint verts[4 * 6] = {
208 0x00, 0x40, 0x60, 0x20, // -x
209 0x10, 0x30, 0x70, 0x50, // +x
210 0x00, 0x10, 0x50, 0x40, // -y
211 0x70, 0x30, 0x20, 0x60, // +y
212 0x00, 0x20, 0x30, 0x10, // -z
213 0x40, 0x50, 0x70, 0x60, // +z
214 };
215
216 GLfloat cube[8][3] =
217 {
218 { s.x , s.y , s.z },
219 { s.x + (soffs)extent, s.y , s.z },
220 { s.x , s.y + (soffs)extent, s.z },
221 { s.x + (soffs)extent, s.y + (soffs)extent, s.z },
222 { s.x , s.y , s.z + (soffs)extent },
223 { s.x + (soffs)extent, s.y , s.z + (soffs)extent },
224 { s.x , s.y + (soffs)extent, s.z + (soffs)extent },
225 { s.x + (soffs)extent, s.y + (soffs)extent, s.z + (soffs)extent },
226 }; 263 }
227
228 glBegin (GL_LINE_LOOP);
229
230 for (i = 0; i < 4 * 6; i++)
231 glVertex3fv (cube [verts [i] >> 4]);
232
233 glEnd ();
234} 264}
235 265
266void octant::event (occ_query &ev)
267{
268 oct_visibility &vs = *(oct_visibility *)get_visibility (ev.ctx);
269 entity *e = (entity *)ev.id;
236 270
271 if (e)
272 {
273 evis &evs = vs.vismap[e];
274 evs.state = ev.count ? FULL : OCCLUDED;
275 }
276 else
277 vs.state = ev.count ? FULL : OCCLUDED;
278}
279
280

Diff Legend

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