Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “octrees”

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.

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

18 records
All sourcesNASA NTRSDOE OSTI
NASA NTRS1987

Octree based automatic meshing from CSG models

Finite element meshes derived automatically from solid models through recursive spatial subdivision schemes (octrees) can be made to inherit the hierarchical structure and the spatial addressability intrinsic to the underlying grid. These two properties, together with the geometric regularity that can also be built into the mesh, make octree based meshes ideally suited for efficient analysis and self-adaptive remeshing and reanalysis. The element decomposition of the octal cells that intersect the boundary of the domain is emphasized. The problem, central to octree based meshing, is solved by combining template mapping and element extraction into a procedure that utilizes both constructive solid geometry and boundary respresentation techniques. Boundary cells that are not intersected by the edge of the domain boundary are easily mapped to predefined element topology. Cells containing edges (and vertices) are first transformed into a planar polyhedron and then triangulated via element extractors. The modeling environments required for the derivation of planar polyhedra and for element extraction are analyzed.

Perucchio, Renato↗
NASA NTRS1987

Geometrical and topological issues in octree based automatic meshing

Finite element meshes derived automatically from solid models through recursive spatial subdivision schemes (octrees) can be made to inherit the hierarchical structure and the spatial addressability intrinsic to the underlying grid. These two properties, together with the geometric regularity that can also be built into the mesh, make octree based meshes ideally suited for efficient analysis and self-adaptive remeshing and reanalysis. The element decomposition of the octal cells that intersect the boundary of the domain is discussed. The problem, central to octree based meshing, is solved by combining template mapping and element extraction into a procedure that utilizes both constructive solid geometry and boundary representation techniques. Boundary cells that are not intersected by the edge of the domain boundary are easily mapped to predefined element topology. Cells containing edges (and vertices) are first transformed into a planar polyhedron and then triangulated via element extractor. The modeling environments required for the derivation of planar polyhedra and for element extraction are analyzed.

Saxena, Mukul↗
NASA NTRS1987

Finite octree meshing through topologically driven geometric operators

The octree technique is developed into the finite octree, and an overview is given. Modeler requirements are given. The octree discretization is discussed along with geometric communication operators. Geometric communication operators returning topological associativity and geometric communication operators returning spatial data are also discussed and illustrated. The advantages are given of the boundary representation and of geometric communication operators. The implementation plays an important role in the integration with a variety of geometric modelers. The capabilities of closed loop processes within a complete finite element system are presented.

Grice, Kurt R.↗
NASA NTRS1990

A real-time robot arm collision detection system

A data structure and update algorithm are presented for a prototype real time collision detection safety system for a multi-robot environment. The data structure is a variant of the octree, which serves as a spatial index. An octree recursively decomposes 3-D space into eight equal cubic octants until each octant meets some decomposition criteria. The octree stores cylspheres (cylinders with spheres on each end) and rectangular solids as primitives (other primitives can easily be added as required). These primitives make up the two seven degrees-of-freedom robot arms and environment modeled by the system. Octree nodes containing more than a predetermined number N of primitives are decomposed. This rule keeps the octree small, as the entire environment for the application can be modeled using a few dozen primitives. As robot arms move, the octree is updated to reflect their changed positions. During most update cycles, any given primitive does not change which octree nodes it is in. Thus, modification to the octree is rarely required. Incidents in which one robot arm comes too close to another arm or an object are reported. Cycle time for interpreting current joint angles, updating the octree, and detecting/reporting imminent collisions averages 30 milliseconds on an Intel 80386 processor running at 20 MHz.

Shaffer, Clifford A.↗
NASA NTRS1992

A real-time robot arm collision avoidance system

A data structure and update algorithm are presented for a prototype real-time collision avoidance safety system simulating a multirobot workspace. The data structure is a variant of the octree, which serves as a spatial index. An octree recursively decomposes 3D space into eight equal cubic octants until each octant meets some decomposition criteria. The N-objects octree, which indexes a collection of 3D primitive solids is used. These primitives make up the two (seven-degrees-of-freedom) robot arms and workspace modeled by the system. As robot arms move, the octree is updated to reflect their changed positions. During most update cycles, any given primitive does not change which octree nodes it is in. Thus, modification to the octree is rarely required. Cycle time for interpreting current arm joint angles, updating the octree to reflect new positions, and detecting/reporting imminent collisions averages 30 ms on an Intel 80386 processor running at 20 MHz.

Shaffer, Clifford A.↗
NASA NTRSDate not supplied

A Wall-Modeled LES Perspective for the High Lift Common Research Model Using LAVA

