MOAB: Mesh Oriented datABase
(version 5.2.1)
|
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