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)
{
  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;
      ctx.vislist.push_back (this);
    }

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