MOAB: Mesh Oriented datABase  (version 5.3.1)
GeomUtil.hpp
Go to the documentation of this file.
00001 /*
00002  * MOAB, a Mesh-Oriented datABase, is a software component for creating,
00003  * storing and accessing finite element mesh data.
00004  *
00005  * Copyright 2004 Sandia Corporation.  Under the terms of Contract
00006  * DE-AC04-94AL85000 with Sandia Corporation, the U.S. Government
00007  * retains certain rights in this software.
00008  *
00009  * This library is free software; you can redistribute it and/or
00010  * modify it under the terms of the GNU Lesser General Public
00011  * License as published by the Free Software Foundation; either
00012  * version 2.1 of the License, or (at your option) any later version.
00013  *
00014  */
00015 
00016 /**\file Geometry.hpp
00017  *\author Jason Kraftcheck (kraftche@cae.wisc.edu)
00018  *\date 2006-07-27
00019  */
00020 
00021 #ifndef MB_GEOM_UTIL_HPP
00022 #define MB_GEOM_UTIL_HPP
00023 
00024 #include "moab/CartVect.hpp"
00025 #include <cmath>
00026 
00027 namespace moab
00028 {
00029 
00030 /** \class GeomUtil
00031  * \brief Functions for computational geometry on triangles, rays, and boxes
00032  */
00033 namespace GeomUtil
00034 {
00035 
00036     /** Given a line segment and an axis-aligned box,
00037      *  return the sub-segment of the line segment that
00038      *  itersects the box.
00039      *
00040      *  Can be used to intersect ray with box by passing seg_end
00041      *  as HUGE_VAL or std::numeric_limits<double>::maximum().
00042      *
00043      *\param box_min   Minimum corner of axis-aligned box
00044      *\param box_max   Maximum corner of axis-aligned box
00045      *\param seg_pt    A point in the line containing the segement
00046      *\param seg_unit_dir A unit vector in the direction of the line
00047      *                 containing the semgent.
00048      *\param seg_start The distance from seg_pt in the direction of
00049      *                 seg_unit_dir at which the segment begins.
00050      *                 As input, the start of the original segment, as output, the
00051      *                 start of the sub-segment intersecting the box.
00052      *                 Note:  seg_start must be less than seg_end
00053      *\param seg_end   The distance from seg_pt in the direction of
00054      *                 seg_unit_dir at which the segment ends.
00055      *                 As input, the end of the original segment, as output, the
00056      *                 end of the sub-segment intersecting the box.
00057      *                 Note:  seg_start must be less than seg_end
00058      *\return true if line semgent intersects box, false otherwise.
00059      */
00060     bool segment_box_intersect( CartVect box_min, CartVect box_max, const CartVect& seg_pt,
00061                                 const CartVect& seg_unit_dir, double& seg_start, double& seg_end );
00062 
00063     /**\brief Test for intersection between a ray and a triangle.
00064      *\param ray_point  The start point of the ray.
00065      *\param ray_unit_direciton  The direction of the ray. Must be a unit vector.
00066      *\param t_out Output: The distance along the ray from ray_point in the
00067      *                  direction of ray_unit_direction at which the ray
00068      *                  itersected the triangle.
00069      *\param ray_length Optional:  If non-null, a pointer a maximum length
00070      *                  for the ray, converting this function to a segment-tri-
00071      *                  intersect test.
00072      *\return true if intersection, false otherwise.
00073      */
00074     bool ray_tri_intersect( const CartVect vertices[3], const CartVect& ray_point, const CartVect& ray_unit_direction,
00075                             double& t_out, const double* ray_length = 0 );
00076 
00077     /**\brief Plücker test for intersection between a ray and a triangle.
00078      *\param vertices            Nodes of the triangle.
00079      *\param ray_point           The start point of the ray.
00080      *\param ray_unit_direction  The direction of the ray. Must be a unit vector.
00081      *\param t_out               Output: The distance along the ray from ray_point in the
00082      *                           direction of ray_unit_direction at which the ray
00083      *                           intersected the triangle.
00084      *\param nonneg_ray_length   Optional: If non-null, a maximum length for the ray,
00085      *                           converting this function to a segment-tri-intersect
00086      *                           test.
00087      *\param neg_ray_length      Optional: If non-null, a maximum length for the ray
00088      *                           behind the origin, converting this function to a
00089      *                           segment-tri-intersect test.
00090      *\param orientation         Optional: Reject intersections without the specified
00091      *                           orientation of ray with respect to triangle normal
00092      *                           vector. Indicate desired orientation by passing
00093      *                           1 (forward), -1 (reverse), or 0 (no preference).
00094      *\param int_type            Optional Output: The type of intersection; used to
00095      *                           identify edge/node intersections.
00096      *\return true if intersection, false otherwise.
00097      */
00098     enum intersection_type
00099     {
00100         NONE = 0,
00101         INTERIOR,
00102         NODE0,
00103         NODE1,
00104         NODE2,
00105         EDGE0,
00106         EDGE1,
00107         EDGE2
00108     };
00109     /* intersection type is determined by which of the intermediate values are == 0.  There
00110        are three such values that can therefore be encoded in a 3 bit integer.
00111        0 = none are == 0 -> interior type
00112        1 = pip0 == 0 -> EDGE0
00113        2 = pip1 == 1 -> EDGE1
00114        4 = pip2 == 2 -> EDGE2
00115        5 = pip2 = pip0 == 0 -> NOEE0
00116        3 = pip0 = pip1 == 0 -> NODE1
00117        6 = pip1 = pip2 == 0 -> NODE2 */
00118     const intersection_type type_list[] = { INTERIOR, EDGE0, EDGE1, NODE1, EDGE2, NODE0, NODE2 };
00119 
00120     bool plucker_ray_tri_intersect( const CartVect vertices[3], const CartVect& ray_point,
00121                                     const CartVect& ray_unit_direction, double& dist_out,
00122                                     const double* nonneg_ray_length = 0, const double* neg_ray_length = 0,
00123                                     const int* orientation = 0, intersection_type* int_type = 0 );
00124     double plucker_edge_test( const CartVect& vertexa, const CartVect& vertexb, const CartVect& ray,
00125                               const CartVect& ray_normal );
00126 
00127     //! Find range of overlap between ray and axis-aligned box.
00128     //!
00129     //!\param box_min   Box corner with minimum coordinate values
00130     //!\param box_max   Box corner with minimum coordinate values
00131     //!\param ray_pt    Coordinates of start point of ray
00132     //!\param ray_dir   Directionion vector for ray such that
00133     //!                 the ray is defined by r(t) = ray_point + t * ray_vect
00134     //!                 for t > 0.
00135     //!\param t_enter   Output: if return value is true, this value
00136     //!                 is the parameter location along the ray at which
00137     //!                 the ray entered the leaf.  If return value is false,
00138     //!                 then this value is undefined.
00139     //!\param t_exit    Output: if return value is true, this value
00140     //!                 is the parameter location along the ray at which
00141     //!                 the ray exited the leaf.  If return value is false,
00142     //!                 then this value is undefined.
00143     //!\return true if ray intersects leaf, false otherwise.
00144     bool ray_box_intersect( const CartVect& box_min, const CartVect& box_max, const CartVect& ray_pt,
00145                             const CartVect& ray_dir, double& t_enter, double& t_exit );
00146 
00147     /**\brief Test if plane intersects axis-aligned box
00148      *
00149      * Test for intersection between an unbounded plane and
00150      * an axis-aligned box.
00151      *\param plane_normal Vector in plane normal direction (need *not*
00152      *                    be a unit vector).  The N in
00153      *                    the plane equation: N . X + D = 0
00154      *\param plane_coeff  The scalar 'D' term in the plane equation:
00155      *                    N . X + D = 0
00156      *\param box_min_corner The smallest coordinates of the box along each
00157      *                    axis.  The corner of the box for which all three
00158      *                    coordinate values are smaller than those of any
00159      *                    other corner.  The X, Y, Z values for the planes
00160      *                    normal to those axes and bounding the box on the
00161      *                    -X, -Y, and -Z sides respectively.
00162      *\param box_max_corner The largest coordinates of the box along each
00163      *                    axis.  The corner of the box for which all three
00164      *                    coordinate values are larger than those of any
00165      *                    other corner.  The X, Y, Z values for the planes
00166      *                    normal to those axes and bounding the box on the
00167      *                    +X, +Y, and +Z sides respectively.
00168      *\return true if overlap, false otherwise.
00169      */
00170     bool box_plane_overlap( const CartVect& plane_normal, double plane_coeff, CartVect box_min_corner,
00171                             CartVect box_max_corner );
00172 
00173     /**\brief Test if triangle intersects axis-aligned box
00174      *
00175      * Test if a triangle intersects an axis-aligned box.
00176      *\param triangle_corners  The corners of the triangle.
00177      *\param box_min_corner The smallest coordinates of the box along each
00178      *                    axis.  The corner of the box for which all three
00179      *                    coordinate values are smaller than those of any
00180      *                    other corner.  The X, Y, Z values for the planes
00181      *                    normal to those axes and bounding the box on the
00182      *                    -X, -Y, and -Z sides respectively.
00183      *\param box_max_corner The largest coordinates of the box along each
00184      *                    axis.  The corner of the box for which all three
00185      *                    coordinate values are larger than those of any
00186      *                    other corner.  The X, Y, Z values for the planes
00187      *                    normal to those axes and bounding the box on the
00188      *                    +X, +Y, and +Z sides respectively.
00189      *\param tolerance    The tolerance used in the intersection test.  The box
00190      *                    size is increased by this amount before the intersection
00191      *                    test.
00192      *\return true if overlap, false otherwise.
00193      */
00194     bool box_tri_overlap( const CartVect triangle_corners[3], const CartVect& box_min_corner,
00195                           const CartVect& box_max_corner, double tolerance );
00196 
00197     /**\brief Test if triangle intersects axis-aligned box
00198      *
00199      * Test if a triangle intersects an axis-aligned box.
00200      *\param triangle_corners  The corners of the triangle.
00201      *\param box_center   The center of the box.
00202      *\param box_hanf_dims The distance along each axis, respectively, from the
00203      *                    box_center to the boundary of the box.
00204      *\return true if overlap, false otherwise.
00205      */
00206     bool box_tri_overlap( const CartVect triangle_corners[3], const CartVect& box_center,
00207                           const CartVect& box_half_dims );
00208 
00209     bool box_point_overlap( const CartVect& box_min_corner, const CartVect& box_max_corner, const CartVect& point,
00210                             double tolerance );
00211 
00212     /**\brief Test if the specified element intersects an axis-aligned box.
00213      *
00214      * Test if element intersects axis-aligned box.  Use element-specific
00215      * optimization if available, otherwise call box_general_elem_overlap.
00216      *
00217      *\param elem_corners The coordinates of the element vertices
00218      *\param elem_type    The toplogy of the element.
00219      *\param box_center   The center of the axis-aligned box
00220      *\param box_half_dims Half of the width of the box in each axial
00221      *                     direction.
00222      */
00223     bool box_elem_overlap( const CartVect* elem_corners, EntityType elem_type, const CartVect& box_center,
00224                            const CartVect& box_half_dims, int nodecount = 0 );
00225 
00226     /**\brief Test if the specified element intersects an axis-aligned box.
00227      *
00228      * Uses MBCN and separating axis theorem for general algorithm that
00229      * works for all fixed-size elements (not poly*).
00230      *
00231      *\param elem_corners The coordinates of the element vertices
00232      *\param elem_type    The toplogy of the element.
00233      *\param box_center   The center of the axis-aligned box
00234      *\param box_half_dims Half of the width of the box in each axial
00235      *                     direction.
00236      */
00237     bool box_linear_elem_overlap( const CartVect* elem_corners, EntityType elem_type, const CartVect& box_center,
00238                                   const CartVect& box_half_dims );
00239 
00240     /**\brief Test if the specified element intersects an axis-aligned box.
00241      *
00242      * Uses MBCN and separating axis theorem for general algorithm that
00243      * works for all fixed-size elements (not poly*).  Box and element
00244      * vertices must be translated such that box center is at origin.
00245      *
00246      *\param elem_corners The coordinates of the element vertices, in
00247      *                    local coordinate system of box.
00248      *\param elem_type    The toplogy of the element.
00249      *\param box_half_dims Half of the width of the box in each axial
00250      *                     direction.
00251      */
00252     bool box_linear_elem_overlap( const CartVect* elem_corners, EntityType elem_type, const CartVect& box_half_dims );
00253 
00254     void closest_location_on_box( const CartVect& box_min_corner, const CartVect& box_max_corner, const CartVect& point,
00255                                   CartVect& closest );
00256 
00257     /**\brief find closest location on triangle
00258      *
00259      * Find closest location on linear triangle.
00260      *\param location  Input position to evaluate from
00261      *\param vertices  Array of three corner vertex coordinates.
00262      *\param closest_out Result position
00263      */
00264     void closest_location_on_tri( const CartVect& location, const CartVect* vertices, CartVect& closest_out );
00265 
00266     /**\brief find closest location on polygon
00267      *
00268      * Find closest location on polygon
00269      *\param location  Input position to evaluate from
00270      *\param vertices  Array of corner vertex coordinates.
00271      *\param num_vertices Length of 'vertices' array.
00272      *\param closest_out Result position
00273      */
00274     void closest_location_on_polygon( const CartVect& location, const CartVect* vertices, int num_vertices,
00275                                       CartVect& closest_out );
00276 
00277     /**\brief find closest topological location on triangle
00278      *
00279      * Find closest location on linear triangle.
00280      *\param location  Input position to evaluate from
00281      *\param vertices  Array of three corner vertex coordinates.
00282      *\param tolerance Tolerance to use when comparing to corners and edges
00283      *\param closest_out Result position
00284      *\param closest_topo Closest topological entity
00285      *                     0-2 : vertex index
00286      *                     3-5 : edge beginning at closest_topo - 3
00287      *                       6 : triangle interior
00288      */
00289     void closest_location_on_tri( const CartVect& location, const CartVect* vertices, double tolerance,
00290                                   CartVect& closest_out, int& closest_topo );
00291 
00292     // Finds whether or not a box defined by the center and the half
00293     // width intersects a trilinear hex defined by its eight vertices.
00294     bool box_hex_overlap( const CartVect hexv[8], const CartVect& box_center, const CartVect& box_dims );
00295 
00296     // Finds whether or not a box defined by the center and the half
00297     // width intersects a linear tetrahedron defined by its four vertices.
00298     bool box_tet_overlap( const CartVect tet_corners[4], const CartVect& box_center, const CartVect& box_dims );
00299 
00300     // tests if 2 boxes overlap within a tolerance
00301     // assume that data is valid, box_min1 << box_max1, and box_min2<< box_max2
00302     // they are overlapping if they are overlapping in all directions
00303     // for example in x direction:
00304     //   box_max2[0] + tolerance < box_min1[0] -- false
00305     bool boxes_overlap( const CartVect& box_min1, const CartVect& box_max1, const CartVect& box_min2,
00306                         const CartVect& box_max2, double tolerance );
00307 
00308     // see if boxes formed by 2 lists of "CartVect"s overlap
00309     bool bounding_boxes_overlap( const CartVect* list1, int num1, const CartVect* list2, int num2, double tolerance );
00310 
00311     // see if boxes from vertices in 2d overlap (used in gnomonic planes right now)
00312     bool bounding_boxes_overlap_2d( const double* list1, int num1, const double* list2, int num2, double tolerance );
00313     // point_in_trilinear_hex
00314     // Tests if a point in xyz space is within a hex element defined with
00315     // its eight vertex points forming a trilinear basis function.  Computes
00316     // the natural coordinates with respect to the hex of the xyz point
00317     // and checks if each are between +/-1.  If anyone is outside the range
00318     // the function returns false, otherwise it returns true.
00319     //
00320     bool point_in_trilinear_hex( const CartVect* hex, const CartVect& xyz, double etol );
00321 
00322     bool nat_coords_trilinear_hex( const CartVect* corner_coords, const CartVect& x, CartVect& xi, double tol );
00323 }  // namespace GeomUtil
00324 
00325 }  // namespace moab
00326 
00327 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines