mSilhouetteExtractor.h

  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#ifndef _MSILHOUETTEEXTRACTOR_H_
 25#define _MSILHOUETTEEXTRACTOR_H_
 26
 27#ifndef _FRAMEALLOCATOR_H_
 28#include "core/frameAllocator.h"
 29#endif
 30
 31#ifndef _TVECTOR_H_
 32#include "core/util/tVector.h"
 33#endif
 34
 35
 36/// @file
 37/// Routines for extracting silhouette polygons from polyhedrons.
 38
 39
 40
 41template< typename Polyhedron >
 42struct SilhouetteExtractorBase
 43{
 44      typedef Polyhedron PolyhedronType;
 45
 46   protected:
 47
 48      /// The polyhedron from which we are extracting silhouettes.
 49      const PolyhedronType* mPolyhedron;
 50
 51      SilhouetteExtractorBase( const PolyhedronType& polyhedron )
 52         : mPolyhedron( &polyhedron ) {}
 53};
 54
 55
 56
 57/// Silhouette extraction routines for perspective projections.
 58template< typename Polyhedron >
 59struct SilhouetteExtractorBasePerspective : public SilhouetteExtractorBase< Polyhedron >
 60{
 61   private:
 62
 63      enum Orientation
 64      {
 65         FrontFacing,
 66         BackFacing
 67      };
 68
 69      /// @name Per-Extraction Data
 70      /// @{
 71
 72      /// The facing direction of each of the polygons.
 73      mutable Orientation* mPolygonOrientations;
 74
 75      /// Frame allocator water mark to release temporary memory after silhouette extraction.
 76      mutable U32 mWaterMark;
 77
 78      /// @}
 79
 80   public:
 81
 82      SilhouetteExtractorBasePerspective( const Polyhedron& polyhedron )
 83         : SilhouetteExtractorBase< Polyhedron >( polyhedron ),
 84           mPolygonOrientations( NULL ),
 85           mWaterMark( 0 ) {}
 86
 87      /// Initialize extraction.
 88      ///
 89      /// @param objectView View->object matrix.
 90      bool begin( const MatrixF& camView ) const
 91      {
 92         mWaterMark = FrameAllocator::getWaterMark();
 93
 94         // Determine orientation of each of the polygons.
 95
 96         const U32 numPolygons = this->mPolyhedron->getNumPlanes();
 97         mPolygonOrientations = ( Orientation* ) FrameAllocator::alloc( sizeof( Orientation ) * numPolygons );
 98
 99         Point3F camPos = camView.getPosition();
100
101         for( U32 i = 0; i < numPolygons; ++ i )
102         {
103            if (this->mPolyhedron->getPlanes()[i].whichSide( camPos ) == PlaneF::Front)
104               mPolygonOrientations[i] = FrontFacing;
105            else
106               mPolygonOrientations[i] = BackFacing;
107         }
108
109         return true;
110      }
111
112      /// End extraction.
113      void end() const
114      {
115         FrameAllocator::setWaterMark( mWaterMark );
116
117         mWaterMark = 0;
118         mPolygonOrientations = NULL;
119      }
120
121      /// Return true if the given edge is a silhouette edge with respect to the
122      /// current perspective transform.
123      ///
124      /// @param edgeIndex Index of edge to test.
125      /// @return True if the given edge is a silhouette when looked at from the given view position.
126      ///
127      /// @note This method depends on inward-facing normals!
128      bool isSilhouetteEdge( U32 edgeIndex ) const
129      {
130         AssertFatal( edgeIndex < this->mPolyhedron->getNumEdges(), "SilhouetteExtractorBasePerspective::isSilhouetteEdge - Index out of range!" );
131
132         const typename Polyhedron::EdgeType& edge = this->mPolyhedron->getEdges()[ edgeIndex ];
133
134         const U32 face0 = edge.face[ 0 ];
135         const U32 face1 = edge.face[ 1 ];
136
137         return ( mPolygonOrientations[ face0 ] != mPolygonOrientations[ face1 ] );
138      }
139};
140
141
142/// Silhouette extraction routines for orthographic projections.
143template< typename Polyhedron >
144struct SilhouetteExtractorBaseOrtho : public SilhouetteExtractorBase< Polyhedron >
145{
146   private:
147
148      /// @name Per-Extraction Data
149      /// @{
150
151      /// Precomputed dot products between view direction and plane normals
152      /// in the polyhedron.
153      mutable F32* mFaceDotProducts;
154
155      /// Frame allocator water mark.
156      mutable U32 mWaterMark;
157
158      /// @}
159
160   public:
161
162      SilhouetteExtractorBaseOrtho( const Polyhedron& polyhedron )
163         : SilhouetteExtractorBase< Polyhedron >( polyhedron ),
164           mFaceDotProducts( NULL ),
165           mWaterMark( 0 )
166      {
167      }
168
169      /// Initialize the extractor.
170      void begin( const Point3F& viewDirOS ) const
171      {
172         const typename Polyhedron::PlaneType* planes = this->mPolyhedron->getPlanes();
173         const U32 numPlanes = this->mPolyhedron->getNumPlanes();
174
175         mWaterMark = FrameAllocator::getWaterMark();
176         mFaceDotProducts = ( F32* ) FrameAllocator::alloc( sizeof( F32 ) * numPlanes );
177
178         for( U32 i = 0; i < numPlanes; ++ i )
179            mFaceDotProducts[ i ] = mDot( planes[ i ], viewDirOS );
180      }
181      
182      /// Finish extraction.
183      void end() const
184      {
185         FrameAllocator::setWaterMark( mWaterMark );
186
187         mFaceDotProducts = NULL;
188         mWaterMark = 0;
189      }
190
191      /// Return true if the given edge is a silhouette edge with respect to the
192      /// view direction.
193      ///
194      /// @param edgeIndex Index of edge to test.
195      /// @return True if the given edge is a silhouette in the projection along the view direction.
196      ///
197      /// @note This method depends on inward-facing normals!
198      bool isSilhouetteEdge( U32 edgeIndex ) const
199      {
200         AssertFatal( edgeIndex < this->mPolyhedron->getNumEdges(), "SilhouetteExtractorBaseOrtho::isSilhouetteEdge - Index out of range!" );
201
202         const typename Polyhedron::EdgeType& edge = this->mPolyhedron->getEdges()[ edgeIndex ];
203
204         const U32 face0 = edge.face[ 0 ];
205         const U32 face1 = edge.face[ 1 ];
206
207         // Not a silhouette if both planes are facing the same way.
208
209         if( mSign( mFaceDotProducts[ face0 ] ) == mSign( mFaceDotProducts[ face1 ] ) )
210            return false;
211
212         // Find out which face is the front facing one.  Since we expect normals
213         // to be pointing inwards, this means a reversal of the normal back facing
214         // test and we're looking for a normal facing the *same* way as our projection.
215
216         const U32 frontFace = mFaceDotProducts[ face0 ] > 0.f ? face0 : face1;
217         if( mFaceDotProducts[ frontFace ] <= 0.f )
218            return false; // This face or other face is perpendicular to us.
219
220         return true;
221      }
222};
223
224
225/// Common implementation parts for silhouette extraction.
226template< typename Base >
227struct SilhouetteExtractorImpl : public Base
228{
229      typedef typename Base::PolyhedronType PolyhedronType;
230
231      SilhouetteExtractorImpl( const PolyhedronType& polyhedron )
232         : Base( polyhedron ) {}
233
234      U32 extractSilhouette( U32* outIndices, U32 maxOutIndices ) const
235      {
236         // First, find the silhouette edges.  We do this with a brute-force
237         // approach here.  This can be optimized (see "Silhouette Algorithms" by Bruce Gooch, Mark
238         // Hartner, and Nathan Beddes).
239
240         U32 numSilhouetteEdges = 0;
241         const U32 numTotalEdges = this->mPolyhedron->getNumEdges();
242         const typename PolyhedronType::EdgeType* edges = this->mPolyhedron->getEdges();
243         FrameTemp< const typename PolyhedronType::EdgeType*> silhouetteEdges( numTotalEdges );
244
245         for( U32 i = 0; i < numTotalEdges; ++ i )
246            if( this->isSilhouetteEdge( i ) )
247               silhouetteEdges[ numSilhouetteEdges ++ ] = &edges[ i ];
248
249         // Allow this to happen rather than asserting as projection-based silhouettes
250         // may fail.
251         if( numSilhouetteEdges < 3 )
252            return 0;
253
254         // Now walk the edge list and find the edges that are connected
255         // with each other.  From this information, emit the silhouette
256         // polygon.
257
258         U32 idx = 0;
259
260         if( idx >= maxOutIndices )
261            return 0;
262         outIndices[ idx ++ ] = silhouetteEdges[ 0 ]->vertex[ 1 ];
263
264         U32 currentIndex = silhouetteEdges[ 0 ]->vertex[ 1 ];
265         U32 currentEdge = 0;
266
267         for( U32 i = 1; i < numSilhouetteEdges; ++ i )
268         {
269            // Find edge that continues on from the current vertex.
270            for( U32 n = 0; n < numSilhouetteEdges; ++ n )
271            {
272               // Skip current edge.
273               if( n == currentEdge )
274                  continue;
275
276               if( silhouetteEdges[ n ]->vertex[ 0 ] == currentIndex )
277                  currentIndex = silhouetteEdges[ n ]->vertex[ 1 ];
278               else if( silhouetteEdges[ n ]->vertex[ 1 ] == currentIndex )
279                  currentIndex = silhouetteEdges[ n ]->vertex[ 0 ];
280               else
281                  continue;
282
283               if( idx >= maxOutIndices )
284                  return 0;
285
286               currentEdge = n;
287               outIndices[ idx ++ ] = currentIndex;
288               break;
289            }
290         }
291
292         return idx;
293      }
294};
295
296
297/// Silhouette edge extraction for orthographic projections.
298template< typename Polyhedron >
299struct SilhouetteExtractorOrtho
300{
301   protected:
302
303      typedef SilhouetteExtractorImpl< SilhouetteExtractorBaseOrtho< Polyhedron> > ExtractorType;
304
305      /// The actual extractor implementation.
306      ExtractorType mExtractor;
307
308   public:
309
310      SilhouetteExtractorOrtho( const Polyhedron& polyhedron )
311         : mExtractor( polyhedron ) {}
312
313      /// Generate a silhouette polygon for the polyhedron based on the given view direction.
314      ///
315      /// @param viewDirOS Object-space normalized view vector.
316      /// @param outIndices Array where the resulting vertex indices will be stored.  Must have
317      ///   enough room.  If you don't know the exact size that you need, just allocate one index
318      ///   for any point in the mesh.
319      /// @param maxOutIndices The number of indices that can be stored in @a outIndices.  If insufficient,
320      ///   the return value will be 0.
321      ///
322      /// @return Number of indices written to @a outIndices or 0 if the silhouette extraction failed.
323      ///
324      /// @note Be aware that silhouette polygons are in most cases non-planar!
325      /// @note The direction of the ordering of the resulting indices is undefined meaning that
326      ///   different silhouettes extracted from the same polyhedron may have different CCW/CW ordering.
327      ///   The only guarantee is that the resulting indices are consecutive.
328      U32 extractSilhouette( const Point3F& viewDirOS, U32* outIndices, U32 maxOutIndices ) const
329      {
330         U32 result = 0;
331
332         mExtractor.begin( viewDirOS );
333         result = mExtractor.extractSilhouette( outIndices, maxOutIndices );
334         mExtractor.end();
335
336         return result;
337      }
338};
339
340
341/// Silhouette edge extraction for perspective projections.
342template< typename Polyhedron >
343struct SilhouetteExtractorPerspective
344{
345   protected:
346
347      typedef SilhouetteExtractorImpl< SilhouetteExtractorBasePerspective< Polyhedron> > ExtractorType;
348
349      /// The actual extractor implementation.
350      ExtractorType mExtractor;
351
352   public:
353
354      SilhouetteExtractorPerspective( const Polyhedron& polyhedron )
355         : mExtractor( polyhedron ) {}
356
357      /// Generate a silhouette polygon for this polyhedron based on the transforms.
358      ///
359      /// @param camView View->object matrix.
360      /// @param outIndices Array where the resulting vertex indices will be stored.  Must have
361      ///   enough room.  If you don't know the exact size that you need, just allocate one index
362      ///   for any point in the mesh.
363      /// @param maxOutIndices The number of indices that can be stored in @a outIndices.  If insufficient,
364      ///   the return value will be 0.
365      ///
366      /// @return Number of indices written to @a outIndices.
367      ///
368      /// @note Be aware that silhouette polygons are in most cases non-planar!
369      /// @note The direction of the ordering of the resulting indices is undefined meaning that
370      ///   different silhouettes extracted from the same polyhedron may have different CCW/CW ordering.
371      ///   The only guarantee is that the resulting indices are consecutive.
372      U32 extractSilhouette( const MatrixF& camView, U32* outIndices, U32 maxOutIndices ) const
373      {
374         U32 result = 0;
375
376         if( mExtractor.begin( camView ) )
377            result = mExtractor.extractSilhouette( outIndices, maxOutIndices );
378
379         mExtractor.end();
380
381         return result;         
382      }
383};
384
385#endif // !_MSILHOUETTEEXTRACTOR_H_
386