libgender/oct.C

#include <cstdlib>

#include <vector>

using namespace std;

#include "opengl.h"

#include "oct.h"
#include "view.h"
#include "entity.h"
#include "material.h" //DEBUG

enum visibility_state {
  PARTIAL,  // surrounding the viewpoint
  FULL,     // in frustum
  OCCLUDED, // in frustom, but occluded
};

struct evis {
  entity *e;
  visibility_state state;
  double next; // time of next check

  void clear ()
  {
    next = 0.;
    state = FULL;
  }

  evis ()
  {
    clear ();
  }
};

struct oct_visibility : visibility_base
{
  vector<evis> vismap;

  visibility_state state;
  bool vis;

  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), vis (true)
  {
  }
};

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

      return false;
    }
 
  //bool visible = size () && vs.state != OCCLUDED;
  bool visible = false;

  // 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.postdepthlist.push_back (this);
          if (vs.vis)
            ctx.vislist.push_back (this);
        }

      vs.state = FULL;

      return true;
    }
  else if (vs.state == OCCLUDED)
    {
      ctx.postdepthlist.push_back (this);

      return false;
    }
  else if (size())
    {
      if (vs.vis)
        {
          ctx.postdepthlist.push_back (this);
          ctx.vislist.push_back (this);
        }
      else
        vs.state = OCCLUDED;

      return true;
    }
  else
    {
      return vs.state != PARTIAL;
    }
}

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

  vs.vismap.resize (size ());

  if (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 == OCCLUDED || !vs.vis)
    {
      ctx.begin_occ_query (*this, 0);
      sector s = orig - ctx.orig;
      gl::draw_bbox (s - extent, s + extent);
      ctx.end_occ_query ();
    }
  else
    {
      vs.vis = false;

      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
            vs.vis = true;
        }
    }
}

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

#if 0
  if (vs.state == FULL || vs.state == OCCLUDED)
   {
    sector s = orig - ctx.orig;
    debugmat->enable (ctx);
  if (max (s) >= extent)
    gl::draw_bbox (s - extent, s + extent);
    debugmat->disable (ctx);
    //printf ("DLP %ld %ld %ld (%ld)\n", orig.x, orig.y, orig.z, extent);//D
   }
#endif

  if (vs.state == 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.first_lighted
              || evs.next > timer.now)
            e->draw (ctx);
          else
            {
              evs.next = timer.now + 0.2;
              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)
    {
#if 1
      for (vector<evis>::iterator i = vs.vismap.begin ();
           i != vs.vismap.end ();
           ++i)
        if (i->e == e)
          {
            i->state = ev.count ? FULL : OCCLUDED;
            return;
          }
#endif
    }
  else
    {
      vs.state = ev.count ? FULL : OCCLUDED;
      vs.vis = ev.count ? true : false;
    }
}


