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 {
  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;
  ((oct_visibility *)vs)->state = OCCLUDED;//D
}

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

  vs.vismap.resize (size ());

  if (vs.state == OCCLUDED || vs.state == SUBTREE_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 == 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 (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 = 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 (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 ? FULL : OCCLUDED;
}


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