A new immersed boundary Wall-Modelled Large Eddy Simulation (WMLES) formulation is developed to study high-lift aerodynamics on the NASA High-Lift Common Research Model (HL-CRM). A sequence of Cartesian Octree grids with sizes ranging from 100 Million through 2.02 Billion grid points is utilized to systematically assess grid-sensitivity and convergence for the in-tunnel (QinetiQ) configuration of the model, and remarkable agreement between the immersed boundary and the curvilinear body-aligned WMLES formulations is reported on grids with comparable resolutions. In the free-air configuration of the model, consistent predictions between the Curvilinear Overset and the Cartesian Octree formulations are reported for angles of attack up to C(L,max) at a=19.57. However, some differences in the onset of stall are seen between the two methods for a>20°: while the curvilinear WMLES experiences wing-root separation with increasing angle of attack (Topology A), the Cartesian Octree formulation shows a different flow topology characterized by boundary layer weakness on the main element, emanating from the pylon-wing attachment (Topology B). In order to obtain further insight into the two-distinct topologies, carefully designed numerical experiments to isolate effects of the model standoff and the tunnel wall-boundary layers are conducted using the immersed boundary WMLES formulation. The increased incidence angle-of-attack on the inboard portion of the wing due to the standoff is shown to be sufficient for triggering a switch from Topology B to Topology A in Cartesian WMLES. The role of the floor boundary layer is further examined in detail by identification of additional corner-flow vorticity generated by the viscous juncture flow interactions between the floor boundary layer and the standoff leading to formation of a strong coherent and persistent vortex on the belly-side of the fuselage. The intensity of this vortex is shown to increase with the thickness of the floor boundary layer. A further increase in the incidence angle of attack near the leading-edge strake caused by the presence of this belly-side vortex is quantified for two-distinct floor boundary layers. Both of the floor boundary layers considered result in the onset of large scale wing-root separation at a=21.47in non-confined (free-air) configurations.

TTT↗
NASA NTRS1998

Efficient Encoding and Rendering of Time-Varying Volume Data

Visualization of time-varying volumetric data sets, which may be obtained from numerical simulations or sensing instruments, provides scientists insights into the detailed dynamics of the phenomenon under study. This paper describes a coherent solution based on quantization, coupled with octree and difference encoding for visualizing time-varying volumetric data. Quantization is used to attain voxel-level compression and may have a significant influence on the performance of the subsequent encoding and visualization steps. Octree encoding is used for spatial domain compression, and difference encoding for temporal domain compression. In essence, neighboring voxels may be fused into macro voxels if they have similar values, and subtrees at consecutive time steps may be merged if they are identical. The software rendering process is tailored according to the tree structures and the volume visualization process. With the tree representation, selective rendering may be performed very efficiently. Additionally, the I/O costs are reduced. With these combined savings, a higher level of user interactivity is achieved. We have studied a variety of time-varying volume datasets, performed encoding based on data statistics, and optimized the rendering calculations wherever possible. Preliminary tests on workstations have shown in many cases tremendous reduction by as high as 90% in both storage space and inter-frame delay.

CODING↗
NASA NTRS2002

Probabilistic #D data fusion for multiresolution surface generation

In this paper we present an algorithm for adaptive resolution integration of 3D data collected from multiple distributed sensors. The input to the algorithm is a set of 3D surface points and associated sensor models. Using a probabilistic rule, a surface probability function is generated that represents the probability that a particular volume of space contains the surface. The surface probability function is represented using an octree data structure; regions of space with samples of large conariance are stored at a coarser level than regions of space containing samples with smaller covariance. The algorithm outputs an adaptive resolution surface generated by connecting points that lie on the ridge of surface probability with triangles scaled to match the local discretization of space given by the algorithm, we present results from 3D data generated by scanning lidar and structure from motion.

3D data fusion multiresolution surface generation ↗
NASA NTRS1993

Parallel unstructured grid generation for computational aerosciences

The objective of this research project is to develop efficient parallel automatic grid generation procedures for use in computational aerosciences. This effort is focused on a parallel version of the Finite Octree grid generator. Progress made during the first six months is reported.

Shephard, Mark S.↗
NASA NTRS1995

Adaptive hybrid prismatic-tetrahedral grids for viscous flows

The paper presents generation of adaptive hybrid prismatic/tetrahedral grids for complex 3-D geometries including multi-body domains. The prisms cover the region close to each body's surface, while tetrahedra are created elsewhere. Two developments are presented for hybrid grid generation around complex 3-D geometries. The first is a new octree/advancing front type of method for generation of the tetrahedra of the hybrid mesh. The main feature of the present advancing front tetrahedra generator that is different from previous such methods is that it does not require the creation of a background mesh by the user for the determination of the grid-spacing and stretching parameters. These are determined via an automatically generated octree. The second development is an Automatic Receding Method (ARM) for treating the narrow gaps in between different bodies in a multiply-connected domain. This method is applied to a two-element wing case. A hybrid grid adaptation scheme that employs both h-refinement and redistribution strategies is developed to provide optimum meshes for viscous flow computations. Grid refinement is a dual adaptation scheme that couples division of tetrahedra, as well as 2-D directional division of prisms.

Kallinderis, Yannis↗
NASA NTRS1995

Methods for prismatic/tetrahedral grid generation and adaptation

