libgender/oct.C

#include <cstdlib>

#include <vector>

using namespace std;

#define GL_GLEXT_PROTOTYPES
#include <GL/gl.h>
#include <GL/glext.h>

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

vector<GLuint> occ_query_objects;

static GLuint begin_occ_query ()
{
  GLuint id;

  if (occ_query_objects.size ())
    {
      id = *(occ_query_objects.end () - 1);
      occ_query_objects.pop_back ();
    }
  else
    glGenQueriesARB (1, &id);

  glBeginQueryARB (GL_SAMPLES_PASSED, id);
  return id;
}

#define end_occ_query() glEndQueryARB (GL_SAMPLES_PASSED)

GLuint occ_query_result (GLuint id)
{
  GLuint count;

  glGetQueryObjectuivARB (id, GL_QUERY_RESULT, &count);
  occ_query_objects.push_back (id);

  return count;
}

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

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

static bool overlap (const sector &o1, uoffs ea, const sector &a, const sector &b)
{
  sector a2, b2;

  ea /= 2;

  a2.x = o1.x + ea;
  a2.y = o1.y + ea;
  a2.z = o1.z + ea;
  
  b2.x = (a.x + b.x) / 2;
  b2.y = (a.y + b.y) / 2;
  b2.z = (a.z + b.z) / 2;

  return abs (a2.x - b2.x) <= ea + (b.x - a.x)
      && abs (a2.y - b2.y) <= ea + (b.y - a.y)
      && abs (a2.z - b2.z) <= ea + (b.z - a.z);
}

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.x - a.x),
                   max (abs (b.y - a.y),
                        abs (b.z - a.z)));

      if (size > extent2 || !extent2)
        {
          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);

              sub[i]->add (e);
            }
        }
    }
}

void octant::remove (entity *e)
{
}

void octant::detect_visibility (view &ctx)
{
  visibility_state &vs = ctx.vismap[this];

  if (vs.generation != ctx.generation)
    vs.visibility = visibility_state::UNKNOWN;

  const sector &cam = ctx.orig;
  if (cam.x >= orig.x && cam.x <= orig.x + extent
      && cam.y >= orig.y && cam.y <= orig.y + extent
      && cam.z >= orig.z && cam.z <= orig.z + extent)
    {
      vs.visibility = visibility_state::PARTIAL;
      vs.generation = ctx.generation;
    }
  else
    {
      point center (
        orig.x + (soffs)extent / 2 - cam.x,
        orig.y + (soffs)extent / 2 - cam.y,
        orig.z + (soffs)extent / 2 - cam.z 
      );

      GLfloat dia = (2. * sqrtf (3))*(GLfloat)extent;

      if (ctx.frustum.t.distance (center) < -dia) return;
      if (ctx.frustum.b.distance (center) < -dia) return;
      if (ctx.frustum.l.distance (center) < -dia) return;
      if (ctx.frustum.r.distance (center) < -dia) return;
      if (ctx.frustum.n.distance (center) < -dia) return;

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

      if (fd < -dia)
        {
          if (fd < -dia * 2)
            return;

          // cull, but do check for potential visibility
          if (size ())
            {
              ctx.farlist.push_back (this);
              return;
            }
        }
    }

  if (size ())
    ctx.vislist.push_back (this);

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

  // bit-toggle to find next child for front-to-back order
  static unsigned char next[8]
    = { 0,  0^1, 1^2, 2^4,  4^3, 3^5, 5^6,  6^7 };

  for (int i = 0; i < 8; i++)
    {
      si ^= next[i];

      if (sub[si])
        sub[si]->detect_visibility (ctx);
    }

  vs.generation = ctx.generation;
}

void octant::display (view &ctx)
{
#if 0
  glBegin (GL_LINES);
  sector s = orig - ctx.orig;
  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 ();
  glDisable(GL_COLOR_MATERIAL);
#endif

  for (iterator i = end (); i != begin (); )
    (*--i)->display (ctx);
}

void
octant::draw_bbox (view &ctx)
{
  sector s = orig - ctx.orig;
  int i;
  GLint verts[4 * 6] = {
     0x00, 0x40, 0x60, 0x20,  // -x
     0x10, 0x30, 0x70, 0x50,  // +x
     0x00, 0x10, 0x50, 0x40,  // -y
     0x70, 0x30, 0x20, 0x60,  // +y
     0x00, 0x20, 0x30, 0x10,  // -z
     0x40, 0x50, 0x70, 0x60,  // +z
  };

  GLfloat cube[8][3] =
    {
      { s.x                , s.y                , s.z                 },
      { s.x + (soffs)extent, s.y                , s.z                 },
      { s.x                , s.y + (soffs)extent, s.z                 },
      { s.x + (soffs)extent, s.y + (soffs)extent, s.z                 }, 
      { s.x                , s.y                , s.z + (soffs)extent },
      { s.x + (soffs)extent, s.y                , s.z + (soffs)extent },
      { s.x                , s.y + (soffs)extent, s.z + (soffs)extent },
      { s.x + (soffs)extent, s.y + (soffs)extent, s.z + (soffs)extent },
    };

  glBegin (GL_QUADS);

  for (i = 0; i < 4 * 6; i++)
    glVertex3fv (cube [verts [i] >> 4]);

  glEnd ();
}


