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

Comparing libgender/oct.C (file contents):
Revision 1.71 by root, Sun Nov 7 02:28:18 2004 UTC vs.
Revision 1.84 by root, Sun Jan 2 12:11:03 2005 UTC

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

Diff Legend

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

Comparing libgender/oct.C (file contents): Revision 1.71 by root, Sun Nov 7 02:28:18 2004 UTC vs. Revision 1.84 by root, Sun Jan 2 12:11:03 2005 UTC

Diff Legend

Comparing libgender/oct.C (file contents):
Revision 1.71 by root, Sun Nov 7 02:28:18 2004 UTC vs.
Revision 1.84 by root, Sun Jan 2 12:11:03 2005 UTC