/*****************************************************************************/ /* */ /* 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 "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; } }