[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.87 by root, Thu Jan 6 03:09:24 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
119	if (!overlap (ctx.frustum.c, sphere (centerf, rad)))	151	if (!overlap (ctx.frustum.c, sphere (centerf, rad)))
120	return false;	152	return false;
121		153
122	oct_visibility &vs = (oct_visibility )get_visibility (ctx);	154	oct_visibility &vs = (oct_visibility )get_visibility (ctx);
123		155
124	if (orig <= ctx.orig && ctx.orig <= orig + extent)	156	//vs.state = FULL;//D
125	vs.state = PARTIAL;	157
		158	#if 0
		159	if (max (abs (centeri)) <= extent)
		160	;
126	else	161	else
127	{	162	{
		163	#endif
		164
128	if (distance (ctx.frustum.t, centerf) < -rad) return false;	165	//if (distance (ctx.frustum.t, centerf) < -rad) return false;
129	if (distance (ctx.frustum.b, centerf) < -rad) return false;	166	//if (distance (ctx.frustum.b, centerf) < -rad) return false;
130	if (distance (ctx.frustum.l, centerf) < -rad) return false;	167	//if (distance (ctx.frustum.l, centerf) < -rad) return false;
131	if (distance (ctx.frustum.r, centerf) < -rad) return false;	168	//if (distance (ctx.frustum.r, centerf) < -rad) return false;
132	if (distance (ctx.frustum.n, centerf) < -rad) return false;	169	////if (distance (ctx.frustum.n, centerf) < -rad) return false;
133		170
134	#if 0	171	#if 0
135	GLfloat fd = distance (ctx.frustum.f, centerf);	172	GLfloat fd = distance (ctx.frustum.f, centerf);
136		173
137	if (fd < -(ctx.c_far - ctx.z_far) -rad * 3.F)	174	if (fd < -(ctx.c_far - ctx.z_far) -rad * 3.F)
138	return false;	175	return false;
139	#endif	176	#endif
140	}
141		177
142	#if 0	178	// very important, optimize?
143	if (vs.state == OCCLUDED && size ())	179	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	180	if (z < 0.F \|\| ctx.perspfact * extent / z < 10.) // very crude "too small to see" check
153	return false;	181	return false;
154	//printf ("z %f, perspfact %f, z*p %f\n", z, ctx.perspfact, ctx.perspfact / z);
155		182
156	#if 0	183	#if 0
157	if (vs.state == PARTIAL \|\| vs.state == FULL)	184	if (vs.state == PARTIAL \|\| vs.state == FULL)
158	ctx.nc_far = max (ctx.nc_far, z);	185	ctx.nc_far = max (ctx.nc_far, z);
159	#endif	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;
160		204
161	// node to start with	205	// node to start with
162	unsigned char si = centeri.x > 0 ? 1 : 0	206	unsigned char si = centeri.x > 0 ? 1 : 0
163	\| centeri.y > 0 ? 2 : 0	207	\| centeri.y > 0 ? 2 : 0
164	\| centeri.z > 0 ? 4 : 0;	208	\| centeri.z > 0 ? 4 : 0;
165		209
166	// bit-toggle to find next child for front-to-back order	210	// bit-toggle to find next child for front-to-back order
167	static unsigned char toggle[8+1]	211	static unsigned char toggle[8+1]
168	= { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7, 0 };	212	= { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7, 0 };
169		213
170	bool visible = vs.state == PARTIAL \|\| vs.state == FULL;
171
172	unsigned char *next = toggle;	214	unsigned char *next = toggle;
173	do	215	do
174	{	216	{
175	si ^= *next;	217	si ^= *next;
176		218
…		…
181		223
182	if (visible)	224	if (visible)
183	{	225	{
184	if (size ())	226	if (size ())
185	ctx.vislist.push_back (this);	227	ctx.vislist.push_back (this);
		228
		229	ctx.postdepthlist.push_back (this);
186	}	230	}
187	else	231	else
188	{	232	{
189	vs.state = OCCLUDED;	233	//vs.state = OCCLUDED;
190	ctx.vislist.push_back (this);	234	ctx.postdepthlist.push_back (this);
191	}	235	}
192		236
193	return visible;	237	return visible;
194	}	238	}
195		239
196	void octant::display (view &ctx)	240	void octant::draw_depth (view &ctx)
197	{	241	{
198	oct_visibility &vs = (oct_visibility )get_visibility (ctx);	242	oct_visibility &vs = (oct_visibility )get_visibility (ctx);
199		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
200	if (vs.state == OCCLUDED)	254	if (evs.state != OCCLUDED)
201	{	255	{
202	if (ctx.pass_type == view::POSTDEPTH)	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);
203	{	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	{
204	ctx.begin_occ_query (*this, 0);	277	ctx.begin_occ_query (*this, 0);
205	sector s = orig - ctx.orig;	278	sector s = orig - ctx.orig;
206	gl::draw_bbox (s, s + extent);	279	gl::draw_bbox (s - extent, s + extent);
207	ctx.end_occ_query ();	280	ctx.end_occ_query ();
208	}
209	}	281	}
210	else	282	else
211	{	283	{
212	int nvis = 0;	284	int nvis = 0;
213		285
214	for (iterator i = begin (); i != end (); )	286	for (int i = 0; i < size (); ++i)
215	{	287	{
216	entity e = i++;	288	entity e = (this)[i];
		289	const evis &evs = vs.get_visibility (i, e);
217		290
218	evis &evs = vs.vismap[e];	291	if (evs.state == OCCLUDED)
219
220	if (ctx.pass_type == view::POSTDEPTH)
221	{	292	{
222	if (evs.state == OCCLUDED)	293	if (!ctx.may_draw (e))
223	{	294	continue;
		295
224	ctx.begin_occ_query (*this, e);	296	ctx.begin_occ_query (*this, e);
225	gl::draw_bbox (e->a - ctx.orig, e->b - ctx.orig);	297	gl::draw_bbox (e->a - ctx.orig, e->b - ctx.orig);
226	ctx.end_occ_query ();	298	ctx.end_occ_query ();
227	}
228	else
229	nvis++;
230	}	299	}
231	else	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)
232	{	374	{
233	if (!ctx.may_draw (e))	375	if (!ctx.may_draw (e))
234	continue;	376	continue;
235		377
236
237	if (evs.state != OCCLUDED)
238	{
239	sector center = ((e->a + e->b) >> 1) - ctx.orig;	378	sector center = ((e->a + e->b) >> 1) - ctx.orig;
240	GLfloat z = length (vec3 (center));	379	GLfloat z = length (vec3 (center));
241	ctx.pixfact = ctx.perspfact / z;	380	ctx.pixfact = ctx.perspfact / z;
242		381
243	ctx.nz_far = max (ctx.nz_far, z + extent);	382	if (ctx.pass->type != LIGHTED
244	ctx.nz_near = min (ctx.nz_near, z - extent);	383	\|\| !ctx.first_lighted
245		384	\|\| evs.last + 1. > timer.now)
246	if (ctx.pass_type == view::DEPTH \|\| evs.last + 0.3 > timer.now)
247	e->draw (ctx);	385	e->draw (ctx);
248	else	386	else
249	{	387	{
250	evs.last = timer.now;	388	evs.last = timer.now;
251	ctx.begin_occ_query (*this, e);	389	ctx.begin_occ_query (*this, e);
252	e->draw (ctx);	390	e->draw (ctx);
253	ctx.end_occ_query ();	391	ctx.end_occ_query ();
254	}
255	}
256	}	392	}
257	}	393	}
258
259	#if 1
260	if (ctx.pass_type == view::POSTDEPTH && nvis == 0 && size ())
261	vs.state = OCCLUDED;
262	#endif
263	}	394	}
264	}	395	}
265		396
266	void octant::event (occ_query &ev)	397	void octant::event (occ_query &ev)
267	{	398	{
268	oct_visibility &vs = (oct_visibility )get_visibility (ev.ctx);	399	oct_visibility &vs = (oct_visibility )get_visibility (ev.ctx);
269	entity e = (entity )ev.id;	400	entity e = (entity )ev.id;
270		401
271	if (e)	402	if (e)
272	{	403	{
273	evis &evs = vs.vismap[e];	404	for (vector<evis>::iterator i = vs.vismap.begin ();
		405	i != vs.vismap.end ();
		406	++i)
		407	if (i->e == e)
		408	{
274	evs.state = ev.count ? FULL : OCCLUDED;	409	i->state = ev.count ? FULL : OCCLUDED;
		410	return;
		411	}
275	}	412	}
276	else	413	else
277	vs.state = ev.count ? FULL : OCCLUDED;	414	vs.state = ev.count ? (vs.state == PARTIAL ? PARTIAL : FULL) : OCCLUDED;
278	}	415	}
279		416
280		417

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.87 by root, Thu Jan 6 03:09:24 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.87 by root, Thu Jan 6 03:09:24 2005 UTC