/****************************************************************************\ Copyright 1995 The University of North Carolina at Chapel Hill. All Rights Reserved. Permission to use, copy, modify and distribute this software and its documentation for educational, research and non-profit purposes, without fee, and without a written agreement is hereby granted, provided that the above copyright notice and the following three paragraphs appear in all copies. IN NO EVENT SHALL THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF NORTH CAROLINA HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. Permission to use, copy, modify and distribute this software and its documentation for educational, research and non-profit purposes, without fee, and without a written agreement is hereby granted, provided that the above copyright notice and the following three paragraphs appear in all copies. THE UNIVERSITY OF NORTH CAROLINA SPECIFICALLY DISCLAIM ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF NORTH CAROLINA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. The authors may be contacted via: US Mail: Jonathan Cohen Amitabh Varshney Department of Computer Science Department of Computer Science Sitterson Hall, CB #3175 State University of New York University of N. Carolina Stony Brook, NY 11794-4400, USA Chapel Hill, NC 27599-3175 Phone: (919)962-1749 Phone: (516)632-8446 EMail: cohenj@cs.unc.edu varshney@cs.sunysb.edu \****************************************************************************/ /*****************************************************************************\ candidate.c -- Description : Functions for computing candidate edges and triangles that may be used to fill a hole. ---------------------------------------------------------------------------- $Source: /cvs/RenderPark/SE/Simplify/candidate.c,v $ $Revision: 1.1.1.1 $ $Date: 2000/04/06 15:35:32 $ $Author: philippe $ $Locker: $ \*****************************************************************************/ /*----------------------------- Local Includes -----------------------------*/ #include #include #include #include #include #include #include /*----------------------------- Local Constants -----------------------------*/ /*------------------------------ Local Macros -------------------------------*/ /* This assumes that vert1 and vert2 are the indices of two of the hole boundary vertices, and that vert2 > vert1. This should return TRUE if the edge defined by these two indices is one of the hole boundary edges (which means that the edge exists in the current mesh and so does not intersect the offset surfaces) and is a viable candidate edge. */ #define BOUNDARY_EDGE(hole, vert1, vert2) \ ((((vert2)-(vert1)) == 1) || \ (((hole)->num_edges==(hole)->num_verts) && \ (((vert2)-(vert1)) == ((hole)->num_verts-1)))) /*------------------------------- Local Types -------------------------------*/ typedef int TupleType[2]; typedef struct double_sort_type { double key; void *data; } DoubleSortType; /*------------------------ Local Function Prototypes ------------------------*/ static int edge_tuple_exists(int *vert_start, TupleType *edge_tuples, int vert1, int vert2, int *tuple_id); static void compute_candidate_edges(Hole *hole, int **vert_start, TupleType **edge_tuples, Octree *outer_offset, Octree *inner_offset, OctreeData **query_result, double fuzz_factor); static void compute_candidate_tris(Hole *hole, int **vert_start, TupleType **edge_tuples); static double find_tri_min_angle(Triangle *tri); static void rank_sort_candidate_tris(Hole *hole); static void quick_sort_doubles(DoubleSortType **sorted, int m, int n); static int mesh_edge(Vertex *vert1, Vertex *vert2); /*------------------------------ Local Globals ------------------------------*/ /*---------------------------------Functions-------------------------------- */ /*****************************************************************************\ @ compute_candidates() ----------------------------------------------------------------------------- description : Compute all the candidate edges and triangles that could be used to fill the hole -- the edges are tested against the offset surface, while the tris are tested later on an as needed basis input : Hole, offset surface, intersection fuzz factor output : Hole data structure has its fields related to edge and triangle candidates filled in notes : \*****************************************************************************/ void compute_candidates(Hole *hole, Octree *outer_offset, Octree *inner_offset, OctreeData **query_result, double fuzz_factor) { int *vert_start; TupleType *edge_tuples; compute_candidate_edges(hole, &vert_start, &edge_tuples, outer_offset, inner_offset, query_result, fuzz_factor); compute_candidate_tris(hole, &vert_start, &edge_tuples); rank_sort_candidate_tris(hole); return; } /** End of compute_candidates() **/ /*****************************************************************************\ @ compute_candidate_edges() ----------------------------------------------------------------------------- description : Compute all possible candidate edges whose vertices are part of the hole boundary and which do not intersect the offset surfaces input : Hole, offset octrees, intersection fuzz_factor. output : The hole's fields corresponding to candidate edges are filled in. vert_start and edge_tuples contain information about the candidate edges and a means of indexing into them quickly notes : \*****************************************************************************/ static void compute_candidate_edges(Hole *hole, int **vert_start, TupleType **edge_tuples, Octree *outer_offset, Octree *inner_offset, OctreeData **query_result, double fuzz_factor) { int i, j; int n; int num_etuples; Edge *edge; Edge an_edge; n = hole->num_verts; ALLOCN((*vert_start), int, n); ALLOCN((*edge_tuples), TupleType, (n*(n-1))/2); num_etuples = 0; for(i = 0; i < hole->num_verts; i++) { /* vert_start is indexed by the location of a vertex within the hole's list of boundary vertices, not by the vertex_id */ (*vert_start)[i] = num_etuples; for(j = i+1; j < hole->num_verts; j++) { an_edge.verts[0] = hole->verts[i]; an_edge.verts[1] = hole->verts[j]; if ((BOUNDARY_EDGE(hole, i, j)) || ((!(mesh_edge(hole->verts[i], hole->verts[j]))) && (!(edge_offsets_intersect(outer_offset, inner_offset, query_result, &an_edge, fuzz_factor))))) { /* add as an etuple - store indices into the list of hole boundary vertices in edge_tuples */ (*edge_tuples)[num_etuples][0] = i; (*edge_tuples)[num_etuples][1] = j; num_etuples++; } } } /* generate the edges */ ALLOCN(hole->candidate_edges, Edge, num_etuples); for(i = 0; i < num_etuples; i++) { edge = &(hole->candidate_edges[i]); edge->id = i; edge->verts[0] = hole->verts[(*edge_tuples)[i][0]]; edge->verts[1] = hole->verts[(*edge_tuples)[i][1]]; edge->tris[0] = edge->tris[1] = NULL; if (BOUNDARY_EDGE(hole, (*edge_tuples)[i][0], (*edge_tuples)[i][1])) edge->handy_mark = 1; /* edge used once - on the hole boundary */ else edge->handy_mark = 0; /* edge not used yet - interior edge */ } hole->num_candidate_edges = num_etuples; return; } /** End of compute_candidate_edges() **/ /*****************************************************************************\ @ compute_candidate_tris() ----------------------------------------------------------------------------- description : Compute all the candidate tris that can be created from the approximation edges input : A hole, and data structures for quickly locating particular candidate edges output : The hole's fields corresponding to candidate triangles are filled in notes : \*****************************************************************************/ static void compute_candidate_tris(Hole *hole, int **vert_start, TupleType **edge_tuples) { int i, j, k, l; int count; Triangle *tri; /* count the number of the approximation triangle tuples */ for(i = count = 0; i < hole->num_verts-1; i++) { for(j = (*vert_start)[i]; j < (*vert_start)[i+1]; j++) { for(k = j+1; k < (*vert_start)[i+1]; k++) if (edge_tuple_exists(*vert_start, *edge_tuples, (*edge_tuples)[j][1], (*edge_tuples)[k][1], &l)) count++; } } ALLOCN(hole->candidate_tris, Triangle, count); /* set up the candidate tris */ for(i = count = 0; i < hole->num_verts-1; i++) for(j = (*vert_start)[i]; j < (*vert_start)[i+1]; j++) for(k = j+1; k < (*vert_start)[i+1]; k++) if (edge_tuple_exists(*vert_start, *edge_tuples, (*edge_tuples)[j][1], (*edge_tuples)[k][1], &l)) { tri = &(hole->candidate_tris[count]); tri->id = count; tri->verts[0] = hole->verts[i]; tri->verts[1] = hole->verts[(*edge_tuples)[j][1]]; tri->verts[2] = hole->verts[(*edge_tuples)[k][1]]; tri->edges[0] = &(hole->candidate_edges[j]); tri->edges[1] = &(hole->candidate_edges[l]); tri->edges[2] = &(hole->candidate_edges[k]); find_plane_eq(tri->verts[0]->coord, tri->verts[1]->coord, tri->verts[2]->coord, tri->plane_eq); tri->handy_mark = -1; count++; } hole->num_candidate_tris = count; FREE(*edge_tuples); FREE(*vert_start); return; } /** End of compute_candidate_tris() **/ /*****************************************************************************\ @ mesh_edge() ----------------------------------------------------------------------------- description : This should return TRUE if the edge defined by these two vertices exists already in the current mesh. Such an edge is not a viable candidate edge unless it's also a hole boundary edge (otherwise it is already shared by two tris and cannot be used again). input : Two vertices output : TRUE if edge exists in current mesh FALSE otherwise notes : \*****************************************************************************/ static int mesh_edge(Vertex *vert1, Vertex *vert2) { int i; Vertex *tempvert; Edge *edge; if (vert1->num_edges > vert2->num_edges) { tempvert = vert2; vert2 = vert1; vert1 = tempvert; } for (i=0; inum_edges; i++) { edge = vert1->edges[i]; if ((edge->verts[0] == vert2) || (edge->verts[1] == vert2)) return TRUE; } return FALSE; } /** End of mesh_edge() **/ /*****************************************************************************\ @ edge_tuple_exists() ----------------------------------------------------------------------------- description : Given a pair of vertices and a list of edge tuples, determine if an edge exists between the two vertices. input : List of starting indices for each vertex id, list of edge_tuples, id's of two vertices which comprise edge in question. output : If edge_tuples exists, returns TRUE and tuple_id indicates which tuple is the proper edge. Otherwise, return FALSE. notes : Assumes that vert1 < vert2 \*****************************************************************************/ static int edge_tuple_exists(int *vert_start, TupleType *edge_tuples, int vert1, int vert2, int *tuple_id) { int i; i = vert_start[vert1]; while ((i < vert_start[vert1+1]) && (edge_tuples[i][1] <= vert2)) { if (edge_tuples[i][1] == vert2) { *tuple_id = i; return TRUE; } i++; } return FALSE; } /** End of edge_tuple_exists() **/ /*****************************************************************************\ @ rank_sort_candidate_tris() ----------------------------------------------------------------------------- description : Rank candidate triangles according to minimum angle and sort into an ordering based on this rank input : Hole output : Hole's ranked_candidate_tris field contains a list of pointers to the candidate tri's in ranked order. notes : \*****************************************************************************/ static void rank_sort_candidate_tris(Hole *hole) { int i; DoubleSortType *tri_records; DoubleSortType **tri_record_list; ALLOCN(hole->ranked_candidate_tris, Triangle *, hole->num_candidate_tris); ALLOCN(tri_records, DoubleSortType, hole->num_candidate_tris+1); ALLOCN(tri_record_list, DoubleSortType *, hole->num_candidate_tris+1); for (i=0; inum_candidate_tris; i++) { tri_records[i].key = find_tri_min_angle(&(hole->candidate_tris[i])); tri_records[i].data = &(hole->candidate_tris[i]); tri_record_list[i] = &(tri_records[i]); } tri_records[hole->num_candidate_tris].key = -HUGE; tri_records[hole->num_candidate_tris].data = NULL; tri_record_list[hole->num_candidate_tris] = &(tri_records[hole->num_candidate_tris]); quick_sort_doubles(tri_record_list, 0, hole->num_candidate_tris-1); for (i=0; inum_candidate_tris; i++) hole->ranked_candidate_tris[i] = (Triangle *)(tri_record_list[i]->data); FREE(tri_record_list); FREE(tri_records); return; } /** End of rank_sort_candidate_tris() **/ /*****************************************************************************\ @ find_tri_min_angle() ----------------------------------------------------------------------------- description : Return the minimum angle in a triangle (in degrees) input : Triangle output : minimum angle in degrees notes : \*****************************************************************************/ static double find_tri_min_angle(Triangle *tri) { int i, j, k; Point diff0, diff1; double theta, min_theta; min_theta = HUGE; for(i=0; i < 3; i++) { j = (i+1)%3; k = (j+1)%3; VEC3_V_OP_V(diff0, tri->verts[j]->coord, -, tri->verts[i]->coord); VEC3_V_OP_V(diff1, tri->verts[k]->coord, -, tri->verts[i]->coord); NORMALIZE3(diff0); NORMALIZE3(diff1); theta = DOTPROD3(diff0, diff1); if (theta > 1.0) theta = 1.0; if (theta < -1.0) theta = -1.0; theta = acos(theta); if (theta < min_theta) min_theta = theta; } /* convert to degrees */ min_theta *= 180.0/M_PI; return min_theta; } /** End of find_tri_min_angle() **/ /*****************************************************************************\ @ quick_sort_doubles() ----------------------------------------------------------------------------- description : sorts the records in descending order of their keys. Assumes that sorted[n+1].key == -HUGE input : List of elements to be sorted, first and last indices to sort output : List is sorted in descending order notes : I really might as well just use qsort()... \*****************************************************************************/ static void quick_sort_doubles(DoubleSortType **sorted, int m, int n) { int i, j; double key; DoubleSortType *temp_ptr; if (m < n) { i = m; j = n + 1; key = sorted[m]->key; do { /*EMPTY*/ /*codecenter suppression*/ while (sorted[++i]->key > key); /*EMPTY*/ /*codecenter suppression*/ while (sorted[--j]->key < key); if (i < j) { /* swap i and j-th elements */ temp_ptr = sorted[i]; sorted[i] = sorted[j]; sorted[j] = temp_ptr; } } while (i < j); /* swap m and j-th elements */ temp_ptr = sorted[m]; sorted[m] = sorted[j]; sorted[j] = temp_ptr; quick_sort_doubles(sorted, m, j-1); quick_sort_doubles(sorted, j+1, n); } return; } /** End of quick_sort_doubles() **/ /*****************************************************************************\ $Log: candidate.c,v $ Revision 1.1.1.1 2000/04/06 15:35:32 philippe Initial CVS release Revision 1.6 1997/04/10 20:10:46 cohenj Added Amitabh's name to credits Revision 1.5 1996/04/18 19:08:41 cohenj minor change in the name of the procedure to test for an intersection between a candidate edge and the offsets. * Revision 1.4 96/04/08 18:47:21 cohenj * added procedure comments. * added copyright * * Revision 1.3 95/10/16 16:29:41 cohenj * modified to eliminate edges that already have two triangles on them in * the mesh from the candidate edges * * Revision 1.2 95/09/30 06:11:10 cohenj * almost done writing revision 1 -- just need the code to update * the model after a vertex is removed and finalize the model after removing * all vertices in the queue. * * Revision 1.1 1995/09/29 19:16:01 cohenj * Initial revision * \*****************************************************************************/