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

struct evis {
  entity *e;
  visibility_state state;
  double last; // time of last check

  void clear ()
  {
    last = 0.;
    state = FULL;
  }

  evis ()
  {
    clear ();
  }
};

struct oct_visibility : visibility_base
{
  vector<evis> vismap;

  visibility_state state;

  evis &get_visibility (int i, entity *e)
  {
    evis &evs = vismap [i];

    if (evs.e != e)
      {
        evs.clear ();
        evs.e = e;
      }

    return evs;
  }

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

octant world(0, sector (0, 0, 0), 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 ();
  ((oct_visibility *)vs)->state = FULL;
}

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

static bool overlap (const sector &orig, uoffs extent, const sector &a, const sector &b)
{
  sector size   = (b - a + 1) >> 1;
  sector center = a + size;

  return abs (orig - center) <= extent + size;
}

static sector offset (const sector &s, int subindex, uoffs extent)
{
  return sector (
    s.x + (subindex & 1 ? extent : -extent),
    s.y + (subindex & 2 ? extent : -extent),
    s.z + (subindex & 4 ? extent : -extent)
  );
}

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

  uoffs size = max (abs (b - a));

  if (size >= extent >> 4)
    {
      if (overlap (orig, extent, a, b))
        {
          push_back (e);
          e->o.push_back (this);
        }
    }
  else
    {
      uoffs extent2 = extent >> 1;

      for (int i = 8; i--; )
        {
          sector s = offset (orig, 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) //, bool fully_visible)
{
  ctx.stat1++;//D

  sector centeri = orig - ctx.orig;
  point centerf = point (centeri);

  GLfloat rad = ctx.diagfact * extent;

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

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

  vs.state = FULL;//D

#if 0
  if (max (abs (centeri)) <= extent)
    ;
  else
    {
#endif

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

  // very important, optimize?
  GLfloat z = ctx.z_near + distance (ctx.frustum.n, centerf) + rad;
  if (ctx.perspfact * extent / z < 10.) // very crude "too small to see" check
    return false;

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

  if (vs.state == OCCLUDED)
    {
      if (extent < ctx.z_far)
        {
          ctx.postdepthlist.push_back (this);
          return false;
        }
      else
        vs.state == PARTIAL;
    }
 
  bool visible = size () && vs.state == FULL;

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

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

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

      ctx.postdepthlist.push_back (this);
    }
  else
    {
      vs.state = OCCLUDED;
      ctx.postdepthlist.push_back (this);
    }

  return visible;
}

void octant::draw_depth (view &ctx)
{
  oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);

  vs.vismap.resize (size ());

  if (vs.state == PARTIAL || vs.state == OCCLUDED)
    return;

  for (int i = 0; i < size (); ++i)
    {
      entity *e = (*this)[i];
      const evis &evs = vs.get_visibility (i, e);

      if (evs.state != OCCLUDED)
        {
          if (!ctx.may_draw (e))
            continue;

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

          e->draw (ctx);
        }
    }
}

void octant::draw_postdepth (view &ctx)
{
  oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);

  if (vs.state == PARTIAL || vs.state == OCCLUDED)
    {
      ctx.begin_occ_query (*this, 0);
      sector s = orig - ctx.orig;
      gl::draw_bbox (s - extent, s + extent);
      ctx.end_occ_query ();
    }
  else
    {
      int nvis = 0;

      for (int i = 0; i < size (); ++i)
        {
          entity *e = (*this)[i];
          const evis &evs = vs.get_visibility (i, e);

          if (evs.state == OCCLUDED)
            {
              if (!ctx.may_draw (e))
                continue;

              ctx.begin_occ_query (*this, e);
              gl::draw_bbox (e->a - ctx.orig, e->b - ctx.orig);
              ctx.end_occ_query ();
            }
          else
            nvis++;
        }

      if (nvis == 0 && size ())
        vs.state = PARTIAL;
    }
}

void octant::draw_lighted (view &ctx)
{
  oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);

