libgender/oct.C

#include <cstdlib>

#include <vector>

using namespace std;

#define GL_GLEXT_PROTOTYPES
#include <GL/gl.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
    glGenQueries (1, &id);

  glBeginQuery (GL_SAMPLES_PASSED, id);
  return id;
}

#define end_occ_query() glEndQuery (GL_SAMPLES_PASSED);

static GLuint occ_query_result (GLuint id)
{
  GLuint count;

  glGetQueryObjectuiv (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 box &bbox)
{
  sector a2, b2;

  ea /= 2;

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

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

void octant::add (entity_base *e)
{
  box bbox = translate (e->bbox, e->orig, sector (0, 0, 0));

  uoffs size = max (abs (bbox.b.x - bbox.a.x),
               max (abs (bbox.b.y - bbox.a.y),
                    abs (bbox.b.z - bbox.a.z)));

  if (overlap (orig, extent, bbox))
    {
      uoffs extent2 = extent / 2;

      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, bbox))
            {
              if (!sub[i])
                sub[i] = new octant (this, s, extent2);

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

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

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

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

  const sector &cam = ctx.v.orig;
#if 0
  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
#endif
    {
      //printf ("OCTANT %d,%d,%d+%d\n", orig.x, orig.y, orig.z, extent);
      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 = (0.5 * sqrtf (3))*(GLfloat)extent;

#if 0
      printf ("DISTANCE %f,%f,%f TO near: %f\n",
          center.x, center.y, center.z,
          ctx.frustum.n.distance (center)
          );
#endif
#if 0
      printf ("DISTANCE %f,%f,%f TO far: %f\n",
          center.x, center.y, center.z,
          ctx.frustum.f.distance (center)
          );
#endif
#if 1
      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;
      if (ctx.frustum.f.distance (center) < -dia) return;
#endif

    }

#if 1
  glBegin (GL_LINES);
  sector s = orig;
  s.x -= ctx.v.orig.x;
  s.y -= ctx.v.orig.y;
  s.z -= ctx.v.orig.z;
  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

#if 0
  if (vs.visibility == visibility_state::PARTIAL
      && vs.generation == ctx.generation)
#endif
    {
      for (iterator i = end (); i-- != begin (); )
#if 0
        printf ("draw %p %d,%d,%d     (%d,%d,%d - %d,%d,%d)\n", *i,
            (*i)->orig.x,
            (*i)->orig.y,
            (*i)->orig.z,
            (*i)->bbox.a.x,
            (*i)->bbox.a.y,
            (*i)->bbox.a.z,
            (*i)->bbox.b.x,
            (*i)->bbox.b.y,
            (*i)->bbox.b.z
            ),
#endif
        (*i)->display (ctx);

      // node to start with
      unsigned char si = ctx.v.d.x < 0 ? 1 : 0
                       | ctx.v.d.y < 0 ? 2 : 0
                       | ctx.v.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]->draw (ctx);
        }
    }

  vs.generation = ctx.generation;
}


