[ViewVC] Diff of: cvs/libgender/oct.C

Comparing libgender/oct.C (file contents):
Revision 1.46 by root, Sun Oct 10 00:19:45 2004 UTC vs.
Revision 1.87 by root, Thu Jan 6 03:09:24 2005 UTC

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

Diff Legend

-–
+Removed lines
-+
+Added lines
-<
+Changed lines
->
+Changed lines

Comparing libgender/oct.C (file contents): Revision 1.46 by root, Sun Oct 10 00:19:45 2004 UTC vs. Revision 1.87 by root, Thu Jan 6 03:09:24 2005 UTC

Diff Legend

Comparing libgender/oct.C (file contents):
Revision 1.46 by root, Sun Oct 10 00:19:45 2004 UTC vs.
Revision 1.87 by root, Thu Jan 6 03:09:24 2005 UTC