1 /*
2 ---------------------------------------------------------------------------
3 Open Asset Import Library (assimp)
4 ---------------------------------------------------------------------------
5
6 Copyright (c) 2006-2019, assimp team
7
8
9
10 All rights reserved.
11
12 Redistribution and use of this software in source and binary forms,
13 with or without modification, are permitted provided that the following
14 conditions are met:
15
16 * Redistributions of source code must retain the above
17 copyright notice, this list of conditions and the
18 following disclaimer.
19
20 * Redistributions in binary form must reproduce the above
21 copyright notice, this list of conditions and the
22 following disclaimer in the documentation and/or other
23 materials provided with the distribution.
24
25 * Neither the name of the assimp team, nor the names of its
26 contributors may be used to endorse or promote products
27 derived from this software without specific prior
28 written permission of the assimp team.
29
30 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
31 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
32 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
33 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
34 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
35 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
36 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
37 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
38 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
39 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
40 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
41 ---------------------------------------------------------------------------
42 */
43
44 /** @file FindDegenerates.cpp
45 * @brief Implementation of the FindDegenerates post-process step.
46 */
47
48
49
50 // internal headers
51 #include "ProcessHelper.h"
52 #include "FindDegenerates.h"
53 #include <assimp/Exceptional.h>
54
55 using namespace Assimp;
56
57 //remove mesh at position 'index' from the scene
58 static void removeMesh(aiScene* pScene, unsigned const index);
59 //correct node indices to meshes and remove references to deleted mesh
60 static void updateSceneGraph(aiNode* pNode, unsigned const index);
61
62 // ------------------------------------------------------------------------------------------------
63 // Constructor to be privately used by Importer
FindDegeneratesProcess()64 FindDegeneratesProcess::FindDegeneratesProcess()
65 : mConfigRemoveDegenerates( false )
66 , mConfigCheckAreaOfTriangle( false ){
67 // empty
68 }
69
70 // ------------------------------------------------------------------------------------------------
71 // Destructor, private as well
~FindDegeneratesProcess()72 FindDegeneratesProcess::~FindDegeneratesProcess() {
73 // nothing to do here
74 }
75
76 // ------------------------------------------------------------------------------------------------
77 // Returns whether the processing step is present in the given flag field.
IsActive(unsigned int pFlags) const78 bool FindDegeneratesProcess::IsActive( unsigned int pFlags) const {
79 return 0 != (pFlags & aiProcess_FindDegenerates);
80 }
81
82 // ------------------------------------------------------------------------------------------------
83 // Setup import configuration
SetupProperties(const Importer * pImp)84 void FindDegeneratesProcess::SetupProperties(const Importer* pImp) {
85 // Get the current value of AI_CONFIG_PP_FD_REMOVE
86 mConfigRemoveDegenerates = (0 != pImp->GetPropertyInteger(AI_CONFIG_PP_FD_REMOVE,0));
87 mConfigCheckAreaOfTriangle = ( 0 != pImp->GetPropertyInteger(AI_CONFIG_PP_FD_CHECKAREA) );
88 }
89
90 // ------------------------------------------------------------------------------------------------
91 // Executes the post processing step on the given imported data.
Execute(aiScene * pScene)92 void FindDegeneratesProcess::Execute( aiScene* pScene) {
93 ASSIMP_LOG_DEBUG("FindDegeneratesProcess begin");
94 for (unsigned int i = 0; i < pScene->mNumMeshes;++i)
95 {
96 //Do not process point cloud, ExecuteOnMesh works only with faces data
97 if ((pScene->mMeshes[i]->mPrimitiveTypes != aiPrimitiveType::aiPrimitiveType_POINT) && ExecuteOnMesh(pScene->mMeshes[i])) {
98 removeMesh(pScene, i);
99 --i; //the current i is removed, do not skip the next one
100 }
101 }
102 ASSIMP_LOG_DEBUG("FindDegeneratesProcess finished");
103 }
104
removeMesh(aiScene * pScene,unsigned const index)105 static void removeMesh(aiScene* pScene, unsigned const index) {
106 //we start at index and copy the pointers one position forward
107 //save the mesh pointer to delete it later
108 auto delete_me = pScene->mMeshes[index];
109 for (unsigned i = index; i < pScene->mNumMeshes - 1; ++i) {
110 pScene->mMeshes[i] = pScene->mMeshes[i+1];
111 }
112 pScene->mMeshes[pScene->mNumMeshes - 1] = nullptr;
113 --(pScene->mNumMeshes);
114 delete delete_me;
115
116 //removing a mesh also requires updating all references to it in the scene graph
117 updateSceneGraph(pScene->mRootNode, index);
118 }
119
updateSceneGraph(aiNode * pNode,unsigned const index)120 static void updateSceneGraph(aiNode* pNode, unsigned const index) {
121 for (unsigned i = 0; i < pNode->mNumMeshes; ++i) {
122 if (pNode->mMeshes[i] > index) {
123 --(pNode->mMeshes[i]);
124 continue;
125 }
126 if (pNode->mMeshes[i] == index) {
127 for (unsigned j = i; j < pNode->mNumMeshes -1; ++j) {
128 pNode->mMeshes[j] = pNode->mMeshes[j+1];
129 }
130 --(pNode->mNumMeshes);
131 --i;
132 continue;
133 }
134 }
135 //recurse to all children
136 for (unsigned i = 0; i < pNode->mNumChildren; ++i) {
137 updateSceneGraph(pNode->mChildren[i], index);
138 }
139 }
140
heron(ai_real a,ai_real b,ai_real c)141 static ai_real heron( ai_real a, ai_real b, ai_real c ) {
142 ai_real s = (a + b + c) / 2;
143 ai_real area = pow((s * ( s - a ) * ( s - b ) * ( s - c ) ), (ai_real)0.5 );
144 return area;
145 }
146
distance3D(const aiVector3D & vA,aiVector3D & vB)147 static ai_real distance3D( const aiVector3D &vA, aiVector3D &vB ) {
148 const ai_real lx = ( vB.x - vA.x );
149 const ai_real ly = ( vB.y - vA.y );
150 const ai_real lz = ( vB.z - vA.z );
151 ai_real a = lx*lx + ly*ly + lz*lz;
152 ai_real d = pow( a, (ai_real)0.5 );
153
154 return d;
155 }
156
calculateAreaOfTriangle(const aiFace & face,aiMesh * mesh)157 static ai_real calculateAreaOfTriangle( const aiFace& face, aiMesh* mesh ) {
158 ai_real area = 0;
159
160 aiVector3D vA( mesh->mVertices[ face.mIndices[ 0 ] ] );
161 aiVector3D vB( mesh->mVertices[ face.mIndices[ 1 ] ] );
162 aiVector3D vC( mesh->mVertices[ face.mIndices[ 2 ] ] );
163
164 ai_real a( distance3D( vA, vB ) );
165 ai_real b( distance3D( vB, vC ) );
166 ai_real c( distance3D( vC, vA ) );
167 area = heron( a, b, c );
168
169 return area;
170 }
171
172 // ------------------------------------------------------------------------------------------------
173 // Executes the post processing step on the given imported mesh
ExecuteOnMesh(aiMesh * mesh)174 bool FindDegeneratesProcess::ExecuteOnMesh( aiMesh* mesh) {
175 mesh->mPrimitiveTypes = 0;
176
177 std::vector<bool> remove_me;
178 if (mConfigRemoveDegenerates) {
179 remove_me.resize( mesh->mNumFaces, false );
180 }
181
182 unsigned int deg = 0, limit;
183 for ( unsigned int a = 0; a < mesh->mNumFaces; ++a ) {
184 aiFace& face = mesh->mFaces[a];
185 bool first = true;
186
187 // check whether the face contains degenerated entries
188 for (unsigned int i = 0; i < face.mNumIndices; ++i) {
189 // Polygons with more than 4 points are allowed to have double points, that is
190 // simulating polygons with holes just with concave polygons. However,
191 // double points may not come directly after another.
192 limit = face.mNumIndices;
193 if (face.mNumIndices > 4) {
194 limit = std::min( limit, i+2 );
195 }
196
197 for (unsigned int t = i+1; t < limit; ++t) {
198 if (mesh->mVertices[face.mIndices[ i ] ] == mesh->mVertices[ face.mIndices[ t ] ]) {
199 // we have found a matching vertex position
200 // remove the corresponding index from the array
201 --face.mNumIndices;
202 --limit;
203 for (unsigned int m = t; m < face.mNumIndices; ++m) {
204 face.mIndices[ m ] = face.mIndices[ m+1 ];
205 }
206 --t;
207
208 // NOTE: we set the removed vertex index to an unique value
209 // to make sure the developer gets notified when his
210 // application attempts to access this data.
211 face.mIndices[ face.mNumIndices ] = 0xdeadbeef;
212
213 if(first) {
214 ++deg;
215 first = false;
216 }
217
218 if ( mConfigRemoveDegenerates ) {
219 remove_me[ a ] = true;
220 goto evil_jump_outside; // hrhrhrh ... yeah, this rocks baby!
221 }
222 }
223 }
224
225 if ( mConfigCheckAreaOfTriangle ) {
226 if ( face.mNumIndices == 3 ) {
227 ai_real area = calculateAreaOfTriangle( face, mesh );
228 if ( area < 1e-6 ) {
229 if ( mConfigRemoveDegenerates ) {
230 remove_me[ a ] = true;
231 ++deg;
232 goto evil_jump_outside;
233 }
234
235 // todo: check for index which is corrupt.
236 }
237 }
238 }
239 }
240
241 // We need to update the primitive flags array of the mesh.
242 switch (face.mNumIndices)
243 {
244 case 1u:
245 mesh->mPrimitiveTypes |= aiPrimitiveType_POINT;
246 break;
247 case 2u:
248 mesh->mPrimitiveTypes |= aiPrimitiveType_LINE;
249 break;
250 case 3u:
251 mesh->mPrimitiveTypes |= aiPrimitiveType_TRIANGLE;
252 break;
253 default:
254 mesh->mPrimitiveTypes |= aiPrimitiveType_POLYGON;
255 break;
256 };
257 evil_jump_outside:
258 continue;
259 }
260
261 // If AI_CONFIG_PP_FD_REMOVE is true, remove degenerated faces from the import
262 if (mConfigRemoveDegenerates && deg) {
263 unsigned int n = 0;
264 for (unsigned int a = 0; a < mesh->mNumFaces; ++a)
265 {
266 aiFace& face_src = mesh->mFaces[a];
267 if (!remove_me[a]) {
268 aiFace& face_dest = mesh->mFaces[n++];
269
270 // Do a manual copy, keep the index array
271 face_dest.mNumIndices = face_src.mNumIndices;
272 face_dest.mIndices = face_src.mIndices;
273
274 if (&face_src != &face_dest) {
275 // clear source
276 face_src.mNumIndices = 0;
277 face_src.mIndices = nullptr;
278 }
279 }
280 else {
281 // Otherwise delete it if we don't need this face
282 delete[] face_src.mIndices;
283 face_src.mIndices = nullptr;
284 face_src.mNumIndices = 0;
285 }
286 }
287 // Just leave the rest of the array unreferenced, we don't care for now
288 mesh->mNumFaces = n;
289 if (!mesh->mNumFaces) {
290 //The whole mesh consists of degenerated faces
291 //signal upward, that this mesh should be deleted.
292 ASSIMP_LOG_DEBUG("FindDegeneratesProcess removed a mesh full of degenerated primitives");
293 return true;
294 }
295 }
296
297 if (deg && !DefaultLogger::isNullLogger()) {
298 ASSIMP_LOG_WARN_F( "Found ", deg, " degenerated primitives");
299 }
300 return false;
301 }
302