SaraP
cbec90699f
- creato il progetto in Visual Studio per compilare come libreria statica - modifiche al codice originale per integrarlo nelle nostre librerie.
587 lines
22 KiB
C++
587 lines
22 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 <limits.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
|
|
|
|
#ifdef PARTITION_FIST
|
|
#define PARALLEL_MINIMUM 1000
|
|
#endif
|
|
|
|
/* */
|
|
/* function prototypes of functions provided in this file */
|
|
/* */
|
|
void Compute(global_struct *all);
|
|
void StatisticsFIST(global_struct *all);
|
|
void ResetAll(global_struct *all);
|
|
|
|
/* */
|
|
/* this subroutine drives the computation of the triangulation of a polygon. */
|
|
/* the polygon has to be planar but may contain multiple loops. all loops of */
|
|
/* the polygon are referenced via the array loops[0,..,num_loops-1], for a */
|
|
/* total of num_loops loops. */
|
|
/* */
|
|
/* if Compute() were to be called from a user's application program then it */
|
|
/* is the responsibility of this application program to initialize all */
|
|
/* arrays appropriately. see ReadPolygon() in io_2D.c, or ReadDXFFile() in */
|
|
/* io_dxf.c. */
|
|
/* */
|
|
void Compute(global_struct *all)
|
|
{
|
|
vertexdef *vert = &all->c_vertex;
|
|
listdef *list = &all->c_list;
|
|
datadef *data = &all->c_data;
|
|
griddef *grid = &all->c_grid;
|
|
eardef *ear = &all->c_ear;
|
|
heapdef *hp;
|
|
rt_options *rt_opt = &all->rt_opt;
|
|
int removed, i, num_reflex;
|
|
boolean got_it;
|
|
list_ind ind;
|
|
|
|
#ifdef PARTITION_FIST
|
|
hp = &all->c_heap[0];
|
|
#else
|
|
hp = &all->c_heap;
|
|
#endif
|
|
|
|
if ((data->num_pnts <= 0) && rt_opt->verbose) {
|
|
FIST_Warning("Compute() - nothing to triangulate!\n");
|
|
return;
|
|
}
|
|
|
|
if (rt_opt->time) all->cpu_time = elapsed(all);
|
|
#ifdef BENCHMARK
|
|
else all->cpu_time = elapsed(all);
|
|
#endif
|
|
|
|
if (all->new_input) {
|
|
/* */
|
|
/* make sure that all polygons are closed even when my code is not */
|
|
/* used properly. */
|
|
/* */
|
|
EnsureClosedPolygon(all);
|
|
|
|
#ifdef BENCHMARK
|
|
gettimeofday(&all->start, NULL);
|
|
#endif
|
|
|
|
/* */
|
|
/* initialize or reset local variables. */
|
|
/* */
|
|
all->reset = false;
|
|
all->troubles = false;
|
|
all->written = false;
|
|
all->done = false;
|
|
all->num_contours = list->num_loops;
|
|
|
|
/* */
|
|
/* the input has been changed; generate fake 3D vertices. this also */
|
|
/* saves the original 2D vertex data. */
|
|
/* */
|
|
Fake3D(all);
|
|
InitTriangles(vert, data->num_pnts + 2 * list->num_loops);
|
|
|
|
/* */
|
|
/* sort the vertices in lexicographic order, discard duplicate */
|
|
/* vertices. also, it resets the "loops" pointers such that every loop */
|
|
/* points to its left-most vertex. */
|
|
/* */
|
|
CleanPolygon(all, &removed);
|
|
|
|
/* */
|
|
/* remove zero-length edges */
|
|
/* */
|
|
if (removed > 0) {
|
|
#ifdef PARTITION_FIST
|
|
#pragma omp parallel for default(shared) schedule(dynamic, 1)
|
|
#endif
|
|
for (i = 0; i < list->num_loops; ++i) {
|
|
RemoveZeroEdges(list, &(list->loops[i]));
|
|
}
|
|
}
|
|
|
|
/* */
|
|
/* compute the bounding box of the polygon(s), and scale the data if */
|
|
/* requested by the user. */
|
|
/* */
|
|
SetBoundingBox(data, &all->bb_min, &all->bb_max);
|
|
if (rt_opt->scale_data) {
|
|
ScaleData(all);
|
|
#ifdef GRAPHICS
|
|
if (rt_opt->graphics && data->data_scaled) UpdateScaleData();
|
|
#endif
|
|
}
|
|
else {
|
|
data->data_scaled = false;
|
|
}
|
|
|
|
/* */
|
|
/* determine the outer polygon and the orientation of the polygons; */
|
|
/* the default orientation is CCW for the outer polygon, and CW for */
|
|
/* the inner polygons. */
|
|
/* */
|
|
AdjustOrientation(all, 0, list->num_loops);
|
|
|
|
if (rt_opt->c2p) { WritePolyFormat(all); return exit(EXIT_SUCCESS); }
|
|
|
|
if (rt_opt->save_poly) WritePolygon(all, rt_opt->output_file);
|
|
if (rt_opt->write_ipe7) WriteIpePolygon(all);
|
|
|
|
if (list->num_loops > 1) BuildGrid(all, 0, list->num_loops);
|
|
else grid->no_grid_yet = true;
|
|
|
|
/* */
|
|
/* mark those vertices whose interior angle is convex */
|
|
/* */
|
|
num_reflex = 0;
|
|
for (i = 0; i < list->num_loops; ++i) {
|
|
ClassifyAngles(all, list->loops[i], &num_reflex);
|
|
}
|
|
|
|
/* */
|
|
/* link the holes with the outer boundary by means of "bridges" */
|
|
/* */
|
|
if (list->num_loops > 1) {
|
|
assert(num_reflex > 0);
|
|
if (rt_opt->verbose) {
|
|
fprintf(stdout,
|
|
"...linking all %d islands with the outer boundary: ",
|
|
list->num_loops - 1);
|
|
fflush(stdout);
|
|
}
|
|
ConstructBridges(all, 0, list->num_loops);
|
|
if (rt_opt->verbose) {
|
|
fprintf(stdout, "done!\n");
|
|
fflush(stdout);
|
|
}
|
|
}
|
|
|
|
/* */
|
|
/* put all ears into a circular linked list */
|
|
/* */
|
|
SetReflexNumber(all, num_reflex);
|
|
if (num_reflex > 0) {
|
|
BuildBuckets(all, list->loops[0]);
|
|
}
|
|
else {
|
|
all->is_convex_face = true;
|
|
SetConvexityStatus(ear, true);
|
|
}
|
|
if (rt_opt->ears_fancy) {
|
|
BuildPntsGrid(all, 0);
|
|
}
|
|
if (!all->is_convex_face) ++vert->num_concave_loops;
|
|
|
|
/* */
|
|
/* classify all ears unless the polygon is trivial */
|
|
/* */
|
|
if (rt_opt->verbose) {
|
|
fprintf(stdout, "...classifying all ears: ");
|
|
fflush(stdout);
|
|
}
|
|
|
|
#ifdef PARTITION_FIST
|
|
/* for the parallel clipping we require a certain minimum of vertices */
|
|
if (data->num_pnts < PARALLEL_MINIMUM)
|
|
all->partition_mode = false;
|
|
if (data->num_pnts <= 3)
|
|
vert->num_triangles = vert->max_num_triangles;
|
|
#endif
|
|
if (data->num_pnts > 3) {
|
|
ClassifyEars(all, list->loops[0]);
|
|
} else {
|
|
if (TrivialPolygon(all, list->loops[0])) all->done = true;
|
|
}
|
|
if (rt_opt->verbose) {
|
|
fprintf(stdout, "done!\n");
|
|
fflush(stdout);
|
|
}
|
|
|
|
/* */
|
|
/* let the user call some application-specific function */
|
|
/* */
|
|
ExtApplFuncNewInput;
|
|
|
|
#ifdef GRAPHICS
|
|
if (rt_opt->graphics && (rt_opt->step_size < INT_MAX)) return;
|
|
#else
|
|
(void) rt_opt->step_size;
|
|
#endif
|
|
}
|
|
|
|
/* FIST-Partition is an ear-clipping approach to clip the contour in
|
|
* parallel using OpenMP. The contour is partitioned into #core segments
|
|
* and for each segment we use a different heap. The triangle array
|
|
* stays the same but the saving is realized differently. We store each
|
|
* triangle on the array position that equals the index of the vertex
|
|
* which was removed from the contour. This enables us to store triangles
|
|
* without any locking or semaphores. */
|
|
#ifdef PARTITION_FIST
|
|
if (!all->done) {
|
|
InitTriangles(vert, list->num_list);
|
|
vert->num_triangles = list->num_list;
|
|
if (all->partition_mode) {
|
|
|
|
if (rt_opt->verbose) {
|
|
fprintf(stdout, "...performing parallel ear-clipping: ");
|
|
fflush(stdout);
|
|
}
|
|
|
|
#pragma omp parallel for default(shared) private(hp)
|
|
for(int p = 0; p < all->number_of_heaps; ++p) {
|
|
hp = &all->c_heap[p];
|
|
boolean done = false;
|
|
|
|
while (!done) {
|
|
if (!ClipEar(all, hp, &done)) {
|
|
#ifdef INFO
|
|
if (rt_opt->verbose) {
|
|
fprintf(stdout, "(a problem occoured in thread %i) ",hp->heap_idx);
|
|
fflush(stdout);
|
|
}
|
|
#endif
|
|
done = true;
|
|
}
|
|
}
|
|
}
|
|
|
|
all->partition_mode = false;
|
|
|
|
#pragma omp parallel for schedule(dynamic, 1)
|
|
for(int p = 0; p < list->num_list; ++p) {
|
|
if(list->list[p].delete_reflex)
|
|
DeleteReflexVertex(all, p);
|
|
}
|
|
|
|
if (rt_opt->verbose) {
|
|
fprintf(stdout, "done! (%i triangles)\n",GetNumTriangles(vert));
|
|
fflush(stdout);
|
|
}
|
|
|
|
hp = &all->c_heap[0];
|
|
InitHeap(hp, data);
|
|
ClassifyAngles(all, list->first_node, &num_reflex);
|
|
ClassifyEars(all, list->first_node);
|
|
} /* end-if all->partition_mode */
|
|
}/* end-if !all->done */
|
|
#endif /* end-if PARTITION_FIST */
|
|
|
|
if (rt_opt->verbose) {
|
|
fprintf(stdout, "...performing ear-clipping: ");
|
|
fflush(stdout);
|
|
}
|
|
|
|
i = 0;
|
|
#ifdef GRAPHICS
|
|
while ((i < rt_opt->step_size) && !all->done) {
|
|
#else
|
|
while (!all->done) {
|
|
#endif
|
|
if (!ClipEar(all, hp, &all->done)) {
|
|
if (all->reset) {
|
|
#ifdef INFO
|
|
if (!rt_opt->quiet) {
|
|
FIST_Warning("Compute() - no further ear to clip!\n");
|
|
FIST_Warning("Compute() - not a simple polygon, isn't it?\n");
|
|
}
|
|
#endif
|
|
ind = GetNode(list);
|
|
ResetPolyList(list, ind);
|
|
list->loops[0] = ind;
|
|
if (Desperate(all, hp, ind, 0, &all->done)) {
|
|
/* */
|
|
/* let the user call some application-specific function */
|
|
/* */
|
|
ExtApplFuncDesperate;
|
|
|
|
#ifdef INFO
|
|
if (!rt_opt->quiet)
|
|
FIST_Warning("Compute() - let's hope for the best...\n");
|
|
#endif
|
|
if (!LetsHope(all, hp, ind)) {
|
|
/* */
|
|
/* let the user call some application-specific function */
|
|
/* */
|
|
ExtApplFuncReligious;
|
|
|
|
#ifdef INFO
|
|
FIST_Warning("Compute() - sorry, I can't do it!\n");
|
|
FIST_Warning("Compute() - ask a triangulation wizard, or clean-up your polygon!\n");
|
|
#endif
|
|
return;
|
|
}
|
|
}
|
|
else {
|
|
all->reset = false;
|
|
}
|
|
}
|
|
else {
|
|
/* */
|
|
/* try again from scratch */
|
|
/* */
|
|
all->troubles = true;
|
|
#ifdef INFO
|
|
if (rt_opt->verbose)
|
|
FIST_Warning("Compute() - 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 */
|
|
/* */
|
|
ExtApplFuncRestart;
|
|
}
|
|
}
|
|
else {
|
|
all->reset = false;
|
|
++i;
|
|
}
|
|
|
|
if (all->done) {
|
|
/* */
|
|
/* let the user call some application-specific function */
|
|
/* */
|
|
ExtApplFuncDoneOneChain;
|
|
|
|
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 (onex of) the remaining parts. */
|
|
/* */
|
|
ResetPolyList(list, ind);
|
|
list->loops[0] = ind;
|
|
grid->no_grid_yet = true;
|
|
BuildBuckets(all, list->loops[0]);
|
|
if (rt_opt->ears_fancy) BuildPntsGrid(all, 0);
|
|
ResetEarStatus(ear);
|
|
ClassifyEars(all, ind);
|
|
all->reset = false;
|
|
all->done = false;
|
|
++i;
|
|
|
|
/* */
|
|
/* let the user call some application-specific function */
|
|
/* */
|
|
ExtApplFuncNextChain;
|
|
}
|
|
}
|
|
}
|
|
|
|
if (rt_opt->verbose) {
|
|
fprintf(stdout, "done!\n");
|
|
fflush(stdout);
|
|
}
|
|
|
|
if (rt_opt->time) all->cpu_time = elapsed(all);
|
|
#ifdef BENCHMARK
|
|
else all->cpu_time = elapsed(all);
|
|
#endif
|
|
|
|
if (all->done) {
|
|
if (!all->written) {
|
|
if (rt_opt->write_geom || rt_opt->write_dxf ||
|
|
rt_opt->write_tri || rt_opt->write_ipe7 ) {
|
|
if (rt_opt->verbose) {
|
|
fprintf(stdout, "\n...writing the output data: ");
|
|
fflush(stdout);
|
|
}
|
|
if (rt_opt->write_geom) WriteGeomOutput(all);
|
|
if (rt_opt->write_dxf) WriteFacesDXF(all, rt_opt->tri_file);
|
|
else if (rt_opt->write_tri) WriteFaces(all, rt_opt->tri_file);
|
|
if (rt_opt->write_ipe7) WriteIpeOutput(all);
|
|
if (rt_opt->verbose) {
|
|
fprintf(stdout, "done!\n");
|
|
fflush(stdout);
|
|
}
|
|
}
|
|
all->written = true;
|
|
}
|
|
|
|
/* */
|
|
/* let the user call some application-specific function */
|
|
/* */
|
|
ExtApplFuncFinished;
|
|
|
|
if (rt_opt->verbose) {
|
|
if (all->troubles)
|
|
printf("\n\nTriangulation completed!\n");
|
|
else
|
|
printf("\n\nTriangulation successfully completed!\n");
|
|
}
|
|
}
|
|
|
|
#ifdef BENCHMARK
|
|
printf("%i,%li\n", GetNumTriangles(vert), (long int)((all->cpu_time)));
|
|
#endif
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
#define NUM_DIST 12
|
|
|
|
void StatisticsFIST(global_struct *all)
|
|
{
|
|
vertexdef *vert = &all->c_vertex;
|
|
listdef *list = &all->c_list;
|
|
quaddef *quad = &all->c_quad;
|
|
|
|
if (!all->rt_opt.quiet && all->rt_opt.graphics && all->rt_opt.time)
|
|
printf("OpenGL interface was used, Statistics output will be erroneous due to the \ngraphical overhead!");
|
|
|
|
if (!all->rt_opt.quiet && all->rt_opt.time) {
|
|
if (all->cpu_time > 0.0) {
|
|
printf("\n\nCPU-time consumption (MS): %8.0f", MDOUBLE_TO_IOMDOUBLE(all->cpu_time));
|
|
}
|
|
else {
|
|
printf("\n\nCPU-time consumption (MS): %8.0f (< 10 MS)",
|
|
MDOUBLE_TO_IOMDOUBLE(all->cpu_time));
|
|
}
|
|
if (vert->num_vertices > 0)
|
|
printf("\nCPU-time/seg (MS, for %7d segs): %18.16f",
|
|
vert->num_vertices,
|
|
MDOUBLE_TO_IOMDOUBLE(all->cpu_time / vert->num_vertices));
|
|
}
|
|
if (all->rt_opt.statistics) {
|
|
if (list->num_faces != 0)
|
|
printf("\n\n#(Input Faces): %8d\n", list->num_faces);
|
|
else
|
|
printf("\n\n#(Input Faces): %8d\n", all->num_contours);
|
|
printf("#(Input Concave Faces): %8d\n", vert->num_concave_loops);
|
|
printf("#(Output Triangles): %8d\n", GetNumTriangles(vert));
|
|
if (vert->num_quads > 0)
|
|
printf("#(Output Quads): %8d\n", vert->num_quads);
|
|
if (vert->num_convex_loops > 0)
|
|
printf("#(Output Convex Faces w/o Quads): %8d\n", vert->num_convex_loops);
|
|
if (quad->num_grouped > 0)
|
|
printf("#(Triangles-->Quads): %8d\n", quad->num_grouped);
|
|
printf("#(Points): %8d\n", vert->num_vertices);
|
|
#ifdef NORMALS
|
|
printf("#(Vertex Normals): %8d\n", vert->num_v_normals);
|
|
printf("#(Texture Vertices): %8d\n", vert->num_t_vertices);
|
|
#endif
|
|
printf("\n\n");
|
|
}
|
|
else if (!all->rt_opt.quiet) {
|
|
printf("\n");
|
|
}
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
void ResetAll(global_struct *all)
|
|
{
|
|
vertexdef *vert = &all->c_vertex;
|
|
#ifdef GRAPHICS
|
|
redrawdef *redraw = &all->c_redraw;
|
|
#endif
|
|
listdef *list = &all->c_list;
|
|
iolistdef *iolist = &all->c_iolist;
|
|
datadef *data = &all->c_data;
|
|
heapdef *heap;
|
|
griddef *grid = &all->c_grid;
|
|
|
|
/* */
|
|
/* let the user call some application-specific function */
|
|
/* */
|
|
ExtApplFuncResetAll;
|
|
|
|
/* */
|
|
/* reset data within individual structures */
|
|
/* */
|
|
#ifdef GRAPHICS
|
|
ResetGraphicsData();
|
|
ResetBufferData(redraw);
|
|
#endif
|
|
|
|
#ifdef PARTITION_FIST
|
|
for(int i = 0; i < all->number_of_heaps; ++i) {
|
|
heap = &all->c_heap[i];
|
|
InitHeap(heap, data);
|
|
}
|
|
#else
|
|
heap = &all->c_heap;
|
|
InitHeap(heap, data);
|
|
#endif
|
|
|
|
ResetListData(list);
|
|
ResetIOListData(iolist);
|
|
ResetGrid(grid);
|
|
|
|
/* */
|
|
/* reset global data */
|
|
/* */
|
|
data->num_pnts = 0;
|
|
list->num_loops = 0;
|
|
vert->num_vertices = 0;
|
|
list->num_faces = 0;
|
|
#ifdef NORMALS
|
|
vert->num_t_vertices = 0;
|
|
vert->num_v_normals = 0;
|
|
vert->num_i_triangles = 0;
|
|
#endif
|
|
vert->num_triangles = 0;
|
|
all->num_contours = 0;
|
|
vert->num_groups = 0;
|
|
|
|
data->data_scaled = false;
|
|
data->scale_factor = C_1_0;
|
|
data->shift.x = C_0_0;
|
|
data->shift.y = C_0_0;
|
|
|
|
all->done = false;
|
|
all->reset = false;
|
|
all->troubles = false;
|
|
all->written = false;
|
|
all->new_input = false;
|
|
all->cpu_time = 0.0;
|
|
all->curr_loop_main = 0;
|
|
all->dxf_file = (FILE*)NULL;
|
|
all->ipe_initialized = false;
|
|
|
|
#ifdef EXPR_WRAPPER
|
|
all->returncore = false;
|
|
#endif
|
|
|
|
return;
|
|
}
|