Revision:	1.32
Committed:	Thu Oct 7 23:39:43 2004 UTC (19 years, 8 months ago) by root
Content type:	text/plain
Branch:	MAIN
Changes since 1.31:	+24 -19 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			#define GL_GLEXT_PROTOTYPES
8			#include <GL/gl.h>
9	root	1.24	#include <GL/glext.h>
10	root	1.8
11	root	1.1	#include "oct.h"
12	root	1.8	#include "view.h"
13	root	1.2	#include "entity.h"
14
15	root	1.8	vector<GLuint> occ_query_objects;
16	root	1.2
17	root	1.8	static GLuint begin_occ_query ()
18	root	1.2	{
19	root	1.8	GLuint id;
20	root	1.2
21	root	1.8	if (occ_query_objects.size ())
22	root	1.3	{
23	root	1.8	id = *(occ_query_objects.end () - 1);
24			occ_query_objects.pop_back ();
25	root	1.3	}
26			else
27	root	1.20	glGenQueriesARB (1, &id);
28	root	1.8
29	root	1.20	glBeginQueryARB (GL_SAMPLES_PASSED, id);
30	root	1.8	return id;
31			}
32
33	root	1.23	#define end_occ_query() glEndQueryARB (GL_SAMPLES_PASSED)
34	root	1.8
35	root	1.23	GLuint occ_query_result (GLuint id)
36	root	1.8	{
37			GLuint count;
38
39	root	1.20	glGetQueryObjectuivARB (id, GL_QUERY_RESULT, &count);
40	root	1.8	occ_query_objects.push_back (id);
41
42			return count;
43			}
44
45			octant world(0, sector (SOFFS_MIN, SOFFS_MIN, SOFFS_MIN), MAXEXTENT);
46
47			octant::octant (octant *parent, const sector &orig, uoffs extent)
48			: parent(parent), orig(orig), extent(extent)
49			{
50			for (fill = 8; fill--; )
51			sub[fill] = 0;
52	root	1.2	}
53
54			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	root	1.8	sector a2, b2;
63	root	1.4
64			ea /= 2;
65
66			a2.x = o1.x + ea;
67			a2.y = o1.y + ea;
68			a2.z = o1.z + ea;
69
70	root	1.32	b2.x = (a.x + b.x) / 2;
71			b2.y = (a.y + b.y) / 2;
72			b2.z = (a.z + b.z) / 2;
73
74			return abs (a2.x - b2.x) <= ea + (b.x - a.x)
75			&& abs (a2.y - b2.y) <= ea + (b.y - a.y)
76			&& abs (a2.z - b2.z) <= ea + (b.z - a.z);
77	root	1.4	}
78
79	root	1.32	void octant::add (entity *e)
80	root	1.2	{
81	root	1.32	const sector &a = e->a;
82			const sector &b = e->b;
83	root	1.7
84	root	1.32	if (overlap (orig, extent, a, b))
85	root	1.4	{
86	root	1.8	uoffs extent2 = extent / 2;
87
88	root	1.32	uoffs size = max (abs (b.x - a.x),
89			max (abs (b.y - a.y),
90			abs (b.z - a.z)));
91
92	root	1.8	if (size > extent2 \|\| !extent2)
93			{
94			push_back (e);
95			e->o.push_back (this);
96			return;
97			}
98	root	1.5
99	root	1.8	for (int i = 8; i--; )
100	root	1.5	{
101	root	1.8	sector s = orig;
102			s.offset (i, extent2);
103	root	1.32
104			if (overlap (s, extent2, a, b))
105	root	1.5	{
106	root	1.8	if (!sub[i])
107			sub[i] = new octant (this, s, extent2);
108
109			sub[i]->add (e);
110	root	1.5	}
111	root	1.8	}
112	root	1.4	}
113	root	1.2	}
114	root	1.1
115	root	1.32	void octant::remove (entity *e)
116	root	1.1	{
117			}
118
119	root	1.19	void octant::detect_visibility (view &ctx)
120	root	1.1	{
121	root	1.8	visibility_state &vs = ctx.vismap[this];
122
123			if (vs.generation != ctx.generation)
124	root	1.10	vs.visibility = visibility_state::UNKNOWN;
125
126	root	1.19	const sector &cam = ctx.orig;
127	root	1.10	if (cam.x >= orig.x && cam.x <= orig.x + extent
128			&& cam.y >= orig.y && cam.y <= orig.y + extent
129			&& cam.z >= orig.z && cam.z <= orig.z + extent)
130			{
131			vs.visibility = visibility_state::PARTIAL;
132			vs.generation = ctx.generation;
133			}
134			else
135			{
136			point center (
137	root	1.18	orig.x + (soffs)extent / 2 - cam.x,
138			orig.y + (soffs)extent / 2 - cam.y,
139	root	1.14	orig.z + (soffs)extent / 2 - cam.z
140	root	1.10	);
141
142	root	1.32	GLfloat dia = (2. * sqrtf (3))*(GLfloat)extent;
143	root	1.14
144			if (ctx.frustum.t.distance (center) < -dia) return;
145			if (ctx.frustum.b.distance (center) < -dia) return;
146			if (ctx.frustum.l.distance (center) < -dia) return;
147			if (ctx.frustum.r.distance (center) < -dia) return;
148			if (ctx.frustum.n.distance (center) < -dia) return;
149	root	1.25
150			GLfloat fd = ctx.frustum.f.distance (center);
151
152			if (fd < -dia)
153			{
154	root	1.29	if (fd < -dia * 2)
155	root	1.26	return;
156
157			// cull, but do check for potential visibility
158			if (size ())
159	root	1.32	{
160			ctx.farlist.push_back (this);
161			return;
162			}
163	root	1.25	}
164	root	1.10	}
165	root	1.8
166	root	1.19	if (size ())
167			ctx.vislist.push_back (this);
168
169			// node to start with
170			unsigned char si = ctx.d.x < 0 ? 1 : 0
171			\| ctx.d.y < 0 ? 2 : 0
172			\| ctx.d.z < 0 ? 4 : 0;
173
174			// bit-toggle to find next child for front-to-back order
175			static unsigned char next[8]
176			= { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7 };
177
178			for (int i = 0; i < 8; i++)
179			{
180			si ^= next[i];
181
182			if (sub[si])
183			sub[si]->detect_visibility (ctx);
184			}
185
186			vs.generation = ctx.generation;
187			}
188
189			void octant::display (view &ctx)
190			{
191	root	1.17	#if 0
192	root	1.8	glBegin (GL_LINES);
193	root	1.25	sector s = orig - ctx.orig;
194	root	1.13	vec3 clr(0, 0.8, 0);
195			glMaterialfv (GL_FRONT_AND_BACK, GL_DIFFUSE, (const GLfloat*)&clr);
196	root	1.8
197			for (int i = 8; i--; )
198			for (int ji = 3; ji--; )
199			{
200			int j = i \| (1 << ji);
201			if (i != j)
202			{
203			glVertex3i (s.x + !!(i & 1) * extent,
204			s.y + !!(i & 2) * extent,
205			s.z + !!(i & 4) * extent);
206			glVertex3i (s.x + !!(j & 1) * extent,
207			s.y + !!(j & 2) * extent,
208			s.z + !!(j & 4) * extent);
209			}
210			}
211
212			glEnd ();
213	root	1.13	glDisable(GL_COLOR_MATERIAL);
214	root	1.8	#endif
215
216	root	1.19	for (iterator i = end (); i != begin (); )
217			(*--i)->display (ctx);
218	root	1.1	}
219	root	1.8
220	root	1.25	void
221			octant::draw_bbox (view &ctx)
222			{
223			sector s = orig - ctx.orig;
224	root	1.27	int i;
225			GLint verts[4 * 6] = {
226	root	1.31	0x00, 0x40, 0x60, 0x20, // -x
227			0x10, 0x30, 0x70, 0x50, // +x
228			0x00, 0x10, 0x50, 0x40, // -y
229			0x70, 0x30, 0x20, 0x60, // +y
230			0x00, 0x20, 0x30, 0x10, // -z
231			0x40, 0x50, 0x70, 0x60, // +z
232	root	1.27	};
233
234	root	1.25	GLfloat cube[8][3] =
235			{
236	root	1.31	{ s.x , s.y , s.z },
237			{ s.x + (soffs)extent, s.y , s.z },
238			{ s.x , s.y + (soffs)extent, s.z },
239			{ s.x + (soffs)extent, s.y + (soffs)extent, s.z },
240			{ s.x , s.y , s.z + (soffs)extent },
241			{ s.x + (soffs)extent, s.y , s.z + (soffs)extent },
242			{ s.x , s.y + (soffs)extent, s.z + (soffs)extent },
243			{ s.x + (soffs)extent, s.y + (soffs)extent, s.z + (soffs)extent },
244	root	1.25	};
245
246			glBegin (GL_QUADS);
247	root	1.31
248			for (i = 0; i < 4 * 6; i++)
249			glVertex3fv (cube [verts [i] >> 4]);
250
251	root	1.25	glEnd ();
252			}
253	root	1.8
254	root	1.2