This paper presents a method to construct an auxiliary planar domain of triangulation for tessellating trimmed parametric surface patches. By minimizing a mapping error function, an approximate locally isometric mapping between a given trimmed parametric surface patch and its triangulation domain is constructed. In this way the shape of triangular elements on the triangulation domain is approximately preserved when mapped into three-dimensional space. We also provide an efficient method to achieve a good initial guess for the minimization of mapping error function. Furthermore, our proposed method guarantees a homeomorphism between a triangulation domain and parametric space/given surface patch by robustly removing the possibility of self-intersection on the developed surface net.
Key words: trimmed surface patch, surface tessellation, locally isometric mapping, triangulation domain
Robustness problems owing to floating point imprecision of the conventional Delaunay test in E2 are discussed and a new decision criterion named interval Delaunay test (IDT) relying on rounded interval arithmetic (RIA) is presented to prevent possible failures in the Bowyer-Watson algorithm.
Key words: Bowyer-Watson algorithm, Delaunay test, floating point imprecision, RIA
We present an efficient and reliable method for computing the unit-in-the-last-place (ulp) of a double precision floating-point number, taking advantage of the standard binary representation for floating-point numbers defined by IEEE Std 754-1985. The ulp is necessary to perform software rounding for robust rounded interval arithmetic (RIA) operations. Hardware rounding, using two of the standard rounding modes defined by IEEE-754, may be more efficient. RIA has been used to produce robust software systems for the solution of systems of nonlinear equations, interrogation of geometric and differential properties of curves and surfaces, curve and surface intersections, and solid modeling.
Key words: binary representation, denormalized number, IEEE Std 754-1985, RIA, ulp
Self-intersection of offsets of regular B�zier surface patches due to local differential geometry and global distance function properties is investigated. The problem of computing starting points for tracing self-intersection curves of offsets is formulated in terms of a system of nonlinear polynomial equations and solved robustly by the interval projected polyhedron algorithm. Trivial solutions are excluded by evaluating the normal bounding pyramids of the surface subpatches mapped from the parameter boxes computed by the polynomial solver with a coarse tolerance. A technique to detect and trace self-intersection curve loops in the parameter domain is also discussed. The method has been successfully tested in tracing complex self-intersection curves of offsets of B�zier surface patches. Examples illustrate the principal features and robustness characteristics of the method.
Key words: offsets, parallel surfaces, self-intersections, ridges, NC machining, trimmed offset
We present an efficient method of approximating a set of mutually non-intersecting simple composite planar and space B�zier curves within a prescribed tolerance using piecewise linear segments and ensuring the existence of a homeomorphism between the piecewise linear approximating segments and the actual nonlinear curves. Equations and a robust solution method relying on the interval projected polyhedron algorithm to determine significant points of planar and space curves are described. Preliminary approximation is obtained by computing those significant points on the input curves. This preliminary approximation, providing the most significant geometric information of input curves, is especially valuable when a coarse approximation of good quality is required such as in finite element meshing applications. The main approximation, which ensures that the approximation error is within a user specified tolerance, is next performed using adaptive subdivision. A convex hull method is effectively employed to compute the approximation error. We prove the existence of a homeomorphism between a set of mutually non-intersecting simple composite curves and the corresponding heap of linear approximating segments which do not have inappropriate intersections. For each pair of linear approximating segments, an intersection check is performed to identify possible inappropriate intersections. If these inappropriate intersections exist, further local refinement of the approximation is performed. A bucketing technique is used to identify the inappropriate intersections, which runs in O(n) time on the average where n is the number of linear approximating segments. Our approximation scheme is also applied to interval composite B�zier curves.
Key words: piecewise linear approximation, significant points, homeomorphism, interval B�zier curves
The strength of a circular, cylindrical sandwich shell subjected to hydrostatic pressure is examined. An energy methodology appropriate for static analysis of sandwich shells is presented. Interactions of the inner and outer shell with the core stiffeners interconnecting these shells are investigated. Numerical results are discussed, together with comparisons between the sandwich shell and alternative designs.
Key words: sandwich shell structure, hydrostatic load, strength analysis, energy formulation
We present an unstructured triangular mesh generation algorithm that approximates a set of mutually non-intersecting simple trimmed rational B-spline surface patches within a user specified geometric tolerance. The proposed method uses numerically robust interval geometric representations/computations and also addresses the problem of topological consistency (homeomorphism) between the exact geometry and its approximation. Those are among the most important outstanding issues in geometry approximation problems. Our surface tessellation algorithm is based on the unstructured Delaunay mesh approach which leads to an efficient adaptive triangulation. A robust decision criterion is utilized to prevent possible failures in the conventional Delaunay triangulation. To satisfy the prescribed geometric tolerance, an adaptive node insertion algorithm is employed. Unstructured triangular meshes for free-form surfaces frequently involve triangles with high aspect ratio and accordingly, result in ill-conditioned meshing. Our proposed algorithm constructs 2D triangulation domains which sufficiently preserve the shape of triangles when mapped into 3D space and furthermore, the algorithm provides an efficient method that explicitly controls the aspect ratio of the triangular elements.
Key words: trimmed B-spline surface patch, well-conditioned unstructured meshing, homeomorphism
The objective of this project is to generate numerically robust and topologically reliable unstructured triangular mesh of surfaces which are the faces of complex solid models. Towards this general objective, we have developed an efficient method of approximating a set of mutually non-intersecting simple composite planar and space interval B�zier curves within a prescribed tolerance using piecewise linear segments and ensuring the existence of a homeomorphism between the actual nonlinear curves and their approximation. We have also been developing an unstructured triangular mesh generation algorithm approximating a set of mutually non-intersecting simple trimmed interval Bezier surfaces. Our method satisfies the prescribed approximation error tolerance and guarantees the existence of a homeomorphism between the actual nonlinear patches and the approximating planar triangles. Furthermore, our algorithm generates moderate number of approximating triangles and it also controls the aspect ratio of the approximating triangles. This brief paper outlines our research objectives.
Key words: well-conditioned unstructured surface meshing, homeomorphism, robustness
The objective of this project is to construct numerically robust and topologically reliable unstructured triangular meshes of surfaces which are the faces of complex solid models for computational fluid dynamics (CFD). Towards this general objective, we have begun by developing an efficient method of approximating a set of mutually non-intersecting simple composite planar and space B�zier curves within a prescribed tolerance using piecewise linear segments and ensuring the existence of a homeomorphism between the piecewise linear approximating segments and the actual nonlinear curves. This brief paper outlines our research objectives.
Key words: well-conditioned unstructured surface meshing, homeomorphism, robustness
The overall objective of this project is to lay the framework for a new generation of robust solid modelers for representing and interrogating solid models with curved boundaries in the context of imprecise (discrete) computer arithmetic. This future robust modeler is aimed to replacing the current inconsistence-prone modelers used in industry. Towards this general objective, we have developed (1) a robust and efficient non-linear polynomial solver for overconstrained, underconstrained and balanced systems based on Bernstein subdivision and rounded interval arithmetic; (2) a consistent 2D and 3D interval curved solid modeler (ISM), in which objects are bounded by interval polynomial curves and surfaces; (3) a unified algorithm for general geometric intersections including ill-conditioned intersections such as tangential contact point, tangential intersection curve, and overlap of curves and surfaces; (4) a graph-based data structure incorporating the special features of ISM; and (5) Boolean operations for 2D and 3D manifold objects, and extended to 2D and 3D non-manifold objects resulting from ill-conditioned intersections.
The objective of this project is to advance the state of knowledge in robustly representing, interrogating and manipulating the geometry of complex objects using imprecise/discrete computer arithmetic and developing the necessary theory and algorithms which can form the basis for geom etric modeling systems of the fu ture. Towards this general objective, we have been studying the concept of interval non-uniform rational B-splines (INURBS) in providing a robust method for generating boundary representations of complex objects in the computer. Creation of boundary representations is a typical instance of the more general problem of shape interrogation and reduces to solving systems of nonlinear polynomial equations or irrational equations involving nonlinear polynomials and square roots of polynomials. This brief paper outlines some of our recent work in this area and its applications.
We present an unstructured triangular mesh generation algorithm that approximates a set of mutually non-intersecting simple trimmed polynomial parametric surface patches within a user specified geometric tolerance. The proposed method uses numerically robust interval geometric representations/computations and also addresses the problem of topological consistency (homeomorphism) between the exact geometry and its approximation. Those are among the most important outstanding issues in geometry approximation problems. We also extract important differential geometric features of input geometry for use in the approximation. Our surface tessellation algorithm is based on the unstructured Delaunay mesh approach which leads to an efficient adaptive triangulation. A robust decision criterion is introduced to prevent possible failures in the conventional Delaunay triangulation. To satisfy the prescribed geometric tolerance, an adaptive node insertion algorithm is employed and furthermore, an efficient method to compute a tight upper bound of the approximation error is proposed. Unstructured triangular meshes for free-form surfaces frequently involve triangles with high aspect ratio and accordingly, result in ill-conditioned meshing. Our proposed algorithm constructs 2D triangulation domains which sufficiently preserve the shape of triangles when mapped into 3D space and furthermore, the algorithm provides an efficient method that explicitly controls the aspect ratio of the triangular elements.
Key words: trimmed surface patch, well-conditioned unstructured meshing; homeomorphism; robustness
Interval solid modeling provides a basis for building robust CAD/CAM systems. However, the available geometric models in industry are incomplete surface models or inaccurate solid models. Gaps and holes or intersections not represented in the topological data structures occur between the patches of these models. This paper reviews the literature on correcting the deficiencies of legacy surface and solid models. This includes building topological data structures as well as correcting geometric inconsistencies. This paper then proposes an algorithm for conversion of 2D legacy solid models to interval solid models.
Key words: legacy models; robustness; topological/geometric inconsistencies; interval solid models