libgender/oct.C

#include <cstdlib>

#include <vector>

using namespace std;

#include "opengl.h"

#include "oct.h"
#include "view.h"
#include "entity.h"

struct oct_visibility : visibility_base
{
  struct visibility {
    enum { UNKNOWN, OCCLUDED, PARTIAL, FULL } state;
    double last; // time of last check
    visibility () : last(0.), state(UNKNOWN) { };
  };

  typedef map<entity *, visibility> evismap;
  evismap vismap;

  oct_visibility (octant &oct)
  {
  }
};

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 / 2;

  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 / 2;
      uoffs size = max (abs (b - a));

      if (size >= extent2 / 2)
        {
          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)
{
  oct_visibility &vs = *(oct_visibility *)get_visibility (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 (orig <= ctx.orig && ctx.orig <= orig + extent)
    ;//vs.visibility = visibility_state::PARTIAL;
  else
    {
      if (ctx.frustum.t.distance (centerf) < -rad) return false;
      if (ctx.frustum.b.distance (centerf) < -rad) return false;
      if (ctx.frustum.l.distance (centerf) < -rad) return false;
      if (ctx.frustum.r.distance (centerf) < -rad) return false;
      if (ctx.frustum.n.distance (centerf) < -rad) return false;

      GLfloat fd = ctx.frustum.f.distance (centerf);

      if (fd < -(ctx.c_far - ctx.z_far) -rad * 3.F)
        return false;
    }

#if 0
  if (vs.visibility == visibility_state::OCCLUDED
      || vs.visibility == visibility_state::UNKNOWN)
    {
      ctx.farlist.push_back (this);
      return;
    }
#endif

#if 0
  if (vs.visibility == visibility_state::UNKNOWN)
    vs.visibility = visibility_state::FULL;
#endif

  GLfloat z = ctx.z_near + ctx.frustum.n.distance (centerf) + rad;
  //printf ("z %f, perspfact %f, z*p %f\n", z, ctx.perspfact, ctx.perspfact / z);

#if 0
  if (vs.visibility == visibility_state::FULL)
#endif
    ctx.nc_far = max (ctx.nc_far, z);

  // 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 ()
#if 0
      && (vs.visibility == visibility_state::PARTIAL
          || vs.visibility == visibility_state::FULL)
#endif
      )
    {
      ctx.nz_far = max (ctx.nz_far, z);
      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

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

      sector diff = (e->a + e->b) / 2 - ctx.orig;
      GLfloat z = norm (vec3 ((e->a + e->b) / 2 - ctx.orig));
      ctx.pixfact = ctx.perspfact / z;

      if (ctx.mode != view::POSTDEPTH)
        e->display (ctx);
    }
}

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

  gl::draw_bbox (ctx, s, s + extent);
}
#endif

void octant::event (occ_query &ev)
{
#if 0
  visibility_state &vs = ev.v.vismap[this];

  vs.last = timer.now;
  vs.visibility = ev.r <= 0
                  ? visibility_state::OCCLUDED
                  : visibility_state::FULL;
#endif
}


