/*****************************************************************************/ /* */ /* 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 /* */ /* get my header files */ /* */ #include "fpkernel.h" #include "martin.h" #include "defs.h" #include "header.h" #ifndef NO_CPUTIME #include #endif #ifdef PARTITION_FIST #define PARALLEL_MINIMUM 1000 #endif /* */ /* function prototypes of functions provided in this file */ /* */ void Compute(global_struct *all); void StatisticsFIST(global_struct *all); void ResetAll(global_struct *all); /* */ /* this subroutine drives the computation of the triangulation of a polygon. */ /* the polygon has to be planar but may contain multiple loops. all loops of */ /* the polygon are referenced via the array loops[0,..,num_loops-1], for a */ /* total of num_loops loops. */ /* */ /* if Compute() were to be called from a user's application program then it */ /* is the responsibility of this application program to initialize all */ /* arrays appropriately. see ReadPolygon() in io_2D.c, or ReadDXFFile() in */ /* io_dxf.c. */ /* */ void Compute(global_struct *all) { vertexdef *vert = &all->c_vertex; listdef *list = &all->c_list; datadef *data = &all->c_data; griddef *grid = &all->c_grid; eardef *ear = &all->c_ear; heapdef *hp; rt_options *rt_opt = &all->rt_opt; int removed, i, num_reflex; boolean got_it; list_ind ind; #ifdef PARTITION_FIST hp = &all->c_heap[0]; #else hp = &all->c_heap; #endif if ((data->num_pnts <= 0) && rt_opt->verbose) { FIST_Warning("Compute() - nothing to triangulate!\n"); return; } if (rt_opt->time) all->cpu_time = elapsed(all); #ifdef BENCHMARK else all->cpu_time = elapsed(all); #endif if (all->new_input) { /* */ /* make sure that all polygons are closed even when my code is not */ /* used properly. */ /* */ EnsureClosedPolygon(all); #ifdef BENCHMARK gettimeofday(&all->start, NULL); #endif /* */ /* initialize or reset local variables. */ /* */ all->reset = false; all->troubles = false; all->written = false; all->done = false; all->num_contours = list->num_loops; /* */ /* the input has been changed; generate fake 3D vertices. this also */ /* saves the original 2D vertex data. */ /* */ Fake3D(all); InitTriangles(vert, data->num_pnts + 2 * list->num_loops); /* */ /* sort the vertices in lexicographic order, discard duplicate */ /* vertices. also, it resets the "loops" pointers such that every loop */ /* points to its left-most vertex. */ /* */ CleanPolygon(all, &removed); /* */ /* remove zero-length edges */ /* */ if (removed > 0) { #ifdef PARTITION_FIST #pragma omp parallel for default(shared) schedule(dynamic, 1) #endif for (i = 0; i < list->num_loops; ++i) { RemoveZeroEdges(list, &(list->loops[i])); } } /* */ /* compute the bounding box of the polygon(s), and scale the data if */ /* requested by the user. */ /* */ SetBoundingBox(data, &all->bb_min, &all->bb_max); if (rt_opt->scale_data) { ScaleData(all); #ifdef GRAPHICS if (rt_opt->graphics && data->data_scaled) UpdateScaleData(); #endif } else { data->data_scaled = false; } /* */ /* determine the outer polygon and the orientation of the polygons; */ /* the default orientation is CCW for the outer polygon, and CW for */ /* the inner polygons. */ /* */ AdjustOrientation(all, 0, list->num_loops); if (rt_opt->c2p) { WritePolyFormat(all); return exit(EXIT_SUCCESS); } if (rt_opt->save_poly) WritePolygon(all, rt_opt->output_file); if (rt_opt->write_ipe7) WriteIpePolygon(all); if (list->num_loops > 1) BuildGrid(all, 0, list->num_loops); else grid->no_grid_yet = true; /* */ /* mark those vertices whose interior angle is convex */ /* */ num_reflex = 0; for (i = 0; i < list->num_loops; ++i) { ClassifyAngles(all, list->loops[i], &num_reflex); } /* */ /* link the holes with the outer boundary by means of "bridges" */ /* */ if (list->num_loops > 1) { assert(num_reflex > 0); if (rt_opt->verbose) { fprintf(stdout, "...linking all %d islands with the outer boundary: ", list->num_loops - 1); fflush(stdout); } ConstructBridges(all, 0, list->num_loops); if (rt_opt->verbose) { fprintf(stdout, "done!\n"); fflush(stdout); } } /* */ /* put all ears into a circular linked list */ /* */ SetReflexNumber(all, num_reflex); if (num_reflex > 0) { BuildBuckets(all, list->loops[0]); } else { all->is_convex_face = true; SetConvexityStatus(ear, true); } if (rt_opt->ears_fancy) { BuildPntsGrid(all, 0); } if (!all->is_convex_face) ++vert->num_concave_loops; /* */ /* classify all ears unless the polygon is trivial */ /* */ if (rt_opt->verbose) { fprintf(stdout, "...classifying all ears: "); fflush(stdout); } #ifdef PARTITION_FIST /* for the parallel clipping we require a certain minimum of vertices */ if (data->num_pnts < PARALLEL_MINIMUM) all->partition_mode = false; if (data->num_pnts <= 3) vert->num_triangles = vert->max_num_triangles; #endif if (data->num_pnts > 3) { ClassifyEars(all, list->loops[0]); } else { if (TrivialPolygon(all, list->loops[0])) all->done = true; } if (rt_opt->verbose) { fprintf(stdout, "done!\n"); fflush(stdout); } /* */ /* let the user call some application-specific function */ /* */ ExtApplFuncNewInput; #ifdef GRAPHICS if (rt_opt->graphics && (rt_opt->step_size < INT_MAX)) return; #else (void) rt_opt->step_size; #endif } /* FIST-Partition is an ear-clipping approach to clip the contour in * parallel using OpenMP. The contour is partitioned into #core segments * and for each segment we use a different heap. The triangle array * stays the same but the saving is realized differently. We store each * triangle on the array position that equals the index of the vertex * which was removed from the contour. This enables us to store triangles * without any locking or semaphores. */ #ifdef PARTITION_FIST if (!all->done) { InitTriangles(vert, list->num_list); vert->num_triangles = list->num_list; if (all->partition_mode) { if (rt_opt->verbose) { fprintf(stdout, "...performing parallel ear-clipping: "); fflush(stdout); } #pragma omp parallel for default(shared) private(hp) for(int p = 0; p < all->number_of_heaps; ++p) { hp = &all->c_heap[p]; boolean done = false; while (!done) { if (!ClipEar(all, hp, &done)) { #ifdef INFO if (rt_opt->verbose) { fprintf(stdout, "(a problem occoured in thread %i) ",hp->heap_idx); fflush(stdout); } #endif done = true; } } } all->partition_mode = false; #pragma omp parallel for schedule(dynamic, 1) for(int p = 0; p < list->num_list; ++p) { if(list->list[p].delete_reflex) DeleteReflexVertex(all, p); } if (rt_opt->verbose) { fprintf(stdout, "done! (%i triangles)\n",GetNumTriangles(vert)); fflush(stdout); } hp = &all->c_heap[0]; InitHeap(hp, data); ClassifyAngles(all, list->first_node, &num_reflex); ClassifyEars(all, list->first_node); } /* end-if all->partition_mode */ }/* end-if !all->done */ #endif /* end-if PARTITION_FIST */ if (rt_opt->verbose) { fprintf(stdout, "...performing ear-clipping: "); fflush(stdout); } i = 0; #ifdef GRAPHICS while ((i < rt_opt->step_size) && !all->done) { #else while (!all->done) { #endif if (!ClipEar(all, hp, &all->done)) { if (all->reset) { #ifdef INFO if (!rt_opt->quiet) { FIST_Warning("Compute() - no further ear to clip!\n"); FIST_Warning("Compute() - not a simple polygon, isn't it?\n"); } #endif ind = GetNode(list); ResetPolyList(list, ind); list->loops[0] = ind; if (Desperate(all, hp, ind, 0, &all->done)) { /* */ /* let the user call some application-specific function */ /* */ ExtApplFuncDesperate; #ifdef INFO if (!rt_opt->quiet) FIST_Warning("Compute() - let's hope for the best...\n"); #endif if (!LetsHope(all, hp, ind)) { /* */ /* let the user call some application-specific function */ /* */ ExtApplFuncReligious; #ifdef INFO FIST_Warning("Compute() - sorry, I can't do it!\n"); FIST_Warning("Compute() - ask a triangulation wizard, or clean-up your polygon!\n"); #endif return; } } else { all->reset = false; } } else { /* */ /* try again from scratch */ /* */ all->troubles = true; #ifdef INFO if (rt_opt->verbose) FIST_Warning("Compute() - re-classifying the ears!\n"); #endif ind = GetNode(list); ResetPolyList(list, ind); ClassifyEars(all, ind); all->reset = true; /* */ /* let the user call some application-specific function */ /* */ ExtApplFuncRestart; } } else { all->reset = false; ++i; } if (all->done) { /* */ /* let the user call some application-specific function */ /* */ ExtApplFuncDoneOneChain; ind = GetNextChain(list, &got_it); if (got_it) { /* */ /* at some point of the triangulation, we could not find any ear */ /* and the polygon was split into two parts. now we have to */ /* handle (onex of) the remaining parts. */ /* */ ResetPolyList(list, ind); list->loops[0] = ind; grid->no_grid_yet = true; BuildBuckets(all, list->loops[0]); if (rt_opt->ears_fancy) BuildPntsGrid(all, 0); ResetEarStatus(ear); ClassifyEars(all, ind); all->reset = false; all->done = false; ++i; /* */ /* let the user call some application-specific function */ /* */ ExtApplFuncNextChain; } } } if (rt_opt->verbose) { fprintf(stdout, "done!\n"); fflush(stdout); } if (rt_opt->time) all->cpu_time = elapsed(all); #ifdef BENCHMARK else all->cpu_time = elapsed(all); #endif if (all->done) { if (!all->written) { if (rt_opt->write_geom || rt_opt->write_dxf || rt_opt->write_tri || rt_opt->write_ipe7 ) { if (rt_opt->verbose) { fprintf(stdout, "\n...writing the output data: "); fflush(stdout); } if (rt_opt->write_geom) WriteGeomOutput(all); if (rt_opt->write_dxf) WriteFacesDXF(all, rt_opt->tri_file); else if (rt_opt->write_tri) WriteFaces(all, rt_opt->tri_file); if (rt_opt->write_ipe7) WriteIpeOutput(all); if (rt_opt->verbose) { fprintf(stdout, "done!\n"); fflush(stdout); } } all->written = true; } /* */ /* let the user call some application-specific function */ /* */ ExtApplFuncFinished; if (rt_opt->verbose) { if (all->troubles) printf("\n\nTriangulation completed!\n"); else printf("\n\nTriangulation successfully completed!\n"); } } #ifdef BENCHMARK printf("%i,%li\n", GetNumTriangles(vert), (long int)((all->cpu_time))); #endif return; } #define NUM_DIST 12 void StatisticsFIST(global_struct *all) { vertexdef *vert = &all->c_vertex; listdef *list = &all->c_list; quaddef *quad = &all->c_quad; if (!all->rt_opt.quiet && all->rt_opt.graphics && all->rt_opt.time) printf("OpenGL interface was used, Statistics output will be erroneous due to the \ngraphical overhead!"); if (!all->rt_opt.quiet && all->rt_opt.time) { if (all->cpu_time > 0.0) { printf("\n\nCPU-time consumption (MS): %8.0f", MDOUBLE_TO_IOMDOUBLE(all->cpu_time)); } else { printf("\n\nCPU-time consumption (MS): %8.0f (< 10 MS)", MDOUBLE_TO_IOMDOUBLE(all->cpu_time)); } if (vert->num_vertices > 0) printf("\nCPU-time/seg (MS, for %7d segs): %18.16f", vert->num_vertices, MDOUBLE_TO_IOMDOUBLE(all->cpu_time / vert->num_vertices)); } if (all->rt_opt.statistics) { if (list->num_faces != 0) printf("\n\n#(Input Faces): %8d\n", list->num_faces); else printf("\n\n#(Input Faces): %8d\n", all->num_contours); printf("#(Input Concave Faces): %8d\n", vert->num_concave_loops); printf("#(Output Triangles): %8d\n", GetNumTriangles(vert)); if (vert->num_quads > 0) printf("#(Output Quads): %8d\n", vert->num_quads); if (vert->num_convex_loops > 0) printf("#(Output Convex Faces w/o Quads): %8d\n", vert->num_convex_loops); if (quad->num_grouped > 0) printf("#(Triangles-->Quads): %8d\n", quad->num_grouped); printf("#(Points): %8d\n", vert->num_vertices); #ifdef NORMALS printf("#(Vertex Normals): %8d\n", vert->num_v_normals); printf("#(Texture Vertices): %8d\n", vert->num_t_vertices); #endif printf("\n\n"); } else if (!all->rt_opt.quiet) { printf("\n"); } return; } void ResetAll(global_struct *all) { vertexdef *vert = &all->c_vertex; #ifdef GRAPHICS redrawdef *redraw = &all->c_redraw; #endif listdef *list = &all->c_list; iolistdef *iolist = &all->c_iolist; datadef *data = &all->c_data; heapdef *heap; griddef *grid = &all->c_grid; /* */ /* let the user call some application-specific function */ /* */ ExtApplFuncResetAll; /* */ /* reset data within individual structures */ /* */ #ifdef GRAPHICS ResetGraphicsData(); ResetBufferData(redraw); #endif #ifdef PARTITION_FIST for(int i = 0; i < all->number_of_heaps; ++i) { heap = &all->c_heap[i]; InitHeap(heap, data); } #else heap = &all->c_heap; InitHeap(heap, data); #endif ResetListData(list); ResetIOListData(iolist); ResetGrid(grid); /* */ /* reset global data */ /* */ data->num_pnts = 0; list->num_loops = 0; vert->num_vertices = 0; list->num_faces = 0; #ifdef NORMALS vert->num_t_vertices = 0; vert->num_v_normals = 0; vert->num_i_triangles = 0; #endif vert->num_triangles = 0; all->num_contours = 0; vert->num_groups = 0; data->data_scaled = false; data->scale_factor = C_1_0; data->shift.x = C_0_0; data->shift.y = C_0_0; all->done = false; all->reset = false; all->troubles = false; all->written = false; all->new_input = false; all->cpu_time = 0.0; all->curr_loop_main = 0; all->dxf_file = (FILE*)NULL; all->ipe_initialized = false; #ifdef EXPR_WRAPPER all->returncore = false; #endif return; }