SEARCH · Engineering Papers

Results for “TRIANGULATION”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 19 records

All sources NASA NTRS DOE OSTI

NASA NTRS1979

A fast, space-efficient average-case algorithm for the 'Greedy' Triangulation of a point set, and a proof that the Greedy Triangulation is not approximately optimal

The paper addresses the problem of how to find the Greedy Triangulation (GT) efficiently in the average case. It is noted that the problem is open whether there exists an efficient approximation algorithm to the Optimum Triangulation. It is first shown how in the worst case, the GT may be obtained in time O(n to the 3) and space O(n). Attention is then given to how the algorithm may be slightly modified to produce a time O(n to the 2), space O(n) solution in the average case. Finally, it is mentioned that Gilbert has found a worst case solution using totally different techniques that require space O(n to the 2) and time O(n to the 2 log n).

Manacher, G. K.↗

NASA NTRS1994

Incremental triangulation by way of edge swapping and local optimization

This document is intended to serve as an installation, usage, and basic theory guide for the two dimensional triangulation software 'HARLEY' written for the Silicon Graphics IRIS workstation. This code consists of an incremental triangulation algorithm based on point insertion and local edge swapping. Using this basic strategy, several types of triangulations can be produced depending on user selected options. For example, local edge swapping criteria can be chosen which minimizes the maximum interior angle (a MinMax triangulation) or which maximizes the minimum interior angle (a MaxMin or Delaunay triangulation). It should be noted that the MinMax triangulation is generally only locally optical (not globally optimal) in this measure. The MaxMin triangulation, however, is both locally and globally optical. In addition, Steiner triangulations can be constructed by inserting new sites at triangle circumcenters followed by edge swapping based on the MaxMin criteria. Incremental insertion of sites also provides flexibility in choosing cell refinement criteria. A dynamic heap structure has been implemented in the code so that once a refinement measure is specified (i.e., maximum aspect ratio or some measure of a solution gradient for the solution adaptive grid generation) the cell with the largest value of this measure is continually removed from the top of the heap and refined. The heap refinement strategy allows the user to specify either the number of cells desired or refine the mesh until all cell refinement measures satisfy a user specified tolerance level. Since the dynamic heap structure is constantly updated, the algorithm always refines the particular cell in the mesh with the largest refinement criteria value. The code allows the user to: triangulate a cloud of prespecified points (sites), triangulate a set of prespecified interior points constrained by prespecified boundary curve(s), Steiner triangulate the interior/exterior of prespecified boundary curve(s), refine existing triangulations based on solution error measures, and partition meshes based on the Cuthill-McKee, spectral, and coordinate bisection strategies.

Wiltberger, N. Lyn↗

NASA NTRS1985

Some properties of n-dimensional triangulations

A number of mathematical results relevant to the problem of constructing a triangulation, i.e., a simplicial tessellation, of the convex hull of an arbitrary finite set of points in n-space are described. The principal results achieved are: (1) a set of n+2 points in n-space may be triangulated in at most 2 different ways; (2) the sphere test defined in this report selects a preferred one of these two triangulations; (3) a set of parameters is defined that permits the characterization and enumeration of all sets of n+2 points in n-space that are significantly different from the point of view of their possible triangulation; (4) the local sphere test induces a global sphere test property for a triangulation; and (5) a triangulation satisfying the global sphere property is dual to the n-dimensional Dirichlet tesselation, i.e., it is a Delaunay triangulation.

Lawson, C. L.↗

NASA NTRS1998

Automatic Generation of CFD-Ready Surface Triangulations from CAD Geometry

This paper presents an approach for the generation of closed manifold surface triangulations from CAD geometry. CAD parts and assemblies are used in their native format, without translation, and a part's native geometry engine is accessed through a modeler-independent application programming interface (API). In seeking a robust and fully automated procedure, the algorithm is based on a new physical space manifold triangulation technique which was developed to avoid robustness issues associated with poorly conditioned mappings. In addition, this approach avoids the usual ambiguities associated with floating-point predicate evaluation on constructed coordinate geometry in a mapped space, The technique is incremental, so that each new site improves the triangulation by some well defined quality measure. Sites are inserted using a variety of priority queues to ensure that new insertions will address the worst triangles first, As a result of this strategy, the algorithm will return its 'best' mesh for a given (prespecified) number of sites. Alternatively, the algorithm may be allowed to terminate naturally after achieving a prespecified measure of mesh quality. The resulting triangulations are 'CFD-ready' in that: (1) Edges match the underlying part model to within a specified tolerance. (2) Triangles on disjoint surfaces in close proximity have matching length-scales. (3) The algorithm produces a triangulation such that no angle is less than a given angle bound, alpha, or greater than Pi - 2alpha This result also sets bounds on the maximum vertex degree, triangle aspect-ratio and maximum stretching rate for the triangulation. In addition to tile output triangulations for a variety of CAD parts, tile discussion presents related theoretical results which assert the existence of such all angle bound, and demonstrate that maximum bounds of between 25 deg and 30 deg may be achieved in practice.

