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, SMALL, OCCLUDED };

struct evis {
  visibility_state state;
  double last; // time of last check
  evis () : last(0.), state(FULL) { };
};

struct oct_visibility : visibility_base
{
  typedef map<entity *, evis> evismap;
  evismap vismap;

  visibility_state state;

  oct_visibility (octant &oct)
  : state(FULL)
  {
  }
};

octant world(0, sector (SOFFS_MIN, SOFFS_MIN, SOFFS_MIN), 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 ();
}

octant::~octant ()
{
  for (fill = 8; fill--; )
    delete sub[fill];
}

static bool overlap (const sector &o1, uoffs ea, const sector &a, const sector &b)
{
  ea /= 2;

  sector center_1 = o1 + ea;
  sector size_2   = b - a;
  sector center_2 = a + (size_2 >> 1);

  return abs (center_1 - center_2) <= ea + size_2;
}

void octant::add (entity *e)
{
  const sector &a = e->a;
  const sector &b = e->b;

  if (overlap (orig, extent, a, b))
    {
      uoffs extent2 = extent >> 1;
      uoffs size = max (abs (b - a));

      if (size >= extent2 >> 1)
        {
          push_back (e);
          e->o.push_back (this);
          return;
        }

      for (int i = 8; i--; )
        {
          sector s = orig;
          s.offset (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)
{
  GLfloat extent2 = 0.5F * (GLfloat)extent;
  sector centeri = orig + (extent >> 1) - ctx.orig;
  point centerf = point (centeri) + ((extent & 1) ? 0.5F : 0.F);

  GLfloat rad = ctx.diagfact * extent2;

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

  oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);

  if (orig <= ctx.orig && ctx.orig <= orig + 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
    }

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

  GLfloat z = ctx.z_near + distance (ctx.frustum.n, centerf) + rad;
  if (ctx.perspfact * extent / z < 1.) // very crude "too small to see" check
    return false;
  //printf ("z %f, perspfact %f, z*p %f\n", z, ctx.perspfact, ctx.perspfact / z);

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

  // node to start with
  unsigned char si = centeri.x > 0 ? 1 : 0
                   | centeri.y > 0 ? 2 : 0
                   | centeri.z > 0 ? 4 : 0;

  //printf ("si %d C %Ld,%Ld,%Ld\n", si, centeri.x, centeri.y, centeri.z);

  // 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])
        sub[si]->detect_visibility (ctx);
    }
  while (*++next);

  if (size ()
      && (vs.state == PARTIAL || vs.state == FULL))
    ctx.vislist.push_back (this);

  return true;
}

void octant::display (view &ctx)
{
#if 0
  sector s = orig - ctx.orig;

  glBegin (GL_LINES);
  vec3 clr(0, 0.8, 0);
  glMaterialfv (GL_FRONT_AND_BACK, GL_DIFFUSE, (const GLfloat*)&clr);

  for (int i = 8; i--; )
    for (int ji = 3; ji--; )
      {
        int j = i | (1 << ji);
        if (i < j)
          {
            glVertex3i (s.x + !!(i & 1) * extent,
                        s.y + !!(i & 2) * extent,
                        s.z + !!(i & 4) * extent);
            glVertex3i (s.x + !!(j & 1) * extent,
                        s.y + !!(j & 2) * extent,
                        s.z + !!(j & 4) * extent);
          }
      }
  
  glEnd ();
#endif
  oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);

  if (vs.state == OCCLUDED)
    {
      if (ctx.pass == view::POSTDEPTH)
        {
          ctx.begin_occ_query (*this, 0);
          sector s = orig - ctx.orig;
          gl::draw_bbox (s, s + extent);
          printf ("bbox %Ld,%ld,%Ld\n", s.x, s.y, s.z);
          ctx.end_occ_query ();
        }
    }
  else
    {
      int nvis = 0;

      for (iterator i = begin (); i != end (); )
        {
          entity *e = *i++;

          if (!ctx.may_draw (e))
            continue;

          evis &evs = vs.vismap[e];

          if (ctx.pass == view::POSTDEPTH)
            {
              if (evs.state == OCCLUDED)
                {
                  ctx.begin_occ_query (*this, e);
                  gl::draw_bbox (e->a - ctx.orig, e->b - ctx.orig);
                  ctx.end_occ_query ();
                }
              else
                nvis++;
            }
          else
            {
              if (evs.state != OCCLUDED)
                {
                  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);

                  if (ctx.pass == view::DEPTH || evs.last + 0.3 > timer.now)
                    e->draw (ctx);
                  else
                    {
                      evs.last = timer.now;
                      ctx.begin_occ_query (*this, e);
                      e->draw (ctx);
                      ctx.end_occ_query ();
                    }
                }
            }
        }

#if 0
      if (ctx.pass == view::POSTDEPTH && nvis == 0 && size ())
        vs.state = OCCLUDED;
#endif
    }
}

