SaraP
cbec90699f
- creato il progetto in Visual Studio per compilare come libreria statica - modifiche al codice originale per integrarlo nelle nostre librerie.
257 lines
9.0 KiB
C++
257 lines
9.0 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 <stdlib.h>
|
|
#include <stdio.h>
|
|
#include <assert.h>
|
|
#include <math.h>
|
|
|
|
/* */
|
|
/* get my header files */
|
|
/* */
|
|
#include "fpkernel.h"
|
|
#include "martin.h"
|
|
#include "defs.h"
|
|
#include "list.h"
|
|
#include "header.h"
|
|
|
|
/* */
|
|
/* prototypes of functions provided in this file */
|
|
/* */
|
|
void CleanPolygon(global_struct *all, int *removed);
|
|
void CleanPolyhedralFace(global_struct *all, int i1, int i2, int *removed);
|
|
void FreeUnsorted(cleandef *clean);
|
|
|
|
|
|
int rec_comp(const void *, const void *);
|
|
int p_comp_fist(const void *, const void *);
|
|
int find_p_ind(point *sorted, int no_vert, point pnt);
|
|
|
|
|
|
#define InitPUnsorted(clean,number) \
|
|
{ \
|
|
if (number > clean->max_num_p_unsorted) { \
|
|
clean->p_unsorted = CORE_ReallocateArray(clean->memptr, clean->p_unsorted, clean->max_num_p_unsorted, \
|
|
number, sort_record, \
|
|
"clean:p_unsorted"); \
|
|
clean->max_num_p_unsorted = number; \
|
|
} \
|
|
}
|
|
|
|
#ifdef PARTITION_FIST
|
|
#define OMP_CRITICAL _Pragma("omp critical(StorePUnsorted)")
|
|
#else
|
|
#define OMP_CRITICAL
|
|
#endif
|
|
#define StorePUnsorted(data, clean, j, index, curr, number, num_pnts) \
|
|
{\
|
|
OMP_CRITICAL \
|
|
{ \
|
|
if (j >= clean->max_num_p_unsorted) { \
|
|
if (j >= num_pnts) number = 1 + (int) ((machine_double) number * 1.1); \
|
|
clean->p_unsorted = CORE_ReallocateArray(clean->memptr, clean->p_unsorted, clean->max_num_p_unsorted, \
|
|
number, sort_record, \
|
|
"clean:p_unsorted"); \
|
|
clean->max_num_p_unsorted = number; \
|
|
} \
|
|
clean->p_unsorted[j].p = data->points[index]; \
|
|
clean->p_unsorted[j].ind = curr; \
|
|
++j; \
|
|
} \
|
|
}
|
|
|
|
|
|
void InitCleanDefaults(cleandef *clean)
|
|
{
|
|
clean->p_unsorted = (sort_record*)NULL;
|
|
clean->max_num_p_unsorted = 0;
|
|
}
|
|
|
|
|
|
void FreeUnsorted(cleandef *clean)
|
|
{
|
|
CORE_FreeMemory(clean->memptr, &clean->p_unsorted, "clean:p_unsorted");
|
|
clean->max_num_p_unsorted = 0;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
void CleanPolygon(global_struct *all, int *removed)
|
|
{
|
|
datadef *data = &all->c_data;
|
|
listdef *list = &all->c_list;
|
|
cleandef *clean = &all->c_clean;
|
|
|
|
int i, j, num_sorted, index, number;
|
|
list_ind ind1, ind2;
|
|
|
|
/* */
|
|
/* store the vertices plus their list indices */
|
|
/* */
|
|
number = data->num_pnts;
|
|
j = 0;
|
|
#ifdef PARTITION_FIST
|
|
#pragma omp parallel for private(index,ind1,ind2)
|
|
#endif
|
|
for (i = 0; i < list->num_loops; ++i) {
|
|
ind2 = ind1 = list->loops[i];
|
|
index = GetIndex(list,ind1);
|
|
StorePUnsorted(data,clean,j, index, ind1, number, data->num_pnts);
|
|
ind2 = GetNextNode(list,ind2);
|
|
index = GetIndex(list,ind2);
|
|
while (ind2 != ind1) {
|
|
StorePUnsorted(data,clean,j, index, ind2, number, data->num_pnts);
|
|
ind2 = GetNextNode(list,ind2);
|
|
index = GetIndex(list,ind2);
|
|
}
|
|
}
|
|
num_sorted = j;
|
|
|
|
/* */
|
|
/* sort the points according to lexicographical order */
|
|
/* */
|
|
qsort(clean->p_unsorted, num_sorted, sizeof(sort_record), &rec_comp);
|
|
|
|
/* */
|
|
/* eliminate duplicate vertices and re-number them */
|
|
/* */
|
|
i = 0;
|
|
data->points[0] = clean->p_unsorted[0].p;
|
|
UpdateIndex(list, clean->p_unsorted[0].ind, 0);
|
|
|
|
for (j = 1; j < num_sorted; ++j) {
|
|
if (p_comp_fist(data->points + i, &(clean->p_unsorted[j].p)) != 0) {
|
|
++i;
|
|
assert(InPointsList(data, i));
|
|
data->points[i] = clean->p_unsorted[j].p;
|
|
}
|
|
UpdateIndex(list, clean->p_unsorted[j].ind, i);
|
|
}
|
|
num_sorted = i + 1;
|
|
*removed = data->num_pnts - num_sorted;
|
|
data->num_pnts = num_sorted;
|
|
|
|
#ifdef GRAPHICS
|
|
/* */
|
|
/* update the drawing buffer accordingly */
|
|
/* */
|
|
if (all->rt_opt.graphics) UpdatePntEdgeBuffers(all);
|
|
#endif
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
void CleanPolyhedralFace(global_struct *all, int i1, int i2, int *removed)
|
|
{
|
|
datadef *data = &all->c_data;
|
|
listdef *list = &all->c_list;
|
|
cleandef *clean = &all->c_clean;
|
|
|
|
int i, j, num_sorted, index;
|
|
list_ind ind1, ind2;
|
|
|
|
InitPUnsorted(clean, data->num_pnts);
|
|
|
|
for (i = 0; i < data->num_pnts; ++i)
|
|
clean->p_unsorted[i].p = data->points[i];
|
|
|
|
/* */
|
|
/* sort points according to lexicographical order */
|
|
/* */
|
|
qsort(data->points, data->num_pnts, sizeof(point), &p_comp_fist);
|
|
|
|
/* */
|
|
/* eliminate duplicate vertices */
|
|
/* */
|
|
i = 0;
|
|
for (j = 1; j < data->num_pnts; ++j) {
|
|
if (p_comp_fist(data->points + i, data->points + j) != 0) {
|
|
++i;
|
|
data->points[i] = data->points[j];
|
|
}
|
|
}
|
|
num_sorted = i + 1;
|
|
*removed = data->num_pnts - num_sorted;
|
|
|
|
/* */
|
|
/* re-number the vertices of the polygonal face */
|
|
/* */
|
|
for (i = i1; i < i2; ++i) {
|
|
ind1 = list->loops[i];
|
|
ind2 = GetNextNode(list,ind1);
|
|
index = GetIndex(list,ind2);
|
|
while (ind2 != ind1) {
|
|
j = find_p_ind(data->points, num_sorted, clean->p_unsorted[index].p);
|
|
assert(j >= 0);
|
|
UpdateIndex(list, ind2, j);
|
|
ind2 = GetNextNode(list,ind2);
|
|
index = GetIndex(list,ind2);
|
|
}
|
|
j = find_p_ind(data->points, num_sorted, clean->p_unsorted[index].p);
|
|
assert(j >= 0);
|
|
UpdateIndex(list, ind2, j);
|
|
}
|
|
|
|
data->num_pnts = num_sorted;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
|
|
int find_p_ind(point *sorted, int no_vert, point pnt)
|
|
{
|
|
point *addr;
|
|
|
|
addr = (point*)
|
|
bsearch(&pnt, sorted, no_vert, sizeof(point), &p_comp_fist);
|
|
if (addr != NULL) return (addr - &(sorted[0]));
|
|
else return (-1);
|
|
}
|
|
|
|
|
|
|
|
int rec_comp(const void *a, const void *b)
|
|
{
|
|
if (((sort_record*)a)->p.x < ((sort_record*)b)->p.x) return -1;
|
|
else if (((sort_record*)a)->p.x > ((sort_record*)b)->p.x) return 1;
|
|
else {
|
|
if (((sort_record*)a)->p.y < ((sort_record*)b)->p.y) return -1;
|
|
else if (((sort_record*)a)->p.y > ((sort_record*)b)->p.y) return 1;
|
|
else return 0;
|
|
}
|
|
}
|
|
|
|
|
|
int p_comp_fist(const void *a, const void *b)
|
|
{
|
|
if (((point*)a)->x < ((point*)b)->x) return -1;
|
|
else if (((point*)a)->x > ((point*)b)->x) return 1;
|
|
else {
|
|
if (((point*)a)->y < ((point*)b)->y) return -1;
|
|
else if (((point*)a)->y > ((point*)b)->y) return 1;
|
|
else return 0;
|
|
}
|
|
}
|