Triangle geometry processing for surface modeling and cartesian grid generation
AssigneeThe United States of America as represented by the Adminstrator of the National Aeronautics and Space Administration
InventorsMichael J. Aftosmis, John E. Melton, Marsha J. Berger
Life of this patent
Estimating the term…
Abstract
Cartesian mesh generation is accomplished for component based geometries, by intersecting components subject to mesh generation to extract wetted surfaces with a geometry engine using adaptive precision arithmetic in a system which automatically breaks ties with respect to geometric degeneracies. During volume mesh generation, intersected surface triangulations are received to enable mesh generation with cell division of an initially coarse grid. The hexagonal cells are resolved, preserving the ability to directionally divide cells which are locally well aligned.
Claims35
A computer implemented method for determining the intersection of selected component geometries where each component is described by a triangulated surface, comprising:
- locating triangle intersection candidates with a fast spatial search;
- performing floating point filtering of geometric primitives by evaluating associated determinants in comparison with calculated error bounds, to determine whether an exact arithmetic determination of the determinants is necessary in view of the result of an evaluation being less than the error bound;
- resolving degeneracies by virtual perturbation;
- and
- identifying regions and minimizing ray casting by traversing connected regions.
A method of grid generation for Cartesian volume grids in three dimensions with embedded boundaries using a computer, comprising:
- performing a rapid triangle Cartesian cell intersection;
- employing an integer coordinate system in a multilevel Cartesian grid;
- using bitmasks for uniquely locating selected features of a cell;
- using outcodes for rapid intersection of segments of triangles and cells;
- matching split cells in adjacent polyhedra by testing adjacent Cartesian edge fragments for overlap;
- and
- identifying polyhedra in split cells.
The method of determining intersection of components described by triangulations in a selected configuration, comprising:
- performing a proximity search;
- conducting primitive geometric operations;
- performing adaptive precision exact arithmetic;
- and
- breaking geometric degeneracies.
In both ray casting and Boolean triangle-to-triangle intersection evaluations, the method comprising:
- performing floating point filtering;
- performing exact arithmetic;
- and
- performing virtual perturbation.
A system for determining the intersection of selected component geometries where each component is described by a triangulated surface, comprising:
- means for locating triangle intersection candidates with fast spatial search;
- means for performing floating point filtering of geometric primitives by evaluating associated determinants in comparison with calculated error bounds, to determine whether an exact arithmetic determination of the determinants is necessary in view of the result of an evaluation being less than the error bound;
- means for resolving degeneracies by virtual perturbation;
- and
- means for identifying regions and minimizing ray casting by traversing connected regions.
A system of generation for Cartesian volume grids in three dimensions with embedded boundaries, comprising:
- means for performing a rapid triangle Cartesian cell intersection;
- means for employing an integer coordinate system in a multilevel Cartesian grid;
- means for using bitmasks for uniquely locating selected features of a cell;
- means for using outcodes for rapid intersection of segments of triangles and cells;
- means for matching split cells in adjacent polyhedra by testing adjacent Cartesian edge fragments for overlap;
- and
- means for identifying polyhedra in split cells.
Dependencies are inferred from the claim text.