Revision:	1.92
Committed:	Wed Aug 10 02:37:11 2005 UTC (18 years, 10 months ago) by root
Content type:	text/plain
Branch:	MAIN
Changes since 1.91:	+14 -9 lines
Log Message:	* empty log message *
#	User	Rev	Content
1	root	1.1	#include <cstdlib>
2
3	root	1.8	#include <vector>
4	root	1.91
5	root	1.8	using namespace std;
6
7	root	1.48	#include "opengl.h"
8	root	1.8
9	root	1.1	#include "oct.h"
10	root	1.8	#include "view.h"
11	root	1.2	#include "entity.h"
12	root	1.89	#include "material.h" //DEBUG
13	root	1.2
14	root	1.90	enum visibility_state {
15			PARTIAL, // surrounding the viewpoint
16			FULL, // in frustum
17			OCCLUDED, // in frustom, but occluded
18			};
19	root	1.56
20	root	1.54	struct evis {
21	root	1.79	entity *e;
22	root	1.56	visibility_state state;
23	root	1.92	double next; // time of next check
24	root	1.79
25			void clear ()
26			{
27	root	1.92	next = 0.;
28	root	1.79	state = FULL;
29			}
30
31			evis ()
32			{
33			clear ();
34			}
35	root	1.54	};
36
37	root	1.52	struct oct_visibility : visibility_base
38			{
39	root	1.79	vector<evis> vismap;
40	root	1.52
41	root	1.56	visibility_state state;
42	root	1.91	bool vis;
43	root	1.52
44	root	1.79	evis &get_visibility (int i, entity *e)
45			{
46			evis &evs = vismap [i];
47
48			if (evs.e != e)
49			{
50			evs.clear ();
51			evs.e = e;
52			}
53
54			return evs;
55			}
56
57	root	1.52	oct_visibility (octant &oct)
58	root	1.91	: state (FULL), vis (true)
59	root	1.52	{
60			}
61			};
62
63	root	1.75	octant world(0, sector (0, 0, 0), MAXEXTENT);
64	root	1.8
65			octant::octant (octant *parent, const sector &orig, uoffs extent)
66	root	1.54	: parent(parent)
67			, orig(orig)
68			, extent(extent)
69	root	1.8	{
70			for (fill = 8; fill--; )
71			sub[fill] = 0;
72	root	1.2	}
73
74	root	1.53	visibility_base *octant::new_visibility ()
75			{
76			return new oct_visibility (*this);
77			}
78
79			void octant::clear_visibility (visibility_base *vs)
80			{
81			((oct_visibility *)vs)->vismap.clear ();
82	root	1.75	((oct_visibility *)vs)->state = FULL;
83	root	1.53	}
84	root	1.65
85	root	1.2	octant::~octant ()
86			{
87			for (fill = 8; fill--; )
88			delete sub[fill];
89			}
90
91	root	1.75	static bool overlap (const sector &orig, uoffs extent, const sector &a, const sector &b)
92	root	1.4	{
93	root	1.75	sector size = (b - a + 1) >> 1;
94			sector center = a + size;
95	root	1.4
96	root	1.75	return abs (orig - center) <= extent + size;
97			}
98	root	1.33
99	root	1.75	static sector offset (const sector &s, int subindex, uoffs extent)
100			{
101			return sector (
102			s.x + (subindex & 1 ? extent : -extent),
103			s.y + (subindex & 2 ? extent : -extent),
104			s.z + (subindex & 4 ? extent : -extent)
105			);
106	root	1.4	}
107
108	root	1.32	void octant::add (entity *e)
109	root	1.2	{
110	root	1.32	const sector &a = e->a;
111			const sector &b = e->b;
112	root	1.7
113	root	1.80	uoffs size = max (abs (b - a));
114
115			if (size >= extent >> 4)
116	root	1.4	{
117	root	1.80	if (overlap (orig, extent, a, b))
118	root	1.8	{
119			push_back (e);
120			e->o.push_back (this);
121			}
122	root	1.80	}
123			else
124			{
125			uoffs extent2 = extent >> 1;
126	root	1.5
127	root	1.8	for (int i = 8; i--; )
128	root	1.5	{
129	root	1.75	sector s = offset (orig, i, extent2);
130	root	1.32
131			if (overlap (s, extent2, a, b))
132	root	1.5	{
133	root	1.8	if (!sub[i])
134	root	1.50	{
135			sub[i] = new octant (this, s, extent2);
136			fill++;
137			}
138	root	1.8
139			sub[i]->add (e);
140	root	1.5	}
141	root	1.8	}
142	root	1.4	}
143	root	1.2	}
144	root	1.1
145	root	1.32	void octant::remove (entity *e)
146	root	1.1	{
147			}
148
149	root	1.80	bool octant::detect_visibility (view &ctx) //, bool fully_visible)
150	root	1.1	{
151	root	1.75	sector centeri = orig - ctx.orig;
152			point centerf = point (centeri);
153	root	1.51
154	root	1.75	GLfloat rad = ctx.diagfact * extent;
155	root	1.43
156	root	1.59	if (!overlap (ctx.frustum.c, sphere (centerf, rad)))
157			return false;
158	root	1.65
159			oct_visibility &vs = (oct_visibility )get_visibility (ctx);
160	root	1.59
161	root	1.90	if (max (centeri) < extent)
162			vs.state = PARTIAL;
163	root	1.10	else
164			{
165	root	1.90	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	root	1.25
172	root	1.59	#if 0
173	root	1.91	GLfloat fd = distance (ctx.frustum.f, centerf);
174	root	1.25
175	root	1.91	if (fd < -(ctx.c_far - ctx.z_far) -rad * 3.F)
176			return false;
177	root	1.80	#endif
178	root	1.8
179	root	1.75	// very important, optimize?
180	root	1.85	GLfloat z = length (ctx.p - centerf) + rad;
181	root	1.86	if (z < 0.F \|\| ctx.perspfact * extent / z < 10.) // very crude "too small to see" check
182	root	1.58	return false;
183	root	1.45
184	root	1.59	#if 0
185	root	1.56	if (vs.state == PARTIAL \|\| vs.state == FULL)
186	root	1.45	ctx.nc_far = max (ctx.nc_far, z);
187	root	1.59	#endif
188	root	1.45
189	root	1.80	if (vs.state == OCCLUDED)
190	root	1.72	{
191	root	1.90	ctx.postdepthlist.push_back (this);
192	root	1.91
193	root	1.90	return false;
194	root	1.72	}
195
196	root	1.91	//bool visible = size () && vs.state != OCCLUDED;
197			bool visible = false;
198	root	1.74
199	root	1.51	// 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	root	1.19
204			// bit-toggle to find next child for front-to-back order
205	root	1.50	static unsigned char toggle[8+1]
206	root	1.51	= { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7, 0 };
207	root	1.19
208	root	1.50	unsigned char *next = toggle;
209			do
210	root	1.19	{
211	root	1.51	si ^= *next;
212	root	1.19
213			if (sub[si])
214	root	1.69	visible = visible \| sub[si]->detect_visibility (ctx);
215	root	1.19	}
216	root	1.51	while (*++next);
217
218	root	1.90	if (visible)
219	root	1.71	{
220			if (size ())
221	root	1.91	{
222			ctx.postdepthlist.push_back (this);
223	root	1.92	if (vs.vis)
224			ctx.vislist.push_back (this);
225	root	1.91	}
226
227			vs.state = FULL;
228	root	1.80
229	root	1.91	return true;
230			}
231			else if (vs.state == OCCLUDED)
232			{
233	root	1.80	ctx.postdepthlist.push_back (this);
234	root	1.91
235			return false;
236	root	1.71	}
237	root	1.91	else if (size())
238	root	1.81	{
239	root	1.92	if (vs.vis)
240			{
241			ctx.postdepthlist.push_back (this);
242			ctx.vislist.push_back (this);
243			}
244			else
245			vs.state = OCCLUDED;
246	root	1.91
247			return true;
248			}
249			else
250			{
251			return vs.state != PARTIAL;
252	root	1.81	}
253	root	1.19	}
254
255	root	1.75	void octant::draw_depth (view &ctx)
256	root	1.19	{
257	root	1.54	oct_visibility &vs = (oct_visibility )get_visibility (ctx);
258	root	1.8
259	root	1.79	vs.vismap.resize (size ());
260
261	root	1.90	if (vs.state == OCCLUDED)
262	root	1.75	return;
263
264	root	1.79	for (int i = 0; i < size (); ++i)
265	root	1.50	{
266	root	1.79	entity e = (this)[i];
267			const evis &evs = vs.get_visibility (i, e);
268	root	1.75
269			if (evs.state != OCCLUDED)
270	root	1.54	{
271	root	1.75	if (!ctx.may_draw (e))
272			continue;
273
274			sector center = ((e->a + e->b) >> 1) - ctx.orig;
275			GLfloat z = length (vec3 (center));
276			ctx.pixfact = ctx.perspfact / z;
277
278			ctx.nz_far = max (ctx.nz_far, z + extent);
279			ctx.nz_near = min (ctx.nz_near, z - extent);
280
281			e->draw (ctx);
282	root	1.56	}
283			}
284	root	1.75	}
285
286			void octant::draw_postdepth (view &ctx)
287			{
288			oct_visibility &vs = (oct_visibility )get_visibility (ctx);
289
290	root	1.91	if (vs.state == OCCLUDED \|\| !vs.vis)
291	root	1.75	{
292			ctx.begin_occ_query (*this, 0);
293			sector s = orig - ctx.orig;
294			gl::draw_bbox (s - extent, s + extent);
295			ctx.end_occ_query ();
296			}
297	root	1.56	else
298			{
299	root	1.92	vs.vis = false;
300	root	1.64
301	root	1.79	for (int i = 0; i < size (); ++i)
302	root	1.56	{
303	root	1.79	entity e = (this)[i];
304			const evis &evs = vs.get_visibility (i, e);
305	root	1.56
306	root	1.75	if (evs.state == OCCLUDED)
307	root	1.56	{
308	root	1.75	if (!ctx.may_draw (e))
309			continue;
310
311			ctx.begin_occ_query (*this, e);
312			gl::draw_bbox (e->a - ctx.orig, e->b - ctx.orig);
313			ctx.end_occ_query ();
314	root	1.56	}
315			else
316	root	1.91	vs.vis = true;
317	root	1.75	}
318			}
319			}
320
321			void octant::draw_lighted (view &ctx)
322			{
323			oct_visibility &vs = (oct_visibility )get_visibility (ctx);
324
325	root	1.90	#if 0
326			if (vs.state == FULL \|\| vs.state == OCCLUDED)
327	root	1.87	{
328	root	1.90	sector s = orig - ctx.orig;
329			debugmat->enable (ctx);
330			if (max (s) >= extent)
331			gl::draw_bbox (s - extent, s + extent);
332			debugmat->disable (ctx);
333			//printf ("DLP %ld %ld %ld (%ld)\n", orig.x, orig.y, orig.z, extent);//D
334	root	1.87	}
335			#endif
336
337	root	1.90	if (vs.state == OCCLUDED)
338	root	1.75	return;
339	root	1.90
340	root	1.79	for (int i = 0; i < size (); ++i)
341	root	1.75	{
342	root	1.79	entity e = (this)[i];
343			evis &evs = vs.get_visibility (i, e);
344	root	1.75
345			if (evs.state != OCCLUDED)
346			{
347	root	1.66	if (!ctx.may_draw (e))
348			continue;
349
350	root	1.75	sector center = ((e->a + e->b) >> 1) - ctx.orig;
351			GLfloat z = length (vec3 (center));
352			ctx.pixfact = ctx.perspfact / z;
353
354	root	1.91	if (!ctx.first_lighted
355	root	1.92	\|\| evs.next > timer.now)
356	root	1.75	e->draw (ctx);
357			else
358			{
359	root	1.92	evs.next = timer.now + 0.2;
360	root	1.75	ctx.begin_occ_query (*this, e);
361			e->draw (ctx);
362			ctx.end_occ_query ();
363	root	1.56	}
364	root	1.54	}
365	root	1.50	}
366	root	1.1	}
367	root	1.8
368	root	1.38	void octant::event (occ_query &ev)
369			{
370	root	1.56	oct_visibility &vs = (oct_visibility )get_visibility (ev.ctx);
371			entity e = (entity )ev.id;
372
373			if (e)
374			{
375	root	1.91	#if 1
376	root	1.79	for (vector<evis>::iterator i = vs.vismap.begin ();
377			i != vs.vismap.end ();
378			++i)
379			if (i->e == e)
380			{
381			i->state = ev.count ? FULL : OCCLUDED;
382			return;
383			}
384	root	1.91	#endif
385	root	1.56	}
386			else
387	root	1.90	{
388			vs.state = ev.count ? FULL : OCCLUDED;
389	root	1.91	vs.vis = ev.count ? true : false;
390	root	1.90	}
391	root	1.52	}
392
393	root	1.2