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

Comparing libgender/oct.C (file contents):
Revision 1.28 by root, Wed Oct 6 16:52:48 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> 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}
54octant::~octant () 53octant::~octant ()
55{ 54{
56 for (fill = 8; fill--; ) 55 for (fill = 8; fill--; )
57 delete sub[fill]; 56 delete sub[fill];
58} 57}
59 58
60static bool overlap (const sector &o1, uoffs ea, const box &bbox) 59static bool overlap (const sector &o1, uoffs ea, const sector &a, const sector &b)
61{ 60{
62 sector a2, b2;
63
64 ea /= 2; 61 ea /= 2;
65 62
66 a2.x = o1.x + ea; 63 sector center_1 = o1 + ea;
67 a2.y = o1.y + ea; 64 sector size_2 = b - a;
68 a2.z = o1.z + ea; 65 sector center_2 = a + (size_2 >> 1);
69
70 b2.x = (bbox.a.x + bbox.b.x) / 2;
71 b2.y = (bbox.a.y + bbox.b.y) / 2;
72 b2.z = (bbox.a.z + bbox.b.z) / 2;
73 66
74 return abs (a2.x - b2.x) <= ea + (bbox.b.x - bbox.a.x) 67 return abs (center_1 - center_2) <= ea + size_2;
75 && abs (a2.y - b2.y) <= ea + (bbox.b.y - bbox.a.y)
76 && abs (a2.z - b2.z) <= ea + (bbox.b.z - bbox.a.z);
77} 68}
78 69
79void octant::add (entity_base *e) 70void octant::add (entity *e)
80{ 71{
81 box bbox = translate (e->bbox, e->orig, sector (0, 0, 0)); 72 const sector &a = e->a;
73 const sector &b = e->b;
82 74
83 uoffs size = max (abs (bbox.b.x - bbox.a.x),
84 max (abs (bbox.b.y - bbox.a.y),
85 abs (bbox.b.z - bbox.a.z)));
86
87 if (overlap (orig, extent, bbox)) 75 if (overlap (orig, extent, a, b))
88 { 76 {
89 uoffs extent2 = extent / 2; 77 uoffs extent2 = extent >> 1;
78 uoffs size = max (abs (b - a));
90 79
91 if (size > extent2 || !extent2) 80 if (size >= extent2 >> 1)
92 { 81 {
93 push_back (e); 82 push_back (e);
94 e->o.push_back (this); 83 e->o.push_back (this);
95 return; 84 return;
96 } 85 }
97 86
98 for (int i = 8; i--; ) 87 for (int i = 8; i--; )
99 { 88 {
100 sector s = orig; 89 sector s = orig;
101 s.offset (i, extent2); 90 s.offset (i, extent2);
91
102 if (overlap (s, extent2, bbox)) 92 if (overlap (s, extent2, a, b))
103 { 93 {
104 if (!sub[i]) 94 if (!sub[i])
95 {
105 sub[i] = new octant (this, s, extent2); 96 sub[i] = new octant (this, s, extent2);
97 fill++;
98 }
106 99
107 sub[i]->add (e); 100 sub[i]->add (e);
108 } 101 }
109 } 102 }
110 } 103 }
111} 104}
112 105
113void octant::remove (entity_base *e) 106void octant::remove (entity *e)
114{ 107{
115} 108}
116 109
117void octant::detect_visibility (view &ctx) 110bool octant::depth_pass (view &ctx)
118{ 111{
119 visibility_state &vs = ctx.vismap[this]; 112 oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);
120 113
121 if (vs.generation != ctx.generation) 114 GLfloat extent2 = 0.5F * (GLfloat)extent;
122 vs.visibility = visibility_state::UNKNOWN; 115 sector centeri = orig + (extent >> 1) - ctx.orig;
116 point centerf = point (centeri) + ((extent & 1) ? 0.5F : 0.F);
123 117
124 const sector &cam = ctx.orig; 118 GLfloat rad = ctx.diagfact * extent2;
125 if (cam.x >= orig.x && cam.x <= orig.x + extent 119
126 && cam.y >= orig.y && cam.y <= orig.y + extent 120 if (orig <= ctx.orig && ctx.orig <= orig + extent)
127 && cam.z >= orig.z && cam.z <= orig.z + extent) 121 vs.state = PARTIAL;
128 {
129 vs.visibility = visibility_state::PARTIAL;
130 vs.generation = ctx.generation;
131 }
132 else 122 else
133 { 123 {
134 point center (
135 orig.x + (soffs)extent / 2 - cam.x,
136 orig.y + (soffs)extent / 2 - cam.y,
137 orig.z + (soffs)extent / 2 - cam.z
138 );
139
140 GLfloat dia = (0.5 * sqrtf (3))*(GLfloat)extent;
141
142 if (ctx.frustum.t.distance (center) < -dia) return; 124 if (ctx.frustum.t.distance (centerf) < -rad) return false;
143 if (ctx.frustum.b.distance (center) < -dia) return; 125 if (ctx.frustum.b.distance (centerf) < -rad) return false;
144 if (ctx.frustum.l.distance (center) < -dia) return; 126 if (ctx.frustum.l.distance (centerf) < -rad) return false;
145 if (ctx.frustum.r.distance (center) < -dia) return; 127 if (ctx.frustum.r.distance (centerf) < -rad) return false;
146 if (ctx.frustum.n.distance (center) < -dia) return; 128 if (ctx.frustum.n.distance (centerf) < -rad) return false;
147 129
148 GLfloat fd = ctx.frustum.f.distance (center); 130 GLfloat fd = ctx.frustum.f.distance (centerf);
149 131
150 if (fd < -dia) 132 if (fd < -(ctx.c_far - ctx.z_far) -rad * 3.F)
151 {
152 if (fd > -dia * 2)
153 return; 133 return false;
154
155 // cull, but do check for potential visibility
156 if (size ())
157 ctx.farlist.push_back (this);
158 }
159 } 134 }
160 135
161 if (size ()) 136 if (vs.state == OCCLUDED)
162 ctx.vislist.push_back (this); 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);
163 144
164 // node to start with 145 // node to start with
165 unsigned char si = ctx.d.x < 0 ? 1 : 0 146 unsigned char si = centeri.x > 0 ? 1 : 0
166 | ctx.d.y < 0 ? 2 : 0 147 | centeri.y > 0 ? 2 : 0
167 | ctx.d.z < 0 ? 4 : 0; 148 | centeri.z > 0 ? 4 : 0;
149
150 //printf ("si %d C %Ld,%Ld,%Ld\n", si, centeri.x, centeri.y, centeri.z);
168 151
169 // bit-toggle to find next child for front-to-back order 152 // bit-toggle to find next child for front-to-back order
170 static unsigned char next[8] 153 static unsigned char toggle[8+1]
171 = { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7 }; 154 = { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7, 0 };
172 155
173 for (int i = 0; i < 8; i++) 156 unsigned char *next = toggle;
157 do
174 { 158 {
175 si ^= next[i]; 159 si ^= *next;
176 160
177 if (sub[si]) 161 if (sub[si])
178 sub[si]->detect_visibility (ctx); 162 sub[si]->depth_pass (ctx);
163 }
164 while (*++next);
165
166 if (size ()
167 && (vs.state == PARTIAL || vs.state == FULL))
179 } 168 {
169 ctx.nz_far = max (ctx.nz_far, z);
170 display (ctx);
171 ctx.vislist.push_back (this);
172 }
180 173
181 vs.generation = ctx.generation; 174 return true;
182} 175}
183 176
184void octant::display (view &ctx) 177void octant::display (view &ctx)
185{ 178{
186#if 0 179#if 0
180 sector s = orig - ctx.orig;
181
187 glBegin (GL_LINES); 182 glBegin (GL_LINES);
188 sector s = orig - ctx.orig;
189 vec3 clr(0, 0.8, 0); 183 vec3 clr(0, 0.8, 0);
190 glMaterialfv (GL_FRONT_AND_BACK, GL_DIFFUSE, (const GLfloat*)&clr); 184 glMaterialfv (GL_FRONT_AND_BACK, GL_DIFFUSE, (const GLfloat*)&clr);
191 185
192 for (int i = 8; i--; ) 186 for (int i = 8; i--; )
193 for (int ji = 3; ji--; ) 187 for (int ji = 3; ji--; )
194 { 188 {
195 int j = i | (1 << ji); 189 int j = i | (1 << ji);
196 if (i != j) 190 if (i < j)
197 { 191 {
198 glVertex3i (s.x + !!(i & 1) * extent, 192 glVertex3i (s.x + !!(i & 1) * extent,
199 s.y + !!(i & 2) * extent, 193 s.y + !!(i & 2) * extent,
200 s.z + !!(i & 4) * extent); 194 s.z + !!(i & 4) * extent);
201 glVertex3i (s.x + !!(j & 1) * extent, 195 glVertex3i (s.x + !!(j & 1) * extent,
… …
203 s.z + !!(j & 4) * extent); 197 s.z + !!(j & 4) * extent);
204 } 198 }
205 } 199 }
206 200
207 glEnd (); 201 glEnd ();
208 glDisable(GL_COLOR_MATERIAL);
209#endif 202#endif
203 oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);
210 204
205 if (vs.state == OCCLUDED)
206 {
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 }
215
216 ctx.begin_occ_query (*this, 0);
217 vb_bbox.draw (gl::bbox_mode, 0, gl::bbox_count);
218 ctx.end_occ_query ();
219 }
220 }
221 else
222 {
211 for (iterator i = end (); i != begin (); ) 223 for (iterator i = end (); i != begin (); )
212 (*--i)->display (ctx); 224 {
213} 225 entity *e = *--i;
214 226
215void 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}
266
267#if 0
216octant::draw_bbox (view &ctx) 268void octant::draw_bbox (view &ctx)
217{ 269{
218 sector s = orig - ctx.orig; 270 sector s = orig - ctx.orig;
219 int i;
220 GLint verts[4 * 6] = {
221 0, 2, 3, 1, // -z
222 4, 5, 7, 6, // +z
223 0, 1, 5, 4, // -y
224 7, 3, 2, 6, // +y
225 0, 4, 6, 2, // -x
226 1, 3, 7, 5, // +x
227 };
228 271
229 /* / 272 gl::draw_bbox (ctx, s, s + extent);
230 * ------- | 273}
231 * | | | 274#endif
232 * | | /
233 * | | /
234 * -------
235 */
236 275
237 GLfloat cube[8][3] = 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)
238 { 282 {
239 { s.x , s.y , s.z }, 283 evis &evs = vs.vismap[e];
240 { s.x + (soffs)extent, s.y , s.z }, 284 evs.state = ev.count ? FULL : OCCLUDED;
241 { s.x , s.y + (soffs)extent, s.z },
242 { s.x + (soffs)extent, s.y + (soffs)extent, s.z },
243 { s.x , s.y , s.z + (soffs)extent },
244 { s.x + (soffs)extent, s.y , s.z + (soffs)extent },
245 { s.x , s.y + (soffs)extent, s.z + (soffs)extent },
246 { s.x + (soffs)extent, s.y + (soffs)extent, s.z + (soffs)extent },
247 }; 285 }
248 286 else
249 glBegin (GL_QUADS); 287 {
250 for (i = 0; i < 4 * 6; i++) { 288 vs.state = ev.count ? FULL : OCCLUDED;
251 glVertex3fv (cube [verts [i]]);
252 } 289 }
253 glEnd ();
254}
255 290
291#if 0
292 visibility_state &vs = ev.v.vismap[this];
256 293
294 vs.last = timer.now;
295 vs.state = ev.r <= 0
296 ? visibility_state::OCCLUDED
297 : visibility_state::FULL;
298#endif
299}
300
301

Diff Legend

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