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 TriangulateProcess.cpp
44 * @brief Implementation of the post processing step to split up
45 * all faces with more than three indices into triangles.
46 *
47 *
48 * The triangulation algorithm will handle concave or convex polygons.
49 * Self-intersecting or non-planar polygons are not rejected, but
50 * they're probably not triangulated correctly.
51 *
52 * DEBUG SWITCHES - do not enable any of them in release builds:
53 *
54 * AI_BUILD_TRIANGULATE_COLOR_FACE_WINDING
55 * - generates vertex colors to represent the face winding order.
56 * the first vertex of a polygon becomes red, the last blue.
57 * AI_BUILD_TRIANGULATE_DEBUG_POLYS
58 * - dump all polygons and their triangulation sequences to
59 * a file
60 */
61#ifndef ASSIMP_BUILD_NO_TRIANGULATE_PROCESS
62#include "TriangulateProcess.h"
63#include "ProcessHelper.h"
64#include "PolyTools.h"
65#include <memory>
66
67//#define AI_BUILD_TRIANGULATE_COLOR_FACE_WINDING
68//#define AI_BUILD_TRIANGULATE_DEBUG_POLYS
69
70#define POLY_GRID_Y 40
71#define POLY_GRID_X 70
72#define POLY_GRID_XPAD 20
73#define POLY_OUTPUT_FILE "assimp_polygons_debug.txt"
74
75using namespace Assimp;
76
77// ------------------------------------------------------------------------------------------------
78// Constructor to be privately used by Importer
79TriangulateProcess::TriangulateProcess()
80{
81 // nothing to do here
82}
83
84// ------------------------------------------------------------------------------------------------
85// Destructor, private as well
86TriangulateProcess::~TriangulateProcess()
87{
88 // nothing to do here
89}
90
91// ------------------------------------------------------------------------------------------------
92// Returns whether the processing step is present in the given flag field.
93bool TriangulateProcess::IsActive( unsigned int pFlags) const
94{
95 return (pFlags & aiProcess_Triangulate) != 0;
96}
97
98// ------------------------------------------------------------------------------------------------
99// Executes the post processing step on the given imported data.
100void TriangulateProcess::Execute( aiScene* pScene)
101{
102 DefaultLogger::get()->debug("TriangulateProcess begin");
103
104 bool bHas = false;
105 for( unsigned int a = 0; a < pScene->mNumMeshes; a++)
106 {
107 if ( TriangulateMesh( pScene->mMeshes[ a ] ) ) {
108 bHas = true;
109 }
110 }
111 if ( bHas ) {
112 DefaultLogger::get()->info( "TriangulateProcess finished. All polygons have been triangulated." );
113 } else {
114 DefaultLogger::get()->debug( "TriangulateProcess finished. There was nothing to be done." );
115 }
116}
117
118
119// ------------------------------------------------------------------------------------------------
120// Triangulates the given mesh.
121bool TriangulateProcess::TriangulateMesh( aiMesh* pMesh)
122{
123 // Now we have aiMesh::mPrimitiveTypes, so this is only here for test cases
124 if (!pMesh->mPrimitiveTypes) {
125 bool bNeed = false;
126
127 for( unsigned int a = 0; a < pMesh->mNumFaces; a++) {
128 const aiFace& face = pMesh->mFaces[a];
129
130 if( face.mNumIndices != 3) {
131 bNeed = true;
132 }
133 }
134 if (!bNeed)
135 return false;
136 }
137 else if (!(pMesh->mPrimitiveTypes & aiPrimitiveType_POLYGON)) {
138 return false;
139 }
140
141 // Find out how many output faces we'll get
142 unsigned int numOut = 0, max_out = 0;
143 bool get_normals = true;
144 for( unsigned int a = 0; a < pMesh->mNumFaces; a++) {
145 aiFace& face = pMesh->mFaces[a];
146 if (face.mNumIndices <= 4) {
147 get_normals = false;
148 }
149 if( face.mNumIndices <= 3) {
150 numOut++;
151
152 }
153 else {
154 numOut += face.mNumIndices-2;
155 max_out = std::max(max_out,face.mNumIndices);
156 }
157 }
158
159 // Just another check whether aiMesh::mPrimitiveTypes is correct
160 ai_assert(numOut != pMesh->mNumFaces);
161
162 aiVector3D* nor_out = NULL;
163
164 // if we don't have normals yet, but expect them to be a cheap side
165 // product of triangulation anyway, allocate storage for them.
166 if (!pMesh->mNormals && get_normals) {
167 // XXX need a mechanism to inform the GenVertexNormals process to treat these normals as preprocessed per-face normals
168 // nor_out = pMesh->mNormals = new aiVector3D[pMesh->mNumVertices];
169 }
170
171 // the output mesh will contain triangles, but no polys anymore
172 pMesh->mPrimitiveTypes |= aiPrimitiveType_TRIANGLE;
173 pMesh->mPrimitiveTypes &= ~aiPrimitiveType_POLYGON;
174
175 aiFace* out = new aiFace[numOut](), *curOut = out;
176 std::vector<aiVector3D> temp_verts3d(max_out+2); /* temporary storage for vertices */
177 std::vector<aiVector2D> temp_verts(max_out+2);
178
179 // Apply vertex colors to represent the face winding?
180#ifdef AI_BUILD_TRIANGULATE_COLOR_FACE_WINDING
181 if (!pMesh->mColors[0])
182 pMesh->mColors[0] = new aiColor4D[pMesh->mNumVertices];
183 else
184 new(pMesh->mColors[0]) aiColor4D[pMesh->mNumVertices];
185
186 aiColor4D* clr = pMesh->mColors[0];
187#endif
188
189#ifdef AI_BUILD_TRIANGULATE_DEBUG_POLYS
190 FILE* fout = fopen(POLY_OUTPUT_FILE,"a");
191#endif
192
193 const aiVector3D* verts = pMesh->mVertices;
194
195 // use std::unique_ptr to avoid slow std::vector<bool> specialiations
196 std::unique_ptr<bool[]> done(new bool[max_out]);
197 for( unsigned int a = 0; a < pMesh->mNumFaces; a++) {
198 aiFace& face = pMesh->mFaces[a];
199
200 unsigned int* idx = face.mIndices;
201 int num = (int)face.mNumIndices, ear = 0, tmp, prev = num-1, next = 0, max = num;
202
203 // Apply vertex colors to represent the face winding?
204#ifdef AI_BUILD_TRIANGULATE_COLOR_FACE_WINDING
205 for (unsigned int i = 0; i < face.mNumIndices; ++i) {
206 aiColor4D& c = clr[idx[i]];
207 c.r = (i+1) / (float)max;
208 c.b = 1.f - c.r;
209 }
210#endif
211
212 aiFace* const last_face = curOut;
213
214 // if it's a simple point,line or triangle: just copy it
215 if( face.mNumIndices <= 3)
216 {
217 aiFace& nface = *curOut++;
218 nface.mNumIndices = face.mNumIndices;
219 nface.mIndices = face.mIndices;
220
221 face.mIndices = NULL;
222 continue;
223 }
224 // optimized code for quadrilaterals
225 else if ( face.mNumIndices == 4) {
226
227 // quads can have at maximum one concave vertex. Determine
228 // this vertex (if it exists) and start tri-fanning from
229 // it.
230 unsigned int start_vertex = 0;
231 for (unsigned int i = 0; i < 4; ++i) {
232 const aiVector3D& v0 = verts[face.mIndices[(i+3) % 4]];
233 const aiVector3D& v1 = verts[face.mIndices[(i+2) % 4]];
234 const aiVector3D& v2 = verts[face.mIndices[(i+1) % 4]];
235
236 const aiVector3D& v = verts[face.mIndices[i]];
237
238 aiVector3D left = (v0-v);
239 aiVector3D diag = (v1-v);
240 aiVector3D right = (v2-v);
241
242 left.Normalize();
243 diag.Normalize();
244 right.Normalize();
245
246 const float angle = std::acos(left*diag) + std::acos(right*diag);
247 if (angle > AI_MATH_PI_F) {
248 // this is the concave point
249 start_vertex = i;
250 break;
251 }
252 }
253
254 const unsigned int temp[] = {face.mIndices[0], face.mIndices[1], face.mIndices[2], face.mIndices[3]};
255
256 aiFace& nface = *curOut++;
257 nface.mNumIndices = 3;
258 nface.mIndices = face.mIndices;
259
260 nface.mIndices[0] = temp[start_vertex];
261 nface.mIndices[1] = temp[(start_vertex + 1) % 4];
262 nface.mIndices[2] = temp[(start_vertex + 2) % 4];
263
264 aiFace& sface = *curOut++;
265 sface.mNumIndices = 3;
266 sface.mIndices = new unsigned int[3];
267
268 sface.mIndices[0] = temp[start_vertex];
269 sface.mIndices[1] = temp[(start_vertex + 2) % 4];
270 sface.mIndices[2] = temp[(start_vertex + 3) % 4];
271
272 // prevent double deletion of the indices field
273 face.mIndices = NULL;
274 continue;
275 }
276 else
277 {
278 // A polygon with more than 3 vertices can be either concave or convex.
279 // Usually everything we're getting is convex and we could easily
280 // triangulate by tri-fanning. However, LightWave is probably the only
281 // modeling suite to make extensive use of highly concave, monster polygons ...
282 // so we need to apply the full 'ear cutting' algorithm to get it right.
283
284 // RERQUIREMENT: polygon is expected to be simple and *nearly* planar.
285 // We project it onto a plane to get a 2d triangle.
286
287 // Collect all vertices of of the polygon.
288 for (tmp = 0; tmp < max; ++tmp) {
289 temp_verts3d[tmp] = verts[idx[tmp]];
290 }
291
292 // Get newell normal of the polygon. Store it for future use if it's a polygon-only mesh
293 aiVector3D n;
294 NewellNormal<3,3,3>(n,max,&temp_verts3d.front().x,&temp_verts3d.front().y,&temp_verts3d.front().z);
295 if (nor_out) {
296 for (tmp = 0; tmp < max; ++tmp)
297 nor_out[idx[tmp]] = n;
298 }
299
300 // Select largest normal coordinate to ignore for projection
301 const float ax = (n.x>0 ? n.x : -n.x);
302 const float ay = (n.y>0 ? n.y : -n.y);
303 const float az = (n.z>0 ? n.z : -n.z);
304
305 unsigned int ac = 0, bc = 1; /* no z coord. projection to xy */
306 float inv = n.z;
307 if (ax > ay) {
308 if (ax > az) { /* no x coord. projection to yz */
309 ac = 1; bc = 2;
310 inv = n.x;
311 }
312 }
313 else if (ay > az) { /* no y coord. projection to zy */
314 ac = 2; bc = 0;
315 inv = n.y;
316 }
317
318 // Swap projection axes to take the negated projection vector into account
319 if (inv < 0.f) {
320 std::swap(ac,bc);
321 }
322
323 for (tmp =0; tmp < max; ++tmp) {
324 temp_verts[tmp].x = verts[idx[tmp]][ac];
325 temp_verts[tmp].y = verts[idx[tmp]][bc];
326 done[tmp] = false;
327 }
328
329#ifdef AI_BUILD_TRIANGULATE_DEBUG_POLYS
330 // plot the plane onto which we mapped the polygon to a 2D ASCII pic
331 aiVector2D bmin,bmax;
332 ArrayBounds(&temp_verts[0],max,bmin,bmax);
333
334 char grid[POLY_GRID_Y][POLY_GRID_X+POLY_GRID_XPAD];
335 std::fill_n((char*)grid,POLY_GRID_Y*(POLY_GRID_X+POLY_GRID_XPAD),' ');
336
337 for (int i =0; i < max; ++i) {
338 const aiVector2D& v = (temp_verts[i] - bmin) / (bmax-bmin);
339 const size_t x = static_cast<size_t>(v.x*(POLY_GRID_X-1)), y = static_cast<size_t>(v.y*(POLY_GRID_Y-1));
340 char* loc = grid[y]+x;
341 if (grid[y][x] != ' ') {
342 for(;*loc != ' '; ++loc);
343 *loc++ = '_';
344 }
345 *(loc+::ai_snprintf(loc, POLY_GRID_XPAD,"%i",i)) = ' ';
346 }
347
348
349 for(size_t y = 0; y < POLY_GRID_Y; ++y) {
350 grid[y][POLY_GRID_X+POLY_GRID_XPAD-1] = '\0';
351 fprintf(fout,"%s\n",grid[y]);
352 }
353
354 fprintf(fout,"\ntriangulation sequence: ");
355#endif
356
357 //
358 // FIXME: currently this is the slow O(kn) variant with a worst case
359 // complexity of O(n^2) (I think). Can be done in O(n).
360 while (num > 3) {
361
362 // Find the next ear of the polygon
363 int num_found = 0;
364 for (ear = next;;prev = ear,ear = next) {
365
366 // break after we looped two times without a positive match
367 for (next=ear+1;done[(next>=max?next=0:next)];++next);
368 if (next < ear) {
369 if (++num_found == 2) {
370 break;
371 }
372 }
373 const aiVector2D* pnt1 = &temp_verts[ear],
374 *pnt0 = &temp_verts[prev],
375 *pnt2 = &temp_verts[next];
376
377 // Must be a convex point. Assuming ccw winding, it must be on the right of the line between p-1 and p+1.
378 if (OnLeftSideOfLine2D(*pnt0,*pnt2,*pnt1)) {
379 continue;
380 }
381
382 // and no other point may be contained in this triangle
383 for ( tmp = 0; tmp < max; ++tmp) {
384
385 // We need to compare the actual values because it's possible that multiple indexes in
386 // the polygon are referring to the same position. concave_polygon.obj is a sample
387 //
388 // FIXME: Use 'epsiloned' comparisons instead? Due to numeric inaccuracies in
389 // PointInTriangle() I'm guessing that it's actually possible to construct
390 // input data that would cause us to end up with no ears. The problem is,
391 // which epsilon? If we chose a too large value, we'd get wrong results
392 const aiVector2D& vtmp = temp_verts[tmp];
393 if ( vtmp != *pnt1 && vtmp != *pnt2 && vtmp != *pnt0 && PointInTriangle2D(*pnt0,*pnt1,*pnt2,vtmp)) {
394 break;
395 }
396 }
397 if (tmp != max) {
398 continue;
399 }
400
401 // this vertex is an ear
402 break;
403 }
404 if (num_found == 2) {
405
406 // Due to the 'two ear theorem', every simple polygon with more than three points must
407 // have 2 'ears'. Here's definitely something wrong ... but we don't give up yet.
408 //
409
410 // Instead we're continuing with the standard tri-fanning algorithm which we'd
411 // use if we had only convex polygons. That's life.
412 DefaultLogger::get()->error("Failed to triangulate polygon (no ear found). Probably not a simple polygon?");
413
414#ifdef AI_BUILD_TRIANGULATE_DEBUG_POLYS
415 fprintf(fout,"critical error here, no ear found! ");
416#endif
417 num = 0;
418 break;
419
420 curOut -= (max-num); /* undo all previous work */
421 for (tmp = 0; tmp < max-2; ++tmp) {
422 aiFace& nface = *curOut++;
423
424 nface.mNumIndices = 3;
425 if (!nface.mIndices)
426 nface.mIndices = new unsigned int[3];
427
428 nface.mIndices[0] = 0;
429 nface.mIndices[1] = tmp+1;
430 nface.mIndices[2] = tmp+2;
431
432 }
433 num = 0;
434 break;
435 }
436
437 aiFace& nface = *curOut++;
438 nface.mNumIndices = 3;
439
440 if (!nface.mIndices) {
441 nface.mIndices = new unsigned int[3];
442 }
443
444 // setup indices for the new triangle ...
445 nface.mIndices[0] = prev;
446 nface.mIndices[1] = ear;
447 nface.mIndices[2] = next;
448
449 // exclude the ear from most further processing
450 done[ear] = true;
451 --num;
452 }
453 if (num > 0) {
454 // We have three indices forming the last 'ear' remaining. Collect them.
455 aiFace& nface = *curOut++;
456 nface.mNumIndices = 3;
457 if (!nface.mIndices) {
458 nface.mIndices = new unsigned int[3];
459 }
460
461 for (tmp = 0; done[tmp]; ++tmp);
462 nface.mIndices[0] = tmp;
463
464 for (++tmp; done[tmp]; ++tmp);
465 nface.mIndices[1] = tmp;
466
467 for (++tmp; done[tmp]; ++tmp);
468 nface.mIndices[2] = tmp;
469
470 }
471 }
472
473#ifdef AI_BUILD_TRIANGULATE_DEBUG_POLYS
474
475 for(aiFace* f = last_face; f != curOut; ++f) {
476 unsigned int* i = f->mIndices;
477 fprintf(fout," (%i %i %i)",i[0],i[1],i[2]);
478 }
479
480 fprintf(fout,"\n*********************************************************************\n");
481 fflush(fout);
482
483#endif
484
485 for(aiFace* f = last_face; f != curOut; ) {
486 unsigned int* i = f->mIndices;
487
488 // drop dumb 0-area triangles
489 if (std::fabs(GetArea2D(temp_verts[i[0]],temp_verts[i[1]],temp_verts[i[2]])) < 1e-5f) {
490 DefaultLogger::get()->debug("Dropping triangle with area 0");
491 --curOut;
492
493 delete[] f->mIndices;
494 f->mIndices = NULL;
495
496 for(aiFace* ff = f; ff != curOut; ++ff) {
497 ff->mNumIndices = (ff+1)->mNumIndices;
498 ff->mIndices = (ff+1)->mIndices;
499 (ff+1)->mIndices = NULL;
500 }
501 continue;
502 }
503
504 i[0] = idx[i[0]];
505 i[1] = idx[i[1]];
506 i[2] = idx[i[2]];
507 ++f;
508 }
509
510 delete[] face.mIndices;
511 face.mIndices = NULL;
512 }
513
514#ifdef AI_BUILD_TRIANGULATE_DEBUG_POLYS
515 fclose(fout);
516#endif
517
518 // kill the old faces
519 delete [] pMesh->mFaces;
520
521 // ... and store the new ones
522 pMesh->mFaces = out;
523 pMesh->mNumFaces = (unsigned int)(curOut-out); /* not necessarily equal to numOut */
524 return true;
525}
526
527#endif // !! ASSIMP_BUILD_NO_TRIANGULATE_PROCESS
528