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