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

Comparing libgender/oct.C (file contents):
Revision 1.39 by root, Sat Oct 9 16:37:31 2004 UTC vs.
Revision 1.92 by root, Wed Aug 10 02:37:11 2005 UTC

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

Diff Legend

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

Comparing libgender/oct.C (file contents): Revision 1.39 by root, Sat Oct 9 16:37:31 2004 UTC vs. Revision 1.92 by root, Wed Aug 10 02:37:11 2005 UTC

Diff Legend

Comparing libgender/oct.C (file contents):
Revision 1.39 by root, Sat Oct 9 16:37:31 2004 UTC vs.
Revision 1.92 by root, Wed Aug 10 02:37:11 2005 UTC