Context Navigation

source: GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/src/ViewCellBspTree.cpp @ 727

Revision 727, 9.4 KB checked in by mattausch, 19 years ago (diff)
added view cell description bsp tree

Line
1	#include <stack>
2	#include <time.h>
3	#include <iomanip>
4
5	#include "Plane3.h"
6	#include "VspBspTree.h"
7	#include "Mesh.h"
8	#include "common.h"
9	#include "ViewCell.h"
10	#include "Environment.h"
11	#include "Polygon3.h"
12	#include "Ray.h"
13	#include "AxisAlignedBox3.h"
14	#include "Exporter.h"
15	#include "Plane3.h"
16	#include "ViewCellBsp.h"
17	#include "ViewCellsManager.h"
18	#include "Beam.h"
19
20	#define USE_FIXEDPOINT_T 0
21
22
23	//-- static members
24
25
26	int VspBspTree::sFrontId = 0;
27	int VspBspTree::sBackId = 0;
28	int VspBspTree::sFrontAndBackId = 0;
29
30	typedef pair<BspNode , BspNodeGeometry > bspNodePair;
31
32
33	// pvs penalty can be different from pvs size
34	inline float EvalPvsPenalty(const int pvs,
35	const int lower,
36	const int upper)
37	{
38	// clamp to minmax values
39	if (pvs < lower)
40	return (float)lower;
41	if (pvs > upper)
42	return (float)upper;
43
44	return (float)pvs;
45	}
46
47
48
49
50	/******************************************************************************/
51	/* class ViewCellBspTree implementation */
52	/******************************************************************************/
53
54
55	BspViewCell *VspBspTree::GetOutOfBoundsCell()
56	{
57	return mOutOfBoundsCell;
58	}
59
60	VspBspTree::~VspBspTree()
61	{
62	DEL_PTR(mRoot);
63	}
64
65	void VspBspTree::CollectViewCells(BspNode *root,
66	bool onlyValid,
67	ViewCellContainer &viewCells,
68	bool onlyUnmailed) const
69	{
70	stack<BspNode *> nodeStack;
71
72	if (!root)
73	return;
74
75	nodeStack.push(root);
76
77	while (!nodeStack.empty())
78	{
79	BspNode *node = nodeStack.top();
80	nodeStack.pop();
81
82	if (node->IsLeaf())
83	{
84	if (!onlyValid \|\| node->TreeValid())
85	{
86	ViewCell leafVc = dynamic_cast<BspLeaf >(node)->GetViewCell();
87
88	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leafVc);
89
90	if (!onlyUnmailed \|\| !viewCell->Mailed())
91	{
92	viewCell->Mail();
93	viewCells.push_back(viewCell);
94	}
95	}
96	}
97	else
98	{
99	BspInterior interior = dynamic_cast<BspInterior >(node);
100
101	nodeStack.push(interior->GetFront());
102	nodeStack.push(interior->GetBack());
103	}
104	}
105
106	}
107
108
109	int ViewCellBspTree::FindNeighbors(BspNode n, vector<BspLeaf > &neighbors,
110	const bool onlyUnmailed) const
111	{
112	stack<bspNodePair> nodeStack;
113
114	BspNodeGeometry nodeGeom;
115	ConstructGeometry(n, nodeGeom);
116
117	// split planes from the root to this node
118	// needed to verify that we found neighbor leaf
119	// TODO: really needed?
120	vector<Plane3> halfSpaces;
121	ExtractHalfSpaces(n, halfSpaces);
122
123
124	BspNodeGeometry *rgeom = new BspNodeGeometry();
125	ConstructGeometry(mRoot, *rgeom);
126
127	nodeStack.push(bspNodePair(mRoot, rgeom));
128
129	while (!nodeStack.empty())
130	{
131	BspNode *node = nodeStack.top().first;
132	BspNodeGeometry *geom = nodeStack.top().second;
133
134	nodeStack.pop();
135
136	if (node->IsLeaf())
137	{
138	// test if this leaf is in valid view space
139	if (node->TreeValid() &&
140	(node != n) &&
141	(!onlyUnmailed \|\| !node->Mailed()))
142	{
143	bool isAdjacent = true;
144
145	if (1)
146	{
147	// test all planes of current node if still adjacent
148	for (int i = 0; (i < halfSpaces.size()) && isAdjacent; ++ i)
149	{
150	const int cf =
151	Polygon3::ClassifyPlane(geom->GetPolys(),
152	halfSpaces[i],
153	mEpsilon);
154
155	if (cf == Polygon3::FRONT_SIDE)
156	{
157	isAdjacent = false;
158	}
159	}
160	}
161	else
162	{
163	// TODO: why is this wrong??
164	// test all planes of current node if still adjacent
165	for (int i = 0; (i < nodeGeom.Size()) && isAdjacent; ++ i)
166	{
167	Polygon3 *poly = nodeGeom.GetPolys()[i];
168
169	const int cf =
170	Polygon3::ClassifyPlane(geom->GetPolys(),
171	poly->GetSupportingPlane(),
172	mEpsilon);
173
174	if (cf == Polygon3::FRONT_SIDE)
175	{
176	isAdjacent = false;
177	}
178	}
179	}
180	// neighbor was found
181	if (isAdjacent)
182	{
183	neighbors.push_back(dynamic_cast<BspLeaf *>(node));
184	}
185	}
186	}
187	else
188	{
189	BspInterior interior = dynamic_cast<BspInterior >(node);
190
191	const int cf = Polygon3::ClassifyPlane(nodeGeom.GetPolys(),
192	interior->GetPlane(),
193	mEpsilon);
194
195	BspNode *front = interior->GetFront();
196	BspNode *back = interior->GetBack();
197
198	BspNodeGeometry *fGeom = new BspNodeGeometry();
199	BspNodeGeometry *bGeom = new BspNodeGeometry();
200
201	geom->SplitGeometry(*fGeom,
202	*bGeom,
203	interior->GetPlane(),
204	mBox,
205	//0.0000001f);
206	mEpsilon);
207
208	if (cf == Polygon3::BACK_SIDE)
209	{
210	nodeStack.push(bspNodePair(interior->GetBack(), bGeom));
211	DEL_PTR(fGeom);
212	}
213	else
214	{
215	if (cf == Polygon3::FRONT_SIDE)
216	{
217	nodeStack.push(bspNodePair(interior->GetFront(), fGeom));
218	DEL_PTR(bGeom);
219	}
220	else
221	{ // random decision
222	nodeStack.push(bspNodePair(front, fGeom));
223	nodeStack.push(bspNodePair(back, bGeom));
224	}
225	}
226	}
227
228	DEL_PTR(geom);
229	}
230
231	return (int)neighbors.size();
232	}
233
234
235
236	BspLeaf *ViewCellBspTree::GetRandomLeaf(const Plane3 &halfspace)
237	{
238	stack<BspNode *> nodeStack;
239	nodeStack.push(mRoot);
240
241	int mask = rand();
242
243	while (!nodeStack.empty())
244	{
245	BspNode *node = nodeStack.top();
246	nodeStack.pop();
247
248	if (node->IsLeaf())
249	{
250	return dynamic_cast<BspLeaf *>(node);
251	}
252	else
253	{
254	BspInterior interior = dynamic_cast<BspInterior >(node);
255	BspNode *next;
256	BspNodeGeometry geom;
257
258	// todo: not very efficient: constructs full cell everytime
259	ConstructGeometry(interior, geom);
260
261	const int cf =
262	Polygon3::ClassifyPlane(geom.GetPolys(), halfspace, mEpsilon);
263
264	if (cf == Polygon3::BACK_SIDE)
265	next = interior->GetFront();
266	else
267	if (cf == Polygon3::FRONT_SIDE)
268	next = interior->GetFront();
269	else
270	{
271	// random decision
272	if (mask & 1)
273	next = interior->GetBack();
274	else
275	next = interior->GetFront();
276	mask = mask >> 1;
277	}
278
279	nodeStack.push(next);
280	}
281	}
282
283	return NULL;
284	}
285
286
287	BspLeaf *ViewCellBspTree::GetRandomLeaf(const bool onlyUnmailed)
288	{
289	stack<BspNode *> nodeStack;
290
291	nodeStack.push(mRoot);
292
293	int mask = rand();
294
295	while (!nodeStack.empty())
296	{
297	BspNode *node = nodeStack.top();
298	nodeStack.pop();
299
300	if (node->IsLeaf())
301	{
302	if ( (!onlyUnmailed \|\| !node->Mailed()) )
303	return dynamic_cast<BspLeaf *>(node);
304	}
305	else
306	{
307	BspInterior interior = dynamic_cast<BspInterior >(node);
308
309	// random decision
310	if (mask & 1)
311	nodeStack.push(interior->GetBack());
312	else
313	nodeStack.push(interior->GetFront());
314
315	mask = mask >> 1;
316	}
317	}
318
319	return NULL;
320	}
321
322
323	float ViewCellBspTree::GetEpsilon() const
324	{
325	return mEpsilon;
326	}
327
328
329	int ViewCellBspTree::CastLineSegment(const Vector3 &origin,
330	const Vector3 &termination,
331	vector<ViewCell *> &viewcells)
332	{
333	int hits = 0;
334	stack<BspRayTraversalData> tQueue;
335
336	float mint = 0.0f, maxt = 1.0f;
337
338	Intersectable::NewMail();
339	ViewCell::NewMail();
340
341	Vector3 entp = origin;
342	Vector3 extp = termination;
343
344	BspNode *node = mRoot;
345	BspNode *farChild = NULL;
346
347	float t;
348	const float thresh = 1e-6f; // matt: change this
349
350	while (1)
351	{
352	if (!node->IsLeaf())
353	{
354	BspInterior in = dynamic_cast<BspInterior >(node);
355
356	Plane3 splitPlane = in->GetPlane();
357
358	const int entSide = splitPlane.Side(entp, thresh);
359	const int extSide = splitPlane.Side(extp, thresh);
360
361	if (entSide < 0)
362	{
363	node = in->GetBack();
364
365	// plane does not split ray => no far child
366	if (extSide <= 0)
367	continue;
368
369	farChild = in->GetFront(); // plane splits ray
370	}
371	else if (entSide > 0)
372	{
373	node = in->GetFront();
374
375	if (extSide >= 0) // plane does not split ray => no far child
376	continue;
377
378	farChild = in->GetBack(); // plane splits ray
379	}
380	else // one of the ray end points is on the plane
381	{ // NOTE: what to do if ray is coincident with plane?
382	if (extSide < 0)
383	node = in->GetBack();
384	else //if (extSide > 0)
385	node = in->GetFront();
386	//else break; // coincident => count no intersections
387
388	continue; // no far child
389	}
390
391	// push data for far child
392	tQueue.push(BspRayTraversalData(farChild, extp));
393
394	// find intersection of ray segment with plane
395	extp = splitPlane.FindIntersection(origin, extp, &t);
396	}
397	else
398	{
399	// reached leaf => intersection with view cell
400	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
401	ViewCell *viewCell;
402
403	if (0)
404	viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
405	else
406	viewCell = leaf->GetViewCell();
407
408	if (!viewCell->Mailed())
409	{
410	viewcells.push_back(viewCell);
411	viewCell->Mail();
412	++ hits;
413	}
414
415	//-- fetch the next far child from the stack
416	if (tQueue.empty())
417	break;
418
419	entp = extp;
420
421	BspRayTraversalData &s = tQueue.top();
422
423	node = s.mNode;
424	extp = s.mExitPoint;
425
426	tQueue.pop();
427	}
428	}
429
430	return hits;
431	}
432
433
434	bool ViewCellBspTree::ViewPointValid(const Vector3 &viewPoint) const
435	{
436	BspNode *node = mRoot;
437
438	while (1)
439	{
440	// early exit
441	if (node->TreeValid())
442	return true;
443
444	if (node->IsLeaf())
445	return false;
446
447	BspInterior in = dynamic_cast<BspInterior >(node);
448
449	if (in->GetPlane().Side(viewPoint) <= 0)
450	{
451	node = in->GetBack();
452	}
453	else
454	{
455	node = in->GetFront();
456	}
457	}
458
459	// should never come here
460	return false;
461	}

Note: See TracBrowser for help on using the repository browser.

Download in other formats: