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

Comparing libgender/oct.C (file contents):
Revision 1.4 by root, Sun Oct 3 05:10:45 2004 UTC vs.
Revision 1.49 by root, Sun Oct 10 18:14:22 2004 UTC

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

Diff Legend

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