SaraP
cbec90699f
- creato il progetto in Visual Studio per compilare come libreria statica - modifiche al codice originale per integrarlo nelle nostre librerie.
347 lines
15 KiB
C++
347 lines
15 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>
|
|
|
|
/* */
|
|
/* get my header files */
|
|
/* */
|
|
#include "fpkernel.h"
|
|
#include "martin.h"
|
|
#include "defs.h"
|
|
#include "header.h"
|
|
|
|
/* */
|
|
/* function prototypes of functions provided in this file */
|
|
/* */
|
|
|
|
|
|
#define EMPTY -1
|
|
|
|
/* */
|
|
/* EdgeLt returns 1 if edge e1 is lexicographically smaller than edge e2, */
|
|
/* and 0 otherwise. */
|
|
/* */
|
|
#define EdgeLt(e1, e2) \
|
|
(((e1).v1 < (e2).v1) ? 1 : \
|
|
(((e1).v1 == (e2).v1) ? ((e1).v2 < (e2).v2) : 0))
|
|
|
|
#define EdgeEq(e1, e2) \
|
|
(((e1).v1 == (e2).v1) && ((e1).v2 == (e2).v2))
|
|
|
|
#define LtEdge(e1, e2) \
|
|
(((e1)->v1 < (e2)->v1) ? 1 : \
|
|
(((e1)->v1 == (e2)->v1) ? ((e1)->v2 < (e2)->v2) : 0))
|
|
|
|
/* */
|
|
/* store the information for one edge in bucket j of the hash table */
|
|
/* */
|
|
#define StoreEdge(quad, vert1, vert2, face, j) \
|
|
{ \
|
|
assert(quad->num_table < quad->max_num_table); \
|
|
assert(j >= 0); \
|
|
assert(j < num_buckets); \
|
|
assert(vert1 <= vert2); \
|
|
quad->element = quad->table + quad->num_table; \
|
|
quad->element->v1 = vert1; \
|
|
quad->element->v2 = vert2; \
|
|
quad->element->tri = face; \
|
|
quad->element->next = quad->heads[j]; \
|
|
quad->heads[j] = quad->num_table; \
|
|
++quad->num_table; \
|
|
}
|
|
|
|
#define InsertEdge(quad, vert1, vert2, face, j, v_min) \
|
|
{ \
|
|
if (vert1 <= vert2) { \
|
|
/* old: j = (vert1 - v_min) / HASH; */ \
|
|
j = vert1 - v_min; \
|
|
StoreEdge(quad, vert1, vert2, face, j); \
|
|
} \
|
|
else { \
|
|
/* old: j = (vert2 - v_min) / HASH; */ \
|
|
j = vert2 - v_min; \
|
|
StoreEdge(quad, vert2, vert1, face, j); \
|
|
} \
|
|
}
|
|
|
|
void InitQuadsDefaults(quaddef *quad)
|
|
{
|
|
quad->num_grouped = 0;
|
|
quad->heads = (int*)NULL;
|
|
quad->max_num_heads = 0;
|
|
|
|
quad->table = (hash_table*)NULL;
|
|
quad->num_table = 0;
|
|
quad->max_num_table = 0;
|
|
}
|
|
|
|
void DetermineQuads(global_struct *all)
|
|
{
|
|
vertexdef *vert = &all->c_vertex;
|
|
quaddef *quad = &all->c_quad;
|
|
|
|
boolean *visited = (boolean*)NULL;
|
|
edge *edges = (edge*)NULL;
|
|
int num_edges, number;
|
|
triangle *t_ptr;
|
|
int i, j, m, n, k;
|
|
int num_buckets, ptr;
|
|
edge *j_edge, *k_edge;
|
|
boolean PutIntoQuad(global_struct *all, triangle *tri1, triangle *tri2, int v1, int v2);
|
|
|
|
num_edges = 3 * vert->num_triangles;
|
|
num_buckets = 1 + vert->num_vertices;
|
|
|
|
visited = (boolean*) ReallocateArray(vert->memptr, visited, vert->num_triangles,
|
|
sizeof(boolean),
|
|
"quads:visited");
|
|
edges = (edge*) ReallocateArray(vert->memptr, edges, num_edges + 1, sizeof(edge),
|
|
"quads:edges");
|
|
|
|
/* we insert every edge (v1,v2), with v1 <= v2, into a hash table. our */
|
|
/* hashing function assigns a vertex index v1 to a subinterval of */
|
|
/* [v_min:v_max}, where v_min and v_max are the minimum (resp., maximum) */
|
|
/* indices of vertices supplied to SortEdges. the size of the subinterval */
|
|
/* is one. the edges within the bucket i of the hash table are maintained */
|
|
/* as a linked list, with heads[i] pointing to its start. for simplicity, */
|
|
/* all bucket lists are stored within one array, table[0:num_table]. */
|
|
/* */
|
|
/* a scan through all bucket lists yields the edges in a pre-sorted order.*/
|
|
/* the final sort can then be done efficiently by means of an insertion */
|
|
/* sort. */
|
|
if (num_buckets > quad->max_num_heads) {
|
|
/* */
|
|
/* (re)allocate the header list for the hash table */
|
|
/* */
|
|
quad->max_num_heads = num_buckets + 1;
|
|
quad->heads = (int*) ReallocateArray(vert->memptr, quad->heads, quad->max_num_heads, sizeof(int),
|
|
"quads:heads");
|
|
}
|
|
for (i = 0; i < num_buckets; ++i) quad->heads[i] = EMPTY;
|
|
|
|
if (num_edges >= quad->max_num_table) {
|
|
/* */
|
|
/* (re)allocate the hash table */
|
|
/* */
|
|
quad->max_num_table = num_edges + 1;
|
|
quad->table = (hash_table*) ReallocateArray(vert->memptr, quad->table, quad->max_num_table,
|
|
sizeof(hash_table),
|
|
"quads:table");
|
|
}
|
|
quad->num_table = 0;
|
|
|
|
/* */
|
|
/* insert the edges into the hash table */
|
|
/* */
|
|
assert(num_buckets < quad->max_num_heads);
|
|
for (i = 0; i < vert->num_triangles; ++i) {
|
|
visited[i] = false;
|
|
t_ptr = &(vert->triangles[i]);
|
|
InsertEdge(quad, t_ptr->v1, t_ptr->v2, i, j, 0);
|
|
InsertEdge(quad, t_ptr->v2, t_ptr->v3, i, j, 0);
|
|
InsertEdge(quad, t_ptr->v1, t_ptr->v3, i, j, 0);
|
|
}
|
|
|
|
/* */
|
|
/* set a sentinel for use in insertion sort. we know that no vertex */
|
|
/* index is larger than v_max. this is why the edge array has to be of */
|
|
/* one element larger than what is needed in order to store the edges */
|
|
/* of the triangles. */
|
|
/* */
|
|
j_edge = edges + num_edges;
|
|
j_edge->v1 = vert->num_vertices + 1;
|
|
j_edge->v2 = vert->num_vertices + 2;
|
|
j_edge->tri = EMPTY;
|
|
|
|
/* */
|
|
/* extract the pre-sorted edges from the hash table, and insert them */
|
|
/* into the edge-array using insertion sort. the overall goal of this */
|
|
/* insertion sort is to minimize the number of assignments. */
|
|
/* */
|
|
k = num_edges - 1;
|
|
|
|
for (i = num_buckets - 1; i >= 0; --i) {
|
|
/* */
|
|
/* for all buckets of the hash table. we start with the bucket that */
|
|
/* contains the largest integers. */
|
|
/* */
|
|
ptr = quad->heads[i]; /* start of bucket list */
|
|
while (ptr != EMPTY) { /* while bucket isn't empty */
|
|
quad->element = quad->table + ptr; /* table[ptr] to be inserted */
|
|
assert(quad->element->v1 >= 0);
|
|
/* otherwise, out-of-bounds! */
|
|
assert(quad->element->v1 <= vert->num_vertices);
|
|
assert(k >= 0);
|
|
k_edge = edges + k; /* edges[k+1:3*end] is sorted */
|
|
j_edge = k_edge + 1;
|
|
/* shuffle table[ptr] upwards */
|
|
while (LtEdge(j_edge, quad->element)) {
|
|
*k_edge = *j_edge; /* copy one edge downwards */
|
|
k_edge = j_edge;
|
|
++j_edge;
|
|
}
|
|
k_edge->v1 = quad->element->v1; /* final place for table[ptr] */
|
|
k_edge->v2 = quad->element->v2;
|
|
k_edge->tri = quad->element->tri;
|
|
ptr = quad->element->next; /* next item in this bucket */
|
|
--k;
|
|
}
|
|
}
|
|
|
|
/* */
|
|
/* scan the list of edges, and group neighboring triangles into quads. */
|
|
/* triangles which have been grouped get marked as `visited'. */
|
|
/* */
|
|
i = 0;
|
|
number = num_edges - 1;
|
|
|
|
while (i < number) {
|
|
m = edges[i].tri;
|
|
j = i + 1;
|
|
if (!visited[m]) {
|
|
n = edges[j].tri;
|
|
if (!visited[n]) {
|
|
if (EdgeEq(edges[i], edges[j])) {
|
|
/* */
|
|
/* these two triangles can be grouped into a quad, provided */
|
|
/* that they have the same orientation */
|
|
/* */
|
|
if (PutIntoQuad(all, &(vert->triangles[m]), &(vert->triangles[n]),
|
|
edges[i].v1, edges[i].v2)) {
|
|
visited[m] = true;
|
|
visited[n] = true;
|
|
++j;
|
|
}
|
|
}
|
|
}
|
|
else {
|
|
++j;
|
|
}
|
|
}
|
|
i = j;
|
|
}
|
|
|
|
/* */
|
|
/* delete all those triangles from the list of triangles that have been */
|
|
/* grouped into quads */
|
|
/* */
|
|
j = 0;
|
|
for (i = 0; i < vert->num_triangles; ++i) {
|
|
if (!visited[i]) {
|
|
vert->triangles[j] = vert->triangles[i];
|
|
++j;
|
|
}
|
|
}
|
|
|
|
quad->num_grouped = vert->num_triangles - j;
|
|
vert->num_triangles = j;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
int edge_comp(const edge *a, const edge *b)
|
|
{
|
|
if (a->v1 < b->v1) return -1;
|
|
else if (a->v1 > b->v1) return 1;
|
|
else {
|
|
if (a->v2 < b->v2) return -1;
|
|
else if (a->v2 > b->v2) return 1;
|
|
else return 0;
|
|
}
|
|
}
|
|
|
|
|
|
|
|
boolean PutIntoQuad(global_struct *all, triangle *tri1, triangle *tri2, int v1, int v2)
|
|
{
|
|
vertexdef *vert = &all->c_vertex;
|
|
|
|
if (((v1 == tri1->v1) && (v2 == tri1->v2)) ||
|
|
((v2 == tri1->v1) && (v1 == tri1->v2))) {
|
|
/* */
|
|
/* (tri1->v1,tri1->v2) is the common diagonal */
|
|
/* */
|
|
if ((tri1->v1 == tri2->v1) && (tri1->v2 == tri2->v3)) {
|
|
StoreQuad(vert, tri1->v2, tri1->v3, tri1->v1, tri2->v2);
|
|
return true;
|
|
}
|
|
else if ((tri1->v1 == tri2->v3) && (tri1->v2 == tri2->v2)) {
|
|
StoreQuad(vert, tri1->v2, tri1->v3, tri1->v1, tri2->v1);
|
|
return true;
|
|
}
|
|
else if ((tri1->v1 == tri2->v2) && (tri1->v2 == tri2->v1)) {
|
|
StoreQuad(vert, tri1->v2, tri1->v3, tri1->v1, tri2->v3);
|
|
return true;
|
|
}
|
|
}
|
|
else if (((v1 == tri1->v2) && (v2 == tri1->v3)) ||
|
|
((v2 == tri1->v2) && (v1 == tri1->v3))) {
|
|
/* */
|
|
/* (tri1->v2,tri1->v3) is the common diagonal */
|
|
/* */
|
|
if ((tri1->v2 == tri2->v1) && (tri1->v3 == tri2->v3)) {
|
|
StoreQuad(vert, tri1->v3, tri1->v1, tri1->v2, tri2->v2);
|
|
return true;
|
|
}
|
|
else if ((tri1->v2 == tri2->v3) && (tri1->v3 == tri2->v2)) {
|
|
StoreQuad(vert, tri1->v3, tri1->v1, tri1->v2, tri2->v1);
|
|
return true;
|
|
}
|
|
else if ((tri1->v2 == tri2->v2) && (tri1->v3 == tri2->v1)) {
|
|
StoreQuad(vert, tri1->v3, tri1->v1, tri1->v2, tri2->v3);
|
|
return true;
|
|
}
|
|
}
|
|
else if (((v1 == tri1->v3) && (v2 == tri1->v1)) ||
|
|
((v2 == tri1->v3) && (v1 == tri1->v1))) {
|
|
/* */
|
|
/* (tri1->v3,tri1->v1) is the common diagonal */
|
|
/* */
|
|
if ((tri1->v3 == tri2->v1) && (tri1->v1 == tri2->v3)) {
|
|
StoreQuad(vert, tri1->v1, tri1->v2, tri1->v3, tri2->v2);
|
|
return true;
|
|
}
|
|
else if ((tri1->v3 == tri2->v3) && (tri1->v1 == tri2->v2)) {
|
|
StoreQuad(vert, tri1->v1, tri1->v2, tri1->v3, tri2->v1);
|
|
return true;
|
|
}
|
|
else if ((tri1->v3 == tri2->v2) && (tri1->v1 == tri2->v1)) {
|
|
StoreQuad(vert, tri1->v1, tri1->v2, tri1->v3, tri2->v3);
|
|
return true;
|
|
}
|
|
}
|
|
else {
|
|
/* */
|
|
/* something is messed up! triangle #1 does not have the edge (v1,v2) */
|
|
/* as an edge! */
|
|
/* */
|
|
if (all->rt_opt.verbose) {
|
|
fprintf(stderr, "***** quads: no common edge??? *****\n");
|
|
fprintf(stderr, "Tri 1: (%d %d %d)\n", tri1->v1, tri1->v2, tri1->v3);
|
|
fprintf(stderr, "Tri 2: (%d %d %d)\n", tri2->v1, tri2->v2, tri2->v3);
|
|
fprintf(stderr, "Edge: (%d %d)\n\n", v1, v2);
|
|
}
|
|
}
|
|
|
|
return false;
|
|
}
|