mPolyhedron.cpp

Detailed Description

  1
  2//-----------------------------------------------------------------------------
  3// Copyright (c) 2012 GarageGames, LLC
  4//
  5// Permission is hereby granted, free of charge, to any person obtaining a copy
  6// of this software and associated documentation files (the "Software"), to
  7// deal in the Software without restriction, including without limitation the
  8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  9// sell copies of the Software, and to permit persons to whom the Software is
 10// furnished to do so, subject to the following conditions:
 11//
 12// The above copyright notice and this permission notice shall be included in
 13// all copies or substantial portions of the Software.
 14//
 15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 21// IN THE SOFTWARE.
 22//-----------------------------------------------------------------------------
 23
 24#include "platform/platform.h"
 25#include "math/mPolyhedron.h"
 26
 27#include "platform/typetraits.h"
 28
 29
 30//-----------------------------------------------------------------------------
 31
 32void PolyhedronVectorData::buildFromPlanes( const PlaneSetF& planes )
 33{
 34   const U32 numSourcePlanes = planes.getNumPlanes();
 35
 36   // Go through the planes and create edges by
 37   // intersecting the various planes.
 38
 39   for( U32 i = 0; i < numSourcePlanes; ++ i )
 40   {
 41      const PlaneF& currentPlane = planes.getPlanes()[ i ];
 42
 43      bool haveEdges = false;
 44      for( U32 n = 0; n < numSourcePlanes; ++ n )
 45      {
 46         if( n == i )
 47            continue;
 48
 49         const PlaneF& intersectPlane = planes.getPlanes()[ n ];
 50
 51         Point3F start;
 52         Point3F dir;
 53
 54         // Intersect the two planes.
 55
 56         if( !currentPlane.intersect( intersectPlane, start, dir ) )
 57            continue;
 58
 59         // Absolutely make sure our direction vector is normalized.
 60
 61         dir.normalize();
 62
 63         // Find the two vertices on the line that are still
 64         // inside the polyhedron by clipping against the other
 65         // planes in the set.
 66
 67         F32 minDist = TypeTraits< F32 >::MAX;
 68         F32 maxDist = TypeTraits< F32 >::MIN;
 69
 70         Point3F v1;
 71         Point3F v2;
 72
 73         Point3F end = start + dir;
 74
 75         for( U32 j = 0; j < numSourcePlanes; j ++ )
 76         {
 77            // Skip if current or intersect plane.
 78            if( j == n || j == i )
 79               continue;
 80
 81            const PlaneF& clipPlane = planes.getPlanes()[ j ];
 82
 83            // Compute the distance at which the plane intersects
 84            // the line.  Skip if parallel.
 85
 86            F32 dist = clipPlane.intersect( start, end );
 87            if( mIsEqual( dist, PARALLEL_PLANE ) )
 88               continue;
 89
 90            // See if the resulting vertex is even inside the planes.
 91            // Skip if not.
 92
 93            Point3F vertex = start + dir * dist;
 94            bool isContained = true;
 95            for( U32 nplane = 0; nplane < numSourcePlanes; ++ nplane )
 96            {
 97               // Skip all planes that we used to construct this vertex.
 98               if( nplane == j || nplane == n || nplane == i )
 99                  continue;
100
101               if( planes.getPlanes()[ nplane ].whichSide( vertex ) == PlaneF::Back )
102               {
103                  isContained = false;
104                  break;
105               }
106            }
107            if( !isContained )
108               continue;
109
110            // Keep track of min and max distance.
111
112            if( mIsEqual( dist, minDist ) || mIsEqual( dist, maxDist ) )
113               continue;
114            else if( dist < minDist )
115            {
116               if( minDist != TypeTraits< F32 >::MAX && maxDist == TypeTraits< F32 >::MIN )
117               {
118                  maxDist = minDist;
119                  v2 = v1;
120               }
121
122               minDist = dist;
123               v1 = vertex;
124            }
125            else if( dist > maxDist )
126            {
127               maxDist = dist;
128               v2 = vertex;
129            }
130         }
131
132         // Skip plane pair if there's no properly formed edge.
133
134         if( minDist == TypeTraits< F32 >::MAX || maxDist == TypeTraits< F32 >::MIN || mIsEqual( minDist, maxDist ) )
135            continue;
136
137         // See if vertex 1 already exists.
138
139         S32 v1index = -1;
140         bool v1Existed = false;
141         for( U32 nvert = 0; nvert < mPointList.size(); ++ nvert )
142            if(mPointList[ nvert ].equal( v1, 0.001f ) )
143            {
144               v1index = nvert;
145               v1Existed = true;
146               break;
147            }
148
149         // See if vertex 2 already exists.
150
151         S32 v2index = -1;
152         bool v2Existed = false;
153         for( U32 nvert = 0; nvert < mPointList.size(); ++ nvert )
154            if(mPointList[ nvert ].equal( v2, 0.001f ) )
155            {
156               v2index = nvert;
157               v2Existed = true;
158               break;
159            }
160
161         // Add vertex 1, if necessary.
162
163         if( !v1Existed )
164         {
165            v1index = mPointList.size();
166         mPointList.push_back( v1 );
167         }
168
169         // Add vertex 2, if necessary.
170
171         if( !v2Existed )
172         {
173            v2index = mPointList.size();
174         mPointList.push_back( v2 );
175         }
176
177         // If both v1 and v2 already existed in the point
178         // set, this must be an edge that we are sharing so try
179         // to find it.
180
181         const U32 thisPlaneIndex = mPlaneList.size();
182         bool foundExistingEdge = false;
183
184         if( v1Existed && v2Existed )
185         {
186            for( U32 nedge = 0; nedge < mEdgeList.size(); ++ nedge )
187            {
188               Edge& edge = mEdgeList[ nedge ];
189
190               if( ( edge.vertex[ 0 ] == v1index && edge.vertex[ 1 ] == v2index ) ||
191                   ( edge.vertex[ 0 ] == v2index && edge.vertex[ 1 ] == v1index ) )
192               {
193                  edge.face[ 1 ] = thisPlaneIndex;
194                  foundExistingEdge = true;
195                  break;
196               }
197            }
198         }
199
200         // Otherwise, add a new edge.
201
202         if( !foundExistingEdge )
203         {
204            bool invert = false;
205
206            // We need to make sure to maintain CW ordering on face[0],
207            // so test to see if we need to go v1->v2 or v2->v1.
208
209            Point3F normal = mCross( currentPlane, v2 - v1 );
210            Point3F testPoint = v1 + normal;
211
212            for( U32 nplane = 0; nplane < numSourcePlanes; ++ nplane )
213            {
214               if( nplane == i )
215                  continue;
216
217               if( planes.getPlanes()[ nplane ].whichSide( testPoint ) == PlaneF::Back )
218               {
219                  invert = true;
220                  break;
221               }
222            }
223
224            if( !invert )
225            {
226            mEdgeList.push_back(
227                  Edge( thisPlaneIndex, 0, v1index, v2index )
228               );
229            }
230            else
231            {
232            mEdgeList.push_back(
233                  Edge( thisPlaneIndex, 0, v2index, v1index )
234               );
235            }
236         }
237
238         // This plane has edges.
239
240         haveEdges = true;
241      }
242
243      // If this plane produced edges, add it.
244
245      if( haveEdges )
246         mPlaneList.push_back( currentPlane );
247   }
248}
249