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