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

Comparing libgender/oct.C (file contents):
Revision 1.3 by root, Sun Oct 3 03:51:51 2004 UTC vs.
Revision 1.19 by root, Wed Oct 6 00:55:37 2004 UTC

1#include <cstdlib> 1#include <cstdlib>
2 2
3#include <vector>
4
5using namespace std;
6
7#define GL_GLEXT_PROTOTYPES
8#include <GL/gl.h>
9
3#include "oct.h" 10#include "oct.h"
11#include "view.h"
4#include "entity.h" 12#include "entity.h"
5 13
6octant world(0, 0); 14vector<GLuint> occ_query_objects;
7 15
8octant::octant (octant *parent, int subindex) 16static GLuint begin_occ_query ()
9: parent(parent) 17{
18 GLuint id;
19
20 if (occ_query_objects.size ())
21 {
22 id = *(occ_query_objects.end () - 1);
23 occ_query_objects.pop_back ();
24 }
25 else
26 glGenQueries (1, &id);
27
28 glBeginQuery (GL_SAMPLES_PASSED, id);
29 return id;
30}
31
32#define end_occ_query() glEndQuery (GL_SAMPLES_PASSED);
33
34static GLuint occ_query_result (GLuint id)
35{
36 GLuint count;
37
38 glGetQueryObjectuiv (id, GL_QUERY_RESULT, &count);
39 occ_query_objects.push_back (id);
40
41 return count;
42}
43
44octant world(0, sector (SOFFS_MIN, SOFFS_MIN, SOFFS_MIN), MAXEXTENT);
45
46octant::octant (octant *parent, const sector &orig, uoffs extent)
47: parent(parent), orig(orig), extent(extent)
10{ 48{
11 for (fill = 8; fill--; ) 49 for (fill = 8; fill--; )
12 sub[fill] = 0; 50 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} 51}
26 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
59static bool overlap (const sector &o1, uoffs ea, const box &bbox)
60{
61 sector a2, b2;
62
63 ea /= 2;
64
65 a2.x = o1.x + ea;
66 a2.y = o1.y + ea;
67 a2.z = o1.z + ea;
68
69 b2.x = (bbox.a.x + bbox.b.x) / 2;
70 b2.y = (bbox.a.y + bbox.b.y) / 2;
71 b2.z = (bbox.a.z + bbox.b.z) / 2;
72
73 return abs (a2.x - b2.x) <= ea + (bbox.b.x - bbox.a.x)
74 && abs (a2.y - b2.y) <= ea + (bbox.b.y - bbox.a.y)
75 && abs (a2.z - b2.z) <= ea + (bbox.b.z - bbox.a.z);
76}
77
33void octant::add (const sector &sec, entity_base *e) 78void octant::add (entity_base *e)
34{ 79{
35 sector orig2; 80 box bbox = translate (e->bbox, e->orig, sector (0, 0, 0));
36 sector extent2;
37 81
38 orig2.x = sec.x + (soffs)e->bbox.a.x; 82 uoffs size = max (abs (bbox.b.x - bbox.a.x),
39 orig2.y = sec.y + (soffs)e->bbox.a.y; 83 max (abs (bbox.b.y - bbox.a.y),
40 orig2.z = sec.z + (soffs)e->bbox.a.z; 84 abs (bbox.b.z - bbox.a.z)));
41 85
42 extent2.x = sec.x + (soffs)e->bbox.b.x - orig2.x; 86 if (overlap (orig, extent, bbox))
43 extent2.x = sec.y + (soffs)e->bbox.b.y - orig2.y; 87 {
44 extent2.x = sec.z + (soffs)e->bbox.b.z - orig2.z; 88 uoffs extent2 = extent / 2;
45 89
90 if (size > extent2 || !extent2)
91 {
46 push_back (e); 92 push_back (e);
47 e->o.push_back (this); 93 e->o.push_back (this);
94 return;
95 }
96
97 for (int i = 8; i--; )
98 {
99 sector s = orig;
100 s.offset (i, extent2);
101 if (overlap (s, extent2, bbox))
102 {
103 if (!sub[i])
104 sub[i] = new octant (this, s, extent2);
105
106 sub[i]->add (e);
107 }
108 }
109 }
48} 110}
49 111
50void octant::remove (entity_base *e) 112void octant::remove (entity_base *e)
51{ 113{
52} 114}
53 115
54void octant::draw (const draw_context &ctx) 116void octant::detect_visibility (view &ctx)
55{ 117{
118 visibility_state &vs = ctx.vismap[this];
119
120 if (vs.generation != ctx.generation)
121 vs.visibility = visibility_state::UNKNOWN;
122
123 const sector &cam = ctx.orig;
124 if (cam.x >= orig.x && cam.x <= orig.x + extent
125 && cam.y >= orig.y && cam.y <= orig.y + extent
126 && cam.z >= orig.z && cam.z <= orig.z + extent)
127 {
128 vs.visibility = visibility_state::PARTIAL;
129 vs.generation = ctx.generation;
130 }
131 else
132 {
133 point center (
134 orig.x + (soffs)extent / 2 - cam.x,
135 orig.y + (soffs)extent / 2 - cam.y,
136 orig.z + (soffs)extent / 2 - cam.z
137 );
138
139 GLfloat dia = (0.5 * sqrtf (3))*(GLfloat)extent;
140
141 if (ctx.frustum.t.distance (center) < -dia) return;
142 if (ctx.frustum.b.distance (center) < -dia) return;
143 if (ctx.frustum.l.distance (center) < -dia) return;
144 if (ctx.frustum.r.distance (center) < -dia) return;
145 if (ctx.frustum.n.distance (center) < -dia) return;
146 if (ctx.frustum.f.distance (center) < -dia) return;
147 }
148
149 if (size ())
150 ctx.vislist.push_back (this);
151
152 // node to start with
153 unsigned char si = ctx.d.x < 0 ? 1 : 0
154 | ctx.d.y < 0 ? 2 : 0
155 | ctx.d.z < 0 ? 4 : 0;
156
157 // bit-toggle to find next child for front-to-back order
158 static unsigned char next[8]
159 = { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7 };
160
161 for (int i = 0; i < 8; i++)
162 {
163 si ^= next[i];
164
165 if (sub[si])
166 sub[si]->detect_visibility (ctx);
167 }
168
169 vs.generation = ctx.generation;
170}
171
172void octant::display (view &ctx)
173{
174#if 0
175 glBegin (GL_LINES);
176 sector s = orig;
177 s.x -= ctx.orig.x;
178 s.y -= ctx.orig.y;
179 s.z -= ctx.orig.z;
180 vec3 clr(0, 0.8, 0);
181 glMaterialfv (GL_FRONT_AND_BACK, GL_DIFFUSE, (const GLfloat*)&clr);
182
183 for (int i = 8; i--; )
184 for (int ji = 3; ji--; )
185 {
186 int j = i | (1 << ji);
187 if (i != j)
188 {
189 glVertex3i (s.x + !!(i & 1) * extent,
190 s.y + !!(i & 2) * extent,
191 s.z + !!(i & 4) * extent);
192 glVertex3i (s.x + !!(j & 1) * extent,
193 s.y + !!(j & 2) * extent,
194 s.z + !!(j & 4) * extent);
195 }
196 }
197
198 glEnd ();
199 glDisable(GL_COLOR_MATERIAL);
200#endif
201
56 for (iterator i = end (); i-- != begin (); ) 202 for (iterator i = end (); i != begin (); )
57 (*i)->draw (ctx); 203 (*--i)->display (ctx);
58} 204}
59 205
206
207

Diff Legend

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