/****************************************************************************\ 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 \****************************************************************************/ /*****************************************************************************\ offset.c -- Description : Functions related to calculating a non-self-intersecting offset surface to a surface mesh. ---------------------------------------------------------------------------- $Source: /cvs/RenderPark/SE/Simplify/offset.c,v $ $Revision: 1.1.1.1 $ $Date: 2000/04/06 15:35:32 $ $Author: philippe $ $Locker: $ \*****************************************************************************/ /*----------------------------- Local Includes -----------------------------*/ #include #include #include #include #ifdef USE_TRIOCTREE #include #else #include #endif #include #include #include #include /*----------------------------- Local Constants -----------------------------*/ #define MIN_STEPS (10) #define MAX_SUBDIVISIONS (20) #define COS_89_5 (0.0087265355) /*------------------------------ Local Macros -------------------------------*/ #define ABS(a) (((a) >= 0) ? (a) : (-a)) /*------------------------------- Local Types -------------------------------*/ /*------------------------ Local Function Prototypes ------------------------*/ void init_offset_surface(Surface *model, Surface *offset); int bad_normal(Vertex *vert); void offset_vertex(Vertex *orig_vert, Vertex *offset_vert, double epsilon, Octree *octree, OctreeData *octdata, OctreeData **query_result, double fuzz_factor, char *frozen, double *vert_epsilon); /*------------------------------ Local Globals ------------------------------*/ /*---------------------------------Functions-------------------------------- */ /*****************************************************************************\ @ init_offset_surface() ----------------------------------------------------------------------------- description : Initialize an offset surface to be a copy of the original surface input : Surface mesh output : Offset surface mesh == surface mesh notes : \*****************************************************************************/ void init_offset_surface(Surface *model, Surface *offset) { int i, j; Vertex *src_vert, *dest_vert; Edge *src_edge, *dest_edge; Triangle *src_tri, *dest_tri; ALLOCN(offset->verts, Vertex, model->num_verts); ALLOCN(offset->tris, Triangle, model->num_tris); ALLOCN(offset->edges, Edge, model->num_edges); for (i=0; inum_verts; i++) { src_vert = &(model->verts[i]); dest_vert = &(offset->verts[i]); dest_vert->id = src_vert->id; VEC3_ASN_OP(dest_vert->coord, =, src_vert->coord); VEC3_ASN_OP(dest_vert->normal, =, src_vert->normal); ALLOCN(dest_vert->tris, Triangle *, src_vert->num_tris); for (j=0; jnum_tris; j++) dest_vert->tris[j] = &(offset->tris[src_vert->tris[j]->id]); dest_vert->num_tris = src_vert->num_tris; ALLOCN(dest_vert->edges, Edge *, src_vert->num_edges); for (j=0; jnum_edges; j++) dest_vert->edges[j] = &(offset->edges[src_vert->edges[j]->id]); dest_vert->num_edges = src_vert->num_edges; dest_vert->other_props = src_vert->other_props; #ifdef VERTEX_EPSILONS dest_vert->epsilon = src_vert->epsilon; #endif } offset->num_verts = model->num_verts; for (i=0; inum_edges; i++) { src_edge = &(model->edges[i]); dest_edge = &(offset->edges[i]); dest_edge->id = src_edge->id; for (j=0; j<2; j++) { dest_edge->verts[j] = &(offset->verts[src_edge->verts[j]->id]); if (src_edge->tris[j] != NULL) dest_edge->tris[j] = &(offset->tris[src_edge->tris[j]->id]); else dest_edge->tris[j] = NULL; } } offset->num_edges = model->num_edges; for (i=0; inum_tris; i++) { src_tri = &(model->tris[i]); dest_tri = &(offset->tris[i]); dest_tri->id = src_tri->id; for (j=0; j<3; j++) { dest_tri->verts[j] = &(offset->verts[src_tri->verts[j]->id]); dest_tri->edges[j] = &(offset->edges[src_tri->edges[j]->id]); } VEC_ASN_OP(dest_tri->plane_eq, =, src_tri->plane_eq, 4); } offset->num_tris = model->num_tris; return; } /** End of init_offset_surface() **/ /*****************************************************************************\ @ bad_normal() ----------------------------------------------------------------------------- description : A bad vertex normal is a normal which differs from the normal of one of the adjacent faces by more than 90 degrees input : A vertex output : TRUE if the normal is bad, FALSE if it's okay notes : \*****************************************************************************/ int bad_normal(Vertex *vert) { int i; for (i=0; inum_tris; i++) if (DOTPROD3(vert->normal, vert->tris[i]->plane_eq) < COS_89_5) return TRUE; return FALSE; } /** End of bad_normal() **/ /*****************************************************************************\ @ offset_vertex() ----------------------------------------------------------------------------- description : Attempt to offset a vertex by some small amount in the direction of its normal vector. If no self-intersection is created, the move is accepted, otherwise it is rejected. input : 1. original mesh vertex 2. offset vertex in position it's been offset to so far 3. epsilon distance by which the vertex should be offset from its _original_ position 4. octree of offset surface, including its data elements and some space in which to store query results. 5. fuzz factor to use in intersection tests output : If vertex is moved, frozen == FALSE and vert_epsilon == epsilon; otherwise, frozen == TRUE and vert_epsilon is unchanged. notes : This routine could stand a bit of improvement. Currently, it does not test for intersections amongst the vertex's adjacent triangles. \*****************************************************************************/ void offset_vertex(Vertex *orig_vert, Vertex *offset_vert, double epsilon, Octree *octree, OctreeData *octdata, OctreeData **query_result, double fuzz_factor, char *frozen, double *vert_epsilon) { int i, j; #ifndef USE_TRIOCTREE int k; OctreeData *element; Extents tri_bbox; double box_fuzz; #endif Point new_coord, prev_coord; Vector displacement; int query_count; Triangle *tri, *tri2; int intersect; if (bad_normal(offset_vert) == TRUE) { *frozen = TRUE; return; } VEC3_V_OP_S(displacement, orig_vert->normal, *, epsilon); VEC3_V_OP_V(new_coord, orig_vert->coord, +, displacement); VEC3_ASN_OP(prev_coord, =, offset_vert->coord); VEC3_ASN_OP(offset_vert->coord, =, new_coord); /* Note that changing the vertex coordinates has implicitly modified all its adjacent triangles (which have a pointer to this vertex). These triangles' plane equations are now incorrect, as are any bounding boxes of these triangles and their locations in the octree. Rather than delete all these triangles from the octree and reinsert them, ignore those triangles in octree queries. Only update the octree if the offset succeeds. */ /* Update all the plane equations so the intersection tests will function correctly. */ for (i=0; inum_tris; i++) { tri = offset_vert->tris[i]; find_plane_eq(tri->verts[0]->coord, tri->verts[1]->coord, tri->verts[2]->coord, tri->plane_eq); } #if 0 /* First test for intersections among the set of triangles surrounding the vertex (these are the cheapest intersection tests and don't require octree queries, so we can back out quickly if any of them fail). */ for (i=0, intersect = FALSE; ((inum_tris-1) && (intersect == FALSE)); i++) for (j=i+1; ((jnum_tris) && (intersect == FALSE)); j++) { intersect = index_filtered_tri_tri_intersect(offset_vert->tris[i], offset_vert->tris[j], fuzz_factor, SURFACE_VS_ITSELF); } /* Back out if we've already found an intersection */ if (intersect == TRUE) { VEC3_ASN_OP(offset_vert->coord, =, prev_coord); for (i=0; inum_tris; i++) { tri = offset_vert->tris[i]; find_plane_eq(tri->verts[0]->coord, tri->verts[1]->coord, tri->verts[2]->coord, tri->plane_eq); } *frozen = TRUE; return; } #endif /* Now look for other intersections by making octree queries. We don't care about triangles surrounding the vertex we're offsetting, because we just tested those (and they're not quite in the correct position in the octree, anyway). */ for (i=0, intersect=FALSE; ((inum_tris) && (intersect == FALSE)); i++) { tri = offset_vert->tris[i]; #ifdef USE_TRIOCTREE trioctree_tri_range_query(octree, tri, query_result, &query_count); #else tri_bbox[HI][X] = tri_bbox[HI][Y] = tri_bbox[HI][Z] = -MAXDOUBLE; tri_bbox[LO][X] = tri_bbox[LO][Y] = tri_bbox[LO][Z] = MAXDOUBLE; for (j=0; j<3; j++) for (k=0; k<3; k++) { tri_bbox[HI][k] = FMAX(tri_bbox[HI][k], tri->verts[j]->coord[k]); tri_bbox[LO][k] = FMIN(tri_bbox[LO][k], tri->verts[j]->coord[k]); } if (fuzz_factor < 0.0) for (j=0; j<3; j++) { box_fuzz = (tri_bbox[HI][j] - tri_bbox[LO][j])*-fuzz_factor; tri_bbox[HI][j] += box_fuzz; tri_bbox[LO][j] -= box_fuzz; } octree_range_query(octree, tri_bbox, query_result, &query_count); #endif for (j=0; ((jdata); #endif if ((tri2->verts[0] == offset_vert) || (tri2->verts[1] == offset_vert) || (tri2->verts[2] == offset_vert)) continue; intersect = index_filtered_tri_tri_intersect(tri, tri2, fuzz_factor, SURFACE_VS_ITSELF); } } /* Back out if we've found an intersection */ if (intersect == TRUE) { VEC3_ASN_OP(offset_vert->coord, =, prev_coord); for (i=0; inum_tris; i++) { tri = offset_vert->tris[i]; find_plane_eq(tri->verts[0]->coord, tri->verts[1]->coord, tri->verts[2]->coord, tri->plane_eq); } *frozen = TRUE; return; } /* No intersection, so we plan to accept this offset. Now we have to make the octree reflect the triangles' current positions. */ #ifdef USE_TRIOCTREE /* put the triangles back to their original positions to remove them from the trioctree */ VEC3_ASN_OP(offset_vert->coord, =, prev_coord); for (i=0; inum_tris; i++) { tri = offset_vert->tris[i]; find_plane_eq(tri->verts[0]->coord, tri->verts[1]->coord, tri->verts[2]->coord, tri->plane_eq); trioctree_remove(octree, tri); } /* now put the triangles back to their final positions and insert into the trioctree */ VEC3_ASN_OP(offset_vert->coord, =, new_coord); for (i=0; inum_tris; i++) { tri = offset_vert->tris[i]; find_plane_eq(tri->verts[0]->coord, tri->verts[1]->coord, tri->verts[2]->coord, tri->plane_eq); trioctree_insert(octree, tri); } #else for (i=0; inum_tris; i++) { tri = offset_vert->tris[i]; element = &(octdata[tri->id]); octree_remove(octree, element); for (j=0; j<3; j++) { element->bbox[HI][j] = FMAX(FMAX(tri->verts[0]->coord[j], tri->verts[1]->coord[j]), tri->verts[2]->coord[j]); element->bbox[LO][j] = FMIN(FMIN(tri->verts[0]->coord[j], tri->verts[1]->coord[j]), tri->verts[2]->coord[j]); } octree_insert(octree, element); } #endif *vert_epsilon = epsilon; return; } /** End of offset_vertex() **/ /*****************************************************************************\ @ min_vert_edge_length() ----------------------------------------------------------------------------- description : Find the minimum length edge adjacent to some vertex. Only count edges that are within 90 degrees of the offset direction (positive or negative of the normal vector). input : Vertex, epsilon (only the sign of the epsilon is used) output : minimum edge length as described above notes : \*****************************************************************************/ static double min_vert_edge_length(Vertex *vert, double epsilon) { int i; Vertex *other_vert; Edge *edge; double sq_length, min_sq_length, length; Vector edge_vec; double dot; for (i=0, min_sq_length = MAXDOUBLE; inum_edges; i++) { edge = vert->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, "min_vert_edge_length: couldn't find other vert\n"); exit(-1); } VEC3_V_OP_V(edge_vec, other_vert->coord, -, vert->coord); dot = DOTPROD3(edge_vec, vert->normal); if ((dot*epsilon) < 0) continue; sq_length = DOTPROD3(edge_vec, edge_vec); if (sq_length <= 0.0) { fprintf(stderr, "min_vert_edge_length: degenerate edge\n"); exit(-1); } min_sq_length = FMIN(min_sq_length, sq_length); } length = sqrt(min_sq_length); return length; } /** End of min_vert_edge_length() **/ /*****************************************************************************\ @ offset_surface() ----------------------------------------------------------------------------- description : Generate a non-self-intersecting offset surface to the given surface mesh input : Surface mesh, epsilon distance of maximum offset, max_node_objs_hint to use in generating octree, and intersection test fuzz factor output : offset surface mesh notes : \*****************************************************************************/ void offset_surface(Surface *model, Surface *offset, double epsilon, int max_node_objs_hint, double fuzz_factor) { char *vert_frozen; double *vert_epsilon; Octree *octree; OctreeData *octdata; OctreeData **query_result; int i, j; Vector box_length; double diag_length, percent_epsilon; double *vert_step_size, max_step_size, min_step_size; int k, num_moving_verts, max_iterations, min_steps, cheated_verts; double new_epsilon, min_edge; fprintf(stderr, "Epsilon: %f\n", epsilon); init_offset_surface(model, offset); surface_to_octree(offset, &octree, &octdata, fabs(epsilon)*1.01, max_node_objs_hint); VEC3_V_OP_S(box_length, octree->root->sides, -, fabs(epsilon)*1.01); VEC3_V_OP_S(box_length, box_length, *, 2.0); diag_length = sqrt(DOTPROD3(box_length, box_length)); percent_epsilon = fabs(epsilon/diag_length * 100.0); ALLOCN(query_result, OctreeData *, offset->num_tris); ALLOCN(vert_frozen, char, offset->num_verts); ALLOCN(vert_epsilon, double, offset->num_verts); ALLOCN(vert_step_size, double, offset->num_verts); min_steps = FMAX(percent_epsilon*MIN_STEPS, MIN_STEPS); max_step_size = (fabs(epsilon) * 0.99)/(double)min_steps; min_step_size = max_step_size; /* initialize per-vertex information */ for (i=0; inum_verts; i++) { vert_frozen[i] = FALSE; vert_epsilon[i] = 0.0; min_edge = min_vert_edge_length(&(offset->verts[i]), epsilon); #ifdef VERTEX_EPSILONS max_step_size = (fabs(offset->verts[i].epsilon)*0.99)/(double)min_steps; #endif vert_step_size[i] = FMIN(0.49 * min_edge, max_step_size) * ((epsilon<0) ? -1.0 : 1.0); min_step_size = FMIN(min_step_size, fabs(vert_step_size[i])); } /* offset method uses per-vertex step sizes, with some subdivision of this step size as necessary */ max_iterations = (int)(fabs(epsilon)/min_step_size); fprintf(stderr, "offsetting vertices (maximum of %d iterations): ", max_iterations); for (i=0, num_moving_verts=offset->num_verts, cheated_verts = 0; ((num_moving_verts > 0) && (i < max_iterations)); i++) { fprintf(stderr, "%d ", i); fflush(stderr); for (j=0; jnum_verts; j++) { if (vert_frozen[j] == TRUE) continue; new_epsilon = vert_epsilon[j] + vert_step_size[j]; #ifndef VERTEX_EPSILONS if ((fabs(new_epsilon) < fabs(epsilon)) && #else /* VERTEX_EPSILONS */ if ((fabs(new_epsilon) < fabs(offset->verts[j].epsilon)) && #endif (fabs(new_epsilon) > fabs(vert_epsilon[j]))) offset_vertex(&(model->verts[j]), &(offset->verts[j]), new_epsilon, octree, octdata, query_result, fuzz_factor, &(vert_frozen[j]), &(vert_epsilon[j])); else vert_frozen[j] = TRUE; if ((vert_frozen[j] == TRUE) && (i < MIN_STEPS)) { for (k=0; ((vert_frozen[j]==TRUE) && (kverts[j].epsilon)) && #endif (fabs(new_epsilon) > fabs(vert_epsilon[j]))) offset_vertex(&(model->verts[j]), &(offset->verts[j]), new_epsilon, octree, octdata, query_result, fuzz_factor, &(vert_frozen[j]), &(vert_epsilon[j])); else vert_frozen[j] = TRUE; } if (vert_frozen[j]==TRUE) cheated_verts++; } if (vert_frozen[j] == TRUE) num_moving_verts--; } } fprintf(stderr, " -- done\n\n"); fprintf(stderr, "Cheated verts: %d\n\n", cheated_verts); fflush(stderr); #ifdef USE_TRIOCTREE fprintf(stderr, "Destroying trioctree..."); trioctree_destroy(&octree); fprintf(stderr, "done\n"); #else fprintf(stderr, "Destroying octree..."); octree_destroy(&octree); fprintf(stderr, "done\n"); FREE(octdata); #endif FREE(query_result); FREE(vert_frozen); FREE(vert_epsilon); FREE(vert_step_size); return; } /** End of offset_surface() **/ /*****************************************************************************\ @ surface_to_octree() ----------------------------------------------------------------------------- description : Create an octree from a surface mesh to allow fast queries during intersection testing input : 1. Surface mesh to be octree'ized 2. buffer_width -- The octree partitions some specific region of space. This region of space shall be the bounding box of the surface mesh + buffer_width extra space in each direction. The allows for the object to be offset, for instance, up to buffer_width distance and still lie in the octree's space. 3. max_node_objs_hint -- Setting the octree parameters is a fairly heuristic process. Because the octree will store triangles of a mesh, no amount of partitioning will cause a cell to hold fewer triangles than the number of triangles adjacent to some vertex contained in the cell. If this hint variable is non-negative, it is used as the cell subdivision criterion (subdivide until cell contains fewer than this number of triangles). Otherwise, this function will choose some number based on the average vertex degree and the standard deviation. output : octree containing surface and octree data elements notes : \*****************************************************************************/ void surface_to_octree(Surface *model, Octree **octree, OctreeData **data, double buffer_width, int max_node_objs_hint) { int i, j, k; #ifndef USE_TRIOCTREE OctreeData *octdata; OctreeData *element; #endif Triangle *tri; Extents global_bbox; double min_max_side, element_max_side, side_length; Vertex *vert; double mean, deviation, sum_of_square_deviations; double variance, std_deviation; int max_node_objs; #ifdef USE_TRIOCTREE Extents element_bbox; #endif fprintf(stderr, "Creating octree..."); #ifndef USE_TRIOCTREE ALLOCN(octdata, OctreeData, model->num_tris); *data = octdata; /* prepare octree data elements */ for (i=0; inum_tris; i++) { tri = &(model->tris[i]); element = &(octdata[i]); 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; } /* calculate total space to be partitioned */ global_bbox[LO][X] = global_bbox[LO][Y] = global_bbox[LO][Z] = MAXDOUBLE; global_bbox[HI][X] = global_bbox[HI][Y] = global_bbox[HI][Z] = -MAXDOUBLE; for (i=0; inum_tris; i++) { for (j=0; j<3; j++) { global_bbox[LO][j] = FMIN(global_bbox[LO][j], octdata[i].bbox[LO][j]); global_bbox[HI][j] = FMAX(global_bbox[HI][j], octdata[i].bbox[HI][j]); } } #else /* calculate total space to be partitioned */ global_bbox[LO][X] = global_bbox[LO][Y] = global_bbox[LO][Z] = MAXDOUBLE; global_bbox[HI][X] = global_bbox[HI][Y] = global_bbox[HI][Z] = -MAXDOUBLE; for (i=0; inum_tris; i++) { tri = &(model->tris[i]); for (j=0; j<3; j++) { for (k=0; k<3; k++) { global_bbox[LO][j] = FMIN(global_bbox[LO][j], tri->verts[k]->coord[j]); global_bbox[HI][j] = FMAX(global_bbox[HI][j], tri->verts[k]->coord[j]); } } } #endif for (i=0; i<3; i++) { global_bbox[LO][i] -= (buffer_width); global_bbox[HI][i] += (buffer_width); } min_max_side = MAXDOUBLE; for (i=0; inum_tris; i++) { tri = &(model->tris[i]); #ifdef USE_TRIOCTREE 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_max_side = 0; for (j=0; j<3; j++) { side_length = element_bbox[HI][j] - element_bbox[LO][j]; element_max_side = FMAX(element_max_side, side_length); } #else element = &(octdata[i]); element_max_side = 0; for (j=0; j<3; j++) { side_length = element->bbox[HI][j] - element->bbox[LO][j]; element_max_side = FMAX(element_max_side, side_length); } #endif if (element_max_side <= 0) { fprintf(stderr, "surface_to_octree: couldn't find element max side\n"); exit(1); } min_max_side = FMIN(min_max_side, element_max_side); } if (min_max_side == MAXDOUBLE) { fprintf(stderr, "surface_to_octree: couldn't find min_max_side\n"); exit(1); } if (max_node_objs_hint <= 0) { /* average tris per vertex -- 3F/V */ mean = model->num_tris * 3 / model->num_verts; for (i=0, sum_of_square_deviations = 0.0; inum_verts; i++) { vert = &(model->verts[i]); deviation = mean - vert->num_tris; sum_of_square_deviations += deviation*deviation; } variance = sum_of_square_deviations / model->num_verts; std_deviation = sqrt(variance); max_node_objs = (int)(mean + 3*std_deviation + 0.99999999) * 1.5; } else max_node_objs = max_node_objs_hint; #ifdef USE_TRIOCTREE trioctree_create(octree, global_bbox, min_max_side*2.0, max_node_objs); for (i=0; inum_tris; i++) trioctree_insert(*octree, &(model->tris[i])); fprintf(stderr, "done\n"); trioctree_print_stats(*octree); #else octree_create(octree, global_bbox, min_max_side*2.0, max_node_objs); for (i=0; inum_tris; i++) octree_insert(*octree, &(octdata[i])); fprintf(stderr, "done\n"); octree_print_stats(*octree); #endif return; } /** End of surface_to_octree() **/ /*****************************************************************************\ $Log: offset.c,v $ Revision 1.1.1.1 2000/04/06 15:35:32 philippe Initial CVS release Revision 1.10 1997/04/10 20:10:46 cohenj Added Amitabh's name to credits Revision 1.9 1996/08/23 21:36:02 cohenj added test for null triangle on an edge before copying * Revision 1.8 96/08/23 18:01:04 cohenj * 1) Reverted to an older heuristic for calculating min_side during * octree creation * 2) Made bad_normal test slightly more conservative * 3) Removed unnecessary tests between triangles surrounding the vertex * currently being offset (intersection tests) * Revision 1.7 1996/04/19 03:35:48 cohenj 1. Moved test_self_intersect() to intersect.c 2. Removed old offset method 3. Fixed the way offset_vertex() deals with testing for intersections of triangles in the neighborhood of the vertex being offset * Revision 1.6 96/04/18 19:16:37 cohenj * 1. Revamped calculation of min_side in surface_to_octree(). * The old calculation didn't perform well if the model's * bounding box had widely varying dimensions * 2. Added filtering to triangle vs. offset intersection tests. * 3. Added code for testing trioctree structure * * Revision 1.5 96/04/08 18:52:52 cohenj * added support for per-vertex epsilons, procedure comments, * and copyright notice * * Revision 1.3 95/10/16 16:29:41 cohenj * Cleaned up. * * 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 95/09/15 16:28:21 cohenj * Initial revision * * Revision 1.2 1995/09/12 18:16:47 cohenj * removed old debugging code * * Revision 1.1 1995/08/30 20:57:04 cohenj * Initial revision * \*****************************************************************************/