1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
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
|
