Planet

navi

home

PPS

about

screenshots

download

development

forum

Context Navigation

source: downloads/OgreMain/src/OgreConvexBody.cpp @ 1

Last change on this file since 1 was 1, checked in by landauf, 17 years ago

File size: 36.5 KB

Line
1	/*
2	-----------------------------------------------------------------------------
3	This source file is part of OGRE
4	(Object-oriented Graphics Rendering Engine)
5	For the latest info, see http://www.ogre3d.org/
6
7	Copyright (c) 2000-2006 Torus Knot Software Ltd
8	Copyright (c) 2006 Matthias Fink, netAllied GmbH <matthias.fink@web.de>
9	Also see acknowledgements in Readme.html
10
11	This program is free software; you can redistribute it and/or modify it under
12	the terms of the GNU Lesser General Public License as published by the Free Software
13	Foundation; either version 2 of the License, or (at your option) any later
14	version.
15
16	This program is distributed in the hope that it will be useful, but WITHOUT
17	ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
18	FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
19
20	You should have received a copy of the GNU Lesser General Public License along with
21	this program; if not, write to the Free Software Foundation, Inc., 59 Temple
22	Place - Suite 330, Boston, MA 02111-1307, USA, or go to
23	http://www.gnu.org/copyleft/lesser.txt.
24
25	You may alternatively use this source under the terms of a specific version of
26	the OGRE Unrestricted License provided you have obtained such a license from
27	Torus Knot Software Ltd.
28	-----------------------------------------------------------------------------
29	*/
30	#include "OgreStableHeaders.h"
31	#include "OgreConvexBody.h"
32	#include "OgreException.h"
33	#include "OgreVector3.h"
34	#include <OgreLogManager.h>
35	#include <OgreRay.h>
36	#include <OgreFrustum.h>
37	#include <OgreAxisAlignedBox.h>
38
39
40	namespace Ogre
41	{
42
43
44	//-----------------------------------------------------------------------
45	// Statics
46	//-----------------------------------------------------------------------
47	ConvexBody::PolygonList ConvexBody::msFreePolygons;
48	#if OGRE_THREAD_SUPPORT
49	boost::recursive_mutex ConvexBody::msFreePolygonsMutex;
50	#endif
51	//-----------------------------------------------------------------------
52	void ConvexBody::_initialisePool()
53	{
54	OGRE_LOCK_MUTEX(msFreePolygonsMutex)
55
56	if (msFreePolygons.empty())
57	{
58	const size_t initialSize = 30;
59
60	// Initialise polygon pool with 30 polys
61	msFreePolygons.resize(initialSize);
62	for (size_t i = 0; i < initialSize; ++i)
63	{
64	msFreePolygons[i] = new Polygon();
65	}
66	}
67	}
68	//-----------------------------------------------------------------------
69	void ConvexBody::_destroyPool()
70	{
71	OGRE_LOCK_MUTEX(msFreePolygonsMutex)
72
73	for (PolygonList::iterator i = msFreePolygons.begin();
74	i != msFreePolygons.end(); ++i)
75	{
76	delete *i;
77	}
78	msFreePolygons.clear();
79	}
80	//-----------------------------------------------------------------------
81	Polygon* ConvexBody::allocatePolygon()
82	{
83	OGRE_LOCK_MUTEX(msFreePolygonsMutex)
84
85	if (msFreePolygons.empty())
86	{
87	// if we ran out of polys to use, create a new one
88	// hopefully this one will return to the pool in due course
89	return new Polygon();
90	}
91	else
92	{
93	Polygon* ret = msFreePolygons.back();
94	ret->reset();
95
96	msFreePolygons.pop_back();
97
98	return ret;
99
100	}
101	}
102	//-----------------------------------------------------------------------
103	void ConvexBody::freePolygon(Polygon* poly)
104	{
105	OGRE_LOCK_MUTEX(msFreePolygonsMutex)
106	msFreePolygons.push_back(poly);
107	}
108	//-----------------------------------------------------------------------
109	//-----------------------------------------------------------------------
110	ConvexBody::ConvexBody()
111	{
112	// Reserve space for 8 polys, normally 6 faces plus a couple of clips
113	mPolygons.reserve(8);
114
115	}
116	//-----------------------------------------------------------------------
117	ConvexBody::~ConvexBody()
118	{
119	reset();
120	}
121	//-----------------------------------------------------------------------
122	ConvexBody::ConvexBody( const ConvexBody& cpy )
123	{
124	for ( size_t i = 0; i < cpy.getPolygonCount(); ++i )
125	{
126	Polygon *p = allocatePolygon();
127	*p = cpy.getPolygon( i );
128	mPolygons.push_back( p );
129	}
130	}
131	//-----------------------------------------------------------------------
132	void ConvexBody::define(const Frustum& frustum)
133	{
134	// ordering of the points:
135	// near (0-3), far (4-7); each (top-right, top-left, bottom-left, bottom-right)
136	// 5-----4
137	// /\| /\|
138	// / \| / \|
139	// 1-----0 \|
140	// \| 6--\|--7
141	// \| / \| /
142	// \|/ \|/
143	// 2-----3
144
145	const Vector3 *pts = frustum.getWorldSpaceCorners();
146
147	/// reset ConvexBody
148	reset();
149
150	/// update vertices: near, far, left, right, bottom, top; fill in ccw
151	Polygon *poly;
152
153	// near
154	poly = allocatePolygon();
155	poly->insertVertex( pts[0] );
156	poly->insertVertex( pts[1] );
157	poly->insertVertex( pts[2] );
158	poly->insertVertex( pts[3] );
159	mPolygons.push_back( poly );
160
161	// far
162	poly = allocatePolygon();
163	poly->insertVertex( pts[5] );
164	poly->insertVertex( pts[4] );
165	poly->insertVertex( pts[7] );
166	poly->insertVertex( pts[6] );
167	mPolygons.push_back( poly );
168
169	// left
170	poly = allocatePolygon();
171	poly->insertVertex( pts[5] );
172	poly->insertVertex( pts[6] );
173	poly->insertVertex( pts[2] );
174	poly->insertVertex( pts[1] );
175	mPolygons.push_back( poly );
176
177	// right
178	poly = allocatePolygon();
179	poly->insertVertex( pts[4] );
180	poly->insertVertex( pts[0] );
181	poly->insertVertex( pts[3] );
182	poly->insertVertex( pts[7] );
183	mPolygons.push_back( poly );
184
185	// bottom
186	poly = allocatePolygon();
187	poly->insertVertex( pts[6] );
188	poly->insertVertex( pts[7] );
189	poly->insertVertex( pts[3] );
190	poly->insertVertex( pts[2] );
191	mPolygons.push_back( poly );
192
193	// top
194	poly = allocatePolygon();
195	poly->insertVertex( pts[4] );
196	poly->insertVertex( pts[5] );
197	poly->insertVertex( pts[1] );
198	poly->insertVertex( pts[0] );
199	mPolygons.push_back( poly );
200	}
201	//-----------------------------------------------------------------------
202	void ConvexBody::define(const AxisAlignedBox& aab)
203	{
204	// ordering of the AAB points:
205	// 1-----2
206	// /\| /\|
207	// / \| / \|
208	// 5-----4 \|
209	// \| 0--\|--3
210	// \| / \| /
211	// \|/ \|/
212	// 6-----7
213
214	const Vector3& min = aab.getMinimum();
215	const Vector3& max = aab.getMaximum();
216
217	Vector3 currentVertex = min;
218
219	Polygon *poly;
220
221	// reset body
222	reset();
223
224	// far
225	poly = allocatePolygon();
226	poly->insertVertex( currentVertex ); // 0
227	currentVertex.y = max.y;
228	poly->insertVertex( currentVertex ); // 1
229	currentVertex.x = max.x;
230	poly->insertVertex( currentVertex ); // 2
231	currentVertex.y = min.y;
232	poly->insertVertex( currentVertex ); // 3
233	insertPolygon( poly );
234
235	// right
236	poly = allocatePolygon();
237	poly->insertVertex( currentVertex ); // 3
238	currentVertex.y = max.y;
239	poly->insertVertex( currentVertex ); // 2
240	currentVertex.z = max.z;
241	poly->insertVertex( currentVertex ); // 4
242	currentVertex.y = min.y;
243	poly->insertVertex( currentVertex ); // 7
244	insertPolygon( poly );
245
246	// near
247	poly = allocatePolygon();
248	poly->insertVertex( currentVertex ); // 7
249	currentVertex.y = max.y;
250	poly->insertVertex( currentVertex ); // 4
251	currentVertex.x = min.x;
252	poly->insertVertex( currentVertex ); // 5
253	currentVertex.y = min.y;
254	poly->insertVertex( currentVertex ); // 6
255	insertPolygon( poly );
256
257	// left
258	poly = allocatePolygon();
259	poly->insertVertex( currentVertex ); // 6
260	currentVertex.y = max.y;
261	poly->insertVertex( currentVertex ); // 5
262	currentVertex.z = min.z;
263	poly->insertVertex( currentVertex ); // 1
264	currentVertex.y = min.y;
265	poly->insertVertex( currentVertex ); // 0
266	insertPolygon( poly );
267
268	// bottom
269	poly = allocatePolygon();
270	poly->insertVertex( currentVertex ); // 0
271	currentVertex.x = max.x;
272	poly->insertVertex( currentVertex ); // 3
273	currentVertex.z = max.z;
274	poly->insertVertex( currentVertex ); // 7
275	currentVertex.x = min.x;
276	poly->insertVertex( currentVertex ); // 6
277	insertPolygon( poly );
278
279	// top
280	poly = allocatePolygon();
281	currentVertex = max;
282	poly->insertVertex( currentVertex ); // 4
283	currentVertex.z = min.z;
284	poly->insertVertex( currentVertex ); // 2
285	currentVertex.x = min.x;
286	poly->insertVertex( currentVertex ); // 1
287	currentVertex.z = max.z;
288	poly->insertVertex( currentVertex ); // 5
289	insertPolygon( poly );
290
291	}
292	//-----------------------------------------------------------------------
293	void ConvexBody::clip(const AxisAlignedBox& aab)
294	{
295	// ordering of the AAB points:
296	// 1-----2
297	// /\| /\|
298	// / \| / \|
299	// 5-----4 \|
300	// \| 0--\|--3
301	// \| / \| /
302	// \|/ \|/
303	// 6-----7
304
305	const Vector3& min = aab.getMinimum();
306	const Vector3& max = aab.getMaximum();
307
308	// clip object for each plane of the AAB
309	Plane p;
310
311
312	// front
313	p.redefine(Vector3::UNIT_Z, max);
314	clip(p);
315
316	// back
317	p.redefine(Vector3::NEGATIVE_UNIT_Z, min);
318	clip(p);
319
320	// left
321	p.redefine(Vector3::NEGATIVE_UNIT_X, min);
322	clip(p);
323
324	// right
325	p.redefine(Vector3::UNIT_X, max);
326	clip(p);
327
328	// bottom
329	p.redefine(Vector3::NEGATIVE_UNIT_Y, min);
330	clip(p);
331
332	// top
333	p.redefine(Vector3::UNIT_Y, max);
334	clip(p);
335
336	}
337	//-----------------------------------------------------------------------
338	void ConvexBody::clip(const Frustum& fr)
339	{
340	// clip the body with each plane
341	for ( unsigned short i = 0; i < 6; ++i )
342	{
343	// clip, but keep positive space this time since frustum planes are
344	// the opposite to other cases (facing inwards rather than outwards)
345	clip(fr.getFrustumPlane(i), false);
346	}
347	}
348	//-----------------------------------------------------------------------
349	void ConvexBody::clip(const ConvexBody& body)
350	{
351	if ( this == &body )
352	return;
353
354	// for each polygon; clip 'this' with each plane of 'body'
355	// front vertex representation is ccw
356
357	Plane pl;
358
359	for ( size_t iPoly = 0; iPoly < body.getPolygonCount(); ++iPoly )
360	{
361	const Polygon& p = body.getPolygon( iPoly );
362
363	OgreAssert( p.getVertexCount() >= 3, "A valid polygon must contain at least three vertices." );
364
365	// set up plane with first three vertices of the polygon (a polygon is always planar)
366	pl.redefine( p.getVertex( 0 ), p.getVertex( 1 ), p.getVertex( 2 ) );
367
368	clip(pl);
369	}
370	}
371	//-----------------------------------------------------------------------
372	void ConvexBody::extend(const Vector3& pt)
373	{
374	// Erase all polygons facing towards the point. For all edges that
375	// are not removed twice (once in AB and once BA direction) build a
376	// convex polygon (triangle) with the point.
377	Polygon::EdgeMap edgeMap;
378
379	for ( size_t i = 0; i < getPolygonCount(); ++i )
380	{
381	const Vector3& normal = getNormal( i );
382	// direction of the point in regard to the polygon
383	// the polygon is planar so we can take an arbitrary vertex
384	Vector3 ptDir = pt - getVertex( i, 0 );
385	ptDir.normalise();
386
387	// remove polygon if dot product is greater or equals null.
388	if ( normal.dotProduct( ptDir ) >= 0 )
389	{
390	// store edges (copy them because if the polygon is deleted
391	// its vertices are also deleted)
392	storeEdgesOfPolygon( i, &edgeMap );
393
394	// remove polygon
395	deletePolygon( i );
396
397	// decrement iterator because of deleted polygon
398	--i;
399	}
400	}
401
402	// point is already a part of the hull (point lies inside)
403	if ( edgeMap.empty() )
404	return;
405
406	// remove the edges that are twice in the list (once from each side: AB,BA)
407
408	Polygon::EdgeMap::iterator it;
409	// iterate from first to the element before the last one
410	for (Polygon::EdgeMap::iterator itStart = edgeMap.begin();
411	itStart != edgeMap.end(); )
412	{
413	// compare with iterator + 1 to end
414	// don't need to skip last entry in itStart since omitted in inner loop
415	it = itStart;
416	++it;
417
418	bool erased = false;
419	// iterate from itStart+1 to the element before the last one
420	for ( ; it != edgeMap.end(); ++it )
421	{
422	if (itStart->first.positionEquals(it->second) &&
423	itStart->second.positionEquals(it->first))
424	{
425	edgeMap.erase(it);
426	// increment itStart before deletion (iterator invalidation)
427	Polygon::EdgeMap::iterator delistart = itStart++;
428	edgeMap.erase(delistart);
429	erased = true;
430
431	break; // found and erased
432	}
433	}
434	// increment itStart if we didn't do it when erasing
435	if (!erased)
436	++itStart;
437
438	}
439
440	// use the remaining edges to build triangles with the point
441	// the vertices of the edges are in ccw order (edgePtA-edgePtB-point
442	// to form a ccw polygon)
443	while ( !edgeMap.empty() )
444	{
445	Polygon::EdgeMap::iterator it = edgeMap.begin();
446
447	// build polygon it.first, it.second, point
448	Polygon *p = allocatePolygon();
449
450	p->insertVertex(it->first);
451	p->insertVertex(it->second);
452
453	p->insertVertex( pt );
454	// attach polygon to body
455	insertPolygon( p );
456
457	// erase the vertices from the list
458	// pointers are now held by the polygon
459	edgeMap.erase( it );
460	}
461	}
462	//-----------------------------------------------------------------------
463	void ConvexBody::reset( void )
464	{
465	for (PolygonList::iterator it = mPolygons.begin();
466	it != mPolygons.end(); ++it)
467	{
468	freePolygon(*it);
469	}
470	mPolygons.clear();
471	}
472	//-----------------------------------------------------------------------
473	size_t ConvexBody::getPolygonCount( void ) const
474	{
475	return mPolygons.size();
476	}
477	//-----------------------------------------------------------------------
478	size_t ConvexBody::getVertexCount( size_t poly ) const
479	{
480	OgreAssert(poly < getPolygonCount(), "Search position out of range" );
481
482	return mPolygons[ poly ]->getVertexCount();
483	}
484	//-----------------------------------------------------------------------
485	bool ConvexBody::hasClosedHull( void ) const
486	{
487	// if this map is returned empty, the body is closed
488	Polygon::EdgeMap edgeMap = getSingleEdges();
489
490	return edgeMap.empty();
491	}
492	//-----------------------------------------------------------------------
493	void ConvexBody::mergePolygons( void )
494	{
495	// Merge all polygons that lay in the same plane as one big polygon.
496	// A convex body does not have two seperate regions (seperated by polygons
497	// with different normals) where the same normal occurs, so we can simply
498	// search all similar normals of a polygon. Two different options are
499	// possible when the normals fit:
500	// - the two polygons are neighbors
501	// - the two polygons aren't neighbors (but a third, fourth,.. polygon lays
502	// in between)
503
504	// Signals if the body holds polygons which aren't neighbors but have the same
505	// normal. That means another step has to be processed.
506	bool bDirty = false;
507
508	for ( size_t iPolyA = 0; iPolyA < getPolygonCount(); ++iPolyA )
509	{
510	// ??
511	OgreAssert( iPolyA >= 0, "strange..." );
512
513	for ( size_t iPolyB = iPolyA+1; iPolyB < getPolygonCount(); ++iPolyB )
514	{
515	const Vector3& n1 = getNormal( iPolyA );
516	const Vector3& n2 = getNormal( iPolyB );
517
518	// if the normals point into the same direction
519	if ( n1.directionEquals( n2, Radian( Degree( 0.00001 ) ) ) )
520	{
521	// indicates if a neighbor has been found and joined
522	bool bFound = false;
523
524	// search the two fitting vertices (if there are any) for the common edge
525	const size_t numVerticesA = getVertexCount( iPolyA );
526	for ( size_t iVertexA = 0; iVertexA < numVerticesA; ++iVertexA )
527	{
528	const size_t numVerticesB = getVertexCount( iPolyB );
529	for ( size_t iVertexB = 0; iVertexB < numVerticesB; ++iVertexB )
530	{
531	const Vector3& aCurrent = getVertex( iPolyA, iVertexA );
532	const Vector3& aNext = getVertex( iPolyA, (iVertexA + 1) % getVertexCount( iPolyA ) );
533	const Vector3& bCurrent = getVertex( iPolyB, iVertexB );
534	const Vector3& bNext = getVertex( iPolyB, (iVertexB + 1) % getVertexCount( iPolyB ) );
535
536	// if the edge is the same the current vertex of A has to be equal to the next of B and the other
537	// way round
538	if ( aCurrent.positionEquals(bNext) &&
539	bCurrent.positionEquals(aNext))
540	{
541	// polygons are neighbors, assemble new one
542	Polygon *pNew = allocatePolygon();
543
544	// insert all vertices of A up to the join (including the common vertex, ignoring
545	// whether the first vertex of A may be a shared vertex)
546	for ( size_t i = 0; i <= iVertexA; ++i )
547	{
548	pNew->insertVertex( getVertex( iPolyA, i%numVerticesA ) );
549	}
550
551	// insert all vertices of B _after_ the join to the end
552	for ( size_t i = iVertexB + 2; i < numVerticesB; ++i )
553	{
554	pNew->insertVertex( getVertex( iPolyB, i ) );
555	}
556
557	// insert all vertices of B from the beginning up to the join (including the common vertex
558	// and excluding the first vertex if the first is part of the shared edge)
559	for ( size_t i = 0; i <= iVertexB; ++i )
560	{
561	pNew->insertVertex( getVertex( iPolyB, i%numVerticesB ) );
562	}
563
564	// insert all vertices of A _after_ the join to the end
565	for ( size_t i = iVertexA + 2; i < numVerticesA; ++i )
566	{
567	pNew->insertVertex( getVertex( iPolyA, i ) );
568	}
569
570	// in case there are double vertices (in special cases), remove them
571	for ( size_t i = 0; i < pNew->getVertexCount(); ++i )
572	{
573	const Vector3& a = pNew->getVertex( i );
574	const Vector3& b = pNew->getVertex( (i + 1) % pNew->getVertexCount() );
575
576	// if the two vertices are the same...
577	if (a.positionEquals(b))
578	{
579	// remove a
580	pNew->deleteVertex( i );
581
582	// decrement counter
583	--i;
584	}
585	}
586
587	// delete the two old ones
588	OgreAssert( iPolyA != iPolyB, "PolyA and polyB are the same!" );
589
590	// polyB is always higher than polyA, so delete polyB first
591	deletePolygon( iPolyB );
592	deletePolygon( iPolyA );
593
594	// continue with next (current is deleted, so don't jump to the next after the next)
595	--iPolyA;
596	--iPolyB;
597
598	// insert new polygon
599	insertPolygon( pNew );
600
601	bFound = true;
602	break;
603	}
604	}
605
606	if ( bFound )
607	{
608	break;
609	}
610	}
611
612	if ( bFound == false )
613	{
614	// there are two polygons available with the same normal direction, but they
615	// could not be merged into one single because of no shared edge
616	bDirty = true;
617	break;
618	}
619	}
620	}
621	}
622
623	// recursion to merge the previous non-neighbors
624	if ( bDirty )
625	{
626	mergePolygons();
627	}
628	}
629	//-----------------------------------------------------------------------
630	const Vector3& ConvexBody::getNormal( size_t poly )
631	{
632	OgreAssert( poly >= 0 && poly < getPolygonCount(), "Search position out of range" );
633
634	return mPolygons[ poly ]->getNormal();
635	}
636	//-----------------------------------------------------------------------
637	AxisAlignedBox ConvexBody::getAABB( void ) const
638	{
639	AxisAlignedBox aab;
640
641	for ( size_t i = 0; i < getPolygonCount(); ++i )
642	{
643	for ( size_t j = 0; j < getVertexCount( i ); ++j )
644	{
645	aab.merge( getVertex( i, j ) );
646	}
647	}
648
649	return aab;
650	}
651	//-----------------------------------------------------------------------
652	bool ConvexBody::operator == ( const ConvexBody& rhs ) const
653	{
654	if ( getPolygonCount() != rhs.getPolygonCount() )
655	return false;
656
657	// Compare the polygons. They may not be in correct order.
658	// A correct convex body does not have identical polygons in its body.
659	bool *bChecked = new bool[ getPolygonCount() ];
660	for ( size_t i=0; i<getPolygonCount(); ++i )
661	{
662	bChecked[ i ] = false;
663	}
664
665	for ( size_t i=0; i<getPolygonCount(); ++i )
666	{
667	bool bFound = false;
668
669	for ( size_t j=0; j<getPolygonCount(); ++j )
670	{
671	const Polygon& pA = getPolygon( i );
672	const Polygon& pB = rhs.getPolygon( j );
673
674	if ( pA == pB )
675	{
676	bFound = true;
677	bChecked[ i ] = true;
678	break;
679	}
680	}
681
682	if ( bFound == false )
683	{
684	OGRE_DELETE_ARRAY( bChecked );
685	return false;
686	}
687	}
688
689	for ( size_t i=0; i<getPolygonCount(); ++i )
690	{
691	if ( bChecked[ i ] != true )
692	{
693	OGRE_DELETE_ARRAY( bChecked );
694	return false;
695	}
696	}
697
698	OGRE_DELETE_ARRAY( bChecked );
699	return true;
700	}
701	//-----------------------------------------------------------------------
702	std::ostream& operator<< ( std::ostream& strm, const ConvexBody& body )
703	{
704	strm << "POLYGON INFO (" << body.getPolygonCount() << ")" << std::endl;
705
706	for ( size_t i = 0; i < body.getPolygonCount(); ++i )
707	{
708	strm << "POLYGON " << i << ", ";
709	strm << body.getPolygon( i );
710	}
711
712	return strm;
713	}
714	//-----------------------------------------------------------------------
715	void ConvexBody::insertPolygon(Polygon* pdata, size_t poly )
716	{
717	OgreAssert(poly <= getPolygonCount(), "Insert position out of range" );
718	OgreAssert( pdata != NULL, "Polygon is NULL" );
719
720	PolygonList::iterator it = mPolygons.begin();
721	std::advance(it, poly);
722
723	mPolygons.insert( it, pdata );
724
725	}
726	//-----------------------------------------------------------------------
727	void ConvexBody::insertPolygon(Polygon* pdata)
728	{
729	OgreAssert( pdata != NULL, "Polygon is NULL" );
730
731	mPolygons.push_back( pdata );
732
733	}
734	//-----------------------------------------------------------------------
735	void ConvexBody::insertVertex(size_t poly, const Vector3& vdata, size_t vertex )
736	{
737	OgreAssert(poly < getPolygonCount(), "Search position (polygon) out of range" );
738
739	mPolygons[poly]->insertVertex(vdata, vertex);
740	}
741	//-----------------------------------------------------------------------
742	void ConvexBody::insertVertex(size_t poly, const Vector3& vdata)
743	{
744	OgreAssert(poly < getPolygonCount(), "Search position (polygon) out of range" );
745
746	mPolygons[poly]->insertVertex(vdata);
747	}
748	//-----------------------------------------------------------------------
749	void ConvexBody::deletePolygon(size_t poly)
750	{
751	OgreAssert(poly < getPolygonCount(), "Search position out of range" );
752
753	PolygonList::iterator it = mPolygons.begin();
754	std::advance(it, poly);
755
756	freePolygon(*it);
757	mPolygons.erase(it);
758	}
759	//-----------------------------------------------------------------------
760	Polygon* ConvexBody::unlinkPolygon(size_t poly)
761	{
762	OgreAssert( poly >= 0 && poly < getPolygonCount(), "Search position out of range" );
763
764	PolygonList::iterator it = mPolygons.begin();
765	std::advance(it, poly);
766
767	// safe address
768	Polygon pRet = it;
769
770	// delete entry
771	mPolygons.erase(it);
772
773	// return polygon pointer
774
775	return pRet;
776	}
777	//-----------------------------------------------------------------------
778	void ConvexBody::moveDataFromBody(ConvexBody& body)
779	{
780	body.mPolygons.swap(this->mPolygons);
781	}
782	//-----------------------------------------------------------------------
783	void ConvexBody::deleteVertex(size_t poly, size_t vertex)
784	{
785	OgreAssert(poly < getPolygonCount(), "Search position out of range" );
786
787	mPolygons[poly]->deleteVertex(vertex);
788	}
789	//-----------------------------------------------------------------------
790	const Polygon& ConvexBody::getPolygon(size_t poly) const
791	{
792	OgreAssert(poly < getPolygonCount(), "Search position out of range");
793
794	return *mPolygons[poly];
795	}
796	//-----------------------------------------------------------------------
797	void ConvexBody::setPolygon(Polygon* pdata, size_t poly)
798	{
799	OgreAssert(poly < getPolygonCount(), "Search position out of range" );
800	OgreAssert(pdata != NULL, "Polygon is NULL" );
801
802	if (pdata != mPolygons[poly])
803	{
804	// delete old polygon
805	freePolygon(mPolygons[ poly ]);
806
807	// set new polygon
808	mPolygons[poly] = pdata;
809	}
810	}
811	//-----------------------------------------------------------------------
812	const Vector3& ConvexBody::getVertex(size_t poly, size_t vertex) const
813	{
814	OgreAssert( poly >= 0 && poly < getPolygonCount(), "Search position out of range" );
815
816	return mPolygons[poly]->getVertex(vertex);
817	}
818	//-----------------------------------------------------------------------
819	void ConvexBody::setVertex(size_t poly, const Vector3& vdata, size_t vertex)
820	{
821	OgreAssert(poly < getPolygonCount(), "Search position out of range");
822
823	mPolygons[poly]->setVertex(vdata, vertex);
824	}
825	//-----------------------------------------------------------------------
826	void ConvexBody::storeEdgesOfPolygon(size_t poly, Polygon::EdgeMap *edgeMap ) const
827	{
828	OgreAssert(poly <= getPolygonCount(), "Search position out of range" );
829	OgreAssert( edgeMap != NULL, "TEdgeMap ptr is NULL" );
830
831	mPolygons[poly]->storeEdges(edgeMap);
832	}
833	//-----------------------------------------------------------------------
834	Polygon::EdgeMap ConvexBody::getSingleEdges() const
835	{
836	Polygon::EdgeMap edgeMap;
837
838	// put all edges of all polygons into a list every edge has to be
839	// walked in each direction once
840	for ( size_t i = 0; i < getPolygonCount(); ++i )
841	{
842	const Polygon& p = getPolygon( i );
843
844	for ( size_t j = 0; j < p.getVertexCount(); ++j )
845	{
846	const Vector3& a = p.getVertex( j );
847	const Vector3& b = p.getVertex( ( j + 1 ) % p.getVertexCount() );
848
849	edgeMap.insert( Polygon::Edge( a, b ) );
850	}
851	}
852
853	// search corresponding parts
854	Polygon::EdgeMap::iterator it;
855	Polygon::EdgeMap::iterator itStart;
856	Polygon::EdgeMap::const_iterator itEnd;
857	while( !edgeMap.empty() )
858	{
859	it = edgeMap.begin(); ++it; // start one element after itStart
860	itStart = edgeMap.begin(); // the element to be compared with the others
861	itEnd = edgeMap.end(); // beyond the last element
862
863	bool bFound = false;
864
865	for ( ; it != itEnd; ++it )
866	{
867	if (itStart->first.positionEquals(it->second) &&
868	itStart->second.positionEquals(it->first))
869	{
870	// erase itStart and it
871	edgeMap.erase( it );
872	edgeMap.erase( itStart );
873
874	bFound = true;
875
876	break; // found
877	}
878	}
879
880	if ( bFound == false )
881	{
882	break; // not all edges could be matched
883	// body is not closed
884	}
885	}
886
887	return edgeMap;
888	}
889	//-----------------------------------------------------------------------
890	void ConvexBody::allocateSpace( size_t numPolygons, size_t numVertices )
891	{
892	reset();
893
894	// allocate numPolygons polygons with each numVertices vertices
895	for ( size_t iPoly = 0; iPoly < numPolygons; ++iPoly )
896	{
897	Polygon *poly = allocatePolygon();
898
899	for ( size_t iVertex = 0; iVertex < numVertices; ++iVertex )
900	{
901	poly->insertVertex( Vector3::ZERO );
902	}
903
904	mPolygons.push_back( poly );
905	}
906	}
907	//-----------------------------------------------------------------------
908	void ConvexBody::clip( const Plane& pl, bool keepNegative )
909	{
910	if ( getPolygonCount() == 0 )
911	return;
912
913	// current will be used as the reference body
914	ConvexBody current;
915	current.moveDataFromBody(*this);
916
917	OgreAssert( this->getPolygonCount() == 0, "Body not empty!" );
918	OgreAssert( current.getPolygonCount() != 0, "Body empty!" );
919
920	// holds all intersection edges for the different polygons
921	Polygon::EdgeMap intersectionEdges;
922
923	// clip all polygons by the intersection plane
924	// add only valid or intersected polygons to *this
925	for ( size_t iPoly = 0; iPoly < current.getPolygonCount(); ++iPoly )
926	{
927
928	// fetch vertex count and ignore polygons with less than three vertices
929	// the polygon is not valid and won't be added
930	const size_t vertexCount = current.getVertexCount( iPoly );
931	if ( vertexCount < 3 )
932	continue;
933
934	// current polygon
935	const Polygon& p = current.getPolygon( iPoly );
936
937	// the polygon to assemble
938	Polygon *pNew = allocatePolygon();
939
940	// the intersection polygon (indeed it's an edge or it's empty)
941	Polygon *pIntersect = allocatePolygon();
942
943	// check if polygons lie inside or outside (or on the plane)
944	// for each vertex check where it is situated in regard to the plane
945	// three possibilities appear:
946	Plane::Side clipSide = keepNegative ? Plane::POSITIVE_SIDE : Plane::NEGATIVE_SIDE;
947	// - side is clipSide: vertex will be clipped
948	// - side is !clipSide: vertex will be untouched
949	// - side is NOSIDE: vertex will be untouched
950	Plane::Side *side = new Plane::Side[ vertexCount ];
951	for ( size_t iVertex = 0; iVertex < vertexCount; ++iVertex )
952	{
953	side[ iVertex ] = pl.getSide( p.getVertex( iVertex ) );
954	}
955
956	// now we check the side combinations for the current and the next vertex
957	// four different combinations exist:
958	// - both points inside (or on the plane): keep the second (add it to the body)
959	// - both points outside: discard both (don't add them to the body)
960	// - first vertex is inside, second is outside: add the intersection point
961	// - first vertex is outside, second is inside: add the intersection point, then the second
962	for ( size_t iVertex = 0; iVertex < vertexCount; ++iVertex )
963	{
964	// determine the next vertex
965	size_t iNextVertex = ( iVertex + 1 ) % vertexCount;
966
967	const Vector3& vCurrent = p.getVertex( iVertex );
968	const Vector3& vNext = p.getVertex( iNextVertex );
969
970	// case 1: both points inside (store next)
971	if ( side[ iVertex ] != clipSide && // NEGATIVE or NONE
972	side[ iNextVertex ] != clipSide ) // NEGATIVE or NONE
973	{
974	// keep the second
975	pNew->insertVertex( vNext );
976	}
977
978	// case 3: inside -> outside (store intersection)
979	else if ( side[ iVertex ] != clipSide &&
980	side[ iNextVertex ] == clipSide )
981	{
982	// Do an intersection with the plane. We use a ray with a start point and a direction.
983	// The ray is forced to hit the plane with any option available (eigher current or next
984	// is the starting point)
985
986	// intersect from the outside vertex towards the inside one
987	Vector3 vDirection = vCurrent - vNext;
988	vDirection.normalise();
989	Ray ray( vNext, vDirection );
990	std::pair< bool, Real > intersect = ray.intersects( pl );
991
992	// store intersection
993	if ( intersect.first )
994	{
995	// convert distance to vector
996	Vector3 vIntersect = ray.getPoint( intersect.second );
997
998	// store intersection
999	pNew->insertVertex( vIntersect );
1000	pIntersect->insertVertex( vIntersect );
1001	}
1002	}
1003
1004	// case 4: outside -> inside (store intersection, store next)
1005	else if ( side[ iVertex ] == clipSide &&
1006	side[ iNextVertex ] != clipSide )
1007	{
1008	// Do an intersection with the plane. We use a ray with a start point and a direction.
1009	// The ray is forced to hit the plane with any option available (eigher current or next
1010	// is the starting point)
1011
1012	// intersect from the outside vertex towards the inside one
1013	Vector3 vDirection = vNext - vCurrent;
1014	vDirection.normalise();
1015	Ray ray( vCurrent, vDirection );
1016	std::pair< bool, Real > intersect = ray.intersects( pl );
1017
1018	// store intersection
1019	if ( intersect.first )
1020	{
1021	// convert distance to vector
1022	Vector3 vIntersect = ray.getPoint( intersect.second );
1023
1024	// store intersection
1025	pNew->insertVertex( vIntersect );
1026	pIntersect->insertVertex( vIntersect );
1027	}
1028
1029	pNew->insertVertex( vNext );
1030
1031	}
1032	// else:
1033	// case 2: both outside (do nothing)
1034
1035	}
1036
1037	// insert the polygon only, if at least three vertices are present
1038	if ( pNew->getVertexCount() >= 3 )
1039	{
1040	// in case there are double vertices, remove them
1041	pNew->removeDuplicates();
1042
1043	// in case there are still at least three vertices, insert the polygon
1044	if ( pNew->getVertexCount() >= 3 )
1045	{
1046	this->insertPolygon( pNew );
1047	}
1048	else
1049	{
1050	// delete pNew because it's empty or invalid
1051	freePolygon(pNew);
1052	pNew = 0;
1053	}
1054	}
1055	else
1056	{
1057	// delete pNew because it's empty or invalid
1058	freePolygon(pNew);
1059	pNew = 0;
1060	}
1061
1062	// insert intersection polygon only, if there are two vertices present
1063	if ( pIntersect->getVertexCount() == 2 )
1064	{
1065	intersectionEdges.insert( Polygon::Edge( pIntersect->getVertex( 0 ),
1066	pIntersect->getVertex( 1 ) ) );
1067	}
1068
1069	// delete intersection polygon
1070	// vertices were copied (if there were any)
1071	freePolygon(pIntersect);
1072	pIntersect = 0;
1073
1074	// delete side info
1075	OGRE_DELETE_ARRAY( side );
1076	}
1077
1078	// if the polygon was partially clipped, close it
1079	// at least three edges are needed for a polygon
1080	if ( intersectionEdges.size() >= 3 )
1081	{
1082	Polygon *pClosing = allocatePolygon();
1083
1084	// Analyze the intersection list and insert the intersection points in ccw order
1085	// Each point is twice in the list because of the fact that we have a convex body
1086	// with convex polygons. All we have to do is order the edges (an even-odd pair)
1087	// in a ccw order. The plane normal shows us the direction.
1088	Polygon::EdgeMap::iterator it = intersectionEdges.begin();
1089
1090	// check the cross product of the first two edges
1091	const Vector3& vFirst = it->first;
1092	const Vector3& vSecond = it->second;
1093
1094	// remove inserted edge
1095	intersectionEdges.erase( it );
1096
1097	Vector3 vNext;
1098
1099	// find mating edge
1100	if (findAndEraseEdgePair(vSecond, intersectionEdges, vNext))
1101	{
1102	// detect the orientation
1103	// the polygon must have the same normal direction as the plane and then n
1104	Vector3 vCross = ( vFirst - vSecond ).crossProduct( vNext - vSecond );
1105	bool frontside = ( pl.normal ).directionEquals( vCross, Degree( 1 ) );
1106
1107	// first inserted vertex
1108	Vector3 firstVertex;
1109	// currently inserted vertex
1110	Vector3 currentVertex;
1111	// direction equals -> front side (walk ccw)
1112	if ( frontside )
1113	{
1114	// start with next as first vertex, then second, then first and continue with first to walk ccw
1115	pClosing->insertVertex( vNext );
1116	pClosing->insertVertex( vSecond );
1117	pClosing->insertVertex( vFirst );
1118	firstVertex = vNext;
1119	currentVertex = vFirst;
1120
1121	#ifdef _DEBUG_INTERSECTION_LIST
1122	std::cout << "Plane: n=" << pl.normal << ", d=" << pl.d << std::endl;
1123	std::cout << "First inserted vertex: " << *next << std::endl;
1124	std::cout << "Second inserted vertex: " << *vSecond << std::endl;
1125	std::cout << "Third inserted vertex: " << *vFirst << std::endl;
1126	#endif
1127	}
1128	// direction does not equal -> back side (walk cw)
1129	else
1130	{
1131	// start with first as first vertex, then second, then next and continue with next to walk ccw
1132	pClosing->insertVertex( vFirst );
1133	pClosing->insertVertex( vSecond );
1134	pClosing->insertVertex( vNext );
1135	firstVertex = vFirst;
1136	currentVertex = vNext;
1137
1138	#ifdef _DEBUG_INTERSECTION_LIST
1139	std::cout << "Plane: n=" << pl.normal << ", d=" << pl.d << std::endl;
1140	std::cout << "First inserted vertex: " << *vFirst << std::endl;
1141	std::cout << "Second inserted vertex: " << *vSecond << std::endl;
1142	std::cout << "Third inserted vertex: " << *next << std::endl;
1143	#endif
1144	}
1145
1146	// search mating edges that have a point in common
1147	// continue this operation as long as edges are present
1148	while ( !intersectionEdges.empty() )
1149	{
1150
1151	if (findAndEraseEdgePair(currentVertex, intersectionEdges, vNext))
1152	{
1153	// insert only if it's not the last (which equals the first) vertex
1154	if ( !intersectionEdges.empty() )
1155	{
1156	currentVertex = vNext;
1157	pClosing->insertVertex( vNext );
1158	}
1159	}
1160	else
1161	{
1162	// degenerated...
1163	break;
1164	}
1165
1166	} // while intersectionEdges not empty
1167
1168	// insert polygon (may be degenerated!)
1169	this->insertPolygon( pClosing );
1170
1171	}
1172	// mating intersection edge NOT found!
1173	else
1174	{
1175	freePolygon(pClosing);
1176	}
1177
1178	} // if intersectionEdges contains more than three elements
1179	}
1180	//-----------------------------------------------------------------------
1181	bool ConvexBody::findAndEraseEdgePair(const Vector3& vec,
1182	Polygon::EdgeMap& intersectionEdges, Vector3& vNext ) const
1183	{
1184	Polygon::EdgeMap::iterator it = intersectionEdges.begin();
1185
1186	for (Polygon::EdgeMap::iterator it = intersectionEdges.begin();
1187	it != intersectionEdges.end(); ++it)
1188	{
1189	if (it->first.positionEquals(vec))
1190	{
1191	vNext = it->second;
1192
1193	// erase found edge
1194	intersectionEdges.erase( it );
1195
1196	return true; // found!
1197	}
1198	else if (it->second.positionEquals(vec))
1199	{
1200	vNext = it->first;
1201
1202	// erase found edge
1203	intersectionEdges.erase( it );
1204
1205	return true; // found!
1206	}
1207	}
1208
1209	return false; // not found!
1210	}
1211	//-----------------------------------------------------------------------
1212	void ConvexBody::logInfo( void ) const
1213	{
1214	std::stringstream ssOut( std::stringstream::out );
1215	ssOut << *this;
1216
1217	Ogre::LogManager::getSingleton().logMessage( Ogre::LML_NORMAL, ssOut.str() );
1218	}
1219	}
1220

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

Download in other formats: