SaraP
cbec90699f
- creato il progetto in Visual Studio per compilare come libreria statica - modifiche al codice originale per integrarlo nelle nostre librerie.
388 lines
18 KiB
C++
388 lines
18 KiB
C++
/*****************************************************************************/
|
|
/* */
|
|
/* 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 <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <math.h>
|
|
#include <assert.h>
|
|
|
|
/* */
|
|
/* get my header files */
|
|
/* */
|
|
#include "fpkernel.h"
|
|
#include "martin.h"
|
|
#include "defs.h"
|
|
#include "header.h"
|
|
|
|
#ifndef NO_CPUTIME
|
|
#include <sys/time.h>
|
|
#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;
|
|
}
|