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

Diff Legend

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