SaraP
cbec90699f
- creato il progetto in Visual Studio per compilare come libreria statica - modifiche al codice originale per integrarlo nelle nostre librerie.
280 lines
12 KiB
C++
280 lines
12 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"
|
|
#ifdef GRAPHICS
|
|
#include "graphics.h"
|
|
#endif
|
|
|
|
/* */
|
|
/* function prototypes of functions provided in this file */
|
|
/* */
|
|
boolean SimpleFace(global_struct *all, list_ind ind1, boolean ears_fancy);
|
|
boolean TrivialPolygon(global_struct *all, list_ind ind1);
|
|
|
|
|
|
/* */
|
|
/* handle a triangle or a quadrangle in a simple and efficient way. if the */
|
|
/* face is more complex than false is returned. */
|
|
/* */
|
|
/* if `keep_quads' is true then faces with four vertices will be stored as */
|
|
/* pairs of triangles in the array `quads'; any subsequent grouping of */
|
|
/* triangles into quads (if `do_quads' is true) will not effect those pairs */
|
|
/* of triangles! */
|
|
/* */
|
|
/* warning: the correctness of this function depends upon the fact that */
|
|
/* `CleanPolyhedralFace' has not yet been executed; i.e., the */
|
|
/* vertex indices have not been changed since the execution of */
|
|
/* `CleanPolyhedron'! (otherwise, we would have to get the original */
|
|
/* indices via calls to `GetOriginal'...) */
|
|
/* */
|
|
boolean SimpleFace(global_struct *all, list_ind ind1, boolean ears_fancy)
|
|
{
|
|
listdef *list = &all->c_list;
|
|
vertexdef *vert = &all->c_vertex;
|
|
datadef *data = &all->c_data;
|
|
|
|
tmp_data_def tmp_data;
|
|
|
|
list_ind ind0, ind2, ind3, ind4;
|
|
int i1, i2, i3, i4;
|
|
vertex pq, pr, nr;
|
|
double x, y, z;
|
|
int ori1, ori2, ori3, ori4;
|
|
|
|
|
|
ind0 = GetPrevNode(list, ind1);
|
|
if (ind0 == ind1) {
|
|
/* */
|
|
/* this polygon has only one vertex! nothing to triangulate... */
|
|
/* */
|
|
FIST_Warning("Polygon with only one vertex?!");
|
|
return true;
|
|
}
|
|
|
|
ind2 = GetNextNode(list, ind1);
|
|
i2 = GetIndex(list, ind2);
|
|
if (ind0 == ind2) {
|
|
/* */
|
|
/* this polygon has only two vertices! nothing to triangulate... */
|
|
/* */
|
|
FIST_Warning("Polygon with only two vertices?!");
|
|
return true;
|
|
}
|
|
|
|
ind3 = GetNextNode(list, ind2);
|
|
i3 = GetIndex(list, ind3);
|
|
if (ind0 == ind3) {
|
|
/* */
|
|
/* this polygon is a triangle! let's triangulate it! ;-) */
|
|
/* */
|
|
i1 = GetIndex(list, ind1);
|
|
StoreTriangle(all, ind1, ind2, ind3, TriTriColor);
|
|
return true;
|
|
}
|
|
|
|
ind4 = GetNextNode(list, ind3);
|
|
i4 = GetIndex(list, ind4);
|
|
if (ind0 == ind4) {
|
|
|
|
if (ears_fancy) return false; /* need to generate "nice" triangles */
|
|
|
|
/* */
|
|
/* this polygon is a quadrangle! not too hard to triangulate it... */
|
|
/* we project the corners of the quadrangle onto one of the coordinate */
|
|
/* planes */
|
|
/* */
|
|
InitPnts(data, 5);
|
|
i1 = GetIndex(list, ind1);
|
|
VectorSub(vert->vertices[i1], vert->vertices[i2], pq);
|
|
VectorSub(vert->vertices[i3], vert->vertices[i2], pr);
|
|
VectorProduct(pq, pr, nr);
|
|
x = Abs(nr.x);
|
|
y = Abs(nr.y);
|
|
z = Abs(nr.z);
|
|
if ((z >= x) && (z >= y)) {
|
|
data->points[1].x = vert->vertices[i1].x;
|
|
data->points[1].y = vert->vertices[i1].y;
|
|
data->points[2].x = vert->vertices[i2].x;
|
|
data->points[2].y = vert->vertices[i2].y;
|
|
data->points[3].x = vert->vertices[i3].x;
|
|
data->points[3].y = vert->vertices[i3].y;
|
|
data->points[4].x = vert->vertices[i4].x;
|
|
data->points[4].y = vert->vertices[i4].y;
|
|
}
|
|
else if ((x >= y) && (x >= z)) {
|
|
data->points[1].x = vert->vertices[i1].z;
|
|
data->points[1].y = vert->vertices[i1].y;
|
|
data->points[2].x = vert->vertices[i2].z;
|
|
data->points[2].y = vert->vertices[i2].y;
|
|
data->points[3].x = vert->vertices[i3].z;
|
|
data->points[3].y = vert->vertices[i3].y;
|
|
data->points[4].x = vert->vertices[i4].z;
|
|
data->points[4].y = vert->vertices[i4].y;
|
|
}
|
|
else {
|
|
data->points[1].x = vert->vertices[i1].x;
|
|
data->points[1].y = vert->vertices[i1].z;
|
|
data->points[2].x = vert->vertices[i2].x;
|
|
data->points[2].y = vert->vertices[i2].z;
|
|
data->points[3].x = vert->vertices[i3].x;
|
|
data->points[3].y = vert->vertices[i3].z;
|
|
data->points[4].x = vert->vertices[i4].x;
|
|
data->points[4].y = vert->vertices[i4].z;
|
|
}
|
|
data->num_pnts = 5;
|
|
|
|
/* */
|
|
/* find a valid diagonal */
|
|
/* */
|
|
Orientation(data, tmp_data, 1, 2, 3, ori2);
|
|
Orientation(data, tmp_data, 1, 3, 4, ori4);
|
|
|
|
if (((ori2 > 0) && (ori4 > 0)) ||
|
|
((ori2 < 0) && (ori4 < 0))) {
|
|
/* */
|
|
/* i1, i3 is a valid diagonal; */
|
|
/* */
|
|
if (all->rt_opt.keep_convex) {
|
|
Orientation(data, tmp_data, 2, 3, 4, ori3);
|
|
Orientation(data, tmp_data, 2, 4, 1, ori1);
|
|
if (((ori1 > 0) && (ori3 > 0)) ||
|
|
((ori1 < 0) && (ori3 < 0))) {
|
|
/* */
|
|
/* i2, i4 is a valid diagonal, too ---> convex quad. */
|
|
/* the triangles are (1, 2, 3) and (1, 3, 4). */
|
|
/* */
|
|
StoreQuad(vert, i1, i2, i3, i4);
|
|
}
|
|
else {
|
|
/* */
|
|
/* oops, this quad does seem to be non-convex. */
|
|
/* */
|
|
StoreTriangle(all, ind1, ind2, ind3, TriCveColor);
|
|
StoreTriangle(all, ind1, ind3, ind4, TriCveColor);
|
|
++vert->num_concave_loops;
|
|
}
|
|
}
|
|
else if (all->rt_opt.keep_quads) {
|
|
/* */
|
|
/* the triangles are (1, 2, 3) and (1, 3, 4). */
|
|
/* */
|
|
StoreQuad(vert, i1, i2, i3, i4);
|
|
}
|
|
else {
|
|
StoreTriangle(all, ind1, ind2, ind3, TriQuadColor);
|
|
StoreTriangle(all, ind1, ind3, ind4, TriQuadColor);
|
|
}
|
|
}
|
|
else {
|
|
/* */
|
|
/* i2, i4 has to be a valid diagonal. (if this is no valid */
|
|
/* diagonal then the corners of the quad form a figure of eight; */
|
|
/* shall we apply any heuristics in order to guess which diagonal */
|
|
/* is more likely to be the better choice? alternatively, we could */
|
|
/* return false and subject it to the standard triangulation */
|
|
/* algorithm. well, let's see how this brute-force solution works.) */
|
|
/* */
|
|
++vert->num_concave_loops;
|
|
if (all->rt_opt.keep_quads && !all->rt_opt.keep_convex)
|
|
/* */
|
|
/* the triangles are (1, 2, 4) and (2, 3, 4). */
|
|
/* */
|
|
StoreQuad(vert, i2, i3, i4, i1);
|
|
else {
|
|
StoreTriangle(all, ind2, ind3, ind4, TriCveColor);
|
|
StoreTriangle(all, ind2, ind4, ind1, TriCveColor);
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
|
|
|
|
|
|
boolean TrivialPolygon(global_struct *all, list_ind ind1)
|
|
{
|
|
listdef *list = &all->c_list;
|
|
#ifdef GRAPHICS
|
|
datadef *data = &all->c_data;
|
|
redrawdef *redraw = &all->c_redraw;
|
|
int i1, i2, i3;
|
|
#endif
|
|
|
|
list_ind ind2, ind3, ind0;
|
|
|
|
ind0 = GetPrevNode(list, ind1);
|
|
if (ind0 == ind1) {
|
|
/* */
|
|
/* this polygon has only one vertex! nothing to triangulate... */
|
|
/* */
|
|
FIST_Warning("Polygon with only one vertex?!");
|
|
return true;
|
|
}
|
|
|
|
ind2 = GetNextNode(list, ind1);
|
|
if (ind0 == ind2) {
|
|
/* */
|
|
/* this polygon has only two vertices! nothing to triangulate... */
|
|
/* */
|
|
FIST_Warning("Polygon with only two vertices?!");
|
|
return true;
|
|
}
|
|
|
|
ind3 = GetNextNode(list, ind2);
|
|
if (ind0 == ind3) {
|
|
/* */
|
|
/* this polygon is a triangle! let's triangulate it! ;-) */
|
|
/* */
|
|
StoreTriangle(all, ind1, ind2, ind3, TriTriColor);
|
|
|
|
/* */
|
|
/* insert the ear into the drawing buffer */
|
|
/* */
|
|
#ifdef GRAPHICS
|
|
if (all->rt_opt.graphics) {
|
|
i1 = GetIndex(list, ind1);
|
|
i2 = GetIndex(list, ind2);
|
|
i3 = GetIndex(list, ind3);
|
|
AddTriToBuffer(redraw, i1, i2, i3, TriColor, TriFillColor);
|
|
DrawTri(data->points[i1], data->points[i2], data->points[i3],
|
|
TriColor, TriFillColor);
|
|
}
|
|
#endif
|
|
return true;
|
|
}
|
|
|
|
return false;
|
|
}
|