libgender/oct.C

#include <cstdlib>

#include <vector>
using namespace std;

#include "opengl.h"

#include "oct.h"
#include "view.h"
#include "entity.h"

enum visibility_state { FULL, PARTIAL, OCCLUDED };

struct evis {
  entity *e;
  visibility_state state;
  double last; // time of last check

  void clear ()
  {
    last = 0.;
    state = FULL;
  }

  evis ()
  {
    clear ();
  }
};

struct oct_visibility : visibility_base
{
  vector<evis> vismap;

  visibility_state state;

  evis &get_visibility (int i, entity *e)
  {
    evis &evs = vismap [i];

    if (evs.e != e)
      {
        evs.clear ();
        evs.e = e;
      }

    return evs;
  }

  oct_visibility (octant &oct)
  : state(FULL)
  {
  }
};

octant world(0, sector (0, 0, 0), MAXEXTENT);

octant::octant (octant *parent, const sector &orig, uoffs extent)
: parent(parent)
, orig(orig)
, extent(extent)
{
  for (fill = 8; fill--; )
    sub[fill] = 0;
}

visibility_base *octant::new_visibility ()
{
  return new oct_visibility (*this);
}

void octant::clear_visibility (visibility_base *vs)
{
  ((oct_visibility *)vs)->vismap.clear ();
  ((oct_visibility *)vs)->state = FULL;
}

octant::~octant ()
{
  for (fill = 8; fill--; )
    delete sub[fill];
}

static bool overlap (const sector &orig, uoffs extent, const sector &a, const sector &b)
{
  sector size   = (b - a + 1) >> 1;
  sector center = a + size;

  return abs (orig - center) <= extent + size;
}

static sector offset (const sector &s, int subindex, uoffs extent)
{
  return sector (
    s.x + (subindex & 1 ? extent : -extent),
    s.y + (subindex & 2 ? extent : -extent),
    s.z + (subindex & 4 ? extent : -extent)
  );
}

void octant::add (entity *e)
{
  const sector &a = e->a;
  const sector &b = e->b;

  uoffs size = max (abs (b - a));

  if (size >= extent >> 4)
    {
      if (overlap (orig, extent, a, b))
        {
          push_back (e);
          e->o.push_back (this);
        }
    }
  else
    {
      uoffs extent2 = extent >> 1;

      for (int i = 8; i--; )
        {
          sector s = offset (orig, i, extent2);

          if (overlap (s, extent2, a, b))
            {
              if (!sub[i])
                {
                  sub[i] = new octant (this, s, extent2);
                  fill++;
                }

              sub[i]->add (e);
            }
        }
    }
}

void octant::remove (entity *e)
{
}

bool octant::detect_visibility (view &ctx) //, bool fully_visible)
{
  ctx.stat1++;//D

  sector centeri = orig - ctx.orig;
  point centerf = point (centeri);

  GLfloat rad = ctx.diagfact * extent;

#if 0
  if (!overlap (ctx.frustum.c, sphere (centerf, rad)))
    return false;
#endif

  oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);

  vs.state = FULL;//D