The present work involves generation of hybrid prismatic/tetrahedral grids for complex 3-D geometries including multi-body domains. The prisms cover the region close to each body's surface, while tetrahedra are created elsewhere. Two developments are presented for hybrid grid generation around complex 3-D geometries. The first is a new octree/advancing front type of method for generation of the tetrahedra of the hybrid mesh. The main feature of the present advancing front tetrahedra generator that is different from previous such methods is that it does not require the creation of a background mesh by the user for the determination of the grid-spacing and stretching parameters. These are determined via an automatically generated octree. The second development is a method for treating the narrow gaps in between different bodies in a multiply-connected domain. This method is applied to a two-element wing case. A High Speed Civil Transport (HSCT) type of aircraft geometry is considered. The generated hybrid grid required only 170 K tetrahedra instead of an estimated two million had a tetrahedral mesh been used in the prisms region as well. A solution adaptive scheme for viscous computations on hybrid grids is also presented. A hybrid grid adaptation scheme that employs both h-refinement and redistribution strategies is developed to provide optimum meshes for viscous flow computations. Grid refinement is a dual adaptation scheme that couples 3-D, isotropic division of tetrahedra and 2-D, directional division of prisms.

Kallinderis, Y.↗
NASA NTRS1997

Out-of-Core Streamline Visualization on Large Unstructured Meshes

It's advantageous for computational scientists to have the capability to perform interactive visualization on their desktop workstations. For data on large unstructured meshes, this capability is not generally available. In particular, particle tracing on unstructured grids can result in a high percentage of non-contiguous memory accesses and therefore may perform very poorly with virtual memory paging schemes. The alternative of visualizing a lower resolution of the data degrades the original high-resolution calculations. This paper presents an out-of-core approach for interactive streamline construction on large unstructured tetrahedral meshes containing millions of elements. The out-of-core algorithm uses an octree to partition and restructure the raw data into subsets stored into disk files for fast data retrieval. A memory management policy tailored to the streamline calculations is used such that during the streamline construction only a very small amount of data are brought into the main memory on demand. By carefully scheduling computation and data fetching, the overhead of reading data from the disk is significantly reduced and good memory performance results. This out-of-core algorithm makes possible interactive streamline visualization of large unstructured-grid data sets on a single mid-range workstation with relatively low main-memory capacity: 5-20 megabytes. Our test results also show that this approach is much more efficient than relying on virtual memory and operating system's paging algorithms.

Ueng, Shyh-Kuang↗
NASA NTRS1999

Fast Time-Varying Volume Rendering Using Time-Space Partition (TSP) Tree

We present a new, algorithm for rapid rendering of time-varying volumes. A new hierarchical data structure that is capable of capturing both the temporal and the spatial coherence is proposed. Conventional hierarchical data structures such as octrees are effective in characterizing the homogeneity of the field values existing in the spatial domain. However, when treating time merely as another dimension for a time-varying field, difficulties frequently arise due to the discrepancy between the field's spatial and temporal resolutions. In addition, treating spatial and temporal dimensions equally often prevents the possibility of detecting the coherence that is unique in the temporal domain. Using the proposed data structure, our algorithm can meet the following goals. First, both spatial and temporal coherence are identified and exploited for accelerating the rendering process. Second, our algorithm allows the user to supply the desired error tolerances at run time for the purpose of image-quality/rendering-speed trade-off. Third, the amount of data that are required to be loaded into main memory is reduced, and thus the I/O overhead is minimized. This low I/O overhead makes our algorithm suitable for out-of-core applications.

Shen, Han-Wei↗
NASA NTRS2019

A new environment to simulate the dynamics in the close proximity of rubble-pile asteroids

This paper presents a new environment to simulate close-proximity dynamics around rubble-pile asteroids. The code provides methods for modeling the asteroid’s gravity field and surface through granular dynamics. It implements stateof-the-art techniques to model both gravity and contact interaction between particles: 1) mutual gravity as either direct N2 or Barnes-Hut GPU-parallel octree and 2) contact dynamics with a soft-body (force-based, smooth dynamics), hard-body (constraint-based, non-smooth dynamics), or hybrid (constraint-based with compliance and damping) approach. A very relevant feature of the code is its ability to handle complex-shaped rigid bodies and their full 6D motion. Examples of spacecraft close-proximity scenarios and their numerical simulations are shown.

Ferrari, Fabio↗
NASA NTRSDate not supplied

Predictions of LAGOON Nose Landing Gear Flow and Noise Using Wall-Modeled Large-Eddy Simulations

Wall-modeled large-eddy simulations (WMLESs) of the LAGOON nose landing gear are conducted with compressible Navier–Stokes equations and immersed boundary technique using the Launch, Ascent, and Vehicle Aerodynamics (LAVA) framework. The simulations are conducted using six different Cartesian octree meshes for the grid sensitivity analysis of the near-field and far-field numerical predictions, where the far-field noise results are computed with the Ffowcs Williams–Hawkings acoustic analogy. The effects of numerical tripping induced at the exact locations of the tripping devices in the experiments are also examined. In general, better comparison with the experimental results are shown for the the near-field results obtained with the simulations under the effects of numerical tripping. The effects of tripping are not significant on the far-field noise calculations and the results have reasonable comparison with the experimental data in the low and medium frequency ranges when an impermeable formulation of the acoustic analogy is used.

CST↗