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)
    {
      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 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_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.81
Committed:	Fri Nov 26 03:48:40 2004 UTC (19 years, 6 months ago) by root
Content type:	text/plain
Branch:	MAIN
Changes since 1.80:	+14 -5 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, 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	}
77
78	octant::~octant ()
79	{
80	for (fill = 8; fill--; )
81	delete sub[fill];
82	}
83
84	static bool overlap (const sector &orig, uoffs extent, const sector &a, const sector &b)
85	{
86	sector size = (b - a + 1) >> 1;
87	sector center = a + size;
88
89	return abs (orig - center) <= extent + size;
90	}
91
92	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	}
100
101	void octant::add (entity *e)
102	{
103	const sector &a = e->a;
104	const sector &b = e->b;
105
106	uoffs size = max (abs (b - a));
107
108	if (size >= extent >> 4)
109	{
110	if (overlap (orig, extent, a, b))
111	{
112	push_back (e);
113	e->o.push_back (this);
114	}
115	}
116	else
117	{
118	uoffs extent2 = extent >> 1;
119
120	for (int i = 8; i--; )
121	{
122	sector s = offset (orig, i, extent2);
123
124	if (overlap (s, extent2, a, b))
125	{
126	if (!sub[i])
127	{
128	sub[i] = new octant (this, s, extent2);
129	fill++;
130	}
131
132	sub[i]->add (e);
133	}
134	}
135	}
136	}
137
138	void octant::remove (entity *e)
139	{
140	}
141
142	bool octant::detect_visibility (view &ctx) //, bool fully_visible)
143	{
144	ctx.stat1++;//D
145
146	sector centeri = orig - ctx.orig;
147	point centerf = point (centeri);
148
149	GLfloat rad = ctx.diagfact * extent;
150
151	if (!overlap (ctx.frustum.c, sphere (centerf, rad)))
152	return false;
153
154	oct_visibility &vs = (oct_visibility )get_visibility (ctx);
155
156	#if 0
157	if (max (abs (centeri)) <= extent)
158	;
159	else
160	{
161	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
167	#if 0
168	GLfloat fd = distance (ctx.frustum.f, centerf);
169
170	if (fd < -(ctx.c_far - ctx.z_far) -rad * 3.F)
171	return false;
172	#endif
173	}
174	#endif
175
176	// very important, optimize?
177	GLfloat z = ctx.z_near + distance (ctx.frustum.n, centerf) + rad;
178	if (ctx.perspfact * extent / z < 10.) // very crude "too small to see" check
179	return false;
180
181	#if 0
182	if (vs.state == PARTIAL \|\| vs.state == FULL)
183	ctx.nc_far = max (ctx.nc_far, z);
184	#endif
185
186	if (vs.state == OCCLUDED)
187	{
188	if (extent < ctx.z_far)
189	{
190	ctx.postdepthlist.push_back (this);
191	return false;
192	}
193	else
194	vs.state == PARTIAL;
195	}
196
197	bool visible = size () && vs.state == FULL;
198
199	// node to start with
200	unsigned char si = centeri.x > 0 ? 1 : 0
201	\| centeri.y > 0 ? 2 : 0
202	\| centeri.z > 0 ? 4 : 0;
203
204	// bit-toggle to find next child for front-to-back order
205	static unsigned char toggle[8+1]
206	= { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7, 0 };
207
208	unsigned char *next = toggle;
209	do
210	{
211	si ^= *next;
212
213	if (sub[si])
214	visible = visible \| sub[si]->detect_visibility (ctx);
215	}
216	while (*++next);
217
218	if (visible)
219	{
220	if (size ())
221	ctx.vislist.push_back (this);
222
223	ctx.postdepthlist.push_back (this);
224	}
225	else
226	{
227	vs.state = OCCLUDED;
228	ctx.postdepthlist.push_back (this);
229	}
230
231	return visible;
232	}
233
234	void octant::draw_depth (view &ctx)
235	{
236	oct_visibility &vs = (oct_visibility )get_visibility (ctx);
237
238	vs.vismap.resize (size ());
239
240	if (vs.state == PARTIAL \|\| vs.state == OCCLUDED)
241	return;
242
243	for (int i = 0; i < size (); ++i)
244	{
245	entity e = (this)[i];
246	const evis &evs = vs.get_visibility (i, e);
247
248	if (evs.state != OCCLUDED)
249	{
250	if (!ctx.may_draw (e))
251	continue;
252
253	sector center = ((e->a + e->b) >> 1) - ctx.orig;
254	GLfloat z = length (vec3 (center));
255	ctx.pixfact = ctx.perspfact / z;
256
257	ctx.nz_far = max (ctx.nz_far, z + extent);
258	ctx.nz_near = min (ctx.nz_near, z - extent);
259
260	e->draw (ctx);
261	}
262	}
263	}
264
265	void octant::draw_postdepth (view &ctx)
266	{
267	oct_visibility &vs = (oct_visibility )get_visibility (ctx);
268
269	if (vs.state == PARTIAL \|\| vs.state == OCCLUDED)
270	{
271	ctx.begin_occ_query (*this, 0);
272	sector s = orig - ctx.orig;
273	gl::draw_bbox (s - extent, s + extent);
274	ctx.end_occ_query ();
275	}
276	else
277	{
278	int nvis = 0;
279
280	for (int i = 0; i < size (); ++i)
281	{
282	entity e = (this)[i];
283	const evis &evs = vs.get_visibility (i, e);
284
285	if (evs.state == OCCLUDED)
286	{
287	if (!ctx.may_draw (e))
288	continue;
289
290	ctx.begin_occ_query (*this, e);
291	gl::draw_bbox (e->a - ctx.orig, e->b - ctx.orig);
292	ctx.end_occ_query ();
293	}
294	else
295	nvis++;
296	}
297
298	if (nvis == 0 && size ())
299	vs.state = PARTIAL;
300	}
301	}
302
303	void octant::draw_lighted (view &ctx)
304	{
305	oct_visibility &vs = (oct_visibility )get_visibility (ctx);
306
307	if (vs.state == PARTIAL \|\| vs.state == OCCLUDED)
308	return;
309
310	#if 1
311	{
312	static vertex_buffer vb;
313	static index_buffer ib;
314
315	sector s = orig - ctx.orig;
316	sector a = s - extent, b = s + extent;
317
318	vertex_v3f vd[] = {
319	point (a.x, a.y, a.z),
320	point (b.x, a.y, a.z),
321	point (a.x, b.y, a.z),
322	point (b.x, b.y, a.z),
323	point (a.x, a.y, b.z),
324	point (b.x, a.y, b.z),
325	point (a.x, b.y, b.z),
326	point (b.x, b.y, b.z),
327	};
328
329	if (!ib)
330	{
331	static GLushort verts[4*6] = {
332	0, 4, 6, 2, // -x
333	1, 3, 7, 5, // +x
334	0, 1, 5, 4, // -y
335	7, 3, 2, 6, // +y
336	0, 2, 3, 1, // -z
337	4, 5, 7, 6, // +z
338	};
339
340	ib.set (verts, 4*6, GL_STATIC_DRAW_ARB);
341	}
342
343	vb.set (vd, 8, GL_STREAM_DRAW_ARB);
344	vb.bind ();
345	for (int i = 0; i < 6; i++)
346	ib.draw (GL_LINE_LOOP, i*4, 4);
347
348	}
349	#endif
350
351	for (int i = 0; i < size (); ++i)
352	{
353	entity e = (this)[i];
354	evis &evs = vs.get_visibility (i, e);
355
356	if (evs.state != OCCLUDED)
357	{
358	if (!ctx.may_draw (e))
359	continue;
360
361	sector center = ((e->a + e->b) >> 1) - ctx.orig;
362	GLfloat z = length (vec3 (center));
363	ctx.pixfact = ctx.perspfact / z;
364
365	if (ctx.pass->type != LIGHTED
366	\|\| !ctx.first_lighted
367	\|\| evs.last + 0.1 > timer.now)
368	e->draw (ctx);
369	else
370	{
371	evs.last = timer.now;
372	ctx.begin_occ_query (*this, e);
373	e->draw (ctx);
374	ctx.end_occ_query ();
375	}
376	}
377	}
378	}
379
380	void octant::event (occ_query &ev)
381	{
382	oct_visibility &vs = (oct_visibility )get_visibility (ev.ctx);
383	entity e = (entity )ev.id;
384
385	if (e)
386	{
387	for (vector<evis>::iterator i = vs.vismap.begin ();
388	i != vs.vismap.end ();
389	++i)
390	if (i->e == e)
391	{
392	i->state = ev.count ? FULL : OCCLUDED;
393	return;
394	}
395	}
396	else
397	vs.state = ev.count ? (vs.state == PARTIAL ? PARTIAL : FULL) : OCCLUDED;
398	}
399
400