Aftosmis, M. J.↗

NASA NTRS1972

Improvement of a geodetic triangulation through control points established by means of satellite or precision traversing

Whether any significant increment to accuracy could be transferred from a super-control continental net (continental satellite net or super-transcontinental traverse) to the fundamental geodetic net (first-order triangulation) is discussed. This objective was accomplished by evaluating the positional accuracy improvement for a triangulation station, which is near the middle of the investigated geodetic triangulation net, by using various station constraints over its geodetic position. This investigation on a 1858 kilometer long triangulation chain shows that the super-control net can provide a useful constraint to the investigated geodetic triangulation net, and thus can improve it only when the accuracy of super-control net is at least 1 part in 500,000.

Saxena, N. K.↗

NASA NTRS1977

Planimetric Martian triangulations

Narrow-angle photographs, which have severe drawbacks for stereophotogrammetry, have advantages for simple plane triangulations. Rectified narrow-angle pictures corrected for map projection effects can be combined in the map plane in relatively accurate planimetric triangulations. Provided the strict precepts of least squares are not followed, these triangulations can incorporate considerable overdetermination without increase in the labor of solving the equations. These plane triangulations have been used successfully in the cartography of Mars and are illustrated here by a triangulation of the environs of the prime Martian landing site.

Arthur, D. W. G.↗

NASA NTRS1986

Properties of n-dimensional triangulations

This paper establishes a number of mathematical results relevant to the problem of constructing a triangulation, i.e., a simplical tessellation of the convex hull of an arbitrary finite set of points in n-space. The principal results of the present paper are: (1) a set of n + 2 points in n-space may be triangulated in at most 2 different ways; (2) the 'sphere test' defined in this paper selects a preferred one of these two triangulations; (3) a set of parameters is defined that permits the characterization and enumeration of all sets on n + 2 points in n-space that are significantly different from the point of view of their possible triangulations; and (4) the local sphere test induces a global sphere test property for a triangulation.

Lawson, Charles L.↗

NASA NTRS1991

Triangulation using synthetic aperture radar images

For the extraction of topographic information about Venus from stereoradar images obtained from the Magellan Mission, a Synthetic Aperture Radar (SAR) compilation system was developed on analytical stereoplotters. The system software was extensively tested by using stereoradar images from various spacecraft and airborne radar systems, including Seasat, SIR-B, ERIM XCL, and STAR-1. Stereomodeling from radar images was proven feasible, and development is on a correct approach. During testing, the software was enhanced and modified to obtain more flexibility and better precision. Triangulation software for establishing control points by using SAR images was also developed through a joint effort with the Defense Mapping Agency. The SAR triangulation system comprises four main programs, TRIDATA, MODDATA, TRISAR, and SHEAR. The first two programs are used to sort and update the data; the third program, the main one, performs iterative statistical adjustment; and the fourth program analyzes the results. Also, input are flight data and data from the Global Positioning System and Inertial System (navigation information). The SAR triangulation system was tested with six strips of STAR-1 radar images on a VAX-750 computer. Each strip contains images of 10 minutes flight time (equivalent to a ground distance of 73.5 km); the images cover a ground width of 22.5 km. All images were collected from the same side. With an input of 44 primary control points, 441 ground control points were produced. The adjustment process converged after eight iterations. With a 6-m/pixel resolution of the radar images, the triangulation adjustment has an average standard elevation error of 81 m. Development of Magellan radargrammetry will be continued to convert both SAR compilation and triangulation systems into digital form.

Wu, Sherman S. C.↗

NASA NTRS1992

Delaunay triangulation and computational fluid dynamics meshes

In aerospace computational fluid dynamics (CFD) calculations, the Delaunay triangulation of suitable quadrilateral meshes can lead to unsuitable triangulated meshes. Here, we present case studies which illustrate the limitations of using structured grid generation methods which produce points in a curvilinear coordinate system for subsequent triangulations for CFD applications. We discuss conditions under which meshes of quadrilateral elements may not produce a Delaunay triangulation suitable for CFD calculations, particularly with regard to high aspect ratio, skewed quadrilateral elements.

Posenau, Mary-Anne K.↗

NASA NTRS1993

