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)
    {
      ctx.postdepthlist.push_back (this);
      return false;
    }
 
  bool visible = size () && (vs.state == PARTIAL || 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;

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