nuclear@0: /* nuclear@0: Open Asset Import Library (assimp) nuclear@0: ---------------------------------------------------------------------- nuclear@0: nuclear@0: Copyright (c) 2006-2012, assimp team nuclear@0: All rights reserved. nuclear@0: nuclear@0: Redistribution and use of this software in source and binary forms, nuclear@0: with or without modification, are permitted provided that the nuclear@0: following conditions are met: nuclear@0: nuclear@0: * Redistributions of source code must retain the above nuclear@0: copyright notice, this list of conditions and the nuclear@0: following disclaimer. nuclear@0: nuclear@0: * Redistributions in binary form must reproduce the above nuclear@0: copyright notice, this list of conditions and the nuclear@0: following disclaimer in the documentation and/or other nuclear@0: materials provided with the distribution. nuclear@0: nuclear@0: * Neither the name of the assimp team, nor the names of its nuclear@0: contributors may be used to endorse or promote products nuclear@0: derived from this software without specific prior nuclear@0: written permission of the assimp team. nuclear@0: nuclear@0: THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS nuclear@0: "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT nuclear@0: LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR nuclear@0: A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT nuclear@0: OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, nuclear@0: SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT nuclear@0: LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, nuclear@0: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY nuclear@0: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT nuclear@0: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE nuclear@0: OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. nuclear@0: nuclear@0: ---------------------------------------------------------------------- nuclear@0: */ nuclear@0: nuclear@0: /** Small helper classes to optimise finding vertizes close to a given location */ nuclear@0: #ifndef AI_SPATIALSORT_H_INC nuclear@0: #define AI_SPATIALSORT_H_INC nuclear@0: nuclear@0: #include nuclear@0: #include "assimp/types.h" nuclear@0: nuclear@0: namespace Assimp nuclear@0: { nuclear@0: nuclear@0: // ------------------------------------------------------------------------------------------------ nuclear@0: /** A little helper class to quickly find all vertices in the epsilon environment of a given nuclear@0: * position. Construct an instance with an array of positions. The class stores the given positions nuclear@0: * by their indices and sorts them by their distance to an arbitrary chosen plane. nuclear@0: * You can then query the instance for all vertices close to a given position in an average O(log n) nuclear@0: * time, with O(n) worst case complexity when all vertices lay on the plane. The plane is chosen nuclear@0: * so that it avoids common planes in usual data sets. */ nuclear@0: // ------------------------------------------------------------------------------------------------ nuclear@0: class SpatialSort nuclear@0: { nuclear@0: public: nuclear@0: nuclear@0: SpatialSort(); nuclear@0: nuclear@0: // ------------------------------------------------------------------------------------ nuclear@0: /** Constructs a spatially sorted representation from the given position array. nuclear@0: * Supply the positions in its layout in memory, the class will only refer to them nuclear@0: * by index. nuclear@0: * @param pPositions Pointer to the first position vector of the array. nuclear@0: * @param pNumPositions Number of vectors to expect in that array. nuclear@0: * @param pElementOffset Offset in bytes from the beginning of one vector in memory nuclear@0: * to the beginning of the next vector. */ nuclear@0: SpatialSort( const aiVector3D* pPositions, unsigned int pNumPositions, nuclear@0: unsigned int pElementOffset); nuclear@0: nuclear@0: /** Destructor */ nuclear@0: ~SpatialSort(); nuclear@0: nuclear@0: public: nuclear@0: nuclear@0: // ------------------------------------------------------------------------------------ nuclear@0: /** Sets the input data for the SpatialSort. This replaces existing data, if any. nuclear@0: * The new data receives new indices in ascending order. nuclear@0: * nuclear@0: * @param pPositions Pointer to the first position vector of the array. nuclear@0: * @param pNumPositions Number of vectors to expect in that array. nuclear@0: * @param pElementOffset Offset in bytes from the beginning of one vector in memory nuclear@0: * to the beginning of the next vector. nuclear@0: * @param pFinalize Specifies whether the SpatialSort's internal representation nuclear@0: * is finalized after the new data has been added. Finalization is nuclear@0: * required in order to use #FindPosition() or #GenerateMappingTable(). nuclear@0: * If you don't finalize yet, you can use #Append() to add data from nuclear@0: * other sources.*/ nuclear@0: void Fill( const aiVector3D* pPositions, unsigned int pNumPositions, nuclear@0: unsigned int pElementOffset, nuclear@0: bool pFinalize = true); nuclear@0: nuclear@0: nuclear@0: // ------------------------------------------------------------------------------------ nuclear@0: /** Same as #Fill(), except the method appends to existing data in the #SpatialSort. */ nuclear@0: void Append( const aiVector3D* pPositions, unsigned int pNumPositions, nuclear@0: unsigned int pElementOffset, nuclear@0: bool pFinalize = true); nuclear@0: nuclear@0: nuclear@0: // ------------------------------------------------------------------------------------ nuclear@0: /** Finalize the spatial hash data structure. This can be useful after nuclear@0: * multiple calls to #Append() with the pFinalize parameter set to false. nuclear@0: * This is finally required before one of #FindPositions() and #GenerateMappingTable() nuclear@0: * can be called to query the spatial sort.*/ nuclear@0: void Finalize(); nuclear@0: nuclear@0: // ------------------------------------------------------------------------------------ nuclear@0: /** Returns an iterator for all positions close to the given position. nuclear@0: * @param pPosition The position to look for vertices. nuclear@0: * @param pRadius Maximal distance from the position a vertex may have to be counted in. nuclear@0: * @param poResults The container to store the indices of the found positions. nuclear@0: * Will be emptied by the call so it may contain anything. nuclear@0: * @return An iterator to iterate over all vertices in the given area.*/ nuclear@0: void FindPositions( const aiVector3D& pPosition, float pRadius, nuclear@0: std::vector& poResults) const; nuclear@0: nuclear@0: // ------------------------------------------------------------------------------------ nuclear@0: /** Fills an array with indices of all positions indentical to the given position. In nuclear@0: * opposite to FindPositions(), not an epsilon is used but a (very low) tolerance of nuclear@0: * four floating-point units. nuclear@0: * @param pPosition The position to look for vertices. nuclear@0: * @param poResults The container to store the indices of the found positions. nuclear@0: * Will be emptied by the call so it may contain anything.*/ nuclear@0: void FindIdenticalPositions( const aiVector3D& pPosition, nuclear@0: std::vector& poResults) const; nuclear@0: nuclear@0: // ------------------------------------------------------------------------------------ nuclear@0: /** Compute a table that maps each vertex ID referring to a spatially close nuclear@0: * enough position to the same output ID. Output IDs are assigned in ascending order nuclear@0: * from 0...n. nuclear@0: * @param fill Will be filled with numPositions entries. nuclear@0: * @param pRadius Maximal distance from the position a vertex may have to nuclear@0: * be counted in. nuclear@0: * @return Number of unique vertices (n). */ nuclear@0: unsigned int GenerateMappingTable(std::vector& fill, nuclear@0: float pRadius) const; nuclear@0: nuclear@0: protected: nuclear@0: /** Normal of the sorting plane, normalized. The center is always at (0, 0, 0) */ nuclear@0: aiVector3D mPlaneNormal; nuclear@0: nuclear@0: /** An entry in a spatially sorted position array. Consists of a vertex index, nuclear@0: * its position and its precalculated distance from the reference plane */ nuclear@0: struct Entry nuclear@0: { nuclear@0: unsigned int mIndex; ///< The vertex referred by this entry nuclear@0: aiVector3D mPosition; ///< Position nuclear@0: float mDistance; ///< Distance of this vertex to the sorting plane nuclear@0: nuclear@0: Entry() { /** intentionally not initialized.*/ } nuclear@0: Entry( unsigned int pIndex, const aiVector3D& pPosition, float pDistance) nuclear@0: : mIndex( pIndex), mPosition( pPosition), mDistance( pDistance) nuclear@0: { } nuclear@0: nuclear@0: bool operator < (const Entry& e) const { return mDistance < e.mDistance; } nuclear@0: }; nuclear@0: nuclear@0: // all positions, sorted by distance to the sorting plane nuclear@0: std::vector mPositions; nuclear@0: }; nuclear@0: nuclear@0: } // end of namespace Assimp nuclear@0: nuclear@0: #endif // AI_SPATIALSORT_H_INC