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, SMALL, OCCLUDED, SUBTREE_OCCLUDED };

struct evis {
  visibility_state state;
  double last; // time of last check
  evis () : last(0.), state(FULL) { };
};

struct oct_visibility : visibility_base
{
  typedef map<entity *, evis> evismap;
  evismap vismap;

  visibility_state state;

  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;

  if (overlap (orig, extent, a, b))
    {
      uoffs extent2 = extent >> 1;
      uoffs size = max (abs (b - a));

      if (size >= extent2)
        {
          push_back (e);
          e->o.push_back (this);
          return;
        }

      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)
{
  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 (max (abs (centeri)) <= extent)
    vs.state = PARTIAL;
  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
    }

  // very important, optimize?
  GLfloat z = ctx.z_near + distance (ctx.frustum.n, centerf) + rad;
  if (ctx.perspfact * extent / z < 1.) // 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 == SUBTREE_OCCLUDED)
    {
      ctx.vislist.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);
    }
  else
    vs.state = SUBTREE_OCCLUDED;

  return visible;
}

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

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

  for (iterator i = begin (); i != end (); )
    {
      entity *e = *i++;

      evis &evs = vs.vismap[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 == OCCLUDED || vs.state == SUBTREE_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 (iterator i = begin (); i != end (); )
        {
          entity *e = *i++;

          evis &evs = vs.vismap[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 = OCCLUDED;
    }
}

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

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

  for (iterator i = begin (); i != end (); )
    {
      entity *e = *i++;

      evis &evs = vs.vismap[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)
    {
      evis &evs = vs.vismap[e];
      evs.state = ev.count ? FULL : OCCLUDED;
    }
  else
    vs.state = ev.count ? FULL : OCCLUDED;
}


Revision:	1.78
Committed:	Wed Nov 10 01:57:15 2004 UTC (19 years, 7 months ago) by root
Content type:	text/plain
Branch:	MAIN
Changes since 1.77:	+1 -4 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.72	enum visibility_state { FULL, PARTIAL, SMALL, OCCLUDED, SUBTREE_OCCLUDED };
13	root	1.56
14	root	1.54	struct evis {
15	root	1.56	visibility_state state;
16	root	1.54	double last; // time of last check
17			evis () : last(0.), state(FULL) { };
18			};
19
20	root	1.52	struct oct_visibility : visibility_base
21			{
22	root	1.54	typedef map<entity *, evis> evismap;
23			evismap vismap;
24	root	1.52
25	root	1.56	visibility_state state;
26	root	1.52
27			oct_visibility (octant &oct)
28	root	1.54	: state(FULL)
29	root	1.52	{
30			}
31			};
32
33	root	1.75	octant world(0, sector (0, 0, 0), MAXEXTENT);
34	root	1.8
35			octant::octant (octant *parent, const sector &orig, uoffs extent)
36	root	1.54	: parent(parent)
37			, orig(orig)
38			, extent(extent)
39	root	1.8	{
40			for (fill = 8; fill--; )
41			sub[fill] = 0;
42	root	1.2	}
43
44	root	1.53	visibility_base *octant::new_visibility ()
45			{
46			return new oct_visibility (*this);
47			}
48
49			void octant::clear_visibility (visibility_base *vs)
50			{
51			((oct_visibility *)vs)->vismap.clear ();
52	root	1.75	((oct_visibility *)vs)->state = FULL;
53	root	1.53	}
54	root	1.65
55	root	1.2	octant::~octant ()
56			{
57			for (fill = 8; fill--; )
58			delete sub[fill];
59			}
60
61	root	1.75	static bool overlap (const sector &orig, uoffs extent, const sector &a, const sector &b)
62	root	1.4	{
63	root	1.75	sector size = (b - a + 1) >> 1;
64			sector center = a + size;
65	root	1.4
66	root	1.75	return abs (orig - center) <= extent + size;
67			}
68	root	1.33
69	root	1.75	static sector offset (const sector &s, int subindex, uoffs extent)
70			{
71			return sector (
72			s.x + (subindex & 1 ? extent : -extent),
73			s.y + (subindex & 2 ? extent : -extent),
74			s.z + (subindex & 4 ? extent : -extent)
75			);
76	root	1.4	}
77
78	root	1.32	void octant::add (entity *e)
79	root	1.2	{
80	root	1.32	const sector &a = e->a;
81			const sector &b = e->b;
82	root	1.7
83	root	1.32	if (overlap (orig, extent, a, b))
84	root	1.4	{
85	root	1.54	uoffs extent2 = extent >> 1;
86	root	1.34	uoffs size = max (abs (b - a));
87	root	1.32
88	root	1.75	if (size >= extent2)
89	root	1.8	{
90			push_back (e);
91			e->o.push_back (this);
92			return;
93			}
94	root	1.5
95	root	1.8	for (int i = 8; i--; )
96	root	1.5	{
97	root	1.75	sector s = offset (orig, i, extent2);
98	root	1.32
99			if (overlap (s, extent2, a, b))
100	root	1.5	{
101	root	1.8	if (!sub[i])
102	root	1.50	{
103			sub[i] = new octant (this, s, extent2);
104			fill++;
105			}
106	root	1.8
107			sub[i]->add (e);
108	root	1.5	}
109	root	1.8	}
110	root	1.4	}
111	root	1.2	}
112	root	1.1
113	root	1.32	void octant::remove (entity *e)
114	root	1.1	{
115			}
116
117	root	1.62	bool octant::detect_visibility (view &ctx)
118	root	1.1	{
119	root	1.77	ctx.stat1++;//D
120
121	root	1.75	sector centeri = orig - ctx.orig;
122			point centerf = point (centeri);
123	root	1.51
124	root	1.75	GLfloat rad = ctx.diagfact * extent;
125	root	1.43
126	root	1.59	if (!overlap (ctx.frustum.c, sphere (centerf, rad)))
127			return false;
128	root	1.65
129			oct_visibility &vs = (oct_visibility )get_visibility (ctx);
130	root	1.59
131	root	1.75	if (max (abs (centeri)) <= extent)
132	root	1.56	vs.state = PARTIAL;
133	root	1.10	else
134			{
135	root	1.59	if (distance (ctx.frustum.t, centerf) < -rad) return false;
136			if (distance (ctx.frustum.b, centerf) < -rad) return false;
137			if (distance (ctx.frustum.l, centerf) < -rad) return false;
138			if (distance (ctx.frustum.r, centerf) < -rad) return false;
139			if (distance (ctx.frustum.n, centerf) < -rad) return false;
140	root	1.25
141	root	1.59	#if 0
142			GLfloat fd = distance (ctx.frustum.f, centerf);
143	root	1.25
144	root	1.47	if (fd < -(ctx.c_far - ctx.z_far) -rad * 3.F)
145	root	1.52	return false;
146	root	1.58	#endif
147	root	1.10	}
148	root	1.8
149	root	1.75	// very important, optimize?
150	root	1.59	GLfloat z = ctx.z_near + distance (ctx.frustum.n, centerf) + rad;
151	root	1.58	if (ctx.perspfact * extent / z < 1.) // very crude "too small to see" check
152			return false;
153	root	1.45
154	root	1.59	#if 0
155	root	1.56	if (vs.state == PARTIAL \|\| vs.state == FULL)
156	root	1.45	ctx.nc_far = max (ctx.nc_far, z);
157	root	1.59	#endif
158	root	1.45
159	root	1.72	if (vs.state == SUBTREE_OCCLUDED)
160			{
161			ctx.vislist.push_back (this);
162			return false;
163			}
164
165	root	1.74	bool visible = size () && (vs.state == PARTIAL \|\| vs.state == FULL);
166
167	root	1.51	// node to start with
168			unsigned char si = centeri.x > 0 ? 1 : 0
169			\| centeri.y > 0 ? 2 : 0
170			\| centeri.z > 0 ? 4 : 0;
171	root	1.19
172			// bit-toggle to find next child for front-to-back order
173	root	1.50	static unsigned char toggle[8+1]
174	root	1.51	= { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7, 0 };
175	root	1.19
176	root	1.50	unsigned char *next = toggle;
177			do
178	root	1.19	{
179	root	1.51	si ^= *next;
180	root	1.19
181			if (sub[si])
182	root	1.69	visible = visible \| sub[si]->detect_visibility (ctx);
183	root	1.19	}
184	root	1.51	while (*++next);
185
186	root	1.71	if (visible)
187			{
188			if (size ())
189			ctx.vislist.push_back (this);
190			}
191			else
192	root	1.78	vs.state = SUBTREE_OCCLUDED;
193	root	1.52
194	root	1.69	return visible;
195	root	1.19	}
196
197	root	1.75	void octant::draw_depth (view &ctx)
198	root	1.19	{
199	root	1.54	oct_visibility &vs = (oct_visibility )get_visibility (ctx);
200	root	1.8
201	root	1.72	if (vs.state == OCCLUDED \|\| vs.state == SUBTREE_OCCLUDED)
202	root	1.75	return;
203
204			for (iterator i = begin (); i != end (); )
205	root	1.50	{
206	root	1.75	entity e = i++;
207
208			evis &evs = vs.vismap[e];
209
210			if (evs.state != OCCLUDED)
211	root	1.54	{
212	root	1.75	if (!ctx.may_draw (e))
213			continue;
214
215			sector center = ((e->a + e->b) >> 1) - ctx.orig;
216			GLfloat z = length (vec3 (center));
217			ctx.pixfact = ctx.perspfact / z;
218
219			ctx.nz_far = max (ctx.nz_far, z + extent);
220			ctx.nz_near = min (ctx.nz_near, z - extent);
221
222			e->draw (ctx);
223	root	1.56	}
224			}
225	root	1.75	}
226
227			void octant::draw_postdepth (view &ctx)
228			{
229			oct_visibility &vs = (oct_visibility )get_visibility (ctx);
230
231			if (vs.state == OCCLUDED \|\| vs.state == SUBTREE_OCCLUDED)
232			{
233			ctx.begin_occ_query (*this, 0);
234			sector s = orig - ctx.orig;
235			gl::draw_bbox (s - extent, s + extent);
236			ctx.end_occ_query ();
237			}
238	root	1.56	else
239			{
240	root	1.64	int nvis = 0;
241
242	root	1.57	for (iterator i = begin (); i != end (); )
243	root	1.56	{
244	root	1.57	entity e = i++;
245	root	1.56
246			evis &evs = vs.vismap[e];
247
248	root	1.75	if (evs.state == OCCLUDED)
249	root	1.56	{
250	root	1.75	if (!ctx.may_draw (e))
251			continue;
252
253			ctx.begin_occ_query (*this, e);
254			gl::draw_bbox (e->a - ctx.orig, e->b - ctx.orig);
255			ctx.end_occ_query ();
256	root	1.56	}
257			else
258	root	1.75	nvis++;
259			}
260
261			if (nvis == 0 && size ())
262			vs.state = OCCLUDED;
263			}
264			}
265
266			void octant::draw_lighted (view &ctx)
267			{
268			oct_visibility &vs = (oct_visibility )get_visibility (ctx);
269
270			if (vs.state == OCCLUDED \|\| vs.state == SUBTREE_OCCLUDED)
271			return;
272
273			for (iterator i = begin (); i != end (); )
274			{
275			entity e = i++;
276
277			evis &evs = vs.vismap[e];
278
279			if (evs.state != OCCLUDED)
280			{
281	root	1.66	if (!ctx.may_draw (e))
282			continue;
283
284	root	1.75	sector center = ((e->a + e->b) >> 1) - ctx.orig;
285			GLfloat z = length (vec3 (center));
286			ctx.pixfact = ctx.perspfact / z;
287
288			if (ctx.pass->type != LIGHTED
289			\|\| !ctx.first_lighted
290			\|\| evs.last + 0.1 > timer.now)
291			e->draw (ctx);
292			else
293			{
294			evs.last = timer.now;
295			ctx.begin_occ_query (*this, e);
296			e->draw (ctx);
297			ctx.end_occ_query ();
298	root	1.56	}
299	root	1.54	}
300	root	1.50	}
301	root	1.1	}
302	root	1.8
303	root	1.38	void octant::event (occ_query &ev)
304			{
305	root	1.56	oct_visibility &vs = (oct_visibility )get_visibility (ev.ctx);
306			entity e = (entity )ev.id;
307
308			if (e)
309			{
310			evis &evs = vs.vismap[e];
311			evs.state = ev.count ? FULL : OCCLUDED;
312			}
313			else
314	root	1.64	vs.state = ev.count ? FULL : OCCLUDED;
315	root	1.52	}
316
317	root	1.2