Revision:	1.16
Committed:	Tue Oct 5 07:48:33 2004 UTC (19 years, 8 months ago) by root
Content type:	text/plain
Branch:	MAIN
Changes since 1.15:	+1 -1 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
10	root	1.1	#include "oct.h"
11	root	1.8	#include "view.h"
12	root	1.2	#include "entity.h"
13
14	root	1.8	vector<GLuint> occ_query_objects;
15	root	1.2
16	root	1.8	static GLuint begin_occ_query ()
17	root	1.2	{
18	root	1.8	GLuint id;
19	root	1.2
20	root	1.8	if (occ_query_objects.size ())
21	root	1.3	{
22	root	1.8	id = *(occ_query_objects.end () - 1);
23			occ_query_objects.pop_back ();
24	root	1.3	}
25			else
26	root	1.11	glGenQueries (1, &id);
27	root	1.8
28	root	1.11	glBeginQuery (GL_SAMPLES_PASSED, id);
29	root	1.8	return id;
30			}
31
32	root	1.11	#define end_occ_query() glEndQuery (GL_SAMPLES_PASSED);
33	root	1.8
34			static GLuint occ_query_result (GLuint id)
35			{
36			GLuint count;
37
38	root	1.11	glGetQueryObjectuiv (id, GL_QUERY_RESULT, &count);
39	root	1.8	occ_query_objects.push_back (id);
40
41			return count;
42			}
43
44			octant world(0, sector (SOFFS_MIN, SOFFS_MIN, SOFFS_MIN), MAXEXTENT);
45
46			octant::octant (octant *parent, const sector &orig, uoffs extent)
47			: parent(parent), orig(orig), extent(extent)
48			{
49			for (fill = 8; fill--; )
50			sub[fill] = 0;
51	root	1.2	}
52
53			octant::~octant ()
54			{
55			for (fill = 8; fill--; )
56			delete sub[fill];
57			}
58
59	root	1.8	static bool overlap (const sector &o1, uoffs ea, const box &bbox)
60	root	1.4	{
61	root	1.8	sector a2, b2;
62	root	1.4
63			ea /= 2;
64
65			a2.x = o1.x + ea;
66			a2.y = o1.y + ea;
67			a2.z = o1.z + ea;
68
69	root	1.8	b2.x = (bbox.a.x + bbox.b.x) / 2;
70			b2.y = (bbox.a.y + bbox.b.y) / 2;
71			b2.z = (bbox.a.z + bbox.b.z) / 2;
72
73			return abs (a2.x - b2.x) <= ea + (bbox.b.x - bbox.a.x)
74			&& abs (a2.y - b2.y) <= ea + (bbox.b.y - bbox.a.y)
75			&& abs (a2.z - b2.z) <= ea + (bbox.b.z - bbox.a.z);
76	root	1.4	}
77
78	root	1.6	void octant::add (entity_base *e)
79	root	1.2	{
80	root	1.8	box bbox = translate (e->bbox, e->orig, sector (0, 0, 0));
81	root	1.7
82			uoffs size = max (abs (bbox.b.x - bbox.a.x),
83	root	1.8	max (abs (bbox.b.y - bbox.a.y),
84			abs (bbox.b.z - bbox.a.z)));
85	root	1.3
86	root	1.8	if (overlap (orig, extent, bbox))
87	root	1.4	{
88	root	1.8	uoffs extent2 = extent / 2;
89
90			if (size > extent2 \|\| !extent2)
91			{
92			push_back (e);
93			e->o.push_back (this);
94			return;
95			}
96	root	1.5
97	root	1.8	for (int i = 8; i--; )
98	root	1.5	{
99	root	1.8	sector s = orig;
100			s.offset (i, extent2);
101			if (overlap (s, extent2, bbox))
102	root	1.5	{
103	root	1.8	if (!sub[i])
104			sub[i] = new octant (this, s, extent2);
105
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			void octant::remove (entity_base *e)
113			{
114			}
115
116	root	1.4	void octant::draw (draw_context &ctx)
117	root	1.1	{
118	root	1.8	visibility_state &vs = ctx.vismap[this];
119
120			if (vs.generation != ctx.generation)
121	root	1.10	vs.visibility = visibility_state::UNKNOWN;
122
123			const sector &cam = ctx.v.orig;
124	root	1.14	#if 0
125	root	1.10	if (cam.x >= orig.x && cam.x <= orig.x + extent
126			&& cam.y >= orig.y && cam.y <= orig.y + extent
127			&& cam.z >= orig.z && cam.z <= orig.z + extent)
128			{
129			vs.visibility = visibility_state::PARTIAL;
130			vs.generation = ctx.generation;
131			}
132			else
133	root	1.14	#endif
134	root	1.10	{
135			//printf ("OCTANT %d,%d,%d+%d\n", orig.x, orig.y, orig.z, extent);
136			point center (
137	root	1.14	orig.x + (soffs)extent / 2 - cam.x ,
138			orig.y + (soffs)extent / 2 - cam.y ,
139			orig.z + (soffs)extent / 2 - cam.z
140	root	1.10	);
141
142	root	1.14	GLfloat dia = (0.5 * sqrtf (3))*(GLfloat)extent;
143
144	root	1.10	#if 0
145			printf ("DISTANCE %f,%f,%f TO near: %f\n",
146			center.x, center.y, center.z,
147			ctx.frustum.n.distance (center)
148			);
149			#endif
150	root	1.12	#if 0
151	root	1.10	printf ("DISTANCE %f,%f,%f TO far: %f\n",
152			center.x, center.y, center.z,
153			ctx.frustum.f.distance (center)
154			);
155			#endif
156	root	1.12	#if 1
157	root	1.14	if (ctx.frustum.t.distance (center) < -dia) return;
158			if (ctx.frustum.b.distance (center) < -dia) return;
159			if (ctx.frustum.l.distance (center) < -dia) return;
160			if (ctx.frustum.r.distance (center) < -dia) return;
161			if (ctx.frustum.n.distance (center) < -dia) return;
162			if (ctx.frustum.f.distance (center) < -dia) return;
163	root	1.10	#endif
164
165			}
166	root	1.8
167	root	1.16	#if 1
168	root	1.8	glBegin (GL_LINES);
169			sector s = orig;
170			s.x -= ctx.v.orig.x;
171			s.y -= ctx.v.orig.y;
172			s.z -= ctx.v.orig.z;
173	root	1.13	vec3 clr(0, 0.8, 0);
174			glMaterialfv (GL_FRONT_AND_BACK, GL_DIFFUSE, (const GLfloat*)&clr);
175	root	1.8
176			for (int i = 8; i--; )
177			for (int ji = 3; ji--; )
178			{
179			int j = i \| (1 << ji);
180			if (i != j)
181			{
182			glVertex3i (s.x + !!(i & 1) * extent,
183			s.y + !!(i & 2) * extent,
184			s.z + !!(i & 4) * extent);
185			glVertex3i (s.x + !!(j & 1) * extent,
186			s.y + !!(j & 2) * extent,
187			s.z + !!(j & 4) * extent);
188			}
189			}
190
191			glEnd ();
192	root	1.13	glDisable(GL_COLOR_MATERIAL);
193	root	1.8	#endif
194
195	root	1.10	#if 0
196			if (vs.visibility == visibility_state::PARTIAL
197	root	1.8	&& vs.generation == ctx.generation)
198	root	1.10	#endif
199	root	1.8	{
200			for (iterator i = end (); i-- != begin (); )
201	root	1.10	#if 0
202			printf ("draw %p %d,%d,%d (%d,%d,%d - %d,%d,%d)\n", *i,
203			(*i)->orig.x,
204			(*i)->orig.y,
205			(*i)->orig.z,
206			(*i)->bbox.a.x,
207			(*i)->bbox.a.y,
208			(*i)->bbox.a.z,
209			(*i)->bbox.b.x,
210			(*i)->bbox.b.y,
211			(*i)->bbox.b.z
212			),
213			#endif
214	root	1.8	(*i)->display (ctx);
215
216	root	1.10	// node to start with
217			unsigned char si = ctx.v.d.x < 0 ? 1 : 0
218			\| ctx.v.d.y < 0 ? 2 : 0
219			\| ctx.v.d.z < 0 ? 4 : 0;
220
221			// bit-toggle to find next child for front-to-back order
222			static unsigned char next[8]
223			= { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7 };
224
225			for (int i = 0; i < 8; i++)
226			{
227			si ^= next[i];
228
229			if (sub[si])
230			sub[si]->draw (ctx);
231			}
232	root	1.8	}
233
234			vs.generation = ctx.generation;
235	root	1.1	}
236	root	1.8
237
238	root	1.2