/****************************************************************************\ 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 \****************************************************************************/ /*****************************************************************************\ fill_hole.c -- Description : Functions for performing recursive hole filling. ---------------------------------------------------------------------------- $Source: /cvs/RenderPark/SE/Simplify/fill_hole.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 /*----------------------------- Local Constants -----------------------------*/ #define MAX_RETRIANGULATIONS 200 /*------------------------------ Local Macros -------------------------------*/ #define NON_MANIFOLD_EDGE(tri) \ (((tri)->edges[0]->handy_mark > 1) || \ ((tri)->edges[1]->handy_mark > 1) || \ ((tri)->edges[2]->handy_mark > 1)) /*------------------------------- Local Types -------------------------------*/ /*------------------------ Local Function Prototypes ------------------------*/ static void create_subholes(Hole *hole, Hole *subholes, int tri_index); static void destroy_subholes(Hole *subholes); static void add_tri_to_hole_solution(Hole *hole, Triangle *tri); static void revert_hole_solution(Hole *hole, int prev_solution_size); /*------------------------------ Local Globals ------------------------------*/ /*---------------------------------Functions-------------------------------- */ /*****************************************************************************\ @ fill_hole() ----------------------------------------------------------------------------- description : Attempt to fill a hole using its set of ranked solution triangles. input : 1. The hole to be filled. 2. Octree of the outer offset surface. 3. Octree of the inner offset surface. 4. Octree of the current surface mesh. 5. Space for octree query result data. 6. Intersection fuzz factor. 7. Flag to indicate whether to use a single path recursion algorithm or to exhaustively try all combinations of solution triangles (within some maximum number of tries). TRUE indicates to use the exhaustive approach. FALSE indicates to use a single path approach. output : If the hole is successfully filled, the hole's solution triangles field indicates which triangles are used in the solution, and the return value is TRUE. Otherwise, the return value is FALSE. notes : \*****************************************************************************/ int fill_hole(Hole *hole, Octree *outer_offset, Octree *inner_offset, Octree *model_octree, OctreeData **query_result, double fuzz_factor, int exhaustive_filling_flag) { int i; Hole subholes[3]; Triangle *tri; int success; int tri_index; int prev_solution_size; static int recursion_level = 0; static int retriangulations_tried; if (recursion_level == 0) { if (hole->num_verts > 2) { ALLOCN(hole->solution_tris, Triangle *, hole->num_verts-2); } else hole->solution_tris = NULL; hole->num_solution_tris = 0; hole->num_solution_tris_ptr = &(hole->num_solution_tris); retriangulations_tried = 0; } if (hole->num_verts < 3) return TRUE; if (hole->num_candidate_tris < (hole->num_verts - 2)) return FALSE; recursion_level++; prev_solution_size = *hole->num_solution_tris_ptr; for (tri_index=0; tri_indexnum_candidate_tris; tri_index++) { tri = hole->ranked_candidate_tris[tri_index]; #ifdef REMOVE_BORDER_VERTS /* if the boundary has a missing edge, be sure to pick a triangle that fills the missing edge so we don't have to trace out a subdivided boundary with a hole */ if (hole->num_verts == (hole->num_edges+1)) { if (((tri->verts[0] != hole->verts[0]) && (tri->verts[1] != hole->verts[0]) && (tri->verts[2] != hole->verts[0])) || ((tri->verts[0] != hole->verts[hole->num_verts-1]) && (tri->verts[1] != hole->verts[hole->num_verts-1]) && (tri->verts[2] != hole->verts[hole->num_verts-1]))) continue; } #endif /* REMOVE_BORDER_VERTS */ if ((NON_MANIFOLD_EDGE(tri)) || (tri_solution_interference(hole, tri, fuzz_factor)) || (tri_model_interference(tri, hole->center_vert, model_octree, query_result, fuzz_factor)) || (tri_offsets_intersect(tri, outer_offset, inner_offset, query_result, fuzz_factor))) continue; /* candidate triangle is rejected */ add_tri_to_hole_solution(hole, tri); create_subholes(hole, subholes, tri_index); for (i=0, success = TRUE; i<3; i++) if (!(fill_hole(&(subholes[i]), outer_offset, inner_offset, model_octree, query_result, fuzz_factor, exhaustive_filling_flag))) { success = FALSE; break; } destroy_subholes(subholes); if (success == TRUE) { recursion_level--; return TRUE; } else { revert_hole_solution(hole, prev_solution_size); if ((exhaustive_filling_flag == TRUE) && ((retriangulations_tried++) < MAX_RETRIANGULATIONS)) continue; else break; } } recursion_level--; return FALSE; } /** End of fill_hole() **/ /*****************************************************************************\ @ create_subholes() ----------------------------------------------------------------------------- description : Given a hole and a triangle inside the hole, create 3 subholes, distributing the candidate triangles among them. input : Hole, index of triangle in the hole's ranked candidate triangle list output : Subholes structures are created notes : \*****************************************************************************/ static void create_subholes(Hole *hole, Hole *subholes, int tri_index) { int i, j, k; Triangle *new_tri; int tri_vert_id; Vertex *vert; Edge *edge; Triangle *tri; int start_tri; new_tri = hole->ranked_candidate_tris[tri_index]; for (i=0; i<3; i++) { subholes[i].center_vert = hole->center_vert; /* may be able to do this allocation more intelligently by counting the sizes for the new holes before allocating */ ALLOCN(subholes[i].verts, Vertex *, hole->num_verts); ALLOCN(subholes[i].edges, Edge *, hole->num_edges); ALLOCN(subholes[i].ranked_candidate_tris, Triangle *, hole->num_candidate_tris); subholes[i].num_verts = 0; subholes[i].num_edges = 0; subholes[i].num_candidate_tris = 0; subholes[i].candidate_edges = NULL; subholes[i].candidate_tris = NULL; subholes[i].num_candidate_edges = 0; subholes[i].solution_tris = hole->solution_tris; subholes[i].num_solution_tris = -1; subholes[i].num_solution_tris_ptr = hole->num_solution_tris_ptr; } for (i=0, tri_vert_id = -1; i < hole->num_verts; i++) { hole->verts[i]->handy_mark = 0; if (hole->verts[i] == new_tri->verts[0]) tri_vert_id = i; } if (tri_vert_id == -1) { printf("recursive_fill_hole(): couldn't find aptri_vert in bverts\n"); exit(-1); } for (i=0; i<3; i++) { for (j=tri_vert_id, k = 0, vert = NULL; vert != new_tri->verts[(i+1)%3]; j=(j+1)%hole->num_verts, k++) { vert = hole->verts[j]; #ifndef REMOVE_BORDER_VERTS if (vert != new_tri->verts[(i+1)%3]) #else if ((vert != new_tri->verts[(i+1)%3]) && (j < hole->num_edges)) #endif edge = hole->edges[j]; else { edge = new_tri->edges[i]; tri_vert_id = j; } subholes[i].verts[k] = vert; subholes[i].edges[k] = edge; vert->handy_mark |= 1<2) subholes[i].num_edges = k; else if (k==2) subholes[i].num_edges = 1; else { printf("recursive_fill_hole(): not enough bverts\n"); exit(-1); } } /* now partition the filler_tris into these three subsets (throw away those that don't fit into any subset) */ subholes[0].num_candidate_tris = subholes[1].num_candidate_tris = subholes[2].num_candidate_tris = 0; #ifdef REMOVE_BORDER_VERTS if (hole->num_verts == (hole->num_edges+1)) start_tri = 0; else #endif start_tri = tri_index+1; for (i = start_tri; inum_candidate_tris; i++) { tri = hole->ranked_candidate_tris[i]; j = (tri->verts[0]->handy_mark & tri->verts[1]->handy_mark & tri->verts[2]->handy_mark); if (j) { k = (j==1) ? 0 : ((j==2) ? 1 : 2); subholes[k].ranked_candidate_tris[subholes[k].num_candidate_tris++] = tri; } } return; } /** End of create_subholes() **/ /*****************************************************************************\ @ destroy_subholes() ----------------------------------------------------------------------------- description : Deallocate 3 subholes. input : Array of 3 subholes. output : Subholes are deallocaed. notes : \*****************************************************************************/ static void destroy_subholes(Hole *subholes) { int i; for (i=0; i<3; i++) { subholes[i].center_vert = NULL; FREE(subholes[i].verts); FREE(subholes[i].edges); subholes[i].candidate_edges = NULL; subholes[i].candidate_tris = NULL; FREE(subholes[i].ranked_candidate_tris); subholes[i].solution_tris = NULL; subholes[i].num_verts = 0; subholes[i].num_edges = 0; subholes[i].num_candidate_edges = 0; subholes[i].num_candidate_tris = 0; subholes[i].num_solution_tris = 0; subholes[i].num_solution_tris_ptr = NULL; } } /** End of destroy_subholes() **/ /*****************************************************************************\ @ add_tri_to_hole_solution() ----------------------------------------------------------------------------- description : Add a triangle to the set of solution triangles of a hole. Also increment the number of times each of its edges has been used. input : Hole, new solution triangle output : New solution triangle has been added to the set of solution triangles. notes : \*****************************************************************************/ static void add_tri_to_hole_solution(Hole *hole, Triangle *tri) { int i; for (i=0; i<3; i++) tri->edges[i]->handy_mark++; hole->solution_tris[(*hole->num_solution_tris_ptr)++] = tri; return; } /** End of add_tri_to_hole_solution() **/ /*****************************************************************************\ @ revert_hole_solution() ----------------------------------------------------------------------------- description : Remove the most recent solution triangles from the set. input : Hole, number of solution triangles to revert to. output : Some solution triangles have been removed from the list of solution triangles, and the usage count of their edges have been decremented. notes : \*****************************************************************************/ static void revert_hole_solution(Hole *hole, int prev_solution_size) { int i; Triangle *tri; while (*hole->num_solution_tris_ptr > prev_solution_size) { tri = hole->solution_tris[(*hole->num_solution_tris_ptr)-1]; for (i=0; i<3; i++) tri->edges[i]->handy_mark--; (*hole->num_solution_tris_ptr)--; } return; } /** End of revert_hole_solution() **/ /*****************************************************************************\ $Log: fill_hole.c,v $ Revision 1.1.1.1 2000/04/06 15:35:32 philippe Initial CVS release Revision 1.4 1997/04/10 20:10:46 cohenj Added Amitabh's name to credits Revision 1.3 1996/04/08 18:48:24 cohenj added procedure comments and copyright * Revision 1.2 95/10/16 16:29:41 cohenj * first working version * * Revision 1.1 95/09/30 06:11:10 cohenj * Initial revision * \*****************************************************************************/