/******************************************************************************\ Copyright 1993 The Regents of the University of California. Modification 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 CALIFORNIA OR 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 CALIFORNIA OR THE UNIVERSITY OF N. 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 CALIFORNIA AND 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 CALIFORNIA HAS NO OBLIGATIONS TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. The authors may be contacted via: US Mail: Brian Mirtich J. Cohen/M. Lin/D. Manocha/K. Ponamgi 387 Soda Hall Department of Computer Science Computer Science Division Sitterson Hall, CB #3175 University of California University of N. Carolina Berkeley, CA 94720 Chapel Hill, NC 27599-3175 Phone: (510) 642-8149 (919)962-1749 EMail: mirtich@cs.berkeley.edu {cohenj,lin,manocha,ponamgi}@cs.unc.edu \*****************************************************************************/ /*****************************************************************************\ dist.h -- Description : This is the header file needed by dist.c, matrix.c, and any application program which uses the closest features code. file: dist.h programmer: Brian Mirtich last revised: 20 Jul 1993 \*****************************************************************************/ /* Protection from multiple includes. */ #ifndef INCLUDED_COLLISION_DIST_H #define INCLUDED_COLLISION_DIST_H /*------------------ Includes Needed for Definitions Below ------------------*/ #include /*-------------------------------- Constants --------------------------------*/ #define __COL_INFINITY 1.0e+20 #define __COL_EPSILON 0.0001 /*--------------------------------- Macros ----------------------------------*/ /*---------------------------------- Types ----------------------------------*/ /* ============================================================================= data structures 1. __col_Vertex, __col_Edge, and __col_Face These are the structures for vertices, edges, and faces. The fields which appear in these structures are listed below. tag: This is an integer field which appears first in all three structures. It takes a value V, E, or F, and is provided so we can identify the type of an arbitrary feature (e.g. one pointed to by a pointer to void) name: This string field is present in the __col_Vertex and __col_Face structures. Edge names are derived from the names of the endpoint vertices. coords & xcoords: coords are the coordinates of a __col_Vertex. When we transform the __col_Vertex to a different frame, xcoords holds the transformed coordinates. u & xu: u is a unit vector pointing from endpoint v1 to endpoint v2 of an __col_Edge. xu is the transformed version when we transform the edge to a different frame. len: The length of an __col_Edge. plane: This field is present in the __col_Face structure. It defines the four coefficients of the plane of the face, i.e. the plane of the face is given by plane[0]*x + plane[1]*y + plane[2]*z + plane[3] = 0. Furthermore, the first 3 components are a unit vector, which form the outward normal of the face. verts: This is a list of vertices (in CCW order) around a __col_Face. edges: This is a list of edges incident to a __col_Vertex, or the boundary edges (in CCW order) of a __col_Face. v1 & v2: The startpoint end endpoint vertices of an __col_Edge. fl & fr: The left and right faces of an __col_Edge, respectively. The "left" face is the one on the left hand side of an observer standing on v1, looking toward v2, and standing on the outside of the polyhedron. cone: This field is present in all three structures, and points to the list of planes defining the features voronoi region. For a __col_Face, only the side planes are present in this list. 2. __col_Polyhedron This is the basic data structure for a polyhedron. It contains the following fields. name: A string; the name of the polyhedron, if any. verts: The list of vertices of the polyhedron. edges: The list of edges of the polyhedron. faces: What a surprise -- the list of faces of the polyhedron. pose: The pose field is a transformation matrix. The coordinates of a polyhedron's vertices, and hence the location of its edges and faces are all defined relative to a body frame. All of the planes defining the voronoi region are also relative to this frame. However, a polyhedron is allowed to move through space, and the pose matrix expresses the pose of the body frame relative to some fixed global frame. Thus, the pose matrix Px of polyhedron x transforms body coordinates to "world" coordinates. Now let x and y be two polyhedra, with pose matrices Px and Py. Suppose we want to compute Txy, a transformation matrix which transforms coordinates from x's body frame to y's body frame, and Tyx, it's inverse. It's easy to show that Txy = Inv(Py) * Px, and Tyx = Inv(Px) * Py. 3. col_Fnode col_Fnode stands for feature node. col_Fnodes are used for building lists of features, such as the lists of features in the __col_Polyhedron structure, and also the list of edges in the __col_Vertex structure, and the lists of vertices and edges in the __col_Face structure. An col_Fnode has two fields. f: f points to an actual feature. f is a union, so it may be treated as a pointer to a __col_Vertex, __col_Edge, or __col_Face, depending on what type of feature list we're dealing with. There is also an "any" field in the union, for when we don't care what type of feature f points to. next: This points to the next col_Fnode in the list, or is NULL if this is the last one. 4. __col_PNode __col_PNode stands for plane node. __col_PNodes are used for building lists of planes which define the voronoi regions for the features of a polyhedron. These lists are pointed to by the cone fields of the __col_Vertex, __col_Edge, and __col_Face structure. __col_PNodes contain the following three fields. plane: These are the four coefficients of the actual plane, i.e. the plane is given by plane[0]*x + plane[1]*y + plane[2]*z + plane[3] = 0. Furthermore, the first three components of plane form a unit vector pointing toward the "good" side of the plane. If a point lies within a voronoi region, it lies on the good side of all planes defining that region. If it lies on the bad sign of any of the planes, it is not in the voronoi region. nbr: This is points to the neighboring feature which gives rise to the particular plane specified by the plane field. When a point lies on the "bad" side of a particular plane, the nbr field points to the feature we should walk to when searching for the closest feature pair. next: This points to the next __col_PNode in the list, or is NULL if this is the last one. ============================================================================= */ typedef struct __col_planeNode { /* plane[0] * x + plane[1] * y + plane[2] * z + plane[3] >= 0 */ col_Vect4 plane; void *nbr; /* point to feature to move to if this test fails */ struct __col_planeNode *next; /* if there are more planes in this cone */ } __col_PNode; typedef struct __col_vertex { int tag; char name[20]; col_Vect3 coords; col_Vect3 xcoords; struct __col_featureNode *edges; __col_PNode *cone; } __col_Vertex; typedef struct __col_face { int tag; char name[20]; struct __col_featureNode *verts; struct __col_featureNode *edges; col_Vect4 plane; __col_PNode *cone; } __col_Face; typedef struct __col_edge { int tag; __col_Vertex *v1, *v2; __col_Face *fl, *fr; col_Vect3 u; /* unit vector from v1 -> v2 */ col_Vect3 xu; /* xformed unit vector from v1 -> v2 */ __col_Real len; /* length of edge */ __col_Real xlen; /* xformed length -- necessary if pose can include scaling */ __col_PNode *cone; } __col_Edge; typedef struct __col_featureNode { union{ __col_Vertex *v; __col_Edge *e; __col_Face *f; void *any; } f; struct __col_featureNode *next; } col_Fnode; typedef struct __col_polyhedron { char name[20]; col_Mat4 pose; col_Mat4 inv_pose; col_Fnode *verts; col_Fnode *edges; col_Fnode *faces; } __col_Polyhedron; /*---------------------------- Function Prototypes --------------------------*/ int __col_randomInt(int n); void *__col_randFeat(__col_Polyhedron *p); int __col_loadPolyhedronLibrary(char *fname, double scale); __col_Polyhedron *__col_createPolyhedron(char *libName, char *name); __col_Real __col_closestFeatures(__col_Polyhedron *poly1, void **feat1, __col_Polyhedron *poly2, void **feat2); /*---------------------------Globals (externed)------------------------------*/ /* Protection from multiple includes. */ #endif /* INCLUDED_COLLISION_DIST_H */ /*****************************************************************************\ \*****************************************************************************/