/*****************************************************************************/ /* */ /* 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 #include #include /* */ /* get my header files */ /* */ #include "fpkernel.h" #include "martin.h" #include "defs.h" #include "basic.h" #include "header.h" /* */ /* function prototypes of functions provided in this file */ /* */ FILE *OpenFile(const char *file_name, const char *access); void FIST_Warning(const char string[]); void Copyright(void); void CopyOutputData(vertexdef *vert, int *num_tri, int (*output_tri)[3]); void CopyInputData2D(global_struct *all, int num_contours, int *num_vtx, double (*input_vtx)[2]); void Help(void); FILE *OpenFile(const char *file_name, const char *access) { FILE *file = NULL; if ((file = fopen(file_name, access)) == NULL) throw FILE_ACCESS_FAILED; return file; } void FIST_Warning(const char string[]) { ExtApplFuncFISTWarning; #ifdef INFO fprintf(stderr, "%s", string); #else (void) string; #endif return; } void Copyright(void) { printf("\n"); printf("(***********************************************************"); printf("******************)\n"); printf("(* "); printf(" *)\n"); printf("(* Copyright (C) %9s M. Held", PROG_YEAR); printf(" *)\n"); printf("(* "); printf(" *)\n"); printf("(* "); printf(" *)\n"); printf("(* %9s %5s ", PROG_NAME, PROG_VERSION); printf(" *)\n"); printf("(* "); printf(" *)\n"); printf("(* Fast, Industrial-Strength Triangulation"); printf(" *)\n"); printf("(* "); printf(" *)\n"); printf("(* "); printf(" *)\n"); printf("(* Start this program as `fist --help' in order to get a sho"); printf("rt summary of *)\n"); printf("(* how to use it. "); printf(" *)\n"); printf("(* "); printf(" *)\n"); printf("(* Please report bugs to held@cs.sbg.ac.at. "); printf(" *)\n"); printf("(* "); printf(" *)\n"); printf("(* "); printf(" *)\n"); printf("(* "); printf(" *)\n"); printf("(* C O P Y R I G H T "); printf(" *)\n"); printf("(* "); printf(" *)\n"); printf("(* This code is provided at no charge to you for purely non-profit purposes *)\n"); printf("(* and only for use internal to your institution. You may use this code for *)\n"); printf("(* academic applications, following standard rules of academic conduct *)\n"); printf("(* including crediting the author(s) and the copyright holder in any *)\n"); printf("(* publication. This code is not in the public domain, and no parts of it *)\n"); printf("(* may be duplicated, altered, sold, re-distributed (in either source-code *)\n"); printf("(* or binary format), or used as a blueprint for somebody else's own *)\n"); printf("(* implementation without obtaining the prior written consent of the *)\n"); printf("(* copyright holder. All rights reserved! *)\n"); printf("(* *)\n"); printf("(* Free use of this code is restricted to purely non-profit purposes within *)\n"); printf("(* academic research institutions. Absolutely all other forms of use require *)\n"); printf("(* the signing of a non-disclosure agreement or of a commercial license. *)\n"); printf("(* Please contact me, Martin Held (held@cs.sbg.ac.at), for commercial *)\n"); printf("(* evaluation and licensing terms. *)\n"); printf("(* *)\n"); printf("(* D I S C L A I M E R *)\n"); printf("(* *)\n"); printf("(* In any case, this code is provided `as is', and you use it at your own *)\n"); printf("(* risk. The author does not accept any responsibility, to the extent *)\n"); printf("(* permitted by applicable law, for the consequences of using it or for its *)\n"); printf("(* usefulness for any particular application. *)\n"); printf("(* "); printf(" *)\n"); printf("(***********************************************************"); printf("******************)\n"); printf("\n"); return; } void Help(void) { printf("\n\n"); printf("(***********************************************************"); printf("******************)\n"); printf("(* "); printf(" *)\n"); printf("(* This program triangulates one multiply-connected planar p"); printf("olygonal area, *)\n"); printf("(* or all the faces of a 3D polyhedron. The program attempts"); printf(" to compute a *)\n"); printf("(* triangulation that is reasonable even if the polygon is n"); printf("ot simple, if *)\n"); printf("(* the outer boundary and the holes overlap, or if the verti"); printf("ces of a *)\n"); printf("(* polyhedral face are non-coplanar. "); printf(" *)\n"); printf("(* "); printf(" *)\n"); printf("(* The program can input and output data in my own file form"); printf("at for *)\n"); printf("(* curvilinear data, or it can input and output an OBJ-file."); printf(" Also, data can *)\n"); printf("(* be entered interactively via the drawing canvas, and the "); printf("computed *)\n"); printf("(* triangulation can be output in format suitable for Geomvi"); printf("ew. (For 2D *)\n"); printf("(* polygons, a (random) z-coordinate is added in the Geomvie"); printf("w output.) *)\n"); printf("(* Polygonal data can also be output in a format suitable fo"); printf("r Ipe, and thus *)\n"); printf("(* be converted to a valid Postscript file by means of Ipe. "); printf(" *)\n"); printf("(* Start this program as `triangulation --help' in order to "); printf("get a short *)\n"); printf("(* summary of how to use it. "); printf(" *)\n"); printf("(* "); printf(" *)\n"); printf("(* Please make sure to read the files README and README.data"); printf(". *)\n"); printf("(* "); printf(" *)\n"); printf("(***********************************************************"); printf("******************)\n"); printf("\n\nSummary of keyboard short-cuts used in the OpenGL interface:\n\n"); printf("`h' ... hit the `h'-key while the cursor is within the drawing\n"); printf(" canvas in order to reproduce this message.\n"); printf("`p' ... tells my code that you will now enter a new polygon.\n"); printf(" the vertices of the polygon are entered via mouse"); printf("-clicks\n"); printf("`c' ... to close the polygonal chain which you have entered.\n"); printf("`t' ... to triangulate the polygonal area. It is also used for\n"); printf(" advancing the graphics display if `--step' was selected\n"); printf(" as a command-line option.\n"); printf("`u' ... to redraw the entities displayed in the drawing canvas;\n"); printf(" it also resizes the display such that all entities fit\n"); printf(" nicely within the graphics window.\n"); printf("`i' ... to zoom in.\n"); printf("`o' ... to zoom out.\n"); printf("`z' ... to zoom into a rectangular region; this region is "); printf("specified\n"); printf(" by clicking first at its lower-left and then at its\n"); printf(" upper-right corner.\n"); printf("`d' ... to erase the drawing canvas and delete all data.\n"); printf("`m' ... toggle; draw or do not draw the vertex markers.\n"); printf("`1' ... toggle; draw or do not draw the data points index.\n"); printf("`f' ... toggle; fill or do not fill the triangles.\n"); printf("`q' ... to terminate the program.\n"); printf("\nPlease note that the interface does not recognize upper-case "); printf("letters.\n"); printf("\nA listing of the command-line options is produced by using the "); printf("option `--help'.\n\n"); printf("Color codes used in the OpenGL graphics:\n"); printf("yellow ...... contour segments.\n"); printf("red ......... bridges and triangulation edges.\n"); printf("grey ........ triangles (clipped ears).\n"); printf("blue ........ (reflex) vertices.\n"); printf("magenta ..... ears (convex vertices that can be clipped).\n"); printf("cyan ........ convex vertices which are no ears.\n"); printf("green ....... convex vertices with 0 degree angle.\n"); printf("orange ...... reflex vertices with 180 degree angle.\n"); printf("white ....... split lines for non-simple polygons.\n\n"); return; } void CopyPolyData(global_struct *all, int v0, int number, double (*input_vtx)[2]) { listdef *list = &all->c_list; datadef *data = &all->c_data; int i, j, first_pnt, curr_loop, v_max; double xc1, yc1; list_ind ind, last_ind; if (number < 3) throw INSUFFICENT_INPUT; InitStoragePnts(data, number); InitStorageList(list, number+1); curr_loop = MakeLoopHeader(list); xc1 = input_vtx[v0][0]; yc1 = input_vtx[v0][1]; #ifdef EXT_APPL_SITES first_pnt = StorePnt(data, xc1, yc1, eas_NIL); #else first_pnt = StorePnt(data, xc1, yc1); #endif //last_pnt = first_pnt; last_ind = list->loops[curr_loop]; ind = MakeNode(list, first_pnt); InsertAfter(list, last_ind, ind); last_ind = ind; if (xc1 < all->bb_min.x) all->bb_min.x = xc1; if (xc1 > all->bb_max.x) all->bb_max.x = xc1; if (yc1 < all->bb_min.y) all->bb_min.y = yc1; if (yc1 > all->bb_max.y) all->bb_max.y = yc1; v_max = v0 + number; for (i = v0 + 1; i < v_max; ++i) { xc1 = input_vtx[i][0]; yc1 = input_vtx[i][1]; #ifdef EXT_APPL_SITES j = StorePnt(data, xc1, yc1, eas_NIL); #else j = StorePnt(data, xc1, yc1); #endif //last_pnt = j; ind = MakeNode(list, j); InsertAfter(list, last_ind, ind); last_ind = ind; if (xc1 < all->bb_min.x) all->bb_min.x = xc1; else if (xc1 > all->bb_max.x) all->bb_max.x = xc1; if (yc1 < all->bb_min.y) all->bb_min.y = yc1; else if (yc1 > all->bb_max.y) all->bb_max.y = yc1; } DeleteHook(list, curr_loop); return; } void CopyInputData2D(global_struct *all, int num_contours, int *num_vtx, double (*input_vtx)[2]) { int i, v0 = 0; all->bb_min.x = all->bb_min.y = fpkernel_DBL_MAX; all->bb_max.x = all->bb_max.y = - fpkernel_DBL_MAX; InitStorageLoops(&all->c_list, num_contours); all->num_contours = num_contours; for (i = 0; i < num_contours; ++i) { assert(num_vtx[i] >= 3); CopyPolyData(all, v0, num_vtx[i], input_vtx); v0 += num_vtx[i]; } all->new_input = true; return; } void CopyOutputData(vertexdef *vert, int *num_tri, int (*output_tri)[3]) { int i; *num_tri = vert->num_triangles; for (i = 0; i < vert->num_triangles; ++i) { #ifdef PARTITION_FIST if(vert->triangles[i].disabled) continue; #endif output_tri[i][0] = vert->triangles[i].v1; output_tri[i][1] = vert->triangles[i].v2; output_tri[i][2] = vert->triangles[i].v3; } return; } void CopyInputData3D(global_struct *all, int num_contours, int *num_vtx, double (*input_vtx)[3]) { vertexdef *vert = &all->c_vertex; listdef *list = &all->c_list; boolean face_received = false; int i, j, v0 = 0, index, v_max; int curr_loop; list_ind ind = NIL, last_ind; double xc1, yc1, zc1; InitFace(list, num_contours); /* set the number of loops for this face */ for (i = 0; i < num_contours; ++i) { curr_loop = MakeLoopHeader(list); last_ind = list->loops[curr_loop]; if (num_vtx[i] < 3) throw INSUFFICENT_INPUT; v_max = v0 + num_vtx[i]; for (j = v0; j < v_max; ++j) { xc1 = input_vtx[j][0]; yc1 = input_vtx[j][1]; zc1 = input_vtx[j][2]; #ifdef EXT_APPL_SITES index = StoreVertex(vert, xc1, yc1, zc1, eas_NIL); #else index = StoreVertex(vert, xc1, yc1, zc1); #endif ind = MakeNode(list, index); InsertAfter(list, last_ind, ind); SetOriginal(list, ind, index); last_ind = ind; } if (ind != NIL) { DeleteHook(list, curr_loop); face_received = true; } else { /* this was a loop without vertices... */ DecrementLoops(list); } v0 += num_vtx[i]; } if (!face_received) { DecrementFaces(list); } else { StoreGroupNumber(list,vert); } return; }