/*****************************************************************************/ /* */ /* F I S T : Fast, Industrial-Strength Triangulation */ /* */ /*****************************************************************************/ /* */ /* (C) Martin Held */ /* (C) Universitaet Salzburg, Salzburg, Austria */ /* */ /* This code is not in the public domain. All rights reserved! Please make */ /* sure to read the full copyright statement contained in api_functions.cpp. */ /* */ /*****************************************************************************/ /* */ /* get standard libraries */ /* */ #include #include #include #include /* */ /* get my header files */ /* */ #include "fpkernel.h" #include "martin.h" #include "defs.h" #include "header.h" #ifndef NO_CPUTIME #include #endif /* */ /* function prototypes of functions provided in this file */ /* */ void Triangulate(global_struct *all); #define Bell '\007' /* */ /* this subroutine drives the computation of the triangulation of the faces */ /* of a polyhedron. all loops of the polyhedral faces are referenced via the */ /* array loops[0,..,num_loops-1], for a total of num_loops-many loops. the */ /* number of loops of face i is stored in faces[i] (0 <= i <= num_faces). */ /* we assume that all loops for all faces are stored consecutively in the */ /* array loops[]. that is, we assume that the loops for face i are stored */ /* in loops[i1,..,i2-1], with */ /* i1 = 0 + faces[0] + faces[1] + ... + faces[i-1], and with */ /* i2 = i1 + faces[i]. */ /* */ /* currently, FIST can read 3D data only in the .obj format, which does not */ /* support multiply-connected faces. thus, I have introduced an additional */ /* key, "H", in order to be able to encode multiply-connected faces in the */ /* .obj format. see ReadPolyhedron() in io.c. if Triangulate() were to be */ /* called from a user's application program then it is the responsibility */ /* of this application program to initialize all arrays appropriately. */ /* */ void Triangulate(global_struct *all) { vertexdef * vert = &all->c_vertex; listdef *list = &all->c_list; eardef *ear = &all->c_ear; datadef *data = &all->c_data; griddef *grid = &all->c_grid; rt_options *rt_opt = &all->rt_opt; heapdef *hp; #ifdef PARTITION_FIST all->partition_mode = false; hp = &all->c_heap[0]; #else hp = &all->c_heap; #endif int removed, i, j, i1, i2, k, k1, k2, num_reflex; boolean got_it; list_ind ind; if ((vert->num_vertices <= 0) && rt_opt->verbose) { FIST_Warning("Triangulate() - nothing to triangulate!\n"); return; } if (!rt_opt->quiet) { printf("%c\n", Bell); printf("%c\n", Bell); printf("%c\n", Bell); fflush(stdout); } #ifndef NO_CPUTIME if (rt_opt->time) gettimeofday(&all->start, NULL); #endif /* */ /* initialize storage for the output data. some of these arrays may get */ /* re-allocated later on. */ /* */ // MODIF : alloco sin da subito lo spazio necessario per evitare riallocazioni dell'array //InitTriangles(vert, list->num_loops); InitTriangles(vert, list->max_num_list); InitGroupTriangles(vert); /* */ /* let the user call some application-specific function */ /* */ ExtApplFuncNewPoly; /* */ /* process the polygonal faces of the polyhedron. for every face, we */ /* check whether it is a triangle or a quadrangle in order to weed out */ /* simple cases which do not require the full triangulation algorithm */ /* */ i1 = 0; i2 = 0; k1 = 0; for (k = 0; k < vert->num_groups; ++k) { /* */ /* for all face groups of the .obj model */ /* */ k2 = vert->groups[k]; for (j = k1; j < k2; ++j) { /* */ /* for all faces of this group. */ /* */ all->ccw_loop = true; all->done = false; i2 = i1 + list->faces[j]; if ((list->faces[j] > 1) || !SimpleFace(all, list->loops[i1], ear->ears_fancy)) { /* */ /* this face has faces[j] many loops[i1,i2-1]. in any case, it */ /* is not a triangle or a quadrangle. */ /* */ ear->tri_color = TriCvxColor; /* likely, it is a convex face */ /* */ /* let the user call some application-specific function */ /* */ ExtApplFuncNewFace; /* */ /* project the polygonal face onto a plane */ /* */ ProjectFace(all, i1, i2); /* */ /* sort the points of this face in lexicographic order and */ /* discard duplicates */ /* */ CleanPolyhedralFace(all, i1, i2, &removed); #ifdef INFO if (rt_opt->verbose && (removed > 0)) fprintf(stderr, "Triangulate() - %d duplicate points removed for face %d!\n", removed, i1); #endif /* */ /* compute the bounding box of the polygon(s), and scale the */ /* 2D data if requested by the user. */ /* */ SetBoundingBox(data, &all->bb_min, &all->bb_max); if (rt_opt->scale_data) ScaleData(all); /* */ /* determine the orientation of the polygon; the default */ /* orientation is CCW for the outer polygon */ /* */ if (list->faces[j] == 1) DetermineOrientation(all, list->loops[i1]); else AdjustOrientation(all, i1, i2); if (list->faces[j] > 1) BuildGrid(all, i1, i2); else grid->no_grid_yet = true; /* */ /* mark those vertices whose interior angle is convex */ /* */ num_reflex = 0; for (i = i1; i < i2; ++i) { ClassifyAngles(all, list->loops[i], &num_reflex); } /* */ /* link the holes with the outer boundary by means of "bridges" */ /* */ if (list->faces[j] > 1) { assert(num_reflex > 0); ConstructBridges(all, i1, i2); } /* */ /* put all ears into a circular linked list */ /* */ ResetPolyList(list, list->loops[i1]); SetReflexNumber(all, num_reflex); if (num_reflex > 0) { BuildBuckets(all, list->loops[i1]); } else { all->is_convex_face = true; SetConvexityStatus(ear, true); } if (ear->ears_fancy) BuildPntsGrid(all, i1); if (rt_opt->keep_convex && all->is_convex_face) { /* */ /* this is a convex face, and we were told not to triangulate */ /* convex faces */ /* */ StoreConvexLoop(all, i1); all->done = true; } else { ClassifyEars(all, list->loops[i1]); all->done = false; if (!all->is_convex_face) ++vert->num_concave_loops; } /* */ /* let the user call some application-specific function */ /* */ ExtApplFuncBeforeTriangulation; /* */ /* triangulate the polygon */ /* */ while (!all->done) { if (!ClipEar(all, hp, &all->done)) { if (all->reset) { #ifdef INFO if (rt_opt->verbose) { FIST_Warning("Triangulate() - no further ear to clip!\n"); FIST_Warning("Triangulate() - not a simple polygon, isn't it?\n"); } #endif ind = GetNode(list); ResetPolyList(list, ind); list->loops[i1] = ind; if (Desperate(all, hp, ind, i1, &all->done)) { /* */ /* let the user call some application-specific */ /* function */ /* */ ExtApplFuncDesperate3D; #ifdef INFO if (rt_opt->verbose) FIST_Warning("Triangulate() - let's hope for the best\n"); #endif if (!LetsHope(all, hp, ind)) { /* */ /* let the user call some application-specific */ /* function */ /* */ ExtApplFuncReligious3D; #ifdef INFO FIST_Warning("Triangulate() - sorry, I can't do it!\n"); FIST_Warning("Triangulate() - ask a triangulation wizard, or clean-up your polyhedron!\n"); #endif return; } } else { all->reset = false; } } else { /* */ /* try again from scratch */ /* */ all->troubles = true; #ifdef INFO if (rt_opt->verbose) FIST_Warning("Triangulate() - re-classifying the ears!\n"); #endif ind = GetNode(list); ResetPolyList(list, ind); ClassifyEars(all, ind); all->reset = true; /* */ /* let the user call some application-specific function */ /* */ ExtApplFuncRestart3D; } } else { all->reset = false; } if (all->done) { /* */ /* let the user call some application-specific function */ /* */ ExtApplFuncDoneOneChain3D; ind = GetNextChain(list, &got_it); if (got_it) { /* */ /* at some point of the triangulation, we could not */ /* find any ear and the polygon was split into two */ /* parts. now we have to handle (one of) the remaining */ /* parts. */ /* */ ResetPolyList(list, ind); list->loops[i1] = ind; grid->no_grid_yet = true; BuildBuckets(all, list->loops[i1]); if (ear->ears_fancy) BuildPntsGrid(all, i1); ResetEarStatus(ear); ClassifyEars(all, ind); all->reset = false; all->done = false; /* */ /* let the user call some application-specific */ /* function */ /* */ ExtApplFuncNextChain3D; } } } } /* one face has been handled */ /* */ /* let the user call some application-specific function */ /* */ ExtApplFuncDoneOneFace; i1 = i2; } /* end_of_loop over all faces of this group */ /* */ /* one entire group of faces has been handled. */ /* */ k1 = k2; StoreGroupData(vert); /* */ /* let the user call some application-specific function */ /* */ ExtApplFuncDoneOneGroup; } if (rt_opt->do_quads) { /* */ /* pair up triangles such that they form quads; this disregards any */ /* group statements in the input .obj file! */ /* */ DetermineQuads(all); } #ifndef NO_CPUTIME if (rt_opt->time) { gettimeofday(&all->end, NULL); all->cpu_time = elapsed(all); } #endif if (!rt_opt->quiet) { printf("%c\n", Bell); printf("%c\n", Bell); printf("%c\n", Bell); fflush(stdout); } if (rt_opt->verbose) { fprintf(stdout, "\n...writing the output data: "); fflush(stdout); } if (rt_opt->write_geom) WriteGeomOutput(all); if (rt_opt->write_tri) WriteFaces(all, rt_opt->tri_file); if (rt_opt->verbose) fprintf(stdout, "done!\n"); /* */ /* let the user call some application-specific function */ /* */ ExtApplFuncFinished3D; if (!rt_opt->quiet) { if (all->troubles) printf("\n\nTriangulation completed!\n"); else printf("\n\nTriangulation successfully completed!\n"); } return; }