#if 0
  if (max (abs (centeri)) <= extent)
    ;
  else
    {
#endif

      //if (distance (ctx.frustum.t, centerf) < -rad) return false;
      //if (distance (ctx.frustum.b, centerf) < -rad) return false;
      //if (distance (ctx.frustum.l, centerf) < -rad) return false;
      //if (distance (ctx.frustum.r, centerf) < -rad) return false;
      ////if (distance (ctx.frustum.n, centerf) < -rad) return false;

#if 0
      GLfloat fd = distance (ctx.frustum.f, centerf);

      if (fd < -(ctx.c_far - ctx.z_far) -rad * 3.F)
        return false;
#endif

  // very important, optimize?
  GLfloat z = length (ctx.p - centerf) + rad;
  if (ctx.perspfact * extent / z < 10.) // very crude "too small to see" check
    return false;

#if 0
  if (vs.state == PARTIAL || vs.state == FULL)
    ctx.nc_far = max (ctx.nc_far, z);
#endif

  if (vs.state == OCCLUDED)
    {
      if (extent < ctx.z_far)
        {
          ctx.postdepthlist.push_back (this);
          return false;
        }
      else
        vs.state == PARTIAL;
    }
 
  bool visible = size () && vs.state == FULL;

  // node to start with
  unsigned char si = centeri.x > 0 ? 1 : 0
                   | centeri.y > 0 ? 2 : 0
                   | centeri.z > 0 ? 4 : 0;

  // bit-toggle to find next child for front-to-back order
  static unsigned char toggle[8+1]
    = { 0,  0^1, 1^2, 2^4, 4^3, 3^5, 5^6,  6^7, 0 };

  unsigned char *next = toggle;
  do
    {
      si ^= *next;

      if (sub[si])
        visible = visible | sub[si]->detect_visibility (ctx);
    }
  while (*++next);

  if (visible)
    {
      if (size ())
        ctx.vislist.push_back (this);

      ctx.postdepthlist.push_back (this);
    }
  else
    {
      vs.state = OCCLUDED;
      ctx.postdepthlist.push_back (this);
    }

  return visible;
}

void octant::draw_depth (view &ctx)
{
  oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);

  vs.vismap.resize (size ());

  if (vs.state == PARTIAL || vs.state == OCCLUDED)
    return;

  for (int i = 0; i < size (); ++i)
    {
      entity *e = (*this)[i];
      const evis &evs = vs.get_visibility (i, e);

      if (evs.state != OCCLUDED)
        {
          if (!ctx.may_draw (e))
            continue;

          sector center = ((e->a + e->b) >> 1) - ctx.orig;
          GLfloat z = length (vec3 (center));
          ctx.pixfact = ctx.perspfact / z;

          ctx.nz_far  = max (ctx.nz_far,  z + extent);
          ctx.nz_near = min (ctx.nz_near, z - extent);

          e->draw (ctx);
        }
    }
}

void octant::draw_postdepth (view &ctx)
{
  oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);

  if (vs.state == PARTIAL || vs.state == OCCLUDED)
    {
      ctx.begin_occ_query (*this, 0);
      sector s = orig - ctx.orig;
      gl::draw_bbox (s - extent, s + extent);
      ctx.end_occ_query ();
    }
  else
    {
      int nvis = 0;

      for (int i = 0; i < size (); ++i)
        {
          entity *e = (*this)[i];
          const evis &evs = vs.get_visibility (i, e);

          if (evs.state == OCCLUDED)
            {
              if (!ctx.may_draw (e))
                continue;

              ctx.begin_occ_query (*this, e);
              gl::draw_bbox (e->a - ctx.orig, e->b - ctx.orig);
              ctx.end_occ_query ();
            }
          else
            nvis++;
        }

      if (nvis == 0 && size ())
        vs.state = PARTIAL;
    }
}

void octant::draw_lighted (view &ctx)
{
  oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);

  if (vs.state == PARTIAL || vs.state == OCCLUDED)
    return;

#if 0
  {
    static vertex_buffer vb;
    static index_buffer ib;

    sector s = orig - ctx.orig;
    sector a = s - extent, b = s + extent;

    vertex_v3f vd[] = {
       point (a.x, a.y, a.z),
       point (b.x, a.y, a.z),
       point (a.x, b.y, a.z),
       point (b.x, b.y, a.z),
       point (a.x, a.y, b.z),
       point (b.x, a.y, b.z),
       point (a.x, b.y, b.z),
       point (b.x, b.y, b.z),
    };

    if (!ib)
      {
        static GLushort verts[4*6] = {
           0, 4, 6, 2,  // -x
           1, 3, 7, 5,  // +x
           0, 1, 5, 4,  // -y
           7, 3, 2, 6,  // +y
           0, 2, 3, 1,  // -z
           4, 5, 7, 6,  // +z
        };

        ib.set (verts, 4*6, GL_STATIC_DRAW_ARB);
      }

    vb.set (vd, 8, GL_STREAM_DRAW_ARB);
    vb.bind ();
    for (int i = 0; i < 6; i++)
      ib.draw (GL_LINE_LOOP, i*4, 4);

  }
