SaraP
cbec90699f
- creato il progetto in Visual Studio per compilare come libreria statica - modifiche al codice originale per integrarlo nelle nostre librerie.
564 lines
26 KiB
C++
564 lines
26 KiB
C++
/*****************************************************************************/
|
|
/* */
|
|
/* F I S T */
|
|
/* */
|
|
/* Fast, Industrial-Strength Triangulation */
|
|
/* */
|
|
/* */
|
|
/* Written by: Martin Held */
|
|
/* */
|
|
/* E-Mail: held@cs.sbg.ac.at */
|
|
/* Fax Mail: (+43 662) 8044-611 */
|
|
/* Voice Mail: (+43 662) 8044-6304 */
|
|
/* Snail Mail: Martin Held */
|
|
/* FB Informatik */
|
|
/* Universitaet Salzburg */
|
|
/* A-5020 Salzburg, Austria */
|
|
/* */
|
|
/*****************************************************************************/
|
|
/* */
|
|
/* Copyright (C) 1997-2025 */
|
|
/* */
|
|
/* (C) Martin Held */
|
|
/* (C) Universitaet Salzburg, Salzburg, Austria */
|
|
/* */
|
|
/* */
|
|
/* This code is provided at no charge to you for non-commercial purposes */
|
|
/* only and only for use internal to your institution. You may use this */
|
|
/* code for academic evaluation and applications, following standard */
|
|
/* rules of academic conduct including crediting the author(s) and the */
|
|
/* copyright holder in any publications. This code is not in the public */
|
|
/* domain, and may not be duplicated, altered, sold or re-distributed */
|
|
/* without obtaining the prior written consent of the copyright holder. */
|
|
/* No part of this code may be used for or included in any commercial */
|
|
/* application unless your institution obtains a commercial license. */
|
|
/* Please contact the author, Martin Held (held@cs.sbg.ac.at), for */
|
|
/* commercial licensing terms. */
|
|
/* */
|
|
/* This code is provided as is, and you use it at your own risk. The */
|
|
/* University of Salzburg and the author accept no responsibility, to the */
|
|
/* extent permitted by applicable law, for the consequences of using it or */
|
|
/* for its usefulness for any particular application. */
|
|
/* */
|
|
/*****************************************************************************/
|
|
/* */
|
|
/* Please read the documentation in the directory READMEs/ before compiling */
|
|
/* or using this code! This file provides high-level API-functions for using */
|
|
/* FIST within your code. Since many users do not want to have to deal with */
|
|
/* dozens of options, the parameter lists are fairly short, and default */
|
|
/* values for most options are used. See InitDefaults() for a full list of */
|
|
/* run-time options. */
|
|
/* */
|
|
/* Please resort to the external-application macros provided in the file */
|
|
/* ext_appl_defs.h for customizing FIST in a non-invasive manner. */
|
|
/* */
|
|
/*****************************************************************************/
|
|
|
|
/* */
|
|
/* get standard libraries */
|
|
/* */
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <math.h>
|
|
#include <limits.h>
|
|
#include <float.h>
|
|
#include <string.h>
|
|
|
|
/* */
|
|
/* get my header files */
|
|
/* */
|
|
#include "fpkernel.h"
|
|
#include "martin.h"
|
|
#include "defs.h"
|
|
#include "header.h"
|
|
#include "api_fist.h"
|
|
|
|
|
|
/* */
|
|
/* function prototypes of functions provided in this file */
|
|
/* */
|
|
boolean FIST_2D_PolyArray(int num_contours, int num_vtx[],
|
|
double (*input_vtx)[2], int *num_tri,
|
|
int (*output_tri)[3]);
|
|
boolean FIST_3D_FaceArray(int num_contours, int num_vtx[],
|
|
double (*input_vtx)[3], int *num_tri,
|
|
int (*output_tri)[3]);
|
|
boolean FIST_HandlePolyhedron(rt_options *rt_opt);
|
|
boolean FIST_HandlePolygon(rt_options *rt_opt);
|
|
void FIST_TerminateProgram(global_struct *all);
|
|
void FIST_HandleError(errordef FistErrorCode);
|
|
|
|
const char* FIST_GetProgName();
|
|
const char* FIST_GetProgVersion();
|
|
const char* FIST_GetProgYear();
|
|
|
|
|
|
|
|
void FIST_TerminateProgram(global_struct *all)
|
|
{
|
|
listdef *list = &all->c_list;
|
|
heapdef *hp;
|
|
unsigned machine_long max_num_bytes = 0;
|
|
|
|
/* */
|
|
/* let the user call some application-specific function */
|
|
/* */
|
|
ExtApplFuncTerminateProg;
|
|
|
|
#ifdef PARTITION_FIST
|
|
for(int i = 0; i < all->number_of_heaps; ++i) {
|
|
hp = &all->c_heap[i];
|
|
FreeHeap(hp);
|
|
}
|
|
FreeMemory((debug_memdef*)&all->c_mem, (void**) &all->c_heap, "all:heaps");
|
|
FreeMemory((debug_memdef*)&all->c_mem, (void**) &all->corner_nodes, "all:corners");
|
|
#else
|
|
hp = &all->c_heap;
|
|
FreeHeap(hp);
|
|
#endif
|
|
FreeList(&all->c_list);
|
|
FreePnts(&all->c_data);
|
|
FreeTriangles(&all->c_vertex);
|
|
FreeQuads(&all->c_vertex);
|
|
FreeVertices(&all->c_vertex);
|
|
|
|
#ifdef NORMALS
|
|
FreeT_Vertices(&all->c_vertex);
|
|
FreeV_Normals(&all->c_vertex);
|
|
FreeI_Triangles(&all->c_vertex);
|
|
#endif
|
|
FreeDistances(&all->c_bridge);
|
|
FreeBridges(&all->c_bridge);
|
|
FreeUnsorted(&all->c_clean);
|
|
FreeOrientation(all);
|
|
FreeGroups(&all->c_vertex);
|
|
FreeConvexLoops(&all->c_vertex);
|
|
FreeGrid(&all->c_grid);
|
|
#ifdef GRAPHICS
|
|
FreeDrawingBuffer(&all->c_redraw);
|
|
#endif
|
|
|
|
max_num_bytes = ReportMaxNumberBytes(list->memptr);
|
|
|
|
if (all->rt_opt.verbose) {
|
|
if (max_num_bytes > 0) {
|
|
printf("\nMemory allocation and deallocation was correct!\n");
|
|
printf("Maximum number of bytes allocated: %lu\n\n",
|
|
max_num_bytes);
|
|
}
|
|
if (!AllMemoryFreed(list->memptr)) {
|
|
FIST_Warning("Compute() - Memory has been allocated but not freed!\n");
|
|
}
|
|
}
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
/* */
|
|
/* FIST exception handling. it does not do more than to issue a statement */
|
|
/* that describes the error encountered. however, the user can influence it */
|
|
/* in a non-invasive manner by setting ExtApplFuncFIST_HandleError. */
|
|
/* */
|
|
void FIST_HandleError(errordef FistErrorCode)
|
|
{
|
|
switch (FistErrorCode) {
|
|
case MEM_ALLOC_FAILED:
|
|
fprintf(stderr,
|
|
"\n*** FIST exception: memory (re-)allocation failed ***\n");
|
|
break;
|
|
case FILE_ACCESS_FAILED:
|
|
fprintf(stderr,
|
|
"\n*** FIST exception: I/O file could not be opened ***\n");
|
|
break;
|
|
case INSUFFICENT_INPUT:
|
|
fprintf(stderr,
|
|
"\n*** FIST exception: less than three/four input vertices ***\n");
|
|
break;
|
|
case EOF_ENCOUNTERED:
|
|
fprintf(stderr,
|
|
"\n*** FIST exception: end-of-file encountered during file input ***\n");
|
|
break;
|
|
case WRONG_INPUT_OPTION:
|
|
fprintf(stderr,
|
|
"\n*** FIST exception: no suitable option for reading file input ***\n");
|
|
break;
|
|
case WRONG_OBJ_FORMAT:
|
|
fprintf(stderr,
|
|
"\n*** FIST exception: .OBJ input file could not be read properly ***\n");
|
|
break;
|
|
case MEM_TRACKING_EXHAUSTED:
|
|
fprintf(stderr,
|
|
"\n*** FIST exception: array for memory tracking exhausted ***\n");
|
|
break;
|
|
case MEM_REALLOC_MISMATCH:
|
|
fprintf(stderr,
|
|
"\n*** FIST exception: size of realloc elements does not match orginal size ***\n");
|
|
break;
|
|
case MEM_TRACKING_MESSED_UP:
|
|
fprintf(stderr,
|
|
"\n*** FIST exception: tracking of memory (de-)allocation messed up ***\n");
|
|
break;
|
|
case MEM_TYPE_MISMATCH:
|
|
fprintf(stderr,
|
|
"\n*** FIST exception: type mismatch during memory access ***\n");
|
|
break;
|
|
case MEM_NULL_POINTER:
|
|
fprintf(stderr,
|
|
"\n*** FIST exception: index out of bounds due to null array pointer ***\n");
|
|
break;
|
|
case IPE_FILE_NOT_INITIALIZED:
|
|
fprintf(stderr,
|
|
"\n*** FIST exception: IPE output file is not initialized ***\n");
|
|
break;
|
|
case IPE_FILE_INIT_FAILED:
|
|
fprintf(stderr,
|
|
"\n*** FIST exception: IPE output file could not be initialized ***\n");
|
|
break;
|
|
default:
|
|
fprintf(stderr,
|
|
"\n*** FIST exception: unknown exception encountered ***\n");
|
|
}
|
|
|
|
ExtApplFuncFIST_HandleError;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
/* */
|
|
/* This function reads a polyhedron in .obj format from a file and computes */
|
|
/* a triangulation of its surface. Please note that it is your */
|
|
/* responsibility to fill the "rt_opt" structure appropriately. In */
|
|
/* particular, you will have to specify an input file; see InitDefaults(). */
|
|
/* Input and output of data is carried out via file I/O. */
|
|
/* */
|
|
boolean FIST_HandlePolyhedron(rt_options *rt_opt)
|
|
{
|
|
global_struct all;
|
|
boolean success = true;
|
|
|
|
try {
|
|
/* */
|
|
/* initialize FIST's main data structures */
|
|
/* */
|
|
InitGlobalStruct(&all, rt_opt, true);
|
|
|
|
/* */
|
|
/* let the user influence the code; e.g., modify run-time options */
|
|
/* */
|
|
ExtApplFuncHandlePolyhedronStart;
|
|
|
|
/* */
|
|
/* read a polyhedron in OBJ-format */
|
|
/* */
|
|
if (rt_opt->verbose) {
|
|
fprintf(stdout, "\n...reading the input data: ");
|
|
fflush(stdout);
|
|
}
|
|
ReadPolyhedron(&all, rt_opt->input_file);
|
|
if (rt_opt->verbose) {
|
|
fprintf(stdout, "done!\n");
|
|
fflush(stdout);
|
|
}
|
|
|
|
/* */
|
|
/* triangulate the faces of the polyhedron */
|
|
/* */
|
|
if (!rt_opt->quiet) {
|
|
fprintf(stdout, "...processing file: `%s'\n", rt_opt->input_file);
|
|
fflush(stdout);
|
|
}
|
|
Triangulate(&all);
|
|
}
|
|
catch (errordef FistErrorCode) {
|
|
FIST_HandleError(FistErrorCode);
|
|
success = false;
|
|
}
|
|
|
|
/* */
|
|
/* print statistics data */
|
|
/* */
|
|
StatisticsFIST(&all);
|
|
|
|
/* */
|
|
/* let the user influence the code */
|
|
/* */
|
|
ExtApplFuncHandlePolyhedronEnd;
|
|
|
|
/* */
|
|
/* free memory and terminate FIST */
|
|
/* */
|
|
FIST_TerminateProgram(&all);
|
|
|
|
return success;
|
|
}
|
|
|
|
|
|
|
|
/* */
|
|
/* This function inputs the boundary of a polygonal area in one of my input */
|
|
/* formats, triangulates it, and writes the data to a file (if requested). */
|
|
/* no interactive OpenGL graphics is supported. See main() for how to use */
|
|
/* my code in conjunction with interactive graphics. Please note that it is */
|
|
/* your responsibility to fill the "rt_opt" structure appropriately. In */
|
|
/* particular, you will have to specify an input file; see InitDefaults(). */
|
|
/* Input and output of data is carried out via file I/O. */
|
|
/* */
|
|
boolean FIST_HandlePolygon(rt_options *rt_opt)
|
|
{
|
|
global_struct all;
|
|
boolean success = true;
|
|
|
|
try {
|
|
/* */
|
|
/* initialize FIST's main data structures */
|
|
/* */
|
|
InitGlobalStruct(&all, rt_opt, true);
|
|
|
|
/* */
|
|
/* let the user influence the code; e.g., modify run-time options */
|
|
/* */
|
|
ExtApplFuncHandlePolygonStart;
|
|
|
|
/* */
|
|
/* read 2D data from input file */
|
|
/* */
|
|
Read2DInputData(&all);
|
|
|
|
/* */
|
|
/* no interactive graphics; triangulate the polygon */
|
|
/* */
|
|
if (!rt_opt->quiet) {
|
|
fprintf(stdout, "...processing file: `%s'\n", rt_opt->input_file);
|
|
fflush(stdout);
|
|
}
|
|
Compute(&all);
|
|
}
|
|
catch (errordef FistErrorCode) {
|
|
FIST_HandleError(FistErrorCode);
|
|
success = false;
|
|
}
|
|
|
|
/* */
|
|
/* print statistics data */
|
|
/* */
|
|
StatisticsFIST(&all);
|
|
|
|
/* */
|
|
/* let the user influence the code */
|
|
/* */
|
|
ExtApplFuncHandlePolygonEnd;
|
|
|
|
/* */
|
|
/* free memory and terminate FIST */
|
|
/* */
|
|
FIST_TerminateProgram(&all);
|
|
|
|
return success;
|
|
}
|
|
|
|
|
|
/* */
|
|
/* This is a bare-bones interface to FIST. It allows the user to pass */
|
|
/* 2D contour data to FIST, and to receive the triangulation computed */
|
|
/* without having to resort to file I/O. */
|
|
/* */
|
|
/* num_contours ... number of input contours; the contours have to define */
|
|
/* a multiply-connected polygonal area bounded by one */
|
|
/* outer contour and possibly several island contours. */
|
|
/* num_vtx[i] ... number of vertices of contour i, starting with i=0. */
|
|
/* input_vtx[i] ... x,y-coordinates of vertex i. */
|
|
/* num_tri ... number of triangles computed. */
|
|
/* output_tri[i] ... indices of the vertices of triangle i. */
|
|
/* */
|
|
/* Note: A polygonal area with a total of N vertices and H holes has exactly */
|
|
/* N - 2 + 2 * H */
|
|
/* triangles. */
|
|
/* */
|
|
/* Please note that it is the responsibility of the user to allocate enough */
|
|
/* memory for the arrays num_vertices, input_vtx, and output_tri!!!! */
|
|
/* FIST will assume that the array bounds and the information on the number */
|
|
/* of input contours and input vertices are consistent! */
|
|
/* */
|
|
boolean FIST_2D_PolyArray(int num_contours, /* #(contours) */
|
|
int num_vtx[], /* #(vertices) per contour */
|
|
double (*input_vtx)[2] , /* x,y-coordinates */
|
|
int *num_tri, /* #(output triangles) */
|
|
int (*output_tri)[3]) /* vtx indices of triangles */
|
|
{
|
|
global_struct all;
|
|
boolean success = true;
|
|
|
|
try {
|
|
/* */
|
|
/* anything to triangulate? */
|
|
/* */
|
|
*num_tri = 0;
|
|
if (num_contours <= 0) {
|
|
*num_tri = 0;
|
|
return true;
|
|
}
|
|
|
|
/* */
|
|
/* initialize default run-time options and perform initializations for */
|
|
/* the various numerical backends that can be used in conjunction with */
|
|
/* FIST. also, initialize FIST's main data structures */
|
|
/* */
|
|
InitGlobalStruct(&all, (rt_options*)NULL, false);
|
|
|
|
/* */
|
|
/* let the user influence the code; e.g., modify run-time options */
|
|
/* */
|
|
ExtApplFunc2D_PolyArrayStart;
|
|
|
|
/* */
|
|
/* fill the user data into FIST's data structures. */
|
|
/* */
|
|
CopyInputData2D(&all, num_contours, num_vtx, input_vtx);
|
|
|
|
/* */
|
|
/* no interactive graphics; triangulate the polygon. */
|
|
/* */
|
|
Compute(&all);
|
|
|
|
/* */
|
|
/* get the output data. */
|
|
/* */
|
|
CopyOutputData(&all.c_vertex, num_tri, output_tri);
|
|
}
|
|
catch (errordef FistErrorCode) {
|
|
FIST_HandleError(FistErrorCode);
|
|
success = false;
|
|
}
|
|
|
|
/* */
|
|
/* print statistics data */
|
|
/* */
|
|
StatisticsFIST(&all);
|
|
|
|
/* */
|
|
/* let the user influence the code */
|
|
/* */
|
|
ExtApplFunc2D_PolyArrayEnd;
|
|
|
|
/* */
|
|
/* free memory and terminate FIST */
|
|
/* */
|
|
FIST_TerminateProgram(&all);
|
|
|
|
return success;
|
|
}
|
|
|
|
|
|
/* */
|
|
/* This is a bare-bones interface to FIST. It allows the user to pass */
|
|
/* 3D contour data to FIST, and to receive the triangulation computed */
|
|
/* without having to resort to file I/O. */
|
|
/* */
|
|
/* num_contours ... number of input contours; the contours have to define */
|
|
/* a multiply-connected polygonal area bounded by one */
|
|
/* outer contour and possibly several island contours. */
|
|
/* num_vtx[i] ... number of vertices of contour i, starting with i=0. */
|
|
/* input_vtx[i] ... x,y,z-coordinates of vertex i. */
|
|
/* num_tri ... number of triangles computed. */
|
|
/* output_tri[i] ... indices of the vertices of triangle i. */
|
|
/* */
|
|
/* Please note that it is the responsibility of the user to allocate enough */
|
|
/* memory for the arrays num_vertices, input_vtx, and output_tri!!!! */
|
|
/* FIST will assume that the array bounds and the information on the number */
|
|
/* of input contours and input vertices are consistent! */
|
|
/* */
|
|
boolean FIST_3D_FaceArray(int num_contours, /* #(contours) */
|
|
int num_vtx[], /* #(vertices) per contour */
|
|
double (*input_vtx)[3], /* x,y,z-coordinates */
|
|
int *num_tri, /* #(output triangles) */
|
|
int (*output_tri)[3]) /* vtx indices of triangles */
|
|
{
|
|
global_struct all;
|
|
boolean success = true;
|
|
|
|
try {
|
|
/* */
|
|
/* anything to triangulate? */
|
|
/* */
|
|
*num_tri = 0;
|
|
if (num_contours <= 0) {
|
|
*num_tri = 0;
|
|
return true;
|
|
}
|
|
|
|
/* */
|
|
/* initialize default run-time options and perform initializations for */
|
|
/* the various numerical backends that can be used in conjunction with */
|
|
/* FIST. also, initialize FIST's main data structures */
|
|
/* */
|
|
InitGlobalStruct(&all, (rt_options*)NULL, false);
|
|
|
|
/* */
|
|
/* let the user influence the code; e.g., modify run-time options */
|
|
/* */
|
|
ExtApplFunc3D_FaceArrayStart;
|
|
|
|
/* */
|
|
/* fill the user data into FIST's data structures. */
|
|
/* */
|
|
CopyInputData3D(&all, num_contours, num_vtx, input_vtx);
|
|
|
|
/* */
|
|
/* no interactive graphics; triangulate the polygon. */
|
|
/* */
|
|
Triangulate(&all);
|
|
|
|
/* */
|
|
/* get the output data. */
|
|
/* */
|
|
CopyOutputData(&all.c_vertex, num_tri, output_tri);
|
|
}
|
|
catch (errordef FistErrorCode) {
|
|
FIST_HandleError(FistErrorCode);
|
|
success = false;
|
|
}
|
|
|
|
/* */
|
|
/* print statistics data */
|
|
/* */
|
|
StatisticsFIST(&all);
|
|
|
|
/* */
|
|
/* let the user influence the code */
|
|
/* */
|
|
ExtApplFunc3D_FaceArrayEnd;
|
|
|
|
/* */
|
|
/* free memory and terminate FIST */
|
|
/* */
|
|
FIST_TerminateProgram(&all);
|
|
|
|
return success;
|
|
}
|
|
|
|
|
|
const char* FIST_GetProgName()
|
|
{
|
|
return PROG_NAME;
|
|
}
|
|
|
|
|
|
|
|
const char* FIST_GetProgVersion()
|
|
{
|
|
return PROG_VERSION;
|
|
}
|
|
|
|
|
|
|
|
const char* FIST_GetProgYear()
|
|
{
|
|
return PROG_YEAR;
|
|
}
|
|
|
|
|
|
|
|
#include "ext_appl_defs.cpp"
|