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

  //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 (z < 0.F || 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 && max (centeri) < extent)
    vs.state = PARTIAL;

  if (vs.state == OCCLUDED)
    {
#if 0
      if (extent < ctx.z_far)
        {
#endif
          ctx.postdepthlist.push_back (this);
          return false;
#if 0
        }
      else
        vs.state == PARTIAL;
#endif
    }
 
  bool visible = size () && vs.state != OCCLUDED;

  // 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 || 1)
    {
      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 0
  if (vs.state == PARTIAL || vs.state == OCCLUDED)
    return;
#endif

  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 1
      if (nvis == 0 && size ())
        vs.state = PARTIAL;
#endif
    }
}

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

#if 1
  if (vs.state == PARTIAL || vs.state == OCCLUDED)
   {
     if (orig.z + extent < -10000000) {
      sector s = orig - ctx.orig;
      gl::draw_bbox (s - extent, s + extent);
      //printf ("DLP %ld %ld %ld (%ld)\n", orig.x, orig.y, orig.z, extent);//D
     }
   }
#endif

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