  if (vs.state == PARTIAL || vs.state == OCCLUDED)
    return;

#if 1
  {
    static vertex_buffer vb;
    static index_buffer ib;

    sector s = orig - ctx.orig;
    sector a = s - extent, b = s + extent;

    vertex_v3f vd[] = {
       point (a.x, a.y, a.z),
       point (b.x, a.y, a.z),
       point (a.x, b.y, a.z),
       point (b.x, b.y, a.z),
       point (a.x, a.y, b.z),
       point (b.x, a.y, b.z),
       point (a.x, b.y, b.z),
       point (b.x, b.y, b.z),
    };

    if (!ib)
      {
        static GLushort verts[4*6] = {
           0, 4, 6, 2,  // -x
           1, 3, 7, 5,  // +x
           0, 1, 5, 4,  // -y
           7, 3, 2, 6,  // +y
           0, 2, 3, 1,  // -z
           4, 5, 7, 6,  // +z
        };

        ib.set (verts, 4*6, GL_STATIC_DRAW_ARB);
      }

    vb.set (vd, 8, GL_STREAM_DRAW_ARB);
    vb.bind ();
    for (int i = 0; i < 6; i++)
      ib.draw (GL_LINE_LOOP, i*4, 4);

  }
#endif

  for (int i = 0; i < size (); ++i)
    {
      entity *e = (*this)[i];
      evis &evs = vs.get_visibility (i, e);

      if (evs.state != OCCLUDED)
        {
          if (!ctx.may_draw (e))
            continue;

          sector center = ((e->a + e->b) >> 1) - ctx.orig;
          GLfloat z = length (vec3 (center));
          ctx.pixfact = ctx.perspfact / z;

          if (ctx.pass->type != LIGHTED 
              || !ctx.first_lighted
              || evs.last + 0.1 > timer.now)
            e->draw (ctx);
          else
            {
              evs.last = timer.now;
              ctx.begin_occ_query (*this, e);
              e->draw (ctx);
              ctx.end_occ_query ();
            }
        }
    }
}

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

  if (e)
    {
      for (vector<evis>::iterator i = vs.vismap.begin ();
           i != vs.vismap.end ();
           ++i)
        if (i->e == e)
          {
            i->state = ev.count ? FULL : OCCLUDED;
            return;
          }
    }
  else
    vs.state = ev.count ? (vs.state == PARTIAL ? PARTIAL : FULL) : OCCLUDED;
}