#endif

  for (int i = 0; i < size (); ++i)
    {
      entity *e = (*this)[i];
      evis &evs = vs.get_visibility (i, e);

      if (evs.state != OCCLUDED)
        {
          if (!ctx.may_draw (e))
            continue;

          sector center = ((e->a + e->b) >> 1) - ctx.orig;
          GLfloat z = length (vec3 (center));
          ctx.pixfact = ctx.perspfact / z;

          if (ctx.pass->type != LIGHTED 
              || !ctx.first_lighted
              || evs.last + 0.1 > timer.now)
            e->draw (ctx);
          else
            {
              evs.last = timer.now;
              ctx.begin_occ_query (*this, e);
              e->draw (ctx);
              ctx.end_occ_query ();
            }
        }
    }
}

void octant::event (occ_query &ev)
{
  oct_visibility &vs = *(oct_visibility *)get_visibility (ev.ctx);
  entity *e = (entity *)ev.id;

  if (e)
    {
      for (vector<evis>::iterator i = vs.vismap.begin ();
           i != vs.vismap.end ();
           ++i)
        if (i->e == e)
          {
            i->state = ev.count ? FULL : OCCLUDED;
            return;
          }
    }
  else
    vs.state = ev.count ? (vs.state == PARTIAL ? PARTIAL : FULL) : OCCLUDED;
}


