/*****************************************************************************/ /* */ /* 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 /* */ /* 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; }