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);

  //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 (z < 0.F || 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 0
      if (extent < ctx.z_far)
        {
#endif
          ctx.postdepthlist.push_back (this);
          return false;
#if 0
        }
      else
        vs.state == PARTIAL;
#endif
    }
 
  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 0
      if (nvis == 0 && size ())
        vs.state = PARTIAL;
#endif
    }
}

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

#if 0
  if (vs.state == PARTIAL || vs.state == OCCLUDED)
   {
      sector s = orig - ctx.orig;
      gl::draw_bbox (s - extent, s + extent);
      printf ("DLP %p\n", this);//D
   }
#endif

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