Approaches to high aspect ratio triangulations

In aerospace computational fluid dynamics calculations, high aspect ratio, or stretched, triangulations are necessary to adequately resolve the features of a viscous flow around bodies. In this paper, we explore alternatives to the Delaunay triangulation which can be used to generate high aspect ratio triangulations of point sets. The method is based on a variation of the lifting map concept which derives Delaunay triangulations from convex hull calculations.

Posenau, M.-A.↗

NASA NTRS1973

Triangulation Error Analysis for the Barium Ion Cloud Experiment

The triangulation method developed specifically for the Barium Ion Cloud Project is discussed. Expression for the four displacement errors, the three slope errors, and the curvature error in the triangulation solution due to a probable error in the lines-of-sight from the observation stations to points on the cloud are derived. The triangulation method is then used to determine the effect of the following on these different errors in the solution: the number and location of the stations, the observation duration, east-west cloud drift, the number of input data points, and the addition of extra cameras to one of the stations. The pointing displacement errors, and the pointing slope errors are compared. The displacement errors in the solution due to a probable error in the position of a moving station plus the weighting factors for the data from the moving station are also determined.

Long, S. A. T.↗

NASA NTRS1992

An advancing front Delaunay triangulation algorithm designed for robustness

A new algorithm is described for generating an unstructured mesh about an arbitrary two-dimensional configuration. Mesh points are generated automatically by the algorithm in a manner which ensures a smooth variation of elements, and the resulting triangulation constitutes the Delaunay triangulation of these points. The algorithm combines the mathematical elegance and efficiency of Delaunay triangulation algorithms with the desirable point placement features, boundary integrity, and robustness traditionally associated with advancing-front-type mesh generation strategies. The method offers increased robustness over previous algorithms in that it cannot fail regardless of the initial boundary point distribution and the prescribed cell size distribution throughout the flow-field.

Mavriplis, D. J.↗

NASA NTRS1993

An advancing front Delaunay triangulation algorithm designed for robustness

Mavriplis, D. J.↗

NASA NTRS1988

A stereo triangulation system for structural identification: Analytical and experimental results

Identification of large space structures' distributed mass, stiffness, and energy dissipation characteristics poses formidable analytical, numerical, and implementation difficulties. Development of reliable on-orbit structural identification methods is important for implementing active vibration suppression concepts which are under widespread study in the large space structures community. Near the heart of the identification problem lies the necessity of making a large number of spatially distributed measurements of the structure's vibratory response and the associated force/moment inputs with sufficient spatial and frequency resolution. In the present paper, we discuss a method whereby tens of active or passive (retro-reflecting) targets on the structure are tracked simultaneously by the focal planes of two or more video cameras mounted on an adjacent platform. Triangulation (optical ray intersection) of the conjugate image centroids yield inertial trajectories of each target on the structure. Given the triangulated motion of the targets, we apply and extend methodology developed by Creamer, Junkins, and Juang to identify the frequencies, mode shapes, and updated estimates for the mass/stiffness/damping parameterization of the structure. The methodology is semi-automated, for example, the post experiment analysis of the video imagery to determine the inertial trajectories of the targets typically requires less than thirty minutes of real time. Using methodology discussed herein, the frequency response of a large number of points on the structure (where reflective targets are mounted) on the structure can be determined from optical measurements alone. For comparison purposes, we also utilize measurements from accelerometers and a calibrated impulse hammer. While our experimental work remains in a research stage of development, we have successfully tracked and stereo triangulated 20 targets (on a vibrating cantilevered grid structure) at a sample frequency of 200 HZ, and have established conclusively the feasibility and desirability of this approach. We discuss, in summary, recent advances in analog and digital video processing methodology, actuation methods, and bring them to bear on the structural identification problem. We include a brief discussion of our experimental hardware and some recent experimental results which support the practical feasibility of this structural vibration sensing approach.

Junkins, J. L.↗

NASA NTRS1995

Algorithms for high aspect ratio oriented triangulations

Grid generation plays an integral part in the solution of computational fluid dynamics problems for aerodynamics applications. A major difficulty with standard structured grid generation, which produces quadrilateral (or hexahedral) elements with implicit connectivity, has been the requirement for a great deal of human intervention in developing grids around complex configurations. This has led to investigations into unstructured grids with explicit connectivities, which are primarily composed of triangular (or tetrahedral) elements, although other subdivisions of convex cells may be used. The existence of large gradients in the solution of aerodynamic problems may be exploited to reduce the computational effort by using high aspect ratio elements in high gradient regions. However, the heuristic approaches currently in use do not adequately address this need for high aspect ratio unstructured grids. High aspect ratio triangulations very often produce the large angles that are to be avoided. Point generation techniques based on contour or front generation are judged to be the most promising in terms of being able to handle complicated multiple body objects, with this technique lending itself well to adaptivity. The eventual goal encompasses several phases: first, a partitioning phase, in which the Voronoi diagram of a set of points and line segments (the input set) will be generated to partition the input domain; second, a contour generation phase in which body-conforming contours are used to subdivide the partition further as well as introduce the foundation for aspect ratio control, and; third, a Steiner triangulation phase in which points are added to the partition to enable triangulation while controlling angle bounds and aspect ratio. This provides a combination of the advancing front/contour techniques and refinement. By using a front, aspect ratio can be better controlled. By using refinement, bounds on angles can be maintained, while attempting to minimize the number of Steiner points.

Posenau, Mary-Anne K.↗

NASA NTRS1998

A Parallel Non-Overlapping Domain-Decomposition Algorithm for Compressible Fluid Flow Problems on Triangulated Domains

This paper considers an algebraic preconditioning algorithm for hyperbolic-elliptic fluid flow problems. The algorithm is based on a parallel non-overlapping Schur complement domain-decomposition technique for triangulated domains. In the Schur complement technique, the triangulation is first partitioned into a number of non-overlapping subdomains and interfaces. This suggests a reordering of triangulation vertices which separates subdomain and interface solution unknowns. The reordering induces a natural 2 x 2 block partitioning of the discretization matrix. Exact LU factorization of this block system yields a Schur complement matrix which couples subdomains and the interface together. The remaining sections of this paper present a family of approximate techniques for both constructing and applying the Schur complement as a domain-decomposition preconditioner. The approximate Schur complement serves as an algebraic coarse space operator, thus avoiding the known difficulties associated with the direct formation of a coarse space discretization. In developing Schur complement approximations, particular attention has been given to improving sequential and parallel efficiency of implementations without significantly degrading the quality of the preconditioner. A computer code based on these developments has been tested on the IBM SP2 using MPI message passing protocol. A number of 2-D calculations are presented for both scalar advection-diffusion equations as well as the Euler equations governing compressible fluid flow to demonstrate performance of the preconditioning algorithm.

Barth, Timothy J.↗

NASA NTRS2005

A Program to Improve the Triangulated Surface Mesh Quality Along Aircraft Component Intersections

A computer program has been developed for improving the quality of unstructured triangulated surface meshes in the vicinity of component intersections. The method relies solely on point removal and edge swapping for improving the triangulations. It can be applied to any lifting surface component such as a wing, canard or horizontal tail component intersected with a fuselage, or it can be applied to a pylon that is intersected with a wing, fuselage or nacelle. The lifting surfaces or pylon are assumed to be aligned in the axial direction with closed trailing edges. The method currently maintains salient edges only at leading and trailing edges of the wing or pylon component. This method should work well for any shape of fuselage that is free of salient edges at the intersection. The method has been successfully demonstrated on a total of 125 different test cases that include both blunt and sharp wing leading edges. The code is targeted for use in the automated environment of numerical optimization where geometric perturbations to individual components can be critical to the aerodynamic performance of a vehicle. Histograms of triangle aspect ratios are reported to assess the quality of the triangles attached to the intersection curves before and after application of the program. Large improvements to the quality of the triangulations were obtained for the 125 test cases; the quality was sufficient for use with an automated tetrahedral mesh generation program that is used as part of an aerodynamic shape optimization method.

Cliff, Susan E.↗

NASA NTRS1997

Numerical Schemes for the Hamilton-Jacobi and Level Set Equations on Triangulated Domains

Borrowing from techniques developed for conservation law equations, numerical schemes which discretize the Hamilton-Jacobi (H-J), level set, and Eikonal equations on triangulated domains are presented. The first scheme is a provably monotone discretization for certain forms of the H-J equations. Unfortunately, the basic scheme lacks proper Lipschitz continuity of the numerical Hamiltonian. By employing a virtual edge flipping technique, Lipschitz continuity of the numerical flux is restored on acute triangulations. Next, schemes are introduced and developed based on the weaker concept of positive coefficient approximations for homogeneous Hamiltonians. These schemes possess a discrete maximum principle on arbitrary triangulations and naturally exhibit proper Lipschitz continuity of the numerical Hamiltonian. Finally, a class of Petrov-Galerkin approximations are considered. These schemes are stabilized via a least-squares bilinear form. The Petrov-Galerkin schemes do not possess a discrete maximum principle but generalize to high order accuracy.

Barth, Timothy J.↗