?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Patch 2793067: fix trunk with OGRE_THREAD_SUPPORT=1 on non-Windows platforms (don...
[ogre3d.git] / OgreMain / src / OgreConvexBody.cpp
blob75cd225f506e993877b85fdb1db55714ebe3d127
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] = OGRE_NEW_T(Polygon, MEMCATEGORY_SCENE_CONTROL)();
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 OGRE_DELETE_T(*i, Polygon, MEMCATEGORY_SCENE_CONTROL);
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 OGRE_NEW_T(Polygon, MEMCATEGORY_SCENE_CONTROL)();
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 = OGRE_ALLOC_T(bool, getPolygonCount(), MEMCATEGORY_SCENE_CONTROL);
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_FREE(bChecked, MEMCATEGORY_SCENE_CONTROL);
685 bChecked = 0;
686 return false;
687 }
688 }
689
690 for ( size_t i=0; i<getPolygonCount(); ++i )
691 {
692 if ( bChecked[ i ] != true )
693 {
694 OGRE_FREE(bChecked, MEMCATEGORY_SCENE_CONTROL);
695 bChecked = 0;
696 return false;
697 }
698 }
699
700 OGRE_FREE(bChecked, MEMCATEGORY_SCENE_CONTROL);
701 bChecked = 0;
702 return true;
703 }
704 //-----------------------------------------------------------------------
705 std::ostream& operator<< ( std::ostream& strm, const ConvexBody& body )
706 {
707 strm << "POLYGON INFO (" << body.getPolygonCount() << ")" << std::endl;
708
709 for ( size_t i = 0; i < body.getPolygonCount(); ++i )
710 {
711 strm << "POLYGON " << i << ", ";
712 strm << body.getPolygon( i );
713 }
714
715 return strm;
716 }
717 //-----------------------------------------------------------------------
718 void ConvexBody::insertPolygon(Polygon* pdata, size_t poly )
719 {
720 OgreAssert(poly <= getPolygonCount(), "Insert position out of range" );
721 OgreAssert( pdata != NULL, "Polygon is NULL" );
722
723 PolygonList::iterator it = mPolygons.begin();
724 std::advance(it, poly);
725
726 mPolygons.insert( it, pdata );
727
728 }
729 //-----------------------------------------------------------------------
730 void ConvexBody::insertPolygon(Polygon* pdata)
731 {
732 OgreAssert( pdata != NULL, "Polygon is NULL" );
733
734 mPolygons.push_back( pdata );
735
736 }
737 //-----------------------------------------------------------------------
738 void ConvexBody::insertVertex(size_t poly, const Vector3& vdata, size_t vertex )
739 {
740 OgreAssert(poly < getPolygonCount(), "Search position (polygon) out of range" );
741
742 mPolygons[poly]->insertVertex(vdata, vertex);
743 }
744 //-----------------------------------------------------------------------
745 void ConvexBody::insertVertex(size_t poly, const Vector3& vdata)
746 {
747 OgreAssert(poly < getPolygonCount(), "Search position (polygon) out of range" );
748
749 mPolygons[poly]->insertVertex(vdata);
750 }
751 //-----------------------------------------------------------------------
752 void ConvexBody::deletePolygon(size_t poly)
753 {
754 OgreAssert(poly < getPolygonCount(), "Search position out of range" );
755
756 PolygonList::iterator it = mPolygons.begin();
757 std::advance(it, poly);
758
759 freePolygon(*it);
760 mPolygons.erase(it);
761 }
762 //-----------------------------------------------------------------------
763 Polygon* ConvexBody::unlinkPolygon(size_t poly)
764 {
765 OgreAssert( poly >= 0 && poly < getPolygonCount(), "Search position out of range" );
766
767 PolygonList::iterator it = mPolygons.begin();
768 std::advance(it, poly);
769
770 // safe address
771 Polygon *pRet = *it;
772
773 // delete entry
774 mPolygons.erase(it);
775
776 // return polygon pointer
777
778 return pRet;
779 }
780 //-----------------------------------------------------------------------
781 void ConvexBody::moveDataFromBody(ConvexBody& body)
782 {
783 body.mPolygons.swap(this->mPolygons);
784 }
785 //-----------------------------------------------------------------------
786 void ConvexBody::deleteVertex(size_t poly, size_t vertex)
787 {
788 OgreAssert(poly < getPolygonCount(), "Search position out of range" );
789
790 mPolygons[poly]->deleteVertex(vertex);
791 }
792 //-----------------------------------------------------------------------
793 const Polygon& ConvexBody::getPolygon(size_t poly) const
794 {
795 OgreAssert(poly < getPolygonCount(), "Search position out of range");
796
797 return *mPolygons[poly];
798 }
799 //-----------------------------------------------------------------------
800 void ConvexBody::setPolygon(Polygon* pdata, size_t poly)
801 {
802 OgreAssert(poly < getPolygonCount(), "Search position out of range" );
803 OgreAssert(pdata != NULL, "Polygon is NULL" );
804
805 if (pdata != mPolygons[poly])
806 {
807 // delete old polygon
808 freePolygon(mPolygons[ poly ]);
809
810 // set new polygon
811 mPolygons[poly] = pdata;
812 }
813 }
814 //-----------------------------------------------------------------------
815 const Vector3& ConvexBody::getVertex(size_t poly, size_t vertex) const
816 {
817 OgreAssert( poly >= 0 && poly < getPolygonCount(), "Search position out of range" );
818
819 return mPolygons[poly]->getVertex(vertex);
820 }
821 //-----------------------------------------------------------------------
822 void ConvexBody::setVertex(size_t poly, const Vector3& vdata, size_t vertex)
823 {
824 OgreAssert(poly < getPolygonCount(), "Search position out of range");
825
826 mPolygons[poly]->setVertex(vdata, vertex);
827 }
828 //-----------------------------------------------------------------------
829 void ConvexBody::storeEdgesOfPolygon(size_t poly, Polygon::EdgeMap *edgeMap ) const
830 {
831 OgreAssert(poly <= getPolygonCount(), "Search position out of range" );
832 OgreAssert( edgeMap != NULL, "TEdgeMap ptr is NULL" );
833
834 mPolygons[poly]->storeEdges(edgeMap);
835 }
836 //-----------------------------------------------------------------------
837 Polygon::EdgeMap ConvexBody::getSingleEdges() const
838 {
839 Polygon::EdgeMap edgeMap;
840
841 // put all edges of all polygons into a list every edge has to be
842 // walked in each direction once
843 for ( size_t i = 0; i < getPolygonCount(); ++i )
844 {
845 const Polygon& p = getPolygon( i );
846
847 for ( size_t j = 0; j < p.getVertexCount(); ++j )
848 {
849 const Vector3& a = p.getVertex( j );
850 const Vector3& b = p.getVertex( ( j + 1 ) % p.getVertexCount() );
851
852 edgeMap.insert( Polygon::Edge( a, b ) );
853 }
854 }
855
856 // search corresponding parts
857 Polygon::EdgeMap::iterator it;
858 Polygon::EdgeMap::iterator itStart;
859 Polygon::EdgeMap::const_iterator itEnd;
860 while( !edgeMap.empty() )
861 {
862 it = edgeMap.begin(); ++it; // start one element after itStart
863 itStart = edgeMap.begin(); // the element to be compared with the others
864 itEnd = edgeMap.end(); // beyond the last element
865
866 bool bFound = false;
867
868 for ( ; it != itEnd; ++it )
869 {
870 if (itStart->first.positionEquals(it->second) &&
871 itStart->second.positionEquals(it->first))
872 {
873 // erase itStart and it
874 edgeMap.erase( it );
875 edgeMap.erase( itStart );
876
877 bFound = true;
878
879 break; // found
880 }
881 }
882
883 if ( bFound == false )
884 {
885 break; // not all edges could be matched
886 // body is not closed
887 }
888 }
889
890 return edgeMap;
891 }
892 //-----------------------------------------------------------------------
893 void ConvexBody::allocateSpace( size_t numPolygons, size_t numVertices )
894 {
895 reset();
896
897 // allocate numPolygons polygons with each numVertices vertices
898 for ( size_t iPoly = 0; iPoly < numPolygons; ++iPoly )
899 {
900 Polygon *poly = allocatePolygon();
901
902 for ( size_t iVertex = 0; iVertex < numVertices; ++iVertex )
903 {
904 poly->insertVertex( Vector3::ZERO );
905 }
906
907 mPolygons.push_back( poly );
908 }
909 }
910 //-----------------------------------------------------------------------
911 void ConvexBody::clip( const Plane& pl, bool keepNegative )
912 {
913 if ( getPolygonCount() == 0 )
914 return;
915
916 // current will be used as the reference body
917 ConvexBody current;
918 current.moveDataFromBody(*this);
919
920 OgreAssert( this->getPolygonCount() == 0, "Body not empty!" );
921 OgreAssert( current.getPolygonCount() != 0, "Body empty!" );
922
923 // holds all intersection edges for the different polygons
924 Polygon::EdgeMap intersectionEdges;
925
926 // clip all polygons by the intersection plane
927 // add only valid or intersected polygons to *this
928 for ( size_t iPoly = 0; iPoly < current.getPolygonCount(); ++iPoly )
929 {
930
931 // fetch vertex count and ignore polygons with less than three vertices
932 // the polygon is not valid and won't be added
933 const size_t vertexCount = current.getVertexCount( iPoly );
934 if ( vertexCount < 3 )
935 continue;
936
937 // current polygon
938 const Polygon& p = current.getPolygon( iPoly );
939
940 // the polygon to assemble
941 Polygon *pNew = allocatePolygon();
942
943 // the intersection polygon (indeed it's an edge or it's empty)
944 Polygon *pIntersect = allocatePolygon();
945
946 // check if polygons lie inside or outside (or on the plane)
947 // for each vertex check where it is situated in regard to the plane
948 // three possibilities appear:
949 Plane::Side clipSide = keepNegative ? Plane::POSITIVE_SIDE : Plane::NEGATIVE_SIDE;
950 // - side is clipSide: vertex will be clipped
951 // - side is !clipSide: vertex will be untouched
952 // - side is NOSIDE: vertex will be untouched
953 Plane::Side *side = OGRE_ALLOC_T(Plane::Side, vertexCount, MEMCATEGORY_SCENE_CONTROL);
954 for ( size_t iVertex = 0; iVertex < vertexCount; ++iVertex )
955 {
956 side[ iVertex ] = pl.getSide( p.getVertex( iVertex ) );
957 }
958
959 // now we check the side combinations for the current and the next vertex
960 // four different combinations exist:
961 // - both points inside (or on the plane): keep the second (add it to the body)
962 // - both points outside: discard both (don't add them to the body)
963 // - first vertex is inside, second is outside: add the intersection point
964 // - first vertex is outside, second is inside: add the intersection point, then the second
965 for ( size_t iVertex = 0; iVertex < vertexCount; ++iVertex )
966 {
967 // determine the next vertex
968 size_t iNextVertex = ( iVertex + 1 ) % vertexCount;
969
970 const Vector3& vCurrent = p.getVertex( iVertex );
971 const Vector3& vNext = p.getVertex( iNextVertex );
972
973 // case 1: both points inside (store next)
974 if ( side[ iVertex ] != clipSide && // NEGATIVE or NONE
975 side[ iNextVertex ] != clipSide ) // NEGATIVE or NONE
976 {
977 // keep the second
978 pNew->insertVertex( vNext );
979 }
980
981 // case 3: inside -> outside (store intersection)
982 else if ( side[ iVertex ] != clipSide &&
983 side[ iNextVertex ] == clipSide )
984 {
985 // Do an intersection with the plane. We use a ray with a start point and a direction.
986 // The ray is forced to hit the plane with any option available (eigher current or next
987 // is the starting point)
988
989 // intersect from the outside vertex towards the inside one
990 Vector3 vDirection = vCurrent - vNext;
991 vDirection.normalise();
992 Ray ray( vNext, vDirection );
993 std::pair< bool, Real > intersect = ray.intersects( pl );
994
995 // store intersection
996 if ( intersect.first )
997 {
998 // convert distance to vector
999 Vector3 vIntersect = ray.getPoint( intersect.second );
1000
1001 // store intersection
1002 pNew->insertVertex( vIntersect );
1003 pIntersect->insertVertex( vIntersect );
1004 }
1005 }
1006
1007 // case 4: outside -> inside (store intersection, store next)
1008 else if ( side[ iVertex ] == clipSide &&
1009 side[ iNextVertex ] != clipSide )
1010 {
1011 // Do an intersection with the plane. We use a ray with a start point and a direction.
1012 // The ray is forced to hit the plane with any option available (eigher current or next
1013 // is the starting point)
1014
1015 // intersect from the outside vertex towards the inside one
1016 Vector3 vDirection = vNext - vCurrent;
1017 vDirection.normalise();
1018 Ray ray( vCurrent, vDirection );
1019 std::pair< bool, Real > intersect = ray.intersects( pl );
1020
1021 // store intersection
1022 if ( intersect.first )
1023 {
1024 // convert distance to vector
1025 Vector3 vIntersect = ray.getPoint( intersect.second );
1026
1027 // store intersection
1028 pNew->insertVertex( vIntersect );
1029 pIntersect->insertVertex( vIntersect );
1030 }
1031
1032 pNew->insertVertex( vNext );
1033
1034 }
1035 // else:
1036 // case 2: both outside (do nothing)
1037
1038 }
1039
1040 // insert the polygon only, if at least three vertices are present
1041 if ( pNew->getVertexCount() >= 3 )
1042 {
1043 // in case there are double vertices, remove them
1044 pNew->removeDuplicates();
1045
1046 // in case there are still at least three vertices, insert the polygon
1047 if ( pNew->getVertexCount() >= 3 )
1048 {
1049 this->insertPolygon( pNew );
1050 }
1051 else
1052 {
1053 // delete pNew because it's empty or invalid
1054 freePolygon(pNew);
1055 pNew = 0;
1056 }
1057 }
1058 else
1059 {
1060 // delete pNew because it's empty or invalid
1061 freePolygon(pNew);
1062 pNew = 0;
1063 }
1064
1065 // insert intersection polygon only, if there are two vertices present
1066 if ( pIntersect->getVertexCount() == 2 )
1067 {
1068 intersectionEdges.insert( Polygon::Edge( pIntersect->getVertex( 0 ),
1069 pIntersect->getVertex( 1 ) ) );
1070 }
1071
1072 // delete intersection polygon
1073 // vertices were copied (if there were any)
1074 freePolygon(pIntersect);
1075 pIntersect = 0;
1076
1077 // delete side info
1078 OGRE_FREE(side, MEMCATEGORY_SCENE_CONTROL);
1079 side = 0;
1080 }
1081
1082 // if the polygon was partially clipped, close it
1083 // at least three edges are needed for a polygon
1084 if ( intersectionEdges.size() >= 3 )
1085 {
1086 Polygon *pClosing = allocatePolygon();
1087
1088 // Analyze the intersection list and insert the intersection points in ccw order
1089 // Each point is twice in the list because of the fact that we have a convex body
1090 // with convex polygons. All we have to do is order the edges (an even-odd pair)
1091 // in a ccw order. The plane normal shows us the direction.
1092 Polygon::EdgeMap::iterator it = intersectionEdges.begin();
1093
1094 // check the cross product of the first two edges
1095 Vector3 vFirst = it->first;
1096 Vector3 vSecond = it->second;
1097
1098 // remove inserted edge
1099 intersectionEdges.erase( it );
1100
1101 Vector3 vNext;
1102
1103 // find mating edge
1104 if (findAndEraseEdgePair(vSecond, intersectionEdges, vNext))
1105 {
1106 // detect the orientation
1107 // the polygon must have the same normal direction as the plane and then n
1108 Vector3 vCross = ( vFirst - vSecond ).crossProduct( vNext - vSecond );
1109 bool frontside = ( pl.normal ).directionEquals( vCross, Degree( 1 ) );
1110
1111 // first inserted vertex
1112 Vector3 firstVertex;
1113 // currently inserted vertex
1114 Vector3 currentVertex;
1115 // direction equals -> front side (walk ccw)
1116 if ( frontside )
1117 {
1118 // start with next as first vertex, then second, then first and continue with first to walk ccw
1119 pClosing->insertVertex( vNext );
1120 pClosing->insertVertex( vSecond );
1121 pClosing->insertVertex( vFirst );
1122 firstVertex = vNext;
1123 currentVertex = vFirst;
1124
1125 #ifdef _DEBUG_INTERSECTION_LIST
1126 std::cout << "Plane: n=" << pl.normal << ", d=" << pl.d << std::endl;
1127 std::cout << "First inserted vertex: " << *next << std::endl;
1128 std::cout << "Second inserted vertex: " << *vSecond << std::endl;
1129 std::cout << "Third inserted vertex: " << *vFirst << std::endl;
1130 #endif
1131 }
1132 // direction does not equal -> back side (walk cw)
1133 else
1134 {
1135 // start with first as first vertex, then second, then next and continue with next to walk ccw
1136 pClosing->insertVertex( vFirst );
1137 pClosing->insertVertex( vSecond );
1138 pClosing->insertVertex( vNext );
1139 firstVertex = vFirst;
1140 currentVertex = vNext;
1141
1142 #ifdef _DEBUG_INTERSECTION_LIST
1143 std::cout << "Plane: n=" << pl.normal << ", d=" << pl.d << std::endl;
1144 std::cout << "First inserted vertex: " << *vFirst << std::endl;
1145 std::cout << "Second inserted vertex: " << *vSecond << std::endl;
1146 std::cout << "Third inserted vertex: " << *next << std::endl;
1147 #endif
1148 }
1149
1150 // search mating edges that have a point in common
1151 // continue this operation as long as edges are present
1152 while ( !intersectionEdges.empty() )
1153 {
1154
1155 if (findAndEraseEdgePair(currentVertex, intersectionEdges, vNext))
1156 {
1157 // insert only if it's not the last (which equals the first) vertex
1158 if ( !intersectionEdges.empty() )
1159 {
1160 currentVertex = vNext;
1161 pClosing->insertVertex( vNext );
1162 }
1163 }
1164 else
1165 {
1166 // degenerated...
1167 break;
1168 }
1169
1170 } // while intersectionEdges not empty
1171
1172 // insert polygon (may be degenerated!)
1173 this->insertPolygon( pClosing );
1174
1175 }
1176 // mating intersection edge NOT found!
1177 else
1178 {
1179 freePolygon(pClosing);
1180 }
1181
1182 } // if intersectionEdges contains more than three elements
1183 }
1184 //-----------------------------------------------------------------------
1185 bool ConvexBody::findAndEraseEdgePair(const Vector3& vec,
1186 Polygon::EdgeMap& intersectionEdges, Vector3& vNext ) const
1187 {
1188 Polygon::EdgeMap::iterator it = intersectionEdges.begin();
1189
1190 for (Polygon::EdgeMap::iterator it = intersectionEdges.begin();
1191 it != intersectionEdges.end(); ++it)
1192 {
1193 if (it->first.positionEquals(vec))
1194 {
1195 vNext = it->second;
1196
1197 // erase found edge
1198 intersectionEdges.erase( it );
1199
1200 return true; // found!
1201 }
1202 else if (it->second.positionEquals(vec))
1203 {
1204 vNext = it->first;
1205
1206 // erase found edge
1207 intersectionEdges.erase( it );
1208
1209 return true; // found!
1210 }
1211 }
1212
1213 return false; // not found!
1214 }
1215 //-----------------------------------------------------------------------
1216 void ConvexBody::logInfo( void ) const
1217 {
1218 StringUtil::StrStreamType ssOut( std::stringstream::out );
1219 ssOut << *this;
1220
1221 Ogre::LogManager::getSingleton().logMessage( Ogre::LML_NORMAL, ssOut.str() );
1222 }
1223 }
1224
Ogre3d mirror of svn