From 058f98a63658dc1a2579826ba167fd61bed1e21f Mon Sep 17 00:00:00 2001 From: sanine Date: Fri, 4 Mar 2022 10:47:15 -0600 Subject: add assimp submodule --- .../code/PostProcessing/TriangulateProcess.cpp | 628 +++++++++++++++++++++ 1 file changed, 628 insertions(+) create mode 100644 src/mesh/assimp-master/code/PostProcessing/TriangulateProcess.cpp (limited to 'src/mesh/assimp-master/code/PostProcessing/TriangulateProcess.cpp') diff --git a/src/mesh/assimp-master/code/PostProcessing/TriangulateProcess.cpp b/src/mesh/assimp-master/code/PostProcessing/TriangulateProcess.cpp new file mode 100644 index 0000000..a18bf1c --- /dev/null +++ b/src/mesh/assimp-master/code/PostProcessing/TriangulateProcess.cpp @@ -0,0 +1,628 @@ +/* +--------------------------------------------------------------------------- +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. +--------------------------------------------------------------------------- +*/ + +/** @file TriangulateProcess.cpp + * @brief Implementation of the post processing step to split up + * all faces with more than three indices into triangles. + * + * + * The triangulation algorithm will handle concave or convex polygons. + * Self-intersecting or non-planar polygons are not rejected, but + * they're probably not triangulated correctly. + * + * DEBUG SWITCHES - do not enable any of them in release builds: + * + * AI_BUILD_TRIANGULATE_COLOR_FACE_WINDING + * - generates vertex colors to represent the face winding order. + * the first vertex of a polygon becomes red, the last blue. + * AI_BUILD_TRIANGULATE_DEBUG_POLYS + * - dump all polygons and their triangulation sequences to + * a file + */ +#ifndef ASSIMP_BUILD_NO_TRIANGULATE_PROCESS + +#include "PostProcessing/TriangulateProcess.h" +#include "PostProcessing/ProcessHelper.h" +#include "Common/PolyTools.h" + +#include +#include + +//#define AI_BUILD_TRIANGULATE_COLOR_FACE_WINDING +//#define AI_BUILD_TRIANGULATE_DEBUG_POLYS + +#define POLY_GRID_Y 40 +#define POLY_GRID_X 70 +#define POLY_GRID_XPAD 20 +#define POLY_OUTPUT_FILE "assimp_polygons_debug.txt" + +using namespace Assimp; + +namespace { + + /** + * @brief Helper struct used to simplify NGON encoding functions. + */ + struct NGONEncoder { + NGONEncoder() : mLastNGONFirstIndex((unsigned int)-1) {} + + /** + * @brief Encode the current triangle, and make sure it is recognized as a triangle. + * + * This method will rotate indices in tri if needed in order to avoid tri to be considered + * part of the previous ngon. This method is to be used whenever you want to emit a real triangle, + * and make sure it is seen as a triangle. + * + * @param tri Triangle to encode. + */ + void ngonEncodeTriangle(aiFace * tri) { + ai_assert(tri->mNumIndices == 3); + + // Rotate indices in new triangle to avoid ngon encoding false ngons + // Otherwise, the new triangle would be considered part of the previous NGON. + if (isConsideredSameAsLastNgon(tri)) { + std::swap(tri->mIndices[0], tri->mIndices[2]); + std::swap(tri->mIndices[1], tri->mIndices[2]); + } + + mLastNGONFirstIndex = tri->mIndices[0]; + } + + /** + * @brief Encode a quad (2 triangles) in ngon encoding, and make sure they are seen as a single ngon. + * + * @param tri1 First quad triangle + * @param tri2 Second quad triangle + * + * @pre Triangles must be properly fanned from the most appropriate vertex. + */ + void ngonEncodeQuad(aiFace *tri1, aiFace *tri2) { + ai_assert(tri1->mNumIndices == 3); + ai_assert(tri2->mNumIndices == 3); + ai_assert(tri1->mIndices[0] == tri2->mIndices[0]); + + // If the selected fanning vertex is the same as the previously + // emitted ngon, we use the opposite vertex which also happens to work + // for tri-fanning a concave quad. + // ref: https://github.com/assimp/assimp/pull/3695#issuecomment-805999760 + if (isConsideredSameAsLastNgon(tri1)) { + // Right-rotate indices for tri1 (index 2 becomes the new fanning vertex) + std::swap(tri1->mIndices[0], tri1->mIndices[2]); + std::swap(tri1->mIndices[1], tri1->mIndices[2]); + + // Left-rotate indices for tri2 (index 2 becomes the new fanning vertex) + std::swap(tri2->mIndices[1], tri2->mIndices[2]); + std::swap(tri2->mIndices[0], tri2->mIndices[2]); + + ai_assert(tri1->mIndices[0] == tri2->mIndices[0]); + } + + mLastNGONFirstIndex = tri1->mIndices[0]; + } + + /** + * @brief Check whether this triangle would be considered part of the lastly emitted ngon or not. + * + * @param tri Current triangle. + * @return true If used as is, this triangle will be part of last ngon. + * @return false If used as is, this triangle is not considered part of the last ngon. + */ + bool isConsideredSameAsLastNgon(const aiFace * tri) const { + ai_assert(tri->mNumIndices == 3); + return tri->mIndices[0] == mLastNGONFirstIndex; + } + + private: + unsigned int mLastNGONFirstIndex; + }; + +} + + +// ------------------------------------------------------------------------------------------------ +// Constructor to be privately used by Importer +TriangulateProcess::TriangulateProcess() +{ + // nothing to do here +} + +// ------------------------------------------------------------------------------------------------ +// Destructor, private as well +TriangulateProcess::~TriangulateProcess() +{ + // nothing to do here +} + +// ------------------------------------------------------------------------------------------------ +// Returns whether the processing step is present in the given flag field. +bool TriangulateProcess::IsActive( unsigned int pFlags) const +{ + return (pFlags & aiProcess_Triangulate) != 0; +} + +// ------------------------------------------------------------------------------------------------ +// Executes the post processing step on the given imported data. +void TriangulateProcess::Execute( aiScene* pScene) +{ + ASSIMP_LOG_DEBUG("TriangulateProcess begin"); + + bool bHas = false; + for( unsigned int a = 0; a < pScene->mNumMeshes; a++) + { + if (pScene->mMeshes[ a ]) { + if ( TriangulateMesh( pScene->mMeshes[ a ] ) ) { + bHas = true; + } + } + } + if ( bHas ) { + ASSIMP_LOG_INFO( "TriangulateProcess finished. All polygons have been triangulated." ); + } else { + ASSIMP_LOG_DEBUG( "TriangulateProcess finished. There was nothing to be done." ); + } +} + +// ------------------------------------------------------------------------------------------------ +// Triangulates the given mesh. +bool TriangulateProcess::TriangulateMesh( aiMesh* pMesh) +{ + // Now we have aiMesh::mPrimitiveTypes, so this is only here for test cases + if (!pMesh->mPrimitiveTypes) { + bool bNeed = false; + + for( unsigned int a = 0; a < pMesh->mNumFaces; a++) { + const aiFace& face = pMesh->mFaces[a]; + + if( face.mNumIndices != 3) { + bNeed = true; + } + } + if (!bNeed) + return false; + } + else if (!(pMesh->mPrimitiveTypes & aiPrimitiveType_POLYGON)) { + return false; + } + + // Find out how many output faces we'll get + uint32_t numOut = 0, max_out = 0; + bool get_normals = true; + for( unsigned int a = 0; a < pMesh->mNumFaces; a++) { + aiFace& face = pMesh->mFaces[a]; + if (face.mNumIndices <= 4) { + get_normals = false; + } + if( face.mNumIndices <= 3) { + numOut++; + + } + else { + numOut += face.mNumIndices-2; + max_out = std::max(max_out,face.mNumIndices); + } + } + + // Just another check whether aiMesh::mPrimitiveTypes is correct + ai_assert(numOut != pMesh->mNumFaces); + + aiVector3D *nor_out = nullptr; + + // if we don't have normals yet, but expect them to be a cheap side + // product of triangulation anyway, allocate storage for them. + if (!pMesh->mNormals && get_normals) { + // XXX need a mechanism to inform the GenVertexNormals process to treat these normals as preprocessed per-face normals + // nor_out = pMesh->mNormals = new aiVector3D[pMesh->mNumVertices]; + } + + // the output mesh will contain triangles, but no polys anymore + pMesh->mPrimitiveTypes |= aiPrimitiveType_TRIANGLE; + pMesh->mPrimitiveTypes &= ~aiPrimitiveType_POLYGON; + + // The mesh becomes NGON encoded now, during the triangulation process. + pMesh->mPrimitiveTypes |= aiPrimitiveType_NGONEncodingFlag; + + aiFace* out = new aiFace[numOut](), *curOut = out; + std::vector temp_verts3d(max_out+2); /* temporary storage for vertices */ + std::vector temp_verts(max_out+2); + + NGONEncoder ngonEncoder; + + // Apply vertex colors to represent the face winding? +#ifdef AI_BUILD_TRIANGULATE_COLOR_FACE_WINDING + if (!pMesh->mColors[0]) + pMesh->mColors[0] = new aiColor4D[pMesh->mNumVertices]; + else + new(pMesh->mColors[0]) aiColor4D[pMesh->mNumVertices]; + + aiColor4D* clr = pMesh->mColors[0]; +#endif + +#ifdef AI_BUILD_TRIANGULATE_DEBUG_POLYS + FILE* fout = fopen(POLY_OUTPUT_FILE,"a"); +#endif + + const aiVector3D* verts = pMesh->mVertices; + + // use std::unique_ptr to avoid slow std::vector specialiations + std::unique_ptr done(new bool[max_out]); + for( unsigned int a = 0; a < pMesh->mNumFaces; a++) { + aiFace& face = pMesh->mFaces[a]; + + unsigned int* idx = face.mIndices; + int num = (int)face.mNumIndices, ear = 0, tmp, prev = num-1, next = 0, max = num; + + // Apply vertex colors to represent the face winding? +#ifdef AI_BUILD_TRIANGULATE_COLOR_FACE_WINDING + for (unsigned int i = 0; i < face.mNumIndices; ++i) { + aiColor4D& c = clr[idx[i]]; + c.r = (i+1) / (float)max; + c.b = 1.f - c.r; + } +#endif + + aiFace* const last_face = curOut; + + // if it's a simple point,line or triangle: just copy it + if( face.mNumIndices <= 3) + { + aiFace& nface = *curOut++; + nface.mNumIndices = face.mNumIndices; + nface.mIndices = face.mIndices; + face.mIndices = nullptr; + + // points and lines don't require ngon encoding (and are not supported either!) + if (nface.mNumIndices == 3) ngonEncoder.ngonEncodeTriangle(&nface); + + continue; + } + // optimized code for quadrilaterals + else if ( face.mNumIndices == 4) { + + // quads can have at maximum one concave vertex. Determine + // this vertex (if it exists) and start tri-fanning from + // it. + unsigned int start_vertex = 0; + for (unsigned int i = 0; i < 4; ++i) { + const aiVector3D& v0 = verts[face.mIndices[(i+3) % 4]]; + const aiVector3D& v1 = verts[face.mIndices[(i+2) % 4]]; + const aiVector3D& v2 = verts[face.mIndices[(i+1) % 4]]; + + const aiVector3D& v = verts[face.mIndices[i]]; + + aiVector3D left = (v0-v); + aiVector3D diag = (v1-v); + aiVector3D right = (v2-v); + + left.Normalize(); + diag.Normalize(); + right.Normalize(); + + const float angle = std::acos(left*diag) + std::acos(right*diag); + if (angle > AI_MATH_PI_F) { + // this is the concave point + start_vertex = i; + break; + } + } + + const unsigned int temp[] = {face.mIndices[0], face.mIndices[1], face.mIndices[2], face.mIndices[3]}; + + aiFace& nface = *curOut++; + nface.mNumIndices = 3; + nface.mIndices = face.mIndices; + + nface.mIndices[0] = temp[start_vertex]; + nface.mIndices[1] = temp[(start_vertex + 1) % 4]; + nface.mIndices[2] = temp[(start_vertex + 2) % 4]; + + aiFace& sface = *curOut++; + sface.mNumIndices = 3; + sface.mIndices = new unsigned int[3]; + + sface.mIndices[0] = temp[start_vertex]; + sface.mIndices[1] = temp[(start_vertex + 2) % 4]; + sface.mIndices[2] = temp[(start_vertex + 3) % 4]; + + // prevent double deletion of the indices field + face.mIndices = nullptr; + + ngonEncoder.ngonEncodeQuad(&nface, &sface); + + continue; + } + else + { + // A polygon with more than 3 vertices can be either concave or convex. + // Usually everything we're getting is convex and we could easily + // triangulate by tri-fanning. However, LightWave is probably the only + // modeling suite to make extensive use of highly concave, monster polygons ... + // so we need to apply the full 'ear cutting' algorithm to get it right. + + // REQUIREMENT: polygon is expected to be simple and *nearly* planar. + // We project it onto a plane to get a 2d triangle. + + // Collect all vertices of of the polygon. + for (tmp = 0; tmp < max; ++tmp) { + temp_verts3d[tmp] = verts[idx[tmp]]; + } + + // Get newell normal of the polygon. Store it for future use if it's a polygon-only mesh + aiVector3D n; + NewellNormal<3,3,3>(n,max,&temp_verts3d.front().x,&temp_verts3d.front().y,&temp_verts3d.front().z); + if (nor_out) { + for (tmp = 0; tmp < max; ++tmp) + nor_out[idx[tmp]] = n; + } + + // Select largest normal coordinate to ignore for projection + const float ax = (n.x>0 ? n.x : -n.x); + const float ay = (n.y>0 ? n.y : -n.y); + const float az = (n.z>0 ? n.z : -n.z); + + unsigned int ac = 0, bc = 1; /* no z coord. projection to xy */ + float inv = n.z; + if (ax > ay) { + if (ax > az) { /* no x coord. projection to yz */ + ac = 1; bc = 2; + inv = n.x; + } + } + else if (ay > az) { /* no y coord. projection to zy */ + ac = 2; bc = 0; + inv = n.y; + } + + // Swap projection axes to take the negated projection vector into account + if (inv < 0.f) { + std::swap(ac,bc); + } + + for (tmp =0; tmp < max; ++tmp) { + temp_verts[tmp].x = verts[idx[tmp]][ac]; + temp_verts[tmp].y = verts[idx[tmp]][bc]; + done[tmp] = false; + } + +#ifdef AI_BUILD_TRIANGULATE_DEBUG_POLYS + // plot the plane onto which we mapped the polygon to a 2D ASCII pic + aiVector2D bmin,bmax; + ArrayBounds(&temp_verts[0],max,bmin,bmax); + + char grid[POLY_GRID_Y][POLY_GRID_X+POLY_GRID_XPAD]; + std::fill_n((char*)grid,POLY_GRID_Y*(POLY_GRID_X+POLY_GRID_XPAD),' '); + + for (int i =0; i < max; ++i) { + const aiVector2D& v = (temp_verts[i] - bmin) / (bmax-bmin); + const size_t x = static_cast(v.x*(POLY_GRID_X-1)), y = static_cast(v.y*(POLY_GRID_Y-1)); + char* loc = grid[y]+x; + if (grid[y][x] != ' ') { + for(;*loc != ' '; ++loc); + *loc++ = '_'; + } + *(loc+::ai_snprintf(loc, POLY_GRID_XPAD,"%i",i)) = ' '; + } + + + for(size_t y = 0; y < POLY_GRID_Y; ++y) { + grid[y][POLY_GRID_X+POLY_GRID_XPAD-1] = '\0'; + fprintf(fout,"%s\n",grid[y]); + } + + fprintf(fout,"\ntriangulation sequence: "); +#endif + + // + // FIXME: currently this is the slow O(kn) variant with a worst case + // complexity of O(n^2) (I think). Can be done in O(n). + while (num > 3) { + + // Find the next ear of the polygon + int num_found = 0; + for (ear = next;;prev = ear,ear = next) { + + // break after we looped two times without a positive match + for (next=ear+1;done[(next>=max?next=0:next)];++next); + if (next < ear) { + if (++num_found == 2) { + break; + } + } + const aiVector2D* pnt1 = &temp_verts[ear], + *pnt0 = &temp_verts[prev], + *pnt2 = &temp_verts[next]; + + // Must be a convex point. Assuming ccw winding, it must be on the right of the line between p-1 and p+1. + if (OnLeftSideOfLine2D(*pnt0,*pnt2,*pnt1)) { + continue; + } + + // and no other point may be contained in this triangle + for ( tmp = 0; tmp < max; ++tmp) { + + // We need to compare the actual values because it's possible that multiple indexes in + // the polygon are referring to the same position. concave_polygon.obj is a sample + // + // FIXME: Use 'epsiloned' comparisons instead? Due to numeric inaccuracies in + // PointInTriangle() I'm guessing that it's actually possible to construct + // input data that would cause us to end up with no ears. The problem is, + // which epsilon? If we chose a too large value, we'd get wrong results + const aiVector2D& vtmp = temp_verts[tmp]; + if ( vtmp != *pnt1 && vtmp != *pnt2 && vtmp != *pnt0 && PointInTriangle2D(*pnt0,*pnt1,*pnt2,vtmp)) { + break; + } + } + if (tmp != max) { + continue; + } + + // this vertex is an ear + break; + } + if (num_found == 2) { + + // Due to the 'two ear theorem', every simple polygon with more than three points must + // have 2 'ears'. Here's definitely something wrong ... but we don't give up yet. + // + + // Instead we're continuing with the standard tri-fanning algorithm which we'd + // use if we had only convex polygons. That's life. + ASSIMP_LOG_ERROR("Failed to triangulate polygon (no ear found). Probably not a simple polygon?"); + +#ifdef AI_BUILD_TRIANGULATE_DEBUG_POLYS + fprintf(fout,"critical error here, no ear found! "); +#endif + num = 0; + break; + + /*curOut -= (max-num); // undo all previous work + for (tmp = 0; tmp < max-2; ++tmp) { + aiFace& nface = *curOut++; + + nface.mNumIndices = 3; + if (!nface.mIndices) + nface.mIndices = new unsigned int[3]; + + nface.mIndices[0] = 0; + nface.mIndices[1] = tmp+1; + nface.mIndices[2] = tmp+2; + + } + num = 0; + break;*/ + } + + aiFace& nface = *curOut++; + nface.mNumIndices = 3; + + if (!nface.mIndices) { + nface.mIndices = new unsigned int[3]; + } + + // setup indices for the new triangle ... + nface.mIndices[0] = prev; + nface.mIndices[1] = ear; + nface.mIndices[2] = next; + + // exclude the ear from most further processing + done[ear] = true; + --num; + } + if (num > 0) { + // We have three indices forming the last 'ear' remaining. Collect them. + aiFace& nface = *curOut++; + nface.mNumIndices = 3; + if (!nface.mIndices) { + nface.mIndices = new unsigned int[3]; + } + + for (tmp = 0; done[tmp]; ++tmp); + nface.mIndices[0] = tmp; + + for (++tmp; done[tmp]; ++tmp); + nface.mIndices[1] = tmp; + + for (++tmp; done[tmp]; ++tmp); + nface.mIndices[2] = tmp; + + } + } + +#ifdef AI_BUILD_TRIANGULATE_DEBUG_POLYS + + for(aiFace* f = last_face; f != curOut; ++f) { + unsigned int* i = f->mIndices; + fprintf(fout," (%i %i %i)",i[0],i[1],i[2]); + } + + fprintf(fout,"\n*********************************************************************\n"); + fflush(fout); + +#endif + + for(aiFace* f = last_face; f != curOut; ) { + unsigned int* i = f->mIndices; + + // drop dumb 0-area triangles - deactivated for now: + //FindDegenerates post processing step can do the same thing + //if (std::fabs(GetArea2D(temp_verts[i[0]],temp_verts[i[1]],temp_verts[i[2]])) < 1e-5f) { + // ASSIMP_LOG_VERBOSE_DEBUG("Dropping triangle with area 0"); + // --curOut; + + // delete[] f->mIndices; + // f->mIndices = nullptr; + + // for(aiFace* ff = f; ff != curOut; ++ff) { + // ff->mNumIndices = (ff+1)->mNumIndices; + // ff->mIndices = (ff+1)->mIndices; + // (ff+1)->mIndices = nullptr; + // } + // continue; + //} + + i[0] = idx[i[0]]; + i[1] = idx[i[1]]; + i[2] = idx[i[2]]; + + // IMPROVEMENT: Polygons are not supported yet by this ngon encoding + triangulation step. + // So we encode polygons as regular triangles. No way to reconstruct the original + // polygon in this case. + ngonEncoder.ngonEncodeTriangle(f); + ++f; + } + + delete[] face.mIndices; + face.mIndices = nullptr; + } + +#ifdef AI_BUILD_TRIANGULATE_DEBUG_POLYS + fclose(fout); +#endif + + // kill the old faces + delete [] pMesh->mFaces; + + // ... and store the new ones + pMesh->mFaces = out; + pMesh->mNumFaces = (unsigned int)(curOut-out); /* not necessarily equal to numOut */ + return true; +} + +#endif // !! ASSIMP_BUILD_NO_TRIANGULATE_PROCESS -- cgit v1.2.1