1/*
2Open Asset Import Library (assimp)
3----------------------------------------------------------------------
4
5Copyright (c) 2006-2017, assimp team
6
7All rights reserved.
8
9Redistribution and use of this software in source and binary forms,
10with or without modification, are permitted provided that the
11following conditions are met:
12
13* Redistributions of source code must retain the above
14 copyright notice, this list of conditions and the
15 following disclaimer.
16
17* Redistributions in binary form must reproduce the above
18 copyright notice, this list of conditions and the
19 following disclaimer in the documentation and/or other
20 materials provided with the distribution.
21
22* Neither the name of the assimp team, nor the names of its
23 contributors may be used to endorse or promote products
24 derived from this software without specific prior
25 written permission of the assimp team.
26
27THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
28"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
29LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
30A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
31OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
32SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
33LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
34DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
35THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
36(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
37OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
38
39----------------------------------------------------------------------
40*/
41
42/** Small helper classes to optimise finding vertizes close to a given location */
43#ifndef AI_SPATIALSORT_H_INC
44#define AI_SPATIALSORT_H_INC
45
46#include <vector>
47#include <assimp/types.h>
48
49namespace Assimp
50{
51
52// ------------------------------------------------------------------------------------------------
53/** A little helper class to quickly find all vertices in the epsilon environment of a given
54 * position. Construct an instance with an array of positions. The class stores the given positions
55 * by their indices and sorts them by their distance to an arbitrary chosen plane.
56 * You can then query the instance for all vertices close to a given position in an average O(log n)
57 * time, with O(n) worst case complexity when all vertices lay on the plane. The plane is chosen
58 * so that it avoids common planes in usual data sets. */
59// ------------------------------------------------------------------------------------------------
60class SpatialSort
61{
62public:
63
64 SpatialSort();
65
66 // ------------------------------------------------------------------------------------
67 /** Constructs a spatially sorted representation from the given position array.
68 * Supply the positions in its layout in memory, the class will only refer to them
69 * by index.
70 * @param pPositions Pointer to the first position vector of the array.
71 * @param pNumPositions Number of vectors to expect in that array.
72 * @param pElementOffset Offset in bytes from the beginning of one vector in memory
73 * to the beginning of the next vector. */
74 SpatialSort( const aiVector3D* pPositions, unsigned int pNumPositions,
75 unsigned int pElementOffset);
76
77 /** Destructor */
78 ~SpatialSort();
79
80public:
81
82 // ------------------------------------------------------------------------------------
83 /** Sets the input data for the SpatialSort. This replaces existing data, if any.
84 * The new data receives new indices in ascending order.
85 *
86 * @param pPositions Pointer to the first position vector of the array.
87 * @param pNumPositions Number of vectors to expect in that array.
88 * @param pElementOffset Offset in bytes from the beginning of one vector in memory
89 * to the beginning of the next vector.
90 * @param pFinalize Specifies whether the SpatialSort's internal representation
91 * is finalized after the new data has been added. Finalization is
92 * required in order to use #FindPosition() or #GenerateMappingTable().
93 * If you don't finalize yet, you can use #Append() to add data from
94 * other sources.*/
95 void Fill( const aiVector3D* pPositions, unsigned int pNumPositions,
96 unsigned int pElementOffset,
97 bool pFinalize = true);
98
99
100 // ------------------------------------------------------------------------------------
101 /** Same as #Fill(), except the method appends to existing data in the #SpatialSort. */
102 void Append( const aiVector3D* pPositions, unsigned int pNumPositions,
103 unsigned int pElementOffset,
104 bool pFinalize = true);
105
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
145protected:
146 /** Normal of the sorting plane, normalized. The center is always at (0, 0, 0) */
147 aiVector3D mPlaneNormal;
148
149 /** An entry in a spatially sorted position array. Consists of a vertex index,
150 * its position and its precalculated distance from the reference plane */
151 struct Entry
152 {
153 unsigned int mIndex; ///< The vertex referred by this entry
154 aiVector3D mPosition; ///< Position
155 ai_real mDistance; ///< Distance of this vertex to the sorting plane
156
157 Entry() { /** intentionally not initialized.*/ }
158 Entry( unsigned int pIndex, const aiVector3D& pPosition, ai_real pDistance)
159 : mIndex( pIndex), mPosition( pPosition), mDistance( pDistance)
160 { }
161
162 bool operator < (const Entry& e) const { return mDistance < e.mDistance; }
163 };
164
165 // all positions, sorted by distance to the sorting plane
166 std::vector<Entry> mPositions;
167};
168
169} // end of namespace Assimp
170
171#endif // AI_SPATIALSORT_H_INC
172