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