1 | /* |
2 | Open Asset Import Library (assimp) |
3 | ---------------------------------------------------------------------- |
4 | |
5 | Copyright (c) 2006-2019, 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 optimize finding vertices close to a given location |
44 | */ |
45 | #ifndef AI_D3DSSPATIALSORT_H_INC |
46 | #define AI_D3DSSPATIALSORT_H_INC |
47 | |
48 | #include <assimp/types.h> |
49 | #include <vector> |
50 | #include <stdint.h> |
51 | |
52 | namespace Assimp { |
53 | |
54 | // ---------------------------------------------------------------------------------- |
55 | /** Specialized version of SpatialSort to support smoothing groups |
56 | * This is used in by the 3DS, ASE and LWO loaders. 3DS and ASE share their |
57 | * normal computation code in SmoothingGroups.inl, the LWO loader has its own |
58 | * implementation to handle all details of its file format correctly. |
59 | */ |
60 | // ---------------------------------------------------------------------------------- |
61 | class ASSIMP_API SGSpatialSort |
62 | { |
63 | public: |
64 | |
65 | SGSpatialSort(); |
66 | |
67 | // ------------------------------------------------------------------- |
68 | /** Construction from a given face array, handling smoothing groups |
69 | * properly |
70 | */ |
71 | explicit SGSpatialSort(const std::vector<aiVector3D>& vPositions); |
72 | |
73 | // ------------------------------------------------------------------- |
74 | /** Add a vertex to the spatial sort |
75 | * @param vPosition Vertex position to be added |
76 | * @param index Index of the vrtex |
77 | * @param smoothingGroup SmoothingGroup for this vertex |
78 | */ |
79 | void Add(const aiVector3D& vPosition, unsigned int index, |
80 | unsigned int smoothingGroup); |
81 | |
82 | // ------------------------------------------------------------------- |
83 | /** Prepare the spatial sorter for use. This step runs in O(logn) |
84 | */ |
85 | void Prepare(); |
86 | |
87 | /** Destructor */ |
88 | ~SGSpatialSort(); |
89 | |
90 | // ------------------------------------------------------------------- |
91 | /** Returns an iterator for all positions close to the given position. |
92 | * @param pPosition The position to look for vertices. |
93 | * @param pSG Only included vertices with at least one shared smooth group |
94 | * @param pRadius Maximal distance from the position a vertex may have |
95 | * to be counted in. |
96 | * @param poResults The container to store the indices of the found |
97 | * positions. Will be emptied by the call so it may contain anything. |
98 | * @param exactMatch Specifies whether smoothing groups are bit masks |
99 | * (false) or integral values (true). In the latter case, a vertex |
100 | * cannot belong to more than one smoothing group. |
101 | * @return An iterator to iterate over all vertices in the given area. |
102 | */ |
103 | // ------------------------------------------------------------------- |
104 | void FindPositions( const aiVector3D& pPosition, uint32_t pSG, |
105 | float pRadius, std::vector<unsigned int>& poResults, |
106 | bool exactMatch = false) const; |
107 | |
108 | protected: |
109 | /** Normal of the sorting plane, normalized. The center is always at (0, 0, 0) */ |
110 | aiVector3D mPlaneNormal; |
111 | |
112 | // ------------------------------------------------------------------- |
113 | /** An entry in a spatially sorted position array. Consists of a |
114 | * vertex index, its position and its pre-calculated distance from |
115 | * the reference plane */ |
116 | // ------------------------------------------------------------------- |
117 | struct Entry { |
118 | unsigned int mIndex; ///< The vertex referred by this entry |
119 | aiVector3D mPosition; ///< Position |
120 | uint32_t mSmoothGroups; |
121 | float mDistance; ///< Distance of this vertex to the sorting plane |
122 | |
123 | Entry() AI_NO_EXCEPT |
124 | : mIndex(0) |
125 | , mPosition() |
126 | , mSmoothGroups(0) |
127 | , mDistance(0.0f) { |
128 | // empty |
129 | } |
130 | |
131 | Entry( unsigned int pIndex, const aiVector3D& pPosition, float pDistance,uint32_t pSG) |
132 | : mIndex( pIndex) |
133 | , mPosition( pPosition) |
134 | , mSmoothGroups(pSG) |
135 | , mDistance( pDistance) { |
136 | // empty |
137 | } |
138 | |
139 | bool operator < (const Entry& e) const { |
140 | return mDistance < e.mDistance; |
141 | } |
142 | }; |
143 | |
144 | // all positions, sorted by distance to the sorting plane |
145 | std::vector<Entry> mPositions; |
146 | }; |
147 | |
148 | } // end of namespace Assimp |
149 | |
150 | #endif // AI_SPATIALSORT_H_INC |
151 | |