void octant::event (occ_query &ev)
{
  oct_visibility &vs = *(oct_visibility *)get_visibility (ev.ctx);
  entity *e = (entity *)ev.id;

  if (e)
    {
      evis &evs = vs.vismap[e];
      evs.state = ev.count ? FULL : OCCLUDED;
    }
  else
    vs.state = ev.count ? FULL : OCCLUDED;
}


Revision:	1.65
Committed:	Sat Oct 23 02:27:51 2004 UTC (19 years, 7 months ago) by root
Content type:	text/plain
Branch:	MAIN
Changes since 1.64:	+3 -2 lines
Log Message:	* empty log message *
#	User	Rev	Content
1	root	1.1	#include <cstdlib>
2
3	root	1.8	#include <vector>
4			using namespace std;
5
6	root	1.48	#include "opengl.h"
7	root	1.8
8	root	1.1	#include "oct.h"
9	root	1.8	#include "view.h"
10	root	1.2	#include "entity.h"
11
12	root	1.56	enum visibility_state { FULL, PARTIAL, SMALL, OCCLUDED };
13
14	root	1.54	struct evis {
15	root	1.56	visibility_state state;
16	root	1.54	double last; // time of last check
17			evis () : last(0.), state(FULL) { };
18			};
19
20	root	1.52	struct oct_visibility : visibility_base
21			{
22	root	1.54	typedef map<entity *, evis> evismap;
23			evismap vismap;
24	root	1.52
25	root	1.56	visibility_state state;
26	root	1.52
27			oct_visibility (octant &oct)
28	root	1.54	: state(FULL)
29	root	1.52	{
30			}
31			};
32
33	root	1.8	octant world(0, sector (SOFFS_MIN, SOFFS_MIN, SOFFS_MIN), MAXEXTENT);
34
35			octant::octant (octant *parent, const sector &orig, uoffs extent)
36	root	1.54	: parent(parent)
37			, orig(orig)
38			, extent(extent)
39	root	1.8	{
40			for (fill = 8; fill--; )
41			sub[fill] = 0;
42	root	1.2	}
43
44	root	1.53	visibility_base *octant::new_visibility ()
45			{
46			return new oct_visibility (*this);
47			}
48
49			void octant::clear_visibility (visibility_base *vs)
50			{
51			((oct_visibility *)vs)->vismap.clear ();
52			}
53	root	1.65
54	root	1.2	octant::~octant ()
55			{
56			for (fill = 8; fill--; )
57			delete sub[fill];
58			}
59
60	root	1.32	static bool overlap (const sector &o1, uoffs ea, const sector &a, const sector &b)
61	root	1.4	{
62			ea /= 2;
63
64	root	1.34	sector center_1 = o1 + ea;
65			sector size_2 = b - a;
66	root	1.54	sector center_2 = a + (size_2 >> 1);
67	root	1.33
68	root	1.34	return abs (center_1 - center_2) <= ea + size_2;
69	root	1.4	}
70
71	root	1.32	void octant::add (entity *e)
72	root	1.2	{
73	root	1.32	const sector &a = e->a;
74			const sector &b = e->b;
75	root	1.7
76	root	1.32	if (overlap (orig, extent, a, b))
77	root	1.4	{
78	root	1.54	uoffs extent2 = extent >> 1;
79	root	1.34	uoffs size = max (abs (b - a));
80	root	1.32
81	root	1.54	if (size >= extent2 >> 1)
82	root	1.8	{
83			push_back (e);
84			e->o.push_back (this);
85			return;
86			}
87	root	1.5
88	root	1.8	for (int i = 8; i--; )
89	root	1.5	{
90	root	1.8	sector s = orig;
91			s.offset (i, extent2);
92	root	1.32
93			if (overlap (s, extent2, a, b))
94	root	1.5	{
95	root	1.8	if (!sub[i])
96	root	1.50	{
97			sub[i] = new octant (this, s, extent2);
98			fill++;
99			}
100	root	1.8
101			sub[i]->add (e);
102	root	1.5	}
103	root	1.8	}
104	root	1.4	}
105	root	1.2	}
106	root	1.1
107	root	1.32	void octant::remove (entity *e)
108	root	1.1	{
109			}
110
111	root	1.62	bool octant::detect_visibility (view &ctx)
112	root	1.1	{
113	root	1.43	GLfloat extent2 = 0.5F * (GLfloat)extent;
114	root	1.51	sector centeri = orig + (extent >> 1) - ctx.orig;
115			point centerf = point (centeri) + ((extent & 1) ? 0.5F : 0.F);
116
117	root	1.43	GLfloat rad = ctx.diagfact * extent2;
118
119	root	1.59	if (!overlap (ctx.frustum.c, sphere (centerf, rad)))
120			return false;
121	root	1.65
122			oct_visibility &vs = (oct_visibility )get_visibility (ctx);
123	root	1.59
124	root	1.34	if (orig <= ctx.orig && ctx.orig <= orig + extent)
125	root	1.56	vs.state = PARTIAL;
126	root	1.10	else
127			{
128	root	1.59	if (distance (ctx.frustum.t, centerf) < -rad) return false;
129			if (distance (ctx.frustum.b, centerf) < -rad) return false;
130			if (distance (ctx.frustum.l, centerf) < -rad) return false;
131			if (distance (ctx.frustum.r, centerf) < -rad) return false;
132			if (distance (ctx.frustum.n, centerf) < -rad) return false;
133	root	1.25
134	root	1.59	#if 0
135			GLfloat fd = distance (ctx.frustum.f, centerf);
136	root	1.25
137	root	1.47	if (fd < -(ctx.c_far - ctx.z_far) -rad * 3.F)
138	root	1.52	return false;
139	root	1.58	#endif
140	root	1.10	}
141	root	1.8
142	root	1.56	if (vs.state == OCCLUDED)
143	root	1.64	{
144			if (size ())
145			ctx.vislist.push_back (this);
146			return false;
147			}
148	root	1.36
149	root	1.59	GLfloat z = ctx.z_near + distance (ctx.frustum.n, centerf) + rad;
150	root	1.58	if (ctx.perspfact * extent / z < 1.) // very crude "too small to see" check
151			return false;
152	root	1.50	//printf ("z %f, perspfact %f, z*p %f\n", z, ctx.perspfact, ctx.perspfact / z);
153	root	1.45
154	root	1.59	#if 0
155	root	1.56	if (vs.state == PARTIAL \|\| vs.state == FULL)
156	root	1.45	ctx.nc_far = max (ctx.nc_far, z);
157	root	1.59	#endif
158	root	1.45
159	root	1.51	// node to start with
160			unsigned char si = centeri.x > 0 ? 1 : 0
161			\| centeri.y > 0 ? 2 : 0
162			\| centeri.z > 0 ? 4 : 0;
163	root	1.44
164	root	1.51	//printf ("si %d C %Ld,%Ld,%Ld\n", si, centeri.x, centeri.y, centeri.z);
165	root	1.19
166			// bit-toggle to find next child for front-to-back order
167	root	1.50	static unsigned char toggle[8+1]
168	root	1.51	= { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7, 0 };
169	root	1.19
170	root	1.50	unsigned char *next = toggle;
171			do
172	root	1.19	{
173	root	1.51	si ^= *next;
174	root	1.19
175			if (sub[si])
176	root	1.62	sub[si]->detect_visibility (ctx);
177	root	1.19	}
178	root	1.51	while (*++next);
179
180			if (size ()
181	root	1.56	&& (vs.state == PARTIAL \|\| vs.state == FULL))
182	root	1.62	ctx.vislist.push_back (this);
183	root	1.52
184			return true;
185	root	1.19	}
186
187			void octant::display (view &ctx)
188			{
189	root	1.17	#if 0
190	root	1.50	sector s = orig - ctx.orig;
191
192	root	1.8	glBegin (GL_LINES);
193	root	1.13	vec3 clr(0, 0.8, 0);
194			glMaterialfv (GL_FRONT_AND_BACK, GL_DIFFUSE, (const GLfloat*)&clr);
195	root	1.8
196			for (int i = 8; i--; )
197			for (int ji = 3; ji--; )
198			{
199			int j = i \| (1 << ji);
200	root	1.50	if (i < j)
201	root	1.8	{
202			glVertex3i (s.x + !!(i & 1) * extent,
203			s.y + !!(i & 2) * extent,
204			s.z + !!(i & 4) * extent);
205			glVertex3i (s.x + !!(j & 1) * extent,
206			s.y + !!(j & 2) * extent,
207			s.z + !!(j & 4) * extent);
208			}
209			}
210
211			glEnd ();
212			#endif
213	root	1.54	oct_visibility &vs = (oct_visibility )get_visibility (ctx);
214	root	1.8
215	root	1.56	if (vs.state == OCCLUDED)
216	root	1.50	{
217	root	1.56	if (ctx.pass == view::POSTDEPTH)
218	root	1.54	{
219	root	1.56	ctx.begin_occ_query (*this, 0);
220	root	1.57	sector s = orig - ctx.orig;
221	root	1.61	gl::draw_bbox (s, s + extent);
222	root	1.64	printf ("bbox %Ld,%ld,%Ld\n", s.x, s.y, s.z);
223	root	1.56	ctx.end_occ_query ();
224			}
225			}
226			else
227			{
228	root	1.64	int nvis = 0;
229
230	root	1.57	for (iterator i = begin (); i != end (); )
231	root	1.56	{
232	root	1.57	entity e = i++;
233	root	1.56
234			if (!ctx.may_draw (e))
235			continue;
236
237			evis &evs = vs.vismap[e];
238
239			if (ctx.pass == view::POSTDEPTH)
240			{
241			if (evs.state == OCCLUDED)
242			{
243			ctx.begin_occ_query (*this, e);
244	root	1.61	gl::draw_bbox (e->a - ctx.orig, e->b - ctx.orig);
245	root	1.56	ctx.end_occ_query ();
246			}
247	root	1.64	else
248			nvis++;
249	root	1.56	}
250			else
251			{
252			if (evs.state != OCCLUDED)
253			{
254			sector center = ((e->a + e->b) >> 1) - ctx.orig;
255	root	1.59	GLfloat z = length (vec3 (center));
256	root	1.56	ctx.pixfact = ctx.perspfact / z;
257	root	1.59
258	root	1.60	ctx.nz_far = max (ctx.nz_far, z + extent);
259			ctx.nz_near = min (ctx.nz_near, z - extent);
260	root	1.56
261	root	1.63	if (ctx.pass == view::DEPTH \|\| evs.last + 0.3 > timer.now)
262	root	1.56	e->draw (ctx);
263			else
264			{
265			evs.last = timer.now;
266			ctx.begin_occ_query (*this, e);
267			e->draw (ctx);
268			ctx.end_occ_query ();
269			}
270			}
271			}
272	root	1.54	}
273	root	1.64
274			#if 0
275			if (ctx.pass == view::POSTDEPTH && nvis == 0 && size ())
276			vs.state = OCCLUDED;
277			#endif
278	root	1.50	}
279	root	1.1	}
280	root	1.8
281	root	1.38	void octant::event (occ_query &ev)
282			{
283	root	1.56	oct_visibility &vs = (oct_visibility )get_visibility (ev.ctx);
284			entity e = (entity )ev.id;
285
286			if (e)
287			{
288			evis &evs = vs.vismap[e];
289			evs.state = ev.count ? FULL : OCCLUDED;
290			}
291			else
292	root	1.64	vs.state = ev.count ? FULL : OCCLUDED;
293	root	1.52	}
294
295	root	1.2