1 /* 2 Open Asset Import Library (assimp) 3 ---------------------------------------------------------------------- 4 5 Copyright (c) 2006-2021, assimp team 6 7 8 All rights reserved. 9 10 Redistribution and use of this software in source and binary forms, 11 with or without modification, are permitted provided that the 12 following conditions are met: 13 14 * Redistributions of source code must retain the above 15 copyright notice, this list of conditions and the 16 following disclaimer. 17 18 * Redistributions in binary form must reproduce the above 19 copyright notice, this list of conditions and the 20 following disclaimer in the documentation and/or other 21 materials provided with the distribution. 22 23 * Neither the name of the assimp team, nor the names of its 24 contributors may be used to endorse or promote products 25 derived from this software without specific prior 26 written permission of the assimp team. 27 28 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 29 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 30 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 31 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 32 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 33 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 34 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 35 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 36 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 37 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 38 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 39 40 ---------------------------------------------------------------------- 41 */ 42 43 /** Small helper classes to optimise finding vertizes close to a given location */ 44 #pragma once 45 #ifndef AI_SPATIALSORT_H_INC 46 #define AI_SPATIALSORT_H_INC 47 48 #ifdef __GNUC__ 49 #pragma GCC system_header 50 #endif 51 52 #include <assimp/types.h> 53 #include <vector> 54 #include <limits> 55 56 namespace Assimp { 57 58 // ------------------------------------------------------------------------------------------------ 59 /** A little helper class to quickly find all vertices in the epsilon environment of a given 60 * position. Construct an instance with an array of positions. The class stores the given positions 61 * by their indices and sorts them by their distance to an arbitrary chosen plane. 62 * You can then query the instance for all vertices close to a given position in an average O(log n) 63 * time, with O(n) worst case complexity when all vertices lay on the plane. The plane is chosen 64 * so that it avoids common planes in usual data sets. */ 65 // ------------------------------------------------------------------------------------------------ 66 class ASSIMP_API SpatialSort { 67 public: 68 SpatialSort(); 69 70 // ------------------------------------------------------------------------------------ 71 /** Constructs a spatially sorted representation from the given position array. 72 * Supply the positions in its layout in memory, the class will only refer to them 73 * by index. 74 * @param pPositions Pointer to the first position vector of the array. 75 * @param pNumPositions Number of vectors to expect in that array. 76 * @param pElementOffset Offset in bytes from the beginning of one vector in memory 77 * to the beginning of the next vector. */ 78 SpatialSort(const aiVector3D *pPositions, unsigned int pNumPositions, 79 unsigned int pElementOffset); 80 81 /** Destructor */ 82 ~SpatialSort(); 83 84 // ------------------------------------------------------------------------------------ 85 /** Sets the input data for the SpatialSort. This replaces existing data, if any. 86 * The new data receives new indices in ascending order. 87 * 88 * @param pPositions Pointer to the first position vector of the array. 89 * @param pNumPositions Number of vectors to expect in that array. 90 * @param pElementOffset Offset in bytes from the beginning of one vector in memory 91 * to the beginning of the next vector. 92 * @param pFinalize Specifies whether the SpatialSort's internal representation 93 * is finalized after the new data has been added. Finalization is 94 * required in order to use #FindPosition() or #GenerateMappingTable(). 95 * If you don't finalize yet, you can use #Append() to add data from 96 * other sources.*/ 97 void Fill(const aiVector3D *pPositions, unsigned int pNumPositions, 98 unsigned int pElementOffset, 99 bool pFinalize = true); 100 101 // ------------------------------------------------------------------------------------ 102 /** Same as #Fill(), except the method appends to existing data in the #SpatialSort. */ 103 void Append(const aiVector3D *pPositions, unsigned int pNumPositions, 104 unsigned int pElementOffset, 105 bool pFinalize = true); 106 107 // ------------------------------------------------------------------------------------ 108 /** Finalize the spatial hash data structure. This can be useful after 109 * multiple calls to #Append() with the pFinalize parameter set to false. 110 * This is finally required before one of #FindPositions() and #GenerateMappingTable() 111 * can be called to query the spatial sort.*/ 112 void Finalize(); 113 114 // ------------------------------------------------------------------------------------ 115 /** Returns an iterator for all positions close to the given position. 116 * @param pPosition The position to look for vertices. 117 * @param pRadius Maximal distance from the position a vertex may have to be counted in. 118 * @param poResults The container to store the indices of the found positions. 119 * Will be emptied by the call so it may contain anything. 120 * @return An iterator to iterate over all vertices in the given area.*/ 121 void FindPositions(const aiVector3D &pPosition, ai_real pRadius, 122 std::vector<unsigned int> &poResults) const; 123 124 // ------------------------------------------------------------------------------------ 125 /** Fills an array with indices of all positions identical to the given position. In 126 * opposite to FindPositions(), not an epsilon is used but a (very low) tolerance of 127 * four floating-point units. 128 * @param pPosition The position to look for vertices. 129 * @param poResults The container to store the indices of the found positions. 130 * Will be emptied by the call so it may contain anything.*/ 131 void FindIdenticalPositions(const aiVector3D &pPosition, 132 std::vector<unsigned int> &poResults) const; 133 134 // ------------------------------------------------------------------------------------ 135 /** Compute a table that maps each vertex ID referring to a spatially close 136 * enough position to the same output ID. Output IDs are assigned in ascending order 137 * from 0...n. 138 * @param fill Will be filled with numPositions entries. 139 * @param pRadius Maximal distance from the position a vertex may have to 140 * be counted in. 141 * @return Number of unique vertices (n). */ 142 unsigned int GenerateMappingTable(std::vector<unsigned int> &fill, 143 ai_real pRadius) const; 144 145 protected: 146 /** Return the distance to the sorting plane. */ 147 ai_real CalculateDistance(const aiVector3D &pPosition) const; 148 149 protected: 150 /** Normal of the sorting plane, normalized. 151 */ 152 aiVector3D mPlaneNormal; 153 154 /** The centroid of the positions, which is used as a point on the sorting plane 155 * when calculating distance. This value is calculated in Finalize. 156 */ 157 aiVector3D mCentroid; 158 159 /** An entry in a spatially sorted position array. Consists of a vertex index, 160 * its position and its pre-calculated distance from the reference plane */ 161 struct Entry { 162 unsigned int mIndex; ///< The vertex referred by this entry 163 aiVector3D mPosition; ///< Position 164 /// Distance of this vertex to the sorting plane. This is set by Finalize. 165 ai_real mDistance; 166 EntryEntry167 Entry() AI_NO_EXCEPT 168 : mIndex(std::numeric_limits<unsigned int>::max()), 169 mPosition(), 170 mDistance(std::numeric_limits<ai_real>::max()) { 171 // empty 172 } EntryEntry173 Entry(unsigned int pIndex, const aiVector3D &pPosition) : 174 mIndex(pIndex), mPosition(pPosition), mDistance(std::numeric_limits<ai_real>::max()) { 175 // empty 176 } 177 178 bool operator<(const Entry &e) const { return mDistance < e.mDistance; } 179 }; 180 181 // all positions, sorted by distance to the sorting plane 182 std::vector<Entry> mPositions; 183 184 /// false until the Finalize method is called. 185 bool mFinalized; 186 }; 187 188 } // end of namespace Assimp 189 190 #endif // AI_SPATIALSORT_H_INC 191