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 0
  if (!overlap (ctx.frustum.c, sphere (centerf, rad)))
    return false;
#endif

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