libgender/oct.C

#include <cstdlib>

#include <vector>

using namespace std;

#include "opengl.h"

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

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)
{
  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 || !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];

  GLfloat extent2 = 0.5F * (GLfloat)extent;
  point center = point (orig + (extent >> 1) - ctx.orig);
  if (extent & 1) center = center + 0.5F;
  GLfloat rad = ctx.diagfact * extent2;

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

  vs.generation = ctx.generation;

  if (orig <= ctx.orig && ctx.orig <= orig + extent)
    vs.visibility = visibility_state::PARTIAL;
  else
    {
      if (ctx.frustum.t.distance (center) < -rad) return;
      if (ctx.frustum.b.distance (center) < -rad) return;
      if (ctx.frustum.l.distance (center) < -rad) return;
      if (ctx.frustum.r.distance (center) < -rad) return;
      if (ctx.frustum.n.distance (center) < -rad) return;

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

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

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

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

  GLfloat z = ctx.z_near + ctx.frustum.n.distance (center) + rad;

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

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

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 ();
#endif

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

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

  gl::draw_box (ctx, s, s + extent);
}

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

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

Revision:	1.49
Committed:	Sun Oct 10 18:14:22 2004 UTC (19 years, 8 months ago) by root
Content type:	text/plain
Branch:	MAIN
Changes since 1.48:	+0 -2 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.8	octant world(0, sector (SOFFS_MIN, SOFFS_MIN, SOFFS_MIN), MAXEXTENT);
14
15			octant::octant (octant *parent, const sector &orig, uoffs extent)
16			: parent(parent), orig(orig), extent(extent)
17			{
18			for (fill = 8; fill--; )
19			sub[fill] = 0;
20	root	1.2	}
21
22			octant::~octant ()
23			{
24			for (fill = 8; fill--; )
25			delete sub[fill];
26			}
27
28	root	1.32	static bool overlap (const sector &o1, uoffs ea, const sector &a, const sector &b)
29	root	1.4	{
30			ea /= 2;
31
32	root	1.34	sector center_1 = o1 + ea;
33			sector size_2 = b - a;
34			sector center_2 = a + size_2 / 2;
35	root	1.33
36	root	1.34	return abs (center_1 - center_2) <= ea + size_2;
37	root	1.4	}
38
39	root	1.32	void octant::add (entity *e)
40	root	1.2	{
41	root	1.32	const sector &a = e->a;
42			const sector &b = e->b;
43	root	1.7
44	root	1.32	if (overlap (orig, extent, a, b))
45	root	1.4	{
46	root	1.8	uoffs extent2 = extent / 2;
47	root	1.34	uoffs size = max (abs (b - a));
48	root	1.32
49	root	1.8	if (size > extent2 \|\| !extent2)
50			{
51			push_back (e);
52			e->o.push_back (this);
53			return;
54			}
55	root	1.5
56	root	1.8	for (int i = 8; i--; )
57	root	1.5	{
58	root	1.8	sector s = orig;
59			s.offset (i, extent2);
60	root	1.32
61			if (overlap (s, extent2, a, b))
62	root	1.5	{
63	root	1.8	if (!sub[i])
64			sub[i] = new octant (this, s, extent2);
65
66			sub[i]->add (e);
67	root	1.5	}
68	root	1.8	}
69	root	1.4	}
70	root	1.2	}
71	root	1.1
72	root	1.32	void octant::remove (entity *e)
73	root	1.1	{
74			}
75
76	root	1.19	void octant::detect_visibility (view &ctx)
77	root	1.1	{
78	root	1.8	visibility_state &vs = ctx.vismap[this];
79
80	root	1.43	GLfloat extent2 = 0.5F * (GLfloat)extent;
81			point center = point (orig + (extent >> 1) - ctx.orig);
82			if (extent & 1) center = center + 0.5F;
83			GLfloat rad = ctx.diagfact * extent2;
84
85	root	1.45	if (vs.generation + 1 != ctx.generation)
86	root	1.10	vs.visibility = visibility_state::UNKNOWN;
87
88	root	1.43	vs.generation = ctx.generation;
89
90	root	1.34	if (orig <= ctx.orig && ctx.orig <= orig + extent)
91	root	1.43	vs.visibility = visibility_state::PARTIAL;
92	root	1.10	else
93			{
94	root	1.37	if (ctx.frustum.t.distance (center) < -rad) return;
95			if (ctx.frustum.b.distance (center) < -rad) return;
96			if (ctx.frustum.l.distance (center) < -rad) return;
97			if (ctx.frustum.r.distance (center) < -rad) return;
98			if (ctx.frustum.n.distance (center) < -rad) return;
99	root	1.25
100			GLfloat fd = ctx.frustum.f.distance (center);
101
102	root	1.47	if (fd < -(ctx.c_far - ctx.z_far) -rad * 3.F)
103			return;
104	root	1.10	}
105	root	1.8
106	root	1.46	if (vs.visibility == visibility_state::OCCLUDED
107			\|\| vs.visibility == visibility_state::UNKNOWN)
108	root	1.45	{
109			ctx.farlist.push_back (this);
110			return;
111			}
112
113	root	1.46	#if 0
114	root	1.36	if (vs.visibility == visibility_state::UNKNOWN)
115			vs.visibility = visibility_state::FULL;
116	root	1.46	#endif
117	root	1.36
118	root	1.45	GLfloat z = ctx.z_near + ctx.frustum.n.distance (center) + rad;
119
120			if (vs.visibility == visibility_state::FULL)
121			ctx.nc_far = max (ctx.nc_far, z);
122
123	root	1.41	if (size ()
124			&& (vs.visibility == visibility_state::PARTIAL
125			\|\| vs.visibility == visibility_state::FULL))
126	root	1.43	{
127	root	1.45	ctx.nz_far = max (ctx.nz_far, z);
128	root	1.43	ctx.vislist.push_back (this);
129	root	1.44	}
130
131	root	1.19	// node to start with
132			unsigned char si = ctx.d.x < 0 ? 1 : 0
133			\| ctx.d.y < 0 ? 2 : 0
134			\| ctx.d.z < 0 ? 4 : 0;
135
136			// bit-toggle to find next child for front-to-back order
137			static unsigned char next[8]
138			= { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7 };
139
140			for (int i = 0; i < 8; i++)
141			{
142			si ^= next[i];
143
144			if (sub[si])
145			sub[si]->detect_visibility (ctx);
146			}
147			}
148
149			void octant::display (view &ctx)
150			{
151	root	1.17	#if 0
152	root	1.8	glBegin (GL_LINES);
153	root	1.25	sector s = orig - ctx.orig;
154	root	1.13	vec3 clr(0, 0.8, 0);
155			glMaterialfv (GL_FRONT_AND_BACK, GL_DIFFUSE, (const GLfloat*)&clr);
156	root	1.8
157			for (int i = 8; i--; )
158			for (int ji = 3; ji--; )
159			{
160			int j = i \| (1 << ji);
161			if (i != j)
162			{
163			glVertex3i (s.x + !!(i & 1) * extent,
164			s.y + !!(i & 2) * extent,
165			s.z + !!(i & 4) * extent);
166			glVertex3i (s.x + !!(j & 1) * extent,
167			s.y + !!(j & 2) * extent,
168			s.z + !!(j & 4) * extent);
169			}
170			}
171
172			glEnd ();
173			#endif
174
175	root	1.19	for (iterator i = end (); i != begin (); )
176			(*--i)->display (ctx);
177	root	1.1	}
178	root	1.8
179	root	1.38	void octant::draw_bbox (view &ctx)
180	root	1.25	{
181			sector s = orig - ctx.orig;
182	root	1.27
183	root	1.37	gl::draw_box (ctx, s, s + extent);
184	root	1.25	}
185	root	1.8
186	root	1.38	void octant::event (occ_query &ev)
187			{
188	root	1.44	visibility_state &vs = ev.v.vismap[this];
189
190			vs.last = timer.now;
191	root	1.47	vs.visibility = ev.r <= 0
192	root	1.44	? visibility_state::OCCLUDED
193			: visibility_state::FULL;
194	root	1.38	}
195	root	1.2