/****************************************************************************\ 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 \****************************************************************************/ /*****************************************************************************\ vertex_removal.c -- Description : Routines in charge of attempting to remove a vertex and making the local surface modifications ---------------------------------------------------------------------------- $Source: /cvs/RenderPark/SE/Simplify/vertex_removal.c,v $ $Revision: 1.1.1.1 $ $Date: 2000/04/06 15:35:32 $ $Author: philippe $ $Locker: $ \*****************************************************************************/ /*----------------------------- Local Includes -----------------------------*/ #include #include #include #include #include #ifdef USE_TRIOCTREE #include #else #include #endif #include #include #include #include /*----------------------------- Local Constants -----------------------------*/ #define COS_TEST_ANGLE -0.98480775 /* cosine of 170 degrees */ /*------------------------------ Local Macros -------------------------------*/ #define BORDER_VERT(vert) (vert->num_edges == (vert->num_tris+1)) /*------------------------------- Local Types -------------------------------*/ /*------------------------ Local Function Prototypes ------------------------*/ static void get_hole_boundary(Vertex *vert, Hole *hole); static void destroy_hole(Hole *hole); static void update_model(Vertex *center_vert, Hole *hole, Octree *model_octree, OctreeData *model_octree_data); static int border_condition_violated(Vertex *vert, Octree *tubes, OctreeData **query_result, double fuzz_factor); /*------------------------------ Local Globals ------------------------------*/ /*---------------------------------Functions-------------------------------- */ /*****************************************************************************\ @ try_removing_vertex() ----------------------------------------------------------------------------- description : Attempt to remove a vertex, subject to distance constraints and non-self-intersection constraints input : Vertex in question, envelope surfaces, border tubes, intersection fuzz_factor, and a boolean flag for exhaustive filling output : If vertex removal is successful, surface is modified and return value of TRUE, otherwise surface is unchanged and return value of FALSE notes : \*****************************************************************************/ int try_removing_vertex(Vertex *vert, Octree *outer_offset, Octree *inner_offset, Octree *tubes, Octree *model_octree, OctreeData *model_octree_data, OctreeData **query_result, double fuzz_factor, int exhaustive_filling_flag) { Hole hole; int vertex_removed; #ifdef REMOVE_BORDER_VERTS if ((BORDER_VERT(vert)) && (border_condition_violated(vert, tubes, query_result, fuzz_factor))) return FALSE; #else if (BORDER_VERT(vert)) return FALSE; #endif /* get the hole boundary */ get_hole_boundary(vert, &hole); /* compute candidate triangles for filling in the hole*/ compute_candidates(&hole, outer_offset, inner_offset, query_result, fuzz_factor); /* attempt to fill hole */ vertex_removed = fill_hole(&hole, outer_offset, inner_offset, model_octree, query_result, fuzz_factor, exhaustive_filling_flag); /* update model to reflect changes, if any */ if (vertex_removed == TRUE) update_model(vert, &hole, model_octree, model_octree_data); /* destroy hole */ destroy_hole(&hole); return vertex_removed; } /** End of try_removing_vertex() **/ /*****************************************************************************\ @ get_hole_boundary() ----------------------------------------------------------------------------- description : Find the chain of vertices and edges surrounding a hole (the hole created by removing a vertex and its adjacent faces) input : Vertex at center of hole output : Hole structure is filled in with appropriate vertices and edges notes : The rest of the hole structure is filled in by the compute_candidates() function. \*****************************************************************************/ static void get_hole_boundary(Vertex *vert, Hole *hole) { int i, j; Triangle *tri; Edge *edge; hole->center_vert = vert; /* first identify all the boundary edges */ ALLOCN(hole->edges, Edge *, vert->num_tris); hole->num_edges = 0; for(i = 0; i < vert->num_tris; i++) { tri = vert->tris[i]; for(j = 0; j < 3; j++) { if ((tri->edges[j]->verts[0] != vert) && (tri->edges[j]->verts[1] != vert)) hole->edges[hole->num_edges++] = tri->edges[j]; } } if (hole->num_edges != vert->num_tris) { fprintf(stderr, "Error getting hole boundary edges\n"); exit(1); } /* identify the boundary vertices */ ALLOCN(hole->verts, Vertex *, vert->num_edges); hole->num_verts = 0; for (i=0; inum_edges; i++) { edge = vert->edges[i]; hole->verts[hole->num_verts++] = (edge->verts[0] == vert) ? edge->verts[1] : edge->verts[0]; } return; } /** End of get_hole_boundary() **/ /*****************************************************************************\ @ destroy_hole() ----------------------------------------------------------------------------- description : Free all dynamically allocated space in a hole structure input : output : notes : \*****************************************************************************/ static void destroy_hole(Hole *hole) { FREE(hole->verts); FREE(hole->edges); FREE(hole->ranked_candidate_tris); FREE(hole->solution_tris); FREE(hole->candidate_tris); FREE(hole->candidate_edges); return; } /** End of destroy_hole() **/ /*****************************************************************************\ @ update_model() ----------------------------------------------------------------------------- description : Remove the vertex from the solution, updating the affected edges, triangles, and surrounding vertices input : The vertex, the hole, and the octree structure for the entire (current) surface output : The surface and it's octree are updated notes : \*****************************************************************************/ static void update_model(Vertex *center_vert, Hole *hole, Octree *model_octree, OctreeData *model_octree_data) { int i, j, k, m; Edge *src_edge, *dest_edge; int src_edge_id, src_tri_id, dest_edge_id, dest_tri_id; Triangle *src_tri, *dest_tri, *tri; Vertex *vert, *other_vert; int num_edge_copies; Triangle *solution_tri, *boundary_tri; Edge *edge, *solution_edge, *boundary_edge; int new_num_tris, new_num_edges, done, found; #ifndef USE_TRIOCTREE OctreeData *element; #endif #ifndef REMOVE_BORDER_VERTS if (hole->num_solution_tris != (center_vert->num_tris - 2)) { fprintf(stderr, "update_model(): f(i+1) != f(i) - 2\n"); exit(1); } #else if (!BORDER_VERT(center_vert)) { if (hole->num_solution_tris != (center_vert->num_tris - 2)) { fprintf(stderr, "update_model(): f(i+1) != f(i) - 2\n"); exit(1); } } else { if (hole->num_solution_tris != (center_vert->num_tris - 1)) { fprintf(stderr, "update_model(): f(i+1) != f(i) - 1\n"); exit(1); } } #endif #ifdef USE_TRIOCTREE for (i=0; inum_tris; i++) { tri = center_vert->tris[i]; trioctree_remove(model_octree, tri); } #else for (i=0; inum_tris; i++) { tri = center_vert->tris[i]; octree_remove(model_octree, &(model_octree_data[tri->id])); } #endif for (i=0; i < hole->num_solution_tris; i++) for (j=0; j<3; j++) for (k=0; k<2; k++) hole->solution_tris[i]->edges[j]->tris[k] = NULL; for (i=0; i < hole->num_solution_tris; i++) for (j=0; j<3; j++) { tri = hole->solution_tris[i]; if (!(tri->edges[j]->tris[0])) tri->edges[j]->tris[0] = tri; else if (!(tri->edges[j]->tris[1])) tri->edges[j]->tris[1] = tri; else { fprintf(stderr, "update_model: too many tris on edge\n"); exit(1); } } /** Update Edges **/ /* only copy new interior edges */ for (i=0; i < hole->num_solution_tris; i++) for (j=0; j<3; j++) hole->solution_tris[i]->edges[j]->handy_mark = 1; #ifdef REMOVE_BORDER_VERTS /* note that the new border edge will not be found among bedges, so it will also be copied */ #endif for (i=0; i < hole->num_solution_tris; i++) { solution_tri = hole->solution_tris[i]; for (j=0; j<3; j++) { solution_edge = solution_tri->edges[j]; for (k=0; k< hole->num_edges; k++) { boundary_edge = hole->edges[k]; if (((solution_edge->verts[0] == boundary_edge->verts[0]) && (solution_edge->verts[1] == boundary_edge->verts[1])) || ((solution_edge->verts[0] == boundary_edge->verts[1]) && (solution_edge->verts[1] == boundary_edge->verts[0]))) { solution_edge->handy_mark = 0; solution_edge->id = (int)boundary_edge; for (m=0; m<2; m++) { boundary_tri = boundary_edge->tris[m]; if (!(boundary_tri)) continue; if ((boundary_tri->verts[0] == center_vert) || (boundary_tri->verts[1] == center_vert) || (boundary_tri->verts[2] == center_vert)) boundary_edge->tris[m] = solution_tri; } } } } } /* only replace original interior edges */ for (i=0; i < hole->num_edges; i++) hole->edges[i]->handy_mark = 0; /* don't replace */ for (i=0; i < center_vert->num_edges; i++) center_vert->edges[i]->handy_mark = 1; /* replace */ dest_tri_id = 0; dest_edge_id = 0; src_tri_id = 0; src_edge_id = 0; #ifndef REMOVE_BORDER_VERTS num_edge_copies = center_vert->num_tris - 3; #else num_edge_copies = (BORDER_VERT(center_vert)) ? center_vert->num_tris-1: center_vert->num_tris-3; #endif for (i=0; isolution_tris[src_tri_id]->edges[src_edge_id]; if (edge->handy_mark) { src_edge = edge; src_edge->handy_mark = 0; } src_edge_id = (src_edge_id+1)%3; if (!(src_edge_id)) src_tri_id++; } /* get next dest edge */ dest_edge = NULL; while (!(dest_edge)) { edge = center_vert->tris[dest_tri_id]->edges[dest_edge_id]; if (edge->handy_mark) { dest_edge = edge; dest_edge->handy_mark = 0; } dest_edge_id = (dest_edge_id+1)%3; if (!(dest_edge_id)) dest_tri_id++; } /* copy the edge */ /* don't modify dest_edge->id */ /* use src_edge->id to store a pointer to the _new_ edge -- corrupts src_edge, which won't be used again anyway */ src_edge->id = (int)dest_edge; /* copy the vert pointers */ dest_edge->verts[0] = src_edge->verts[0]; dest_edge->verts[1] = src_edge->verts[1]; /* copy the tri pointers temporarily -- these will have to be overwritten with pointers into the solution mesh tris */ dest_edge->tris[0] = src_edge->tris[0]; dest_edge->tris[1] = src_edge->tris[1]; /* finish the copy */ dest_edge->handy_mark = src_edge->handy_mark; } #ifdef REMOVE_BORDER_VERTS if ((BORDER_VERT(center_vert)) && (center_vert->num_tris == 1)) { tri = center_vert->tris[0]; for (i=0; i<3; i++) { edge = tri->edges[i]; if (edge->tris[0] == tri) { edge->tris[0] = edge->tris[1]; edge->tris[1] = NULL; } else if (edge->tris[1] == tri) edge->tris[1] = NULL; } } #endif /** Update tris **/ for (i=0; i < hole->num_solution_tris; i++) { dest_tri = center_vert->tris[i]; src_tri = hole->solution_tris[i]; /* leave the id -- it will remain the index into solution mesh tris */ /* copy the new id into src_tri -- this corrupts src_tri, which won't be used again anyway */ src_tri->id = dest_tri->id; /* copy the vert pointers */ VEC3_ASN_OP(dest_tri->verts, =, src_tri->verts); /* copy the edges by looking at the source edge's id field, which now contains a pointer to the _new_ edge */ for (j=0; j<3; j++) { dest_tri->edges[j] = (Edge *)src_tri->edges[j]->id; for (k=0; k<2; k++) /* fix up the edge's aptri pointers */ if (dest_tri->edges[j]->tris[k] == src_tri) dest_tri->edges[j]->tris[k] = dest_tri; } /* copy plane equation */ VEC_ASN_OP(dest_tri->plane_eq, =, src_tri->plane_eq, 4); /* copy the rest */ dest_tri->handy_mark = src_tri->handy_mark; } /** Update the surrounding vertices **/ /* count number of new tris to be added to each vert */ for (i=0; inum_verts; i++) hole->verts[i]->handy_mark = 0; for (i=0; inum_solution_tris; i++) for (j=0; j<3; j++) hole->solution_tris[i]->verts[j]->handy_mark++; /* now redo the edge and face lists for each vertex */ for (i=0; i < hole->num_verts; i++) { vert = hole->verts[i]; new_num_tris = vert->num_tris - 2 + vert->handy_mark; if (BORDER_VERT(vert)) new_num_edges = new_num_tris + 1; else new_num_edges = new_num_tris; #ifdef REMOVE_BORDER_VERTS if ((BORDER_VERT(center_vert)) && ((i==0) || (i==hole->num_verts-1))) { new_num_tris = vert->num_tris - 1 + vert->handy_mark; if (BORDER_VERT(vert)) new_num_edges = new_num_tris + 1; else new_num_edges = new_num_tris; } #endif /* find the first edge to use for tracing around the vertex and the first tri that's on the counter-clockwise direction around the vertex from that edge */ if (!(BORDER_VERT(vert))) { /* any adjacent edge will do for the first edge -- just choose one from the hole boundary */ edge = hole->edges[i]; if (edge->verts[0] == vert) other_vert = edge->verts[1]; else if (edge->verts[1] == vert) other_vert = edge->verts[0]; else { fprintf(stderr, "update_model: couldn't find vert on first edge\n"); exit(1); } for (j=0; j<2; j++) { tri = edge->tris[j]; for (k=0, done = FALSE; k<3; k++) if ((tri->verts[k] == vert) && (tri->verts[(k+1)%3] == other_vert)) { done = TRUE; break; } if (done == TRUE) break; } if (done != TRUE) { fprintf(stderr, "update_model: can't find first face to trace vertex\n"); exit(1); } } else { /* choose first edge from vertex's current edge list, because this must be the correct border edge */ edge = vert->edges[0]; #ifdef REMOVE_BORDER_VERTS /* it may be necessary to use the newly created border edge as the first edge */ if ((BORDER_VERT(center_vert)) && ((edge->verts[0] == center_vert) || (edge->verts[1] == center_vert))) { if (i != (hole->num_verts-1)) { fprintf(stderr, "update_model: bad border condition\n"); exit(1); } if (center_vert->num_tris == 1) { /* special case -- the vertex we removed was on a single triangle, so we're just removing that triangle -- the "new" border edge in this case is actually a previously existing edge of the model */ edge = vert->edges[1]; if (!(((edge->verts[0] == hole->verts[0]) && (edge->verts[1] == hole->verts[hole->num_verts-1])) || ((edge->verts[1] == hole->verts[0]) && (edge->verts[0] == hole->verts[hole->num_verts-1])))) { fprintf(stderr, "update_model: couldn't find new "); fprintf(stderr, "boundary edge for special case\n"); exit(1); } } else { for (j=0, found=FALSE; jnum_edges; j++) { edge = center_vert->edges[j]; if (((edge->verts[0] == hole->verts[0]) && (edge->verts[1] == hole->verts[hole->num_verts-1])) || ((edge->verts[1] == hole->verts[0]) && (edge->verts[0] == hole->verts[hole->num_verts-1]))) { found = TRUE; break; } } if (found != TRUE) { fprintf(stderr, "update_model: couldn't find new boundary edge\n"); exit(1); } } } #endif tri = edge->tris[0]; if (edge->tris[1] != NULL) { fprintf(stderr, "update_model: border edge with 2 tris\n"); exit(1); } } /* REALLOC the edge and tri lists */ REALLOCN(vert->tris, Triangle *, vert->num_tris, new_num_tris); REALLOCN(vert->edges, Edge *, vert->num_edges, new_num_edges); if (BORDER_VERT(vert)) { vert->edges[0] = edge; vert->num_edges = 1; } else vert->num_edges = 0; vert->tris[0] = tri; vert->num_tris = 1; for (j=0, found=FALSE; j<3; j++) { if (tri->edges[j] == edge) { edge = tri->edges[(j+2)%3]; found = TRUE; break; } } if (found != TRUE) { fprintf(stderr, "update_model: couldn't find next edge\n"); exit(1); } vert->edges[vert->num_edges++] = edge; /* now walk around the vertex finding the next tri and next edge based on the previous tri and edge, until we reach the last edge */ while (vert->num_edges != new_num_edges) { if (edge->tris[0] == tri) tri = edge->tris[1]; else if (edge->tris[1] == tri) tri = edge->tris[0]; else { fprintf(stderr, "update_model: couldn't find next tri\n"); exit(1); } if (tri == NULL) { fprintf(stderr, "update_model: next tri is NULL pointer\n"); exit(1); } vert->tris[vert->num_tris++] = tri; for (j=0, found=FALSE; j<3; j++) { if (tri->edges[j] == edge) { edge = tri->edges[(j+2)%3]; found = TRUE; break; } } if (found != TRUE) { fprintf(stderr, "update_model: couldn't find next edge\n"); exit(1); } vert->edges[vert->num_edges++] = edge; } } /***** Update the Octree *****/ #ifdef USE_TRIOCTREE for (i=0; inum_solution_tris; i++) { tri = center_vert->tris[i]; trioctree_insert(model_octree, tri); } #else for (i=0; inum_solution_tris; i++) { tri = center_vert->tris[i]; element = &(model_octree_data[tri->id]); for (j=0; j<3; j++) { element->bbox[LO][j] = MAXDOUBLE; element->bbox[HI][j] = -MAXDOUBLE; for (k=0; k<3; k++) { element->bbox[LO][j] = FMIN(element->bbox[LO][j], tri->verts[k]->coord[j]); element->bbox[HI][j] = FMAX(element->bbox[HI][j], tri->verts[k]->coord[j]); } } element->data = tri; octree_insert(model_octree, element); } #endif FREE(center_vert->tris); FREE(center_vert->edges); center_vert->num_tris = center_vert->num_edges = 0; return; } /** End of update_model() **/ /*****************************************************************************\ @ border_condition_violated() ----------------------------------------------------------------------------- description : Vertices on a mesh border may have extra conditions imposed on them which may inhibit their removal -- this routine tests the extra conditions input : vertex, border tubes (if any), intersection fuzz_factor output : TRUE if the condition is violated, FALSE if not notes : \*****************************************************************************/ static int border_condition_violated(Vertex *vert, Octree *tubes, OctreeData **query_result, double fuzz_factor) { Edge *edge; Vertex *vert1, *vert2; #if (BORDER_TEST == TUBES_TEST) Edge an_edge; #else Vector vec1, vec2; double dot; #endif /* find the two adjacent border vertices which would be joined if this border vertex is removed */ edge = vert->edges[0]; if (edge->verts[0] == vert) vert1 = edge->verts[1]; else if (edge->verts[1] == vert) vert1 = edge->verts[0]; else { fprintf(stderr, "border_condition_violated: couldn't find vert on border edge\n"); exit(1); } edge = vert->edges[vert->num_edges-1]; if (edge->verts[0] == vert) vert2 = edge->verts[1]; else if (edge->verts[1] == vert) vert2 = edge->verts[0]; else { fprintf(stderr, "border_condition_violated: couldn't find vert on border edge\n"); exit(1); } /* test the border condition */ #if (BORDER_TEST == TUBES_TEST) an_edge.verts[0] = vert1; an_edge.verts[1] = vert2; return edge_tubes_intersect(&an_edge, tubes, query_result, fuzz_factor); #elif (BORDER_TEST == ANGLE_TEST) VEC3_V_OP_V(vec1, vert1->coord, -, vert->coord); VEC3_V_OP_V(vec2, vert2->coord, -, vert->coord); NORMALIZE3(vec1); NORMALIZE3(vec2); dot = DOTPROD3(vec1, vec2); return ((dot > COS_TEST_ANGLE) ? TRUE : FALSE); #elif (BORDER_TEST == XY_ANGLE_TEST) VEC3_V_OP_V(vec1, vert1->coord, -, vert->coord); VEC3_V_OP_V(vec2, vert2->coord, -, vert->coord); vec1[Z] = vec2[Z] = 0.0; NORMALIZE3(vec1); NORMALIZE3(vec2); dot = DOTPROD3(vec1, vec2); return ((dot > COS_TEST_ANGLE) ? TRUE : FALSE); #else INVALID_CHOICE_OF_BORDER_TEST!!!!! #endif } /** End of border_condition_violated() **/ /*****************************************************************************\ $Log: vertex_removal.c,v $ Revision 1.1.1.1 2000/04/06 15:35:32 philippe Initial CVS release Revision 1.7 1997/04/10 20:10:46 cohenj Added Amitabh's name to credits Revision 1.6 1996/04/19 03:10:31 cohenj #define some variable declarations * Revision 1.5 96/04/18 19:19:29 cohenj * 1. Added code for testing trioctree. * 2. Changed form of edge_tube intersection parameters * * Revision 1.4 96/04/08 19:16:36 cohenj * added procedure comments and copyright notice. * * Revision 1.3 95/10/16 16:29:41 cohenj * first working version * * 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 * \*****************************************************************************/