/****************************************************************************\ 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 \****************************************************************************/ /*****************************************************************************\ geometry.c -- Description : A few general purpose routines to manipulate the basic geometric types (defined in geometry.h) ---------------------------------------------------------------------------- $Source: /cvs/RenderPark/SE/Simplify/geometry.c,v $ $Revision: 1.1.1.1 $ $Date: 2000/04/06 15:35:32 $ $Author: philippe $ $Locker: $ \*****************************************************************************/ /*----------------------------- Local Includes -----------------------------*/ #include #include #include /*----------------------------- Local Constants -----------------------------*/ /*------------------------------ Local Macros -------------------------------*/ /*------------------------------- Local Types -------------------------------*/ /*------------------------ Local Function Prototypes ------------------------*/ /*------------------------------ Local Globals ------------------------------*/ /*---------------------------------Functions-------------------------------- */ /*****************************************************************************\ @ find_plane_eq() ----------------------------------------------------------------------------- description : Calculate a plane equation from 3 points in the form: ax + by + cz = d input : 3 points output : [0]x + [1]y + [2]z = [3] notes : assumes vertices are in ctr-clockwise direction \*****************************************************************************/ void find_plane_eq(Point pt0, Point pt1, Point pt2, double plane_eq[4]) { Point diff1, diff2; VEC3_V_OP_V(diff1, pt2, -, pt0); VEC3_V_OP_V(diff2, pt2, -, pt1); CROSSPROD3(plane_eq, diff1, diff2); NORMALIZE3(plane_eq); plane_eq[3] = DOTPROD3(plane_eq, pt0); } /** End of find_plane_eq() **/ /*****************************************************************************\ @ tri_to_rawtri() ----------------------------------------------------------------------------- description : Convert a triangle data structure, which may have lots of fields, to a bottom-of-the-line triangle, with just vertex coordinates and a plane equation input : Triangle output : RawTriangle notes : \*****************************************************************************/ void tri_to_rawtri(Triangle *tri, RawTriangle *rawtri) { int i; for (i=0; i<3; i++) VEC3_ASN_OP(rawtri->verts[i], =, tri->verts[i]->coord); VEC_ASN_OP(rawtri->plane_eq, =, tri->plane_eq, 4); return; } /** End of tri_to_rawtri() **/ /*****************************************************************************\ @ get_common_index_verts() ----------------------------------------------------------------------------- description : Given two triangles with indices to a set of shared vertices, find which, if any, vertices they have in common input : Two triangles output : 1. Number of vertices in common 2. Array of these common vertices, indicating which place each of these vertices has in each of the two triangles' list of vertices. common_verts[0][0] == 1st common vertex's place in tri1's list of vertices (1st, 2nd, or 3rd) common_verts[0][1] == 1st common vertex's place in tri2's list of vertices (1st, 2nd, or 3rd) common_verts[1][0] == 2nd common vertex's place in tri1's list of vertices common_verts[1][1] == 2nd common vertex's place in tri2's list of vertices common_verts[2][0] == 3rd common vertex's place in tri1's list of vertices common_verts[2][1] == 3rd common vertex's place in tri2's list of vertices notes : \*****************************************************************************/ int get_common_index_verts(Triangle *tri1, Triangle *tri2, int common_verts[3][2]) { int i, j; int num_common_verts; num_common_verts = 0; for (i=0; i<3; i++) for (j=0; j<3; j++) if (tri1->verts[i]->id == tri2->verts[j]->id) { common_verts[num_common_verts][0] = i; common_verts[num_common_verts][1] = j; num_common_verts++; } return num_common_verts; } /** End of get_common_index_verts() **/ /*****************************************************************************\ @ get_common_coord_verts() ----------------------------------------------------------------------------- description : Given two triangles, find which, if any, vertices they have in common (with exactly the same coordinates) input : Two triangles output : 1. Number of vertices in common 2. Array of these common vertices, indicating which place each of these vertices has in each of the two triangles' list of vertices. common_verts[0][0] == 1st common vertex's place in tri1's list of vertices (1st, 2nd, or 3rd) common_verts[0][1] == 1st common vertex's place in tri2's list of vertices (1st, 2nd, or 3rd) common_verts[1][0] == 2nd common vertex's place in tri1's list of vertices common_verts[1][1] == 2nd common vertex's place in tri2's list of vertices common_verts[2][0] == 3rd common vertex's place in tri1's list of vertices common_verts[2][1] == 3rd common vertex's place in tri2's list of vertices notes : \*****************************************************************************/ int get_common_coord_verts(Triangle *tri1, Triangle *tri2, int common_verts[3][2]) { int i, j; int num_common_verts; num_common_verts = 0; for (i=0; i<3; i++) for (j=0; j<3; j++) if (VEC3_EQ(tri1->verts[i]->coord, tri2->verts[j]->coord)) { common_verts[num_common_verts][0] = i; common_verts[num_common_verts][1] = j; num_common_verts++; } return num_common_verts; } /** End of get_common_coord_verts() **/ /*****************************************************************************\ @ get_common_coord_edge_tri_verts() ----------------------------------------------------------------------------- description : input : output : notes : \*****************************************************************************/ int get_common_coord_edge_tri_verts(Edge *edge, Triangle *tri, int common_verts[2][2]) { int i, j; int num_common_verts; num_common_verts = 0; for (i=0; i<2; i++) for (j=0; j<3; j++) if (VEC3_EQ(edge->verts[i]->coord, tri->verts[j]->coord)) { common_verts[num_common_verts][0] = i; common_verts[num_common_verts][1] = j; num_common_verts++; } return num_common_verts; } /** End of get_common_coord_edge_tri_verts() **/ /*****************************************************************************\ @ point_line_distance() ----------------------------------------------------------------------------- description : Find the distance from a point to an infinite line input : 3 vertices -- one is the point, the other two lie on the infinite line output : distance from the point to the line notes : \*****************************************************************************/ double point_line_distance(Vertex *point, Vertex *line_vert1, Vertex *line_vert2) { double plane_eq[4]; Point line_closest_point; double t; double distance; VEC3_V_OP_V(plane_eq, line_vert2->coord, -, line_vert1->coord); NORMALIZE3(plane_eq); /* may not be necessary? */ plane_eq[3] = DOTPROD3(plane_eq, point->coord); t = (plane_eq[3] - DOTPROD3(line_vert1->coord, plane_eq)); VEC3_V_OP_V_OP_S(line_closest_point, line_vert1->coord, +, plane_eq, *, t); distance = sqrt(SQ_DIST3(point->coord, line_closest_point)); return distance; } /** End of point_line_distance() **/ /*****************************************************************************\ @ free_surface() ----------------------------------------------------------------------------- description : Deallocate the dynamic space associated with a Surface structure input : Surface structure output : notes : \*****************************************************************************/ void free_surface(Surface *surface) { int i; for (i=0; inum_verts; i++) { FREE(surface->verts[i].edges); FREE(surface->verts[i].tris); } FREE(surface->verts); FREE(surface->edges); FREE(surface->tris); surface->num_verts = surface->num_edges = surface->num_tris = 0; return; } /** End of free_surface() **/ /*****************************************************************************\ $Log: geometry.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:12:44 cohenj no change * Revision 1.5 96/04/18 19:09:33 cohenj * added some more functions for finding common vertices * * Revision 1.4 96/04/08 18:49:08 cohenj * added procedure comments and copyright * >> . * * Revision 1.3 95/10/16 16:29:41 cohenj * added free_surface() function * * 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 * \*****************************************************************************/