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 (!overlap (ctx.frustum.c, sphere (centerf, rad)))
    return false;

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

#if 0
  if (max (abs (centeri)) <= extent)
    ;
  else
    {
      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
    }
#endif

  // very important, optimize?
  GLfloat z = ctx.z_near + distance (ctx.frustum.n, 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 1
  {
    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.81
Committed:	Fri Nov 26 03:48:40 2004 UTC (19 years, 7 months ago) by root
Content type:	text/plain
Branch:	MAIN
Changes since 1.80:	+14 -5 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.59	if (!overlap (ctx.frustum.c, sphere (centerf, rad)))
152			return false;
153	root	1.65
154			oct_visibility &vs = (oct_visibility )get_visibility (ctx);
155	root	1.59
156	root	1.80	#if 0
157	root	1.75	if (max (abs (centeri)) <= extent)
158	root	1.80	;
159	root	1.10	else
160			{
161	root	1.59	if (distance (ctx.frustum.t, centerf) < -rad) return false;
162			if (distance (ctx.frustum.b, centerf) < -rad) return false;
163			if (distance (ctx.frustum.l, centerf) < -rad) return false;
164			if (distance (ctx.frustum.r, centerf) < -rad) return false;
165			if (distance (ctx.frustum.n, centerf) < -rad) return false;
166	root	1.25
167	root	1.59	#if 0
168			GLfloat fd = distance (ctx.frustum.f, centerf);
169	root	1.25
170	root	1.47	if (fd < -(ctx.c_far - ctx.z_far) -rad * 3.F)
171	root	1.52	return false;
172	root	1.58	#endif
173	root	1.10	}
174	root	1.80	#endif
175	root	1.8
176	root	1.75	// very important, optimize?
177	root	1.59	GLfloat z = ctx.z_near + distance (ctx.frustum.n, centerf) + rad;
178	root	1.80	if (ctx.perspfact * extent / z < 10.) // very crude "too small to see" check
179	root	1.58	return false;
180	root	1.45
181	root	1.59	#if 0
182	root	1.56	if (vs.state == PARTIAL \|\| vs.state == FULL)
183	root	1.45	ctx.nc_far = max (ctx.nc_far, z);
184	root	1.59	#endif
185	root	1.45
186	root	1.80	if (vs.state == OCCLUDED)
187	root	1.72	{
188	root	1.81	if (extent < ctx.z_far)
189			{
190			ctx.postdepthlist.push_back (this);
191			return false;
192			}
193			else
194			vs.state == PARTIAL;
195	root	1.72	}
196
197	root	1.81	bool visible = size () && vs.state == FULL;
198	root	1.74
199	root	1.51	// node to start with
200			unsigned char si = centeri.x > 0 ? 1 : 0
201			\| centeri.y > 0 ? 2 : 0
202			\| centeri.z > 0 ? 4 : 0;
203	root	1.19
204			// bit-toggle to find next child for front-to-back order
205	root	1.50	static unsigned char toggle[8+1]
206	root	1.51	= { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7, 0 };
207	root	1.19
208	root	1.50	unsigned char *next = toggle;
209			do
210	root	1.19	{
211	root	1.51	si ^= *next;
212	root	1.19
213			if (sub[si])
214	root	1.69	visible = visible \| sub[si]->detect_visibility (ctx);
215	root	1.19	}
216	root	1.51	while (*++next);
217
218	root	1.71	if (visible)
219			{
220			if (size ())
221			ctx.vislist.push_back (this);
222	root	1.80
223			ctx.postdepthlist.push_back (this);
224	root	1.71	}
225			else
226	root	1.81	{
227			vs.state = OCCLUDED;
228			ctx.postdepthlist.push_back (this);
229			}
230	root	1.52
231	root	1.69	return visible;
232	root	1.19	}
233
234	root	1.75	void octant::draw_depth (view &ctx)
235	root	1.19	{
236	root	1.54	oct_visibility &vs = (oct_visibility )get_visibility (ctx);
237	root	1.8
238	root	1.79	vs.vismap.resize (size ());
239
240	root	1.80	if (vs.state == PARTIAL \|\| vs.state == OCCLUDED)
241	root	1.75	return;
242
243	root	1.79	for (int i = 0; i < size (); ++i)
244	root	1.50	{
245	root	1.79	entity e = (this)[i];
246			const evis &evs = vs.get_visibility (i, e);
247	root	1.75
248			if (evs.state != OCCLUDED)
249	root	1.54	{
250	root	1.75	if (!ctx.may_draw (e))
251			continue;
252
253			sector center = ((e->a + e->b) >> 1) - ctx.orig;
254			GLfloat z = length (vec3 (center));
255			ctx.pixfact = ctx.perspfact / z;
256
257			ctx.nz_far = max (ctx.nz_far, z + extent);
258			ctx.nz_near = min (ctx.nz_near, z - extent);
259
260			e->draw (ctx);
261	root	1.56	}
262			}
263	root	1.75	}
264
265			void octant::draw_postdepth (view &ctx)
266			{
267			oct_visibility &vs = (oct_visibility )get_visibility (ctx);
268
269	root	1.80	if (vs.state == PARTIAL \|\| vs.state == OCCLUDED)
270	root	1.75	{
271			ctx.begin_occ_query (*this, 0);
272			sector s = orig - ctx.orig;
273			gl::draw_bbox (s - extent, s + extent);
274			ctx.end_occ_query ();
275			}
276	root	1.56	else
277			{
278	root	1.64	int nvis = 0;
279
280	root	1.79	for (int i = 0; i < size (); ++i)
281	root	1.56	{
282	root	1.79	entity e = (this)[i];
283			const evis &evs = vs.get_visibility (i, e);
284	root	1.56
285	root	1.75	if (evs.state == OCCLUDED)
286	root	1.56	{
287	root	1.75	if (!ctx.may_draw (e))
288			continue;
289
290			ctx.begin_occ_query (*this, e);
291			gl::draw_bbox (e->a - ctx.orig, e->b - ctx.orig);
292			ctx.end_occ_query ();
293	root	1.56	}
294			else
295	root	1.75	nvis++;
296			}
297
298			if (nvis == 0 && size ())
299	root	1.80	vs.state = PARTIAL;
300	root	1.75	}
301			}
302
303			void octant::draw_lighted (view &ctx)
304			{
305			oct_visibility &vs = (oct_visibility )get_visibility (ctx);
306
307	root	1.80	if (vs.state == PARTIAL \|\| vs.state == OCCLUDED)
308	root	1.75	return;
309
310	root	1.80	#if 1
311			{
312			static vertex_buffer vb;
313			static index_buffer ib;
314
315			sector s = orig - ctx.orig;
316			sector a = s - extent, b = s + extent;
317
318			vertex_v3f vd[] = {
319			point (a.x, a.y, a.z),
320			point (b.x, a.y, a.z),
321			point (a.x, b.y, a.z),
322			point (b.x, b.y, a.z),
323			point (a.x, a.y, b.z),
324			point (b.x, a.y, b.z),
325			point (a.x, b.y, b.z),
326			point (b.x, b.y, b.z),
327			};
328
329			if (!ib)
330			{
331			static GLushort verts[4*6] = {
332			0, 4, 6, 2, // -x
333			1, 3, 7, 5, // +x
334			0, 1, 5, 4, // -y
335			7, 3, 2, 6, // +y
336			0, 2, 3, 1, // -z
337			4, 5, 7, 6, // +z
338			};
339
340			ib.set (verts, 4*6, GL_STATIC_DRAW_ARB);
341			}
342
343			vb.set (vd, 8, GL_STREAM_DRAW_ARB);
344			vb.bind ();
345			for (int i = 0; i < 6; i++)
346	root	1.81	ib.draw (GL_LINE_LOOP, i*4, 4);
347
348	root	1.80	}
349			#endif
350
351	root	1.79	for (int i = 0; i < size (); ++i)
352	root	1.75	{
353	root	1.79	entity e = (this)[i];
354			evis &evs = vs.get_visibility (i, e);
355	root	1.75
356			if (evs.state != OCCLUDED)
357			{
358	root	1.66	if (!ctx.may_draw (e))
359			continue;
360
361	root	1.75	sector center = ((e->a + e->b) >> 1) - ctx.orig;
362			GLfloat z = length (vec3 (center));
363			ctx.pixfact = ctx.perspfact / z;
364
365			if (ctx.pass->type != LIGHTED
366			\|\| !ctx.first_lighted
367			\|\| evs.last + 0.1 > timer.now)
368			e->draw (ctx);
369			else
370			{
371			evs.last = timer.now;
372			ctx.begin_occ_query (*this, e);
373			e->draw (ctx);
374			ctx.end_occ_query ();
375	root	1.56	}
376	root	1.54	}
377	root	1.50	}
378	root	1.1	}
379	root	1.8
380	root	1.38	void octant::event (occ_query &ev)
381			{
382	root	1.56	oct_visibility &vs = (oct_visibility )get_visibility (ev.ctx);
383			entity e = (entity )ev.id;
384
385			if (e)
386			{
387	root	1.79	for (vector<evis>::iterator i = vs.vismap.begin ();
388			i != vs.vismap.end ();
389			++i)
390			if (i->e == e)
391			{
392			i->state = ev.count ? FULL : OCCLUDED;
393			return;
394			}
395	root	1.56	}
396			else
397	root	1.80	vs.state = ev.count ? (vs.state == PARTIAL ? PARTIAL : FULL) : OCCLUDED;
398	root	1.52	}
399
400	root	1.2