Revision:	1.82
Committed:	Sat Nov 27 03:33:51 2004 UTC (19 years, 6 months ago) by root
Content type:	text/plain
Branch:	MAIN
Changes since 1.81:	+9 -7 lines
Log Message:	* empty log message *
#	Content
1	#include <cstdlib>
2
3	#include <vector>
4	using namespace std;
5
6	#include "opengl.h"
7
8	#include "oct.h"
9	#include "view.h"
10	#include "entity.h"
11
12	enum visibility_state { FULL, PARTIAL, OCCLUDED };
13
14	struct evis {
15	entity *e;
16	visibility_state state;
17	double last; // time of last check
18
19	void clear ()
20	{
21	last = 0.;
22	state = FULL;
23	}
24
25	evis ()
26	{
27	clear ();
28	}
29	};
30
31	struct oct_visibility : visibility_base
32	{
33	vector<evis> vismap;
34
35	visibility_state state;
36
37	evis &get_visibility (int i, entity *e)
38	{
39	evis &evs = vismap [i];
40
41	if (evs.e != e)
42	{
43	evs.clear ();
44	evs.e = e;
45	}
46
47	return evs;
48	}
49
50	oct_visibility (octant &oct)
51	: state(FULL)
52	{
53	}
54	};
55
56	octant world(0, sector (0, 0, 0), MAXEXTENT);
57
58	octant::octant (octant *parent, const sector &orig, uoffs extent)
59	: parent(parent)
60	, orig(orig)
61	, extent(extent)
62	{
63	for (fill = 8; fill--; )
64	sub[fill] = 0;
65	}
66
67	visibility_base *octant::new_visibility ()
68	{
69	return new oct_visibility (*this);
70	}
71
72	void octant::clear_visibility (visibility_base *vs)
73	{
74	((oct_visibility *)vs)->vismap.clear ();
75	((oct_visibility *)vs)->state = FULL;
76	}
77
78	octant::~octant ()
79	{
80	for (fill = 8; fill--; )
81	delete sub[fill];
82	}
83
84	static bool overlap (const sector &orig, uoffs extent, const sector &a, const sector &b)
85	{
86	sector size = (b - a + 1) >> 1;
87	sector center = a + size;
88
89	return abs (orig - center) <= extent + size;
90	}
91
92	static sector offset (const sector &s, int subindex, uoffs extent)
93	{
94	return sector (
95	s.x + (subindex & 1 ? extent : -extent),
96	s.y + (subindex & 2 ? extent : -extent),
97	s.z + (subindex & 4 ? extent : -extent)
98	);
99	}
100
101	void octant::add (entity *e)
102	{
103	const sector &a = e->a;
104	const sector &b = e->b;
105
106	uoffs size = max (abs (b - a));
107
108	if (size >= extent >> 4)
109	{
110	if (overlap (orig, extent, a, b))
111	{
112	push_back (e);
113	e->o.push_back (this);
114	}
115	}
116	else
117	{
118	uoffs extent2 = extent >> 1;
119
120	for (int i = 8; i--; )
121	{
122	sector s = offset (orig, i, extent2);
123
124	if (overlap (s, extent2, a, b))
125	{
126	if (!sub[i])
127	{
128	sub[i] = new octant (this, s, extent2);
129	fill++;
130	}
131
132	sub[i]->add (e);
133	}
134	}
135	}
136	}
137
138	void octant::remove (entity *e)
139	{
140	}
141
142	bool octant::detect_visibility (view &ctx) //, bool fully_visible)
143	{
144	ctx.stat1++;//D
145
146	sector centeri = orig - ctx.orig;
147	point centerf = point (centeri);
148
149	GLfloat rad = ctx.diagfact * extent;
150
151	if (!overlap (ctx.frustum.c, sphere (centerf, rad)))
152	return false;
153
154	oct_visibility &vs = (oct_visibility )get_visibility (ctx);
155
156	vs.state = FULL;//D
157
158	#if 0
159	if (max (abs (centeri)) <= extent)
160	;
161	else
162	{
163	#endif
164
165	//if (distance (ctx.frustum.t, centerf) < -rad) return false;
166	//if (distance (ctx.frustum.b, centerf) < -rad) return false;
167	//if (distance (ctx.frustum.l, centerf) < -rad) return false;
168	//if (distance (ctx.frustum.r, centerf) < -rad) return false;
169	////if (distance (ctx.frustum.n, centerf) < -rad) return false;
170
171	#if 0
172	GLfloat fd = distance (ctx.frustum.f, centerf);
173
174	if (fd < -(ctx.c_far - ctx.z_far) -rad * 3.F)
175	return false;
176	#endif
177
178	// very important, optimize?
179	GLfloat z = ctx.z_near + distance (ctx.frustum.n, centerf) + rad;
180	if (ctx.perspfact * extent / z < 10.) // very crude "too small to see" check
181	return false;
182
183	#if 0
184	if (vs.state == PARTIAL \|\| vs.state == FULL)
185	ctx.nc_far = max (ctx.nc_far, z);
186	#endif
187
188	if (vs.state == OCCLUDED)
189	{
190	if (extent < ctx.z_far)
191	{
192	ctx.postdepthlist.push_back (this);
193	return false;
194	}
195	else
196	vs.state == PARTIAL;
197	}
198
199	bool visible = size () && vs.state == FULL;
200
201	// node to start with
202	unsigned char si = centeri.x > 0 ? 1 : 0
203	\| centeri.y > 0 ? 2 : 0
204	\| centeri.z > 0 ? 4 : 0;
205
206	// bit-toggle to find next child for front-to-back order
207	static unsigned char toggle[8+1]
208	= { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7, 0 };
209
210	unsigned char *next = toggle;
211	do
212	{
213	si ^= *next;
214
215	if (sub[si])
216	visible = visible \| sub[si]->detect_visibility (ctx);
217	}
218	while (*++next);
219
220	if (visible)
221	{
222	if (size ())
223	ctx.vislist.push_back (this);
224
225	ctx.postdepthlist.push_back (this);
226	}
227	else
228	{
229	vs.state = OCCLUDED;
230	ctx.postdepthlist.push_back (this);
231	}
232
233	return visible;
234	}
235
236	void octant::draw_depth (view &ctx)
237	{
238	oct_visibility &vs = (oct_visibility )get_visibility (ctx);
239
240	vs.vismap.resize (size ());
241
242	if (vs.state == PARTIAL \|\| vs.state == OCCLUDED)
243	return;
244
245	for (int i = 0; i < size (); ++i)
246	{
247	entity e = (this)[i];
248	const evis &evs = vs.get_visibility (i, e);
249
250	if (evs.state != OCCLUDED)
251	{
252	if (!ctx.may_draw (e))
253	continue;
254
255	sector center = ((e->a + e->b) >> 1) - ctx.orig;
256	GLfloat z = length (vec3 (center));
257	ctx.pixfact = ctx.perspfact / z;
258
259	ctx.nz_far = max (ctx.nz_far, z + extent);
260	ctx.nz_near = min (ctx.nz_near, z - extent);
261
262	e->draw (ctx);
263	}
264	}
265	}
266
267	void octant::draw_postdepth (view &ctx)
268	{
269	oct_visibility &vs = (oct_visibility )get_visibility (ctx);
270
271	if (vs.state == PARTIAL \|\| vs.state == OCCLUDED)
272	{
273	ctx.begin_occ_query (*this, 0);
274	sector s = orig - ctx.orig;
275	gl::draw_bbox (s - extent, s + extent);
276	ctx.end_occ_query ();
277	}
278	else
279	{
280	int nvis = 0;
281
282	for (int i = 0; i < size (); ++i)
283	{
284	entity e = (this)[i];
285	const evis &evs = vs.get_visibility (i, e);
286
287	if (evs.state == OCCLUDED)
288	{
289	if (!ctx.may_draw (e))
290	continue;
291
292	ctx.begin_occ_query (*this, e);
293	gl::draw_bbox (e->a - ctx.orig, e->b - ctx.orig);
294	ctx.end_occ_query ();
295	}
296	else
297	nvis++;
298	}
299
300	if (nvis == 0 && size ())
301	vs.state = PARTIAL;
302	}
303	}
304
305	void octant::draw_lighted (view &ctx)
306	{
307	oct_visibility &vs = (oct_visibility )get_visibility (ctx);
308
309	if (vs.state == PARTIAL \|\| vs.state == OCCLUDED)
310	return;
311
312	#if 1
313	{
314	static vertex_buffer vb;
315	static index_buffer ib;
316
317	sector s = orig - ctx.orig;
318	sector a = s - extent, b = s + extent;
319
320	vertex_v3f vd[] = {
321	point (a.x, a.y, a.z),
322	point (b.x, a.y, a.z),
323	point (a.x, b.y, a.z),
324	point (b.x, b.y, a.z),
325	point (a.x, a.y, b.z),
326	point (b.x, a.y, b.z),
327	point (a.x, b.y, b.z),
328	point (b.x, b.y, b.z),
329	};
330
331	if (!ib)
332	{
333	static GLushort verts[4*6] = {
334	0, 4, 6, 2, // -x
335	1, 3, 7, 5, // +x
336	0, 1, 5, 4, // -y
337	7, 3, 2, 6, // +y
338	0, 2, 3, 1, // -z
339	4, 5, 7, 6, // +z
340	};
341
342	ib.set (verts, 4*6, GL_STATIC_DRAW_ARB);
343	}
344
345	vb.set (vd, 8, GL_STREAM_DRAW_ARB);
346	vb.bind ();
347	for (int i = 0; i < 6; i++)
348	ib.draw (GL_LINE_LOOP, i*4, 4);
349
350	}
351	#endif
352
353	for (int i = 0; i < size (); ++i)
354	{
355	entity e = (this)[i];
356	evis &evs = vs.get_visibility (i, e);
357
358	if (evs.state != OCCLUDED)
359	{
360	if (!ctx.may_draw (e))
361	continue;
362
363	sector center = ((e->a + e->b) >> 1) - ctx.orig;
364	GLfloat z = length (vec3 (center));
365	ctx.pixfact = ctx.perspfact / z;
366
367	if (ctx.pass->type != LIGHTED
368	\|\| !ctx.first_lighted
369	\|\| evs.last + 0.1 > timer.now)
370	e->draw (ctx);
371	else
372	{
373	evs.last = timer.now;
374	ctx.begin_occ_query (*this, e);
375	e->draw (ctx);
376	ctx.end_occ_query ();
377	}
378	}
379	}
380	}
381
382	void octant::event (occ_query &ev)
383	{
384	oct_visibility &vs = (oct_visibility )get_visibility (ev.ctx);
385	entity e = (entity )ev.id;
386
387	if (e)
388	{
389	for (vector<evis>::iterator i = vs.vismap.begin ();
390	i != vs.vismap.end ();
391	++i)
392	if (i->e == e)
393	{
394	i->state = ev.count ? FULL : OCCLUDED;
395	return;
396	}
397	}
398	else
399	vs.state = ev.count ? (vs.state == PARTIAL ? PARTIAL : FULL) : OCCLUDED;
400	}
401
402