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

struct oct_visibility : visibility_base
{
  bool evis;
  int occ_res;

  void clear ()
  {
    occ_res = -1;
    evis = true;
  }

  oct_visibility (octant &oct)
  {
    clear ();
  }
};

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)->clear ();
}

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)
{
}

int octant::detect_visibility (view &ctx)
{
  oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);

  sector centeri = orig - ctx.orig;
  point centerf = point (centeri);

  GLfloat rad = ctx.diagfact * extent;

  if (max (centeri) < extent)
    vs.occ_res = 1;

  if (!overlap (ctx.frustum.c, sphere (centerf, rad)))
    return VIS_NONE;

  if (max (centeri) < extent)
    vs.occ_res = 1;
  else if (distance (ctx.frustum.t, centerf) < -rad
           || distance (ctx.frustum.b, centerf) < -rad
           || distance (ctx.frustum.l, centerf) < -rad
           || distance (ctx.frustum.r, centerf) < -rad
           || distance (ctx.frustum.n, centerf) < -rad)
    return VIS_NONE;

#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 VIS_NONE;

#if 0
  if (vs.state == PARTIAL || vs.state == FULL)
    ctx.nc_far = max (ctx.nc_far, z);
#endif

  if (extent > 1<<24) // float resolution
    vs.occ_res = 1;

  if (!vs.occ_res)
    {
      vs.occ_res = -1;
      vs.evis = false;
      return VIS_OCCLUDED;
    }
  else if (vs.occ_res > 0)
    vs.evis = true;

#if 0
  else if (!(vs.subvis || vs.evis))
    {
      ctx.postdepthlist.push_back (this);
      return false;
    }
#endif
 
  int subvis [8];
  bool any_full = false, any_occ = 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;

      int vis = sub [si]
                ? sub [si]->detect_visibility (ctx)
                : VIS_NONE;

      subvis [si] = vis;
      any_full |= vis == VIS_FULL;
      any_occ  |= vis == VIS_OCCLUDED;
    }
  while (*++next);

  if (any_full)
    {
      vs.evis = true;

      ctx.postdepthlist.push_back (this);
      ctx.vislist.push_back (this);

      for (int i = 0; i < 8; i++)
        if (subvis [i] == VIS_OCCLUDED)
          ctx.postdepthlist.push_back (sub [i]);

      return VIS_FULL;
    }
  else if (vs.evis && size ())
    {
      ctx.postdepthlist.push_back (this);
      ctx.vislist.push_back (this);

      for (int i = 0; i < 8; i++)
        if (subvis [i] == VIS_OCCLUDED)
          ctx.postdepthlist.push_back (sub [i]);

      return VIS_FULL;
    }
  else if (any_occ)
    {
      vs.evis = false;
      return VIS_OCCLUDED;
    }
  else
    return VIS_NONE;
}

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

  for (vector<entity *>::const_iterator i = end (); i-- != begin (); )
    {
      entity *e = *i;
      entity_visibility &evis = *(entity_visibility *)e->get_visibility (ctx);

      if (evis.occ_res)
        {
          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.evis)
    {
      vs.evis = false;

      for (vector<entity *>::const_iterator i = end (); i-- != begin (); )
        {
          entity *e = *i;
          entity_visibility &evis = *(entity_visibility *)e->get_visibility (ctx);

          evis.occ_res = 1;
          if (evis.occ_res)
            vs.evis = true;
          else
            {
              if (!ctx.may_draw (e))
                continue;

              ctx.stat1++;
              ctx.begin_occ_query (evis.occ_res);
              gl::draw_bbox (e->a - ctx.orig, e->b - ctx.orig);
              ctx.end_occ_query ();
            }
        }
    }

  if (!vs.evis)
    {
      ctx.begin_occ_query (vs.occ_res);
      sector s = orig - ctx.orig;
      gl::draw_bbox (s - extent, s + extent);
      ctx.end_occ_query ();
    }
}

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

  for (vector<entity *>::const_iterator i = end (); i-- != begin (); )
    {
      entity *e = *i;
      entity_visibility &evis = *(entity_visibility *)e->get_visibility (ctx);

      if (evis.occ_res)
        {
          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
              || evis.next > timer.now)
            e->draw (ctx);
          else
            {
              evis.next = timer.now + 0.2;
              ctx.begin_occ_query (evis.occ_res);
              e->draw (ctx);
              ctx.end_occ_query ();
            }
        }
    }
}


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