Revision:	1.85
Committed:	Sun Jan 2 12:21:48 2005 UTC (19 years, 5 months ago) by root
Content type:	text/plain
Branch:	MAIN
Changes since 1.84:	+2 -2 lines
Log Message:	* empty log message *
#	User	Rev	Content
1	root	1.1	#include <cstdlib>
2
3	root	1.8	#include <vector>
4			using namespace std;
5
6	root	1.48	#include "opengl.h"
7	root	1.8
8	root	1.1	#include "oct.h"
9	root	1.8	#include "view.h"
10	root	1.2	#include "entity.h"
11
12	root	1.80	enum visibility_state { FULL, PARTIAL, OCCLUDED };
13	root	1.56
14	root	1.54	struct evis {
15	root	1.79	entity *e;
16	root	1.56	visibility_state state;
17	root	1.54	double last; // time of last check
18	root	1.79
19			void clear ()
20			{
21			last = 0.;
22			state = FULL;
23			}
24
25			evis ()
26			{
27			clear ();
28			}
29	root	1.54	};
30
31	root	1.52	struct oct_visibility : visibility_base
32			{
33	root	1.79	vector<evis> vismap;
34	root	1.52
35	root	1.56	visibility_state state;
36	root	1.52
37	root	1.79	evis &get_visibility (int i, entity *e)
38			{
39			evis &evs = vismap [i];
40
41			if (evs.e != e)
42			{
43			evs.clear ();
44			evs.e = e;
45			}
46
47			return evs;
48			}
49
50	root	1.52	oct_visibility (octant &oct)
51	root	1.54	: state(FULL)
52	root	1.52	{
53			}
54			};
55
56	root	1.75	octant world(0, sector (0, 0, 0), MAXEXTENT);
57	root	1.8
58			octant::octant (octant *parent, const sector &orig, uoffs extent)
59	root	1.54	: parent(parent)
60			, orig(orig)
61			, extent(extent)
62	root	1.8	{
63			for (fill = 8; fill--; )
64			sub[fill] = 0;
65	root	1.2	}
66
67	root	1.53	visibility_base *octant::new_visibility ()
68			{
69			return new oct_visibility (*this);
70			}
71
72			void octant::clear_visibility (visibility_base *vs)
73			{
74			((oct_visibility *)vs)->vismap.clear ();
75	root	1.75	((oct_visibility *)vs)->state = FULL;
76	root	1.53	}
77	root	1.65
78	root	1.2	octant::~octant ()
79			{
80			for (fill = 8; fill--; )
81			delete sub[fill];
82			}
83
84	root	1.75	static bool overlap (const sector &orig, uoffs extent, const sector &a, const sector &b)
85	root	1.4	{
86	root	1.75	sector size = (b - a + 1) >> 1;
87			sector center = a + size;
88	root	1.4
89	root	1.75	return abs (orig - center) <= extent + size;
90			}
91	root	1.33
92	root	1.75	static sector offset (const sector &s, int subindex, uoffs extent)
93			{
94			return sector (
95			s.x + (subindex & 1 ? extent : -extent),
96			s.y + (subindex & 2 ? extent : -extent),
97			s.z + (subindex & 4 ? extent : -extent)
98			);
99	root	1.4	}
100
101	root	1.32	void octant::add (entity *e)
102	root	1.2	{
103	root	1.32	const sector &a = e->a;
104			const sector &b = e->b;
105	root	1.7
106	root	1.80	uoffs size = max (abs (b - a));
107
108			if (size >= extent >> 4)
109	root	1.4	{
110	root	1.80	if (overlap (orig, extent, a, b))
111	root	1.8	{
112			push_back (e);
113			e->o.push_back (this);
114			}
115	root	1.80	}
116			else
117			{
118			uoffs extent2 = extent >> 1;
119	root	1.5
120	root	1.8	for (int i = 8; i--; )
121	root	1.5	{
122	root	1.75	sector s = offset (orig, i, extent2);
123	root	1.32
124			if (overlap (s, extent2, a, b))
125	root	1.5	{
126	root	1.8	if (!sub[i])
127	root	1.50	{
128			sub[i] = new octant (this, s, extent2);
129			fill++;
130			}
131	root	1.8
132			sub[i]->add (e);
133	root	1.5	}
134	root	1.8	}
135	root	1.4	}
136	root	1.2	}
137	root	1.1
138	root	1.32	void octant::remove (entity *e)
139	root	1.1	{
140			}
141
142	root	1.80	bool octant::detect_visibility (view &ctx) //, bool fully_visible)
143	root	1.1	{
144	root	1.77	ctx.stat1++;//D
145
146	root	1.75	sector centeri = orig - ctx.orig;
147			point centerf = point (centeri);
148	root	1.51
149	root	1.75	GLfloat rad = ctx.diagfact * extent;
150	root	1.43
151	root	1.84	#if 0
152	root	1.59	if (!overlap (ctx.frustum.c, sphere (centerf, rad)))
153			return false;
154	root	1.84	#endif
155	root	1.65
156			oct_visibility &vs = (oct_visibility )get_visibility (ctx);
157	root	1.59
158	root	1.82	vs.state = FULL;//D
159
160	root	1.80	#if 0
161	root	1.75	if (max (abs (centeri)) <= extent)
162	root	1.80	;
163	root	1.10	else
164			{
165	root	1.82	#endif
166
167			//if (distance (ctx.frustum.t, centerf) < -rad) return false;
168			//if (distance (ctx.frustum.b, centerf) < -rad) return false;
169			//if (distance (ctx.frustum.l, centerf) < -rad) return false;
170			//if (distance (ctx.frustum.r, centerf) < -rad) return false;
171			////if (distance (ctx.frustum.n, centerf) < -rad) return false;
172	root	1.25
173	root	1.59	#if 0
174			GLfloat fd = distance (ctx.frustum.f, centerf);
175	root	1.25
176	root	1.47	if (fd < -(ctx.c_far - ctx.z_far) -rad * 3.F)
177	root	1.52	return false;
178	root	1.80	#endif
179	root	1.8
180	root	1.75	// very important, optimize?
181	root	1.85	GLfloat z = length (ctx.p - centerf) + rad;
182			if (ctx.perspfact * extent / z < 10.) // very crude "too small to see" check
183	root	1.58	return false;
184	root	1.45
185	root	1.59	#if 0
186	root	1.56	if (vs.state == PARTIAL \|\| vs.state == FULL)
187	root	1.45	ctx.nc_far = max (ctx.nc_far, z);
188	root	1.59	#endif
189	root	1.45
190	root	1.80	if (vs.state == OCCLUDED)
191	root	1.72	{
192	root	1.81	if (extent < ctx.z_far)
193			{
194			ctx.postdepthlist.push_back (this);
195			return false;
196			}
197			else
198			vs.state == PARTIAL;
199	root	1.72	}
200
201	root	1.81	bool visible = size () && vs.state == FULL;
202	root	1.74
203	root	1.51	// node to start with
204			unsigned char si = centeri.x > 0 ? 1 : 0
205			\| centeri.y > 0 ? 2 : 0
206			\| centeri.z > 0 ? 4 : 0;
207	root	1.19
208			// bit-toggle to find next child for front-to-back order
209	root	1.50	static unsigned char toggle[8+1]
210	root	1.51	= { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7, 0 };
211	root	1.19
212	root	1.50	unsigned char *next = toggle;
213			do
214	root	1.19	{
215	root	1.51	si ^= *next;
216	root	1.19
217			if (sub[si])
218	root	1.69	visible = visible \| sub[si]->detect_visibility (ctx);
219	root	1.19	}
220	root	1.51	while (*++next);
221
222	root	1.71	if (visible)
223			{
224			if (size ())
225			ctx.vislist.push_back (this);
226	root	1.80
227			ctx.postdepthlist.push_back (this);
228	root	1.71	}
229			else
230	root	1.81	{
231			vs.state = OCCLUDED;
232			ctx.postdepthlist.push_back (this);
233			}
234	root	1.52
235	root	1.69	return visible;
236	root	1.19	}
237
238	root	1.75	void octant::draw_depth (view &ctx)
239	root	1.19	{
240	root	1.54	oct_visibility &vs = (oct_visibility )get_visibility (ctx);
241	root	1.8
242	root	1.79	vs.vismap.resize (size ());
243
244	root	1.80	if (vs.state == PARTIAL \|\| vs.state == OCCLUDED)
245	root	1.75	return;
246
247	root	1.79	for (int i = 0; i < size (); ++i)
248	root	1.50	{
249	root	1.79	entity e = (this)[i];
250			const evis &evs = vs.get_visibility (i, e);
251	root	1.75
252			if (evs.state != OCCLUDED)
253	root	1.54	{
254	root	1.75	if (!ctx.may_draw (e))
255			continue;
256
257			sector center = ((e->a + e->b) >> 1) - ctx.orig;
258			GLfloat z = length (vec3 (center));
259			ctx.pixfact = ctx.perspfact / z;
260
261			ctx.nz_far = max (ctx.nz_far, z + extent);
262			ctx.nz_near = min (ctx.nz_near, z - extent);
263
264			e->draw (ctx);
265	root	1.56	}
266			}
267	root	1.75	}
268
269			void octant::draw_postdepth (view &ctx)
270			{
271			oct_visibility &vs = (oct_visibility )get_visibility (ctx);
272
273	root	1.80	if (vs.state == PARTIAL \|\| vs.state == OCCLUDED)
274	root	1.75	{
275			ctx.begin_occ_query (*this, 0);
276			sector s = orig - ctx.orig;
277			gl::draw_bbox (s - extent, s + extent);
278			ctx.end_occ_query ();
279			}
280	root	1.56	else
281			{
282	root	1.64	int nvis = 0;
283
284	root	1.79	for (int i = 0; i < size (); ++i)
285	root	1.56	{
286	root	1.79	entity e = (this)[i];
287			const evis &evs = vs.get_visibility (i, e);
288	root	1.56
289	root	1.75	if (evs.state == OCCLUDED)
290	root	1.56	{
291	root	1.75	if (!ctx.may_draw (e))
292			continue;
293
294			ctx.begin_occ_query (*this, e);
295			gl::draw_bbox (e->a - ctx.orig, e->b - ctx.orig);
296			ctx.end_occ_query ();
297	root	1.56	}
298			else
299	root	1.75	nvis++;
300			}
301
302			if (nvis == 0 && size ())
303	root	1.80	vs.state = PARTIAL;
304	root	1.75	}
305			}
306
307			void octant::draw_lighted (view &ctx)
308			{
309			oct_visibility &vs = (oct_visibility )get_visibility (ctx);
310
311	root	1.80	if (vs.state == PARTIAL \|\| vs.state == OCCLUDED)
312	root	1.75	return;
313
314	root	1.83	#if 0
315	root	1.80	{
316			static vertex_buffer vb;
317			static index_buffer ib;
318
319			sector s = orig - ctx.orig;
320			sector a = s - extent, b = s + extent;
321
322			vertex_v3f vd[] = {
323			point (a.x, a.y, a.z),
324			point (b.x, a.y, a.z),
325			point (a.x, b.y, a.z),
326			point (b.x, b.y, a.z),
327			point (a.x, a.y, b.z),
328			point (b.x, a.y, b.z),
329			point (a.x, b.y, b.z),
330			point (b.x, b.y, b.z),
331			};
332
333			if (!ib)
334			{
335			static GLushort verts[4*6] = {
336			0, 4, 6, 2, // -x
337			1, 3, 7, 5, // +x
338			0, 1, 5, 4, // -y
339			7, 3, 2, 6, // +y
340			0, 2, 3, 1, // -z
341			4, 5, 7, 6, // +z
342			};
343
344			ib.set (verts, 4*6, GL_STATIC_DRAW_ARB);
345			}
346
347			vb.set (vd, 8, GL_STREAM_DRAW_ARB);
348			vb.bind ();
349			for (int i = 0; i < 6; i++)
350	root	1.81	ib.draw (GL_LINE_LOOP, i*4, 4);
351
352	root	1.80	}
353			#endif
354
355	root	1.79	for (int i = 0; i < size (); ++i)
356	root	1.75	{
357	root	1.79	entity e = (this)[i];
358			evis &evs = vs.get_visibility (i, e);
359	root	1.75
360			if (evs.state != OCCLUDED)
361			{
362	root	1.66	if (!ctx.may_draw (e))
363			continue;
364
365	root	1.75	sector center = ((e->a + e->b) >> 1) - ctx.orig;
366			GLfloat z = length (vec3 (center));
367			ctx.pixfact = ctx.perspfact / z;
368
369			if (ctx.pass->type != LIGHTED
370			\|\| !ctx.first_lighted
371			\|\| evs.last + 0.1 > timer.now)
372			e->draw (ctx);
373			else
374			{
375			evs.last = timer.now;
376			ctx.begin_occ_query (*this, e);
377			e->draw (ctx);
378			ctx.end_occ_query ();
379	root	1.56	}
380	root	1.54	}
381	root	1.50	}
382	root	1.1	}
383	root	1.8
384	root	1.38	void octant::event (occ_query &ev)
385			{
386	root	1.56	oct_visibility &vs = (oct_visibility )get_visibility (ev.ctx);
387			entity e = (entity )ev.id;
388
389			if (e)
390			{
391	root	1.79	for (vector<evis>::iterator i = vs.vismap.begin ();
392			i != vs.vismap.end ();
393			++i)
394			if (i->e == e)
395			{
396			i->state = ev.count ? FULL : OCCLUDED;
397			return;
398			}
399	root	1.56	}
400			else
401	root	1.80	vs.state = ev.count ? (vs.state == PARTIAL ? PARTIAL : FULL) : OCCLUDED;
402	root	1.52	}
403
404	root	1.2