SaraP
cbec90699f
- creato il progetto in Visual Studio per compilare come libreria statica - modifiche al codice originale per integrarlo nelle nostre librerie.
637 lines
23 KiB
C++
637 lines
23 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 "list.h"
|
|
#include "header.h"
|
|
#include "basic.h"
|
|
#include "numerics.h"
|
|
#include "bv_tree.h"
|
|
#ifdef GRAPHICS
|
|
#include "graphics.h"
|
|
#endif
|
|
|
|
#ifdef PARTITION_FIST
|
|
//#include <omp.h>
|
|
#define HEAP_BARRIER 10
|
|
#endif
|
|
|
|
/* */
|
|
/* function prototypes of functions provided in this file */
|
|
/* */
|
|
void InitEarDefaults(eardef *ear);
|
|
void ClassifyAngles(global_struct *all, list_ind ind, int *num_reflex);
|
|
void ClassifyEars(global_struct *all, list_ind ind);
|
|
boolean IsEar(global_struct *all, heapdef *hp, list_ind ind2, list_ind *ind1,
|
|
list_ind *ind3, machine_double *ratio);
|
|
boolean ClipEar(global_struct *all, heapdef *hp, boolean *done);
|
|
void SetConvexityStatus(eardef *ear, boolean status);
|
|
void ResetEarStatus(eardef *ear);
|
|
|
|
void InitEarDefaults(eardef *ear)
|
|
{
|
|
ear->tri_color = TriTriColor;
|
|
ear->is_convex_polygon = true;
|
|
ear->ears_may_have_changed = true;
|
|
}
|
|
|
|
void ResetEarStatus(eardef *ear)
|
|
{
|
|
ear->ears_may_have_changed = true;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
/* */
|
|
/* sets the "convexity" flag from outside of this file. */
|
|
/* */
|
|
void SetConvexityStatus(eardef *ear, boolean status)
|
|
{
|
|
if (status) {
|
|
ear->is_convex_polygon = true;
|
|
}
|
|
else {
|
|
ear->is_convex_polygon = false;
|
|
ear->tri_color = TriCveColor;
|
|
}
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
|
|
/* */
|
|
/* classifies all the internal angles of the loop referenced by ind. */
|
|
/* the following classification is used: */
|
|
/* 3 ... if angle is about 180 degrees and triangle is very small */
|
|
/* 2 ... if angle is 0 degrees */
|
|
/* 1 ... if angle is between 0 and 180 degrees */
|
|
/* 0 ... if angle is 180 degrees */
|
|
/* -1 ... if angle is between 180 and 360 degrees */
|
|
/* -2 ... if angle is 360 degrees */
|
|
/* */
|
|
void ClassifyAngles(global_struct *all, list_ind ind, int *num_reflex)
|
|
{
|
|
listdef *list = &all->c_list;
|
|
datadef *data = &all->c_data;
|
|
eardef *ear = &all->c_ear;
|
|
|
|
list_ind ind0, ind1, ind2;
|
|
int i0, i1, i2;
|
|
int angle;
|
|
|
|
ind1 = ind;
|
|
i1 = GetIndex(list, ind1);
|
|
ind0 = GetPrevNode(list, ind1);
|
|
i0 = GetIndex(list, ind0);
|
|
do {
|
|
ind2 = GetNextNode(list, ind1);
|
|
i2 = GetIndex(list, ind2);
|
|
angle = IsConvexAngle(list, data, i0, i1, i2, ind1);
|
|
SetAngle(list, ind1, angle);
|
|
if (angle <= 0) ++(*num_reflex);
|
|
#ifdef GRAPHICS
|
|
if (all->rt_opt.graphics) {
|
|
if (angle == 1) DrawPnt(data->points[i1], ConvexColor);
|
|
else if (angle == 2) DrawPnt(data->points[i1], ZeroColor);
|
|
else if (angle == 0) DrawPnt(data->points[i1], TangentColor);
|
|
}
|
|
#endif
|
|
i0 = i1;
|
|
i1 = i2;
|
|
ind1 = ind2;
|
|
} while (ind1 != ind);
|
|
|
|
ear->ears_may_have_changed = true;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
/* */
|
|
/* initial determination of all ears. */
|
|
/* */
|
|
/* also, the lengths of the edges of the polygon are initialized */
|
|
/* */
|
|
void ClassifyEars(global_struct *all, list_ind ind)
|
|
{
|
|
listdef *list = &all->c_list;
|
|
datadef *data = &all->c_data;
|
|
eardef *ear = &all->c_ear;
|
|
heapdef *hp;
|
|
#ifdef PARTITION_FIST
|
|
int number_per_partition = (int) list->num_list / all->number_of_heaps;
|
|
int current_partition, loop_count, max_loop_count;
|
|
int *helper_array;
|
|
helper_array = (int*) malloc(sizeof(int)*list->max_num_list);
|
|
#endif
|
|
|
|
list_ind ind1;
|
|
#ifdef GRAPHICS
|
|
int i1;
|
|
#endif
|
|
list_ind ind0, ind2;
|
|
machine_double ratio;
|
|
|
|
#ifdef PARTITION_FIST
|
|
current_partition = loop_count = max_loop_count = 0;
|
|
for(int i = 0; i < all->number_of_heaps; ++i) {
|
|
hp = &all->c_heap[i];
|
|
InitHeap(hp, data);
|
|
hp->sorted = hp->ears_sorted = all->rt_opt.ears_sorted;
|
|
hp->ears_random = all->rt_opt.ears_random;
|
|
}
|
|
if (!all->partition_mode)
|
|
hp = &all->c_heap[0];
|
|
#else
|
|
hp = &all->c_heap;
|
|
InitHeap(hp, data);
|
|
hp->sorted = hp->ears_sorted = all->rt_opt.ears_sorted;
|
|
hp->ears_random = all->rt_opt.ears_random;
|
|
#endif
|
|
|
|
|
|
if (ear->ears_may_have_changed) {
|
|
/* */
|
|
/* normally, we will always classify the ears. this flag is only set */
|
|
/* to false in the case of repeated invocations of this routine and */
|
|
/* only if the situation has not changed since the last invocation. */
|
|
/* */
|
|
ind1 = ind;
|
|
|
|
#ifdef PARTITION_FIST
|
|
if (number_per_partition < 1)
|
|
all->partition_mode = false;
|
|
|
|
if (all->partition_mode) {
|
|
|
|
/* Write the list->list indices of the contour loop in an array in */
|
|
/* the right order. This enables parallel classification. */
|
|
do {
|
|
helper_array[max_loop_count++] = ind1;
|
|
ind1 = GetNextNode(list,ind1);
|
|
} while(ind != ind1);
|
|
|
|
#pragma omp parallel for default(shared) private(hp,ind0,ind1,ind2,ratio)
|
|
for(int k = 0; k < all->number_of_heaps; ++k) {
|
|
hp = &all->c_heap[k];
|
|
|
|
for(int i = 1; i < max_loop_count/all->number_of_heaps; ++i) {
|
|
if(i + k*max_loop_count/all->number_of_heaps > max_loop_count) continue;
|
|
|
|
ind1 = helper_array[i + k*max_loop_count/all->number_of_heaps];
|
|
if (GetAngle(list, ind1) > 0) {
|
|
if (IsEar(all, hp, ind1, &ind0, &ind2, &ratio)) {
|
|
DumpOnHeap(hp, ratio, ind1, ind0, ind2);
|
|
}
|
|
}
|
|
}
|
|
MakeHeap(hp);
|
|
}
|
|
|
|
for(int i = 0; i < all->number_of_heaps; ++i)
|
|
all->corner_nodes[i] = helper_array[i*max_loop_count/all->number_of_heaps];
|
|
|
|
free(helper_array);
|
|
} else {
|
|
hp = &all->c_heap[current_partition];
|
|
#endif
|
|
do {
|
|
|
|
#ifdef STAGES
|
|
SetStage(list, ind1, 0);
|
|
#endif
|
|
if (GetAngle(list, ind1) > 0) {
|
|
if (IsEar(all, hp, ind1, &ind0, &ind2, &ratio)) {
|
|
DumpOnHeap(hp, ratio, ind1, ind0, ind2);
|
|
#ifdef GRAPHICS
|
|
if (all->rt_opt.graphics) {
|
|
i1 = GetIndex(list, ind1);
|
|
DrawPnt(data->points[i1], EarColor);
|
|
}
|
|
#endif
|
|
}
|
|
}
|
|
|
|
ind1 = GetNextNode(list, ind1);
|
|
} while (ind1 != ind);
|
|
MakeHeap(hp);
|
|
}
|
|
#ifdef PARTITION_FIST
|
|
}
|
|
#endif
|
|
ear->ears_may_have_changed = false;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
/* */
|
|
/* this function checks whether a diagonal is valid, i.e., whether it is */
|
|
/* locally within the polygon, and whether it does not intersect any other */
|
|
/* segment of the polygon. also, some degenerate cases get a special */
|
|
/* handling. */
|
|
/* */
|
|
boolean IsEar(global_struct *all, heapdef *hp, list_ind ind2, list_ind *ind1,
|
|
list_ind *ind3, machine_double *ratio)
|
|
{
|
|
listdef *list = &all->c_list;
|
|
datadef *data = &all->c_data;
|
|
eardef *ear = &all->c_ear;
|
|
|
|
tmp_data_def tmp_data;
|
|
|
|
int i0, i1, i2, i3, i4;
|
|
list_ind ind0, ind4;
|
|
bounding_box bb;
|
|
int i_close = NIL;
|
|
machine_double ratio1;
|
|
boolean convex, cone_ok;
|
|
|
|
i2 = GetIndex(list, ind2);
|
|
*ind3 = GetNextNode(list, ind2);
|
|
i3 = GetIndex(list, *ind3);
|
|
*ind1 = GetPrevNode(list, ind2);
|
|
i1 = GetIndex(list, *ind1);
|
|
|
|
/* */
|
|
/* the potential ear is given by the triangle (i1,i2,i3), with (i1,i3) */
|
|
/* forming the diagonal */
|
|
/* */
|
|
if (ear->is_convex_polygon) {
|
|
/* */
|
|
/* this is a convex polygon. no need to test for earity. */
|
|
/* */
|
|
if (hp->ears_sorted) {
|
|
/* */
|
|
/* determine the quality of the triangle. note that there are no */
|
|
/* reflex vertices. */
|
|
/* */
|
|
*ratio = GetRatio(data, i1, i3, i2);
|
|
if (ear->ears_fancy) {
|
|
ratio1 = TopQualityGrid(all, i1, i3);
|
|
if (*ratio < ratio1) *ratio = ratio1;
|
|
}
|
|
#ifdef STAGES
|
|
*ratio += Max(GetStage(list, *ind1), GetStage(list, ind2));
|
|
#endif
|
|
}
|
|
else {
|
|
*ratio = CD_1_0;
|
|
}
|
|
return true;
|
|
}
|
|
else {
|
|
if ((i1 == i3) || (i1 == i2) || (i2 == i3) ||
|
|
(GetAngle(list, ind2) == 2)) {
|
|
/* */
|
|
/* oops, this is not a simple polygon! */
|
|
/* */
|
|
*ratio = CD_0_0;
|
|
return true;
|
|
}
|
|
|
|
ind4 = GetNextNode(list, *ind3);
|
|
i4 = GetIndex(list, ind4);
|
|
ind0 = GetPrevNode(list, *ind1);
|
|
i0 = GetIndex(list, ind0);
|
|
|
|
/* */
|
|
/* check whether the new diagonal i1, i3 locally is within the */
|
|
/* polygon */
|
|
/* */
|
|
convex = GetAngle(list, *ind1) > 0;
|
|
#ifdef GRAZING
|
|
DiagIsInConeEps(data, tmp_data, i0, i1, i2, i3, convex, true, cone_ok);
|
|
#else
|
|
DiagIsInCone(data, tmp_data, i0, i1, i2, i3, convex, true, cone_ok);
|
|
#endif
|
|
if (!cone_ok) return false;
|
|
convex = GetAngle(list, *ind3) > 0;
|
|
#ifdef GRAZING
|
|
DiagIsInConeEps(data, tmp_data, i2, i3, i4, i1, convex, false, cone_ok);
|
|
#else
|
|
DiagIsInCone(data, tmp_data, i2, i3, i4, i1, convex, false, cone_ok);
|
|
#endif
|
|
|
|
if (cone_ok) {
|
|
/* */
|
|
/* check whether this diagonal is a valid diagonal. We use */
|
|
/* "buckets" (i.e., a grid) or no hashing at all. */
|
|
/* */
|
|
BBox(data, i1, i3, bb);
|
|
|
|
/* */
|
|
/* use CE2 + grid */
|
|
/* */
|
|
if (!BucketIntersectionExists(all, i2, ind2, i3, i1, bb, &i_close,
|
|
ear->ears_top || ear->ears_fancy)) {
|
|
if ((i0 == i3) || (i1 == i4)) {
|
|
*ratio = CD_0_0;
|
|
}
|
|
else if (hp->ears_sorted) {
|
|
/* */
|
|
/* determine the quality of the triangle */
|
|
/* */
|
|
if (ear->ears_top) {
|
|
if (i_close != NIL) {
|
|
*ratio = GetDoubleRatio(data, i1, i3, i2, i_close);
|
|
}
|
|
else {
|
|
*ratio = GetRatio(data, i1, i3, i2);
|
|
}
|
|
}
|
|
else if (ear->ears_fancy) {
|
|
if (i_close != NIL) {
|
|
*ratio = GetDoubleRatio(data, i1, i3, i2, i_close);
|
|
}
|
|
else {
|
|
*ratio = GetRatio(data, i1, i3, i2);
|
|
}
|
|
ratio1 = TopQualityGrid(all, i1, i3);
|
|
if (*ratio < ratio1) *ratio = ratio1;
|
|
}
|
|
else {
|
|
*ratio = GetRatio(data, i1, i3, i2);
|
|
}
|
|
#ifdef STAGES
|
|
*ratio += Max(GetStage(list, *ind1), GetStage(list, ind2));
|
|
#endif
|
|
}
|
|
else {
|
|
*ratio = CD_1_0;
|
|
}
|
|
return true;
|
|
}
|
|
}
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
/* */
|
|
/* this is the main function that drives the ear-clipping. it obtains an ear */
|
|
/* from set of ears maintained in a priority queue, clips this ear, and */
|
|
/* updates all data structures appropriately. (ears are arranged in the */
|
|
/* priority queue (i.e., heap) according to a quality criterion that tries */
|
|
/* to avoid skinny triangles.) */
|
|
/* */
|
|
boolean ClipEar(global_struct *all, heapdef *hp, boolean *done)
|
|
{
|
|
listdef *list = &all->c_list;
|
|
datadef *data = &all->c_data;
|
|
eardef *ear = &all->c_ear;
|
|
#ifdef GRAPHICS
|
|
int i2;
|
|
#endif
|
|
|
|
list_ind ind0, ind2, ind1, ind3, ind4;
|
|
list_ind index0, index1, index2, index3, index4;
|
|
int i0, i1, i3, i4;
|
|
int angle1, angle3, old1, old3;
|
|
machine_double ratio;
|
|
#ifdef STAGES
|
|
int stage;
|
|
#endif
|
|
|
|
do {
|
|
if (!DeleteFromHeap(hp, &ind2, &index1, &index3)) {
|
|
/* */
|
|
/* no ear exists?! */
|
|
/* */
|
|
#ifdef PARTITION_FIST
|
|
if (all->partition_mode) {
|
|
*done = true;
|
|
return true;
|
|
}
|
|
#endif
|
|
return false;
|
|
}
|
|
|
|
/* */
|
|
/* get the successors and predecessors in the list of nodes and */
|
|
/* check whether the ear still is part of the boundary */
|
|
/* */
|
|
ind1 = GetPrevNode(list, ind2);
|
|
ind3 = GetNextNode(list, ind2);
|
|
|
|
} while ((index1 != ind1) || (index3 != ind3));
|
|
|
|
#ifdef PARTITION_FIST
|
|
if (all->partition_mode && isCorner(all, hp->heap_idx, ind2))
|
|
return true;
|
|
#endif
|
|
|
|
i1 = GetIndex(list, ind1);
|
|
#ifdef GRAPHICS
|
|
i2 = GetIndex(list, ind2);
|
|
#endif
|
|
i3 = GetIndex(list, ind3);
|
|
|
|
#ifdef STAGES
|
|
stage = Max(GetStage(list, ind1), GetStage(list, ind2)) + 4;
|
|
SetStage(list, ind1, stage);
|
|
#endif
|
|
|
|
/* */
|
|
/* delete the clipped ear from the list of nodes */
|
|
/* */
|
|
DeleteLinks(list, ind2);
|
|
|
|
/* */
|
|
/* store the ear in a list of ears which have already been clipped */
|
|
/* */
|
|
StoreTriangle(all, ind1, ind2, ind3, ear->tri_color);
|
|
|
|
/* */
|
|
/* insert the ear into the drawing buffer */
|
|
/* */
|
|
#ifdef GRAPHICS
|
|
if (all->rt_opt.graphics) {
|
|
AddTriToBuffer(&all->c_redraw, i1, i2, i3, TriColor, TriFillColor);
|
|
#ifdef PARTITION_FIST
|
|
if(!all->partition_mode) {
|
|
#endif
|
|
DrawTri(data->points[i1], data->points[i2],
|
|
data->points[i3], TriColor, TriFillColor);
|
|
DrawSeg(data->points[i1], data->points[i3], PolyColor);
|
|
#ifdef PARTITION_FIST
|
|
}
|
|
#endif
|
|
}
|
|
#endif
|
|
|
|
#ifdef PARTITION_FIST
|
|
if (all->partition_mode &&
|
|
(isCorner(all, hp->heap_idx, ind1) || isCorner(all, hp->heap_idx, ind3)))
|
|
return true;
|
|
#endif
|
|
/* */
|
|
/* update the angle classification at ind1 and ind3 */
|
|
/* */
|
|
ind0 = GetPrevNode(list, ind1);
|
|
i0 = GetIndex(list, ind0);
|
|
if (ind0 == ind3) {
|
|
/* */
|
|
/* nothing left */
|
|
/* */
|
|
*done = true;
|
|
return true;
|
|
}
|
|
angle1 = IsConvexAngle(list, data, i0, i1, i3, ind1);
|
|
old1 = GetAngle(list, ind1);
|
|
angle1 = Max(angle1, old1);
|
|
ind4 = GetNextNode(list, ind3);
|
|
i4 = GetIndex(list, ind4);
|
|
angle3 = IsConvexAngle(list, data, i1, i3, i4, ind3);
|
|
old3 = GetAngle(list, ind3);
|
|
angle3 = Max(angle3, old3);
|
|
|
|
if (angle1 > 0) {
|
|
if (old1 <= 0) {
|
|
#ifdef PARTITION_FIST
|
|
if(all->partition_mode)
|
|
list->list[ind1].delete_reflex = true;
|
|
else
|
|
#endif
|
|
DeleteReflexVertex(all, ind1);
|
|
ear->ears_may_have_changed = true;
|
|
}
|
|
}
|
|
if (angle3 > 0) {
|
|
if (old3 <= 0) {
|
|
#ifdef PARTITION_FIST
|
|
if(all->partition_mode)
|
|
list->list[ind3].delete_reflex = true;
|
|
else
|
|
#endif
|
|
DeleteReflexVertex(all, ind3);
|
|
ear->ears_may_have_changed = true;
|
|
}
|
|
}
|
|
|
|
SetAngle(list, ind1, angle1);
|
|
SetAngle(list, ind3, angle3);
|
|
|
|
#ifdef GRAPHICS
|
|
if (all->rt_opt.graphics
|
|
#ifdef PARTITION_FIST
|
|
&& !all->partition_mode
|
|
#endif
|
|
) {
|
|
if (angle1 == 1)
|
|
DrawPnt(data->points[i1], ConvexColor);
|
|
else if (angle1 == 2)
|
|
DrawPnt(data->points[i1], ZeroColor);
|
|
else if (angle1 == 0)
|
|
DrawPnt(data->points[i1], TangentColor);
|
|
else if (angle1 <= -1)
|
|
DrawPnt(data->points[i1], PntsColor);
|
|
if (angle3 == 1)
|
|
DrawPnt(data->points[i3], ConvexColor);
|
|
else if (angle3 == 2)
|
|
DrawPnt(data->points[i3], ZeroColor);
|
|
else if (angle3 == 0)
|
|
DrawPnt(data->points[i3], TangentColor);
|
|
else if (angle3 <= -1)
|
|
DrawPnt(data->points[i3], PntsColor);
|
|
}
|
|
#endif
|
|
|
|
/* */
|
|
/* check whether either of ind1 and ind3 is an ear. (the "ratio" is */
|
|
/* a quality criterion used to clip "nice" ears.) */
|
|
/* */
|
|
if (angle1 > 0) {
|
|
#ifdef PARTITION_FIST
|
|
if(!all->partition_mode ||
|
|
(all->partition_mode && !isCorner(all, hp->heap_idx, ind1)))
|
|
#endif
|
|
if (IsEar(all, hp, ind1, &index0, &index2, &ratio)) {
|
|
/* */
|
|
/* insert the new ear into the priority queue of ears */
|
|
/* */
|
|
InsertIntoHeap(hp, ratio, ind1, index0, index2);
|
|
#ifdef GRAPHICS
|
|
if (all->rt_opt.graphics
|
|
#ifdef PARTITION_FIST
|
|
&& !all->partition_mode
|
|
#endif
|
|
)
|
|
DrawPnt(data->points[i1], EarColor);
|
|
#endif
|
|
}
|
|
}
|
|
|
|
if (angle3 > 0) {
|
|
#ifdef PARTITION_FIST
|
|
if(!all->partition_mode ||
|
|
(all->partition_mode && !isCorner(all, hp->heap_idx, ind3)))
|
|
#endif
|
|
if(IsEar(all, hp, ind3, &index2, &index4, &ratio)) {
|
|
InsertIntoHeap(hp, ratio, ind3, index2, index4);
|
|
#ifdef GRAPHICS
|
|
if (all->rt_opt.graphics
|
|
#ifdef PARTITION_FIST
|
|
&& !all->partition_mode
|
|
#endif
|
|
)
|
|
DrawPnt(data->points[i3], EarColor);
|
|
#endif
|
|
}
|
|
}
|
|
|
|
/* */
|
|
/* check whether the triangulation is finished. */
|
|
/* */
|
|
if (ind0 == ind4) {
|
|
/* */
|
|
/* only one triangle left -- clip it! ;-) */
|
|
StoreTriangle(all, ind1, ind3, ind4, ear->tri_color);
|
|
#ifdef GRAPHICS
|
|
if (all->rt_opt.graphics) {
|
|
AddTriToBuffer(&all->c_redraw, i1, i3, i4, TriColor, TriFillColor);
|
|
#ifdef PARTITION_FIST
|
|
if(!all->partition_mode)
|
|
#endif
|
|
DrawTri(data->points[i1], data->points[i3], data->points[i4],
|
|
TriColor, TriFillColor);
|
|
}
|
|
#endif
|
|
*done = true;
|
|
}
|
|
else {
|
|
*done = false;
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|