Revision:	1.53
Committed:	Sat Oct 16 14:48:48 2004 UTC (19 years, 7 months ago) by root
Content type:	text/plain
Branch:	MAIN
Changes since 1.52:	+13 -10 lines
Log Message:	* empty log message *
#	User	Rev	Content
1	root	1.1	#include <cstdlib>
2
3	root	1.8	#include <vector>
4
5			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
13	root	1.52	struct oct_visibility : visibility_base
14			{
15			struct visibility {
16			enum { UNKNOWN, OCCLUDED, PARTIAL, FULL } state;
17			double last; // time of last check
18			visibility () : last(0.), state(UNKNOWN) { };
19			};
20
21			typedef map<entity *, visibility> evismap;
22			evismap vismap;
23
24			oct_visibility (octant &oct)
25			{
26			}
27			};
28
29	root	1.8	octant world(0, sector (SOFFS_MIN, SOFFS_MIN, SOFFS_MIN), MAXEXTENT);
30
31			octant::octant (octant *parent, const sector &orig, uoffs extent)
32			: parent(parent), orig(orig), extent(extent)
33			{
34			for (fill = 8; fill--; )
35			sub[fill] = 0;
36	root	1.2	}
37
38	root	1.53	visibility_base *octant::new_visibility ()
39			{
40			return new oct_visibility (*this);
41			}
42
43			void octant::clear_visibility (visibility_base *vs)
44			{
45			((oct_visibility *)vs)->vismap.clear ();
46			}
47	root	1.2	octant::~octant ()
48			{
49			for (fill = 8; fill--; )
50			delete sub[fill];
51			}
52
53	root	1.32	static bool overlap (const sector &o1, uoffs ea, const sector &a, const sector &b)
54	root	1.4	{
55			ea /= 2;
56
57	root	1.34	sector center_1 = o1 + ea;
58			sector size_2 = b - a;
59			sector center_2 = a + size_2 / 2;
60	root	1.33
61	root	1.34	return abs (center_1 - center_2) <= ea + size_2;
62	root	1.4	}
63
64	root	1.32	void octant::add (entity *e)
65	root	1.2	{
66	root	1.32	const sector &a = e->a;
67			const sector &b = e->b;
68	root	1.7
69	root	1.32	if (overlap (orig, extent, a, b))
70	root	1.4	{
71	root	1.8	uoffs extent2 = extent / 2;
72	root	1.34	uoffs size = max (abs (b - a));
73	root	1.32
74	root	1.50	if (size >= extent2 / 2)
75	root	1.8	{
76			push_back (e);
77			e->o.push_back (this);
78			return;
79			}
80	root	1.5
81	root	1.8	for (int i = 8; i--; )
82	root	1.5	{
83	root	1.8	sector s = orig;
84			s.offset (i, extent2);
85	root	1.32
86			if (overlap (s, extent2, a, b))
87	root	1.5	{
88	root	1.8	if (!sub[i])
89	root	1.50	{
90			sub[i] = new octant (this, s, extent2);
91			fill++;
92			}
93	root	1.8
94			sub[i]->add (e);
95	root	1.5	}
96	root	1.8	}
97	root	1.4	}
98	root	1.2	}
99	root	1.1
100	root	1.32	void octant::remove (entity *e)
101	root	1.1	{
102			}
103
104	root	1.52	bool octant::detect_visibility (view &ctx)
105	root	1.1	{
106	root	1.52	oct_visibility &vs = (oct_visibility )get_visibility (ctx);
107	root	1.50
108	root	1.43	GLfloat extent2 = 0.5F * (GLfloat)extent;
109	root	1.51	sector centeri = orig + (extent >> 1) - ctx.orig;
110			point centerf = point (centeri) + ((extent & 1) ? 0.5F : 0.F);
111
112	root	1.43	GLfloat rad = ctx.diagfact * extent2;
113
114	root	1.34	if (orig <= ctx.orig && ctx.orig <= orig + extent)
115	root	1.52	;//vs.visibility = visibility_state::PARTIAL;
116	root	1.10	else
117			{
118	root	1.52	if (ctx.frustum.t.distance (centerf) < -rad) return false;
119			if (ctx.frustum.b.distance (centerf) < -rad) return false;
120			if (ctx.frustum.l.distance (centerf) < -rad) return false;
121			if (ctx.frustum.r.distance (centerf) < -rad) return false;
122			if (ctx.frustum.n.distance (centerf) < -rad) return false;
123	root	1.25
124	root	1.51	GLfloat fd = ctx.frustum.f.distance (centerf);
125	root	1.25
126	root	1.47	if (fd < -(ctx.c_far - ctx.z_far) -rad * 3.F)
127	root	1.52	return false;
128	root	1.10	}
129	root	1.8
130	root	1.52	#if 0
131	root	1.46	if (vs.visibility == visibility_state::OCCLUDED
132			\|\| vs.visibility == visibility_state::UNKNOWN)
133	root	1.45	{
134			ctx.farlist.push_back (this);
135			return;
136			}
137	root	1.52	#endif
138	root	1.45
139	root	1.46	#if 0
140	root	1.36	if (vs.visibility == visibility_state::UNKNOWN)
141			vs.visibility = visibility_state::FULL;
142	root	1.46	#endif
143	root	1.36
144	root	1.51	GLfloat z = ctx.z_near + ctx.frustum.n.distance (centerf) + rad;
145	root	1.50	//printf ("z %f, perspfact %f, z*p %f\n", z, ctx.perspfact, ctx.perspfact / z);
146	root	1.45
147	root	1.52	#if 0
148	root	1.45	if (vs.visibility == visibility_state::FULL)
149	root	1.52	#endif
150	root	1.45	ctx.nc_far = max (ctx.nc_far, z);
151
152	root	1.51	// node to start with
153			unsigned char si = centeri.x > 0 ? 1 : 0
154			\| centeri.y > 0 ? 2 : 0
155			\| centeri.z > 0 ? 4 : 0;
156	root	1.44
157	root	1.51	//printf ("si %d C %Ld,%Ld,%Ld\n", si, centeri.x, centeri.y, centeri.z);
158	root	1.19
159			// bit-toggle to find next child for front-to-back order
160	root	1.50	static unsigned char toggle[8+1]
161	root	1.51	= { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7, 0 };
162	root	1.19
163	root	1.50	unsigned char *next = toggle;
164			do
165	root	1.19	{
166	root	1.51	si ^= *next;
167	root	1.19
168			if (sub[si])
169			sub[si]->detect_visibility (ctx);
170			}
171	root	1.51	while (*++next);
172
173			if (size ()
174	root	1.52	#if 0
175	root	1.51	&& (vs.visibility == visibility_state::PARTIAL
176	root	1.52	\|\| vs.visibility == visibility_state::FULL)
177			#endif
178			)
179	root	1.51	{
180			ctx.nz_far = max (ctx.nz_far, z);
181			ctx.vislist.push_back (this);
182			}
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
214	root	1.19	for (iterator i = end (); i != begin (); )
215	root	1.50	{
216			entity e = --i;
217
218			sector diff = (e->a + e->b) / 2 - ctx.orig;
219			GLfloat z = norm (vec3 ((e->a + e->b) / 2 - ctx.orig));
220			ctx.pixfact = ctx.perspfact / z;
221
222	root	1.53	if (ctx.mode != view::POSTDEPTH)
223			e->display (ctx);
224	root	1.50	}
225	root	1.1	}
226	root	1.8
227	root	1.53	#if 0
228	root	1.38	void octant::draw_bbox (view &ctx)
229	root	1.25	{
230			sector s = orig - ctx.orig;
231	root	1.27
232	root	1.50	gl::draw_bbox (ctx, s, s + extent);
233	root	1.25	}
234	root	1.53	#endif
235	root	1.8
236	root	1.38	void octant::event (occ_query &ev)
237			{
238	root	1.52	#if 0
239	root	1.44	visibility_state &vs = ev.v.vismap[this];
240
241			vs.last = timer.now;
242	root	1.47	vs.visibility = ev.r <= 0
243	root	1.44	? visibility_state::OCCLUDED
244			: visibility_state::FULL;
245	root	1.52	#endif
246			}
247
248	root	1.2