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