Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Octree”

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.

At least 37 records · Page 2

A fast reconstruction method of the dense point-cloud model for cultural heritage artifacts based on compressed sensing and sparse auto-encoder

Since the point cloud data of cultural heritage artifacts obtained by the laser scanner is enormous and dense, these lead to a large quantity of network resource for storing, processing, and transmission. This paper provided a fast reconstruction method of the dense point cloud model for cultural relics based on sparse auto-encoder and compressed sensing. Firstly, the octree method based on the hash function was utilized to extract local features and remove redundant points. Secondly, the point cloud, which can be seen as the 3D geometric signal, is projected to the discrete Laplacian sparse basis via the point cloud adjacency matrix. Then, aiming at the bottleneck of slow recovery caused by tremendous scale of inverse problem based on compressed sensing theory, the sparse auto-encoder was applied to reduce the dimension and speed up the recovery. Finally, the OMP algorithm was applied to reconstruct 3D point cloud model based on the stochastic Gauss matrix. In order to test the performance of our methods, the 3D point cloud model of terracotta warriors and horses head were used. And the experimental results demonstrated that our approach can obviously accelerate the process of reconstruction of the dense point cloud model for the cultural heritage artifacts and ensure the recovery accuracy.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Compression-based integral curve data reuse framework for flow visualization

Currently, by default, integral curves are repeatedly re-computed in different flow visualization applications, such as FTLE field computation, source-destination queries, etc., leading to unnecessary resource cost. We present a compression-based data reuse framework for integral curves, to greatly reduce their retrieval cost, especially in a resource-limited environment. In our design, a hierarchical and hybrid compression scheme is proposed to balance three objectives, including high compression ratio, controllable error, and low decompression cost. Specifically, we use and combine digitized curve sparse representation, floating-point data compression, and octree space partitioning to adaptively achieve the objectives. Results have shown that our data reuse framework could acquire tens of times acceleration in the resource-limited environment compared to on-the-fly particle tracing, and keep controllable information loss. Moreover, our method could provide fast integral curve retrieval for more complex data, such as unstructured mesh data.

97 MATHEMATICS AND COMPUTING↗

Detecting Radiation-Induced Injury Using Rapid 3D Variogram Analysis of CT Images of Rat Lungs

A new heterogeneity analysis approach to discern radiation-induced lung damage was tested on CT images of irradiated rats. The method, combining octree decomposition with variogram analysis, demonstrated a significant correlation with radiation exposure levels, whereas conventional measurements and pulmonary function tests did not. The results suggest the new approach may be highly sensitive for assessing even subtle radiation-induced changes

Jacob, Rick E.↗

Adaptive mesh refinement for steady flows in Nek5000

Adaptive mesh refinement is performed in the framework of the spectral element method augmented by approaches to error estimation and control. The h-refinement technique is used for adapting the mesh, where selected grid elements are split by a quadtree (2D) or octree (3D) structure. Continuity between parent-child elements is enforced by high-order interpolation of the solution across the common faces. Parallel mesh partitioning and grid management respectively, are taken care of by the external libraries ParMETIS and p4est. Two methods are considered for estimating and controlling the error of the solution. The first error estimate is local and based on the spectral properties of the solution on each element. This method gives a local measure of the L-2-norm of the solution over the entire computational domain. The second error estimate uses the dual-weighted residuals method - it is based on and takes into account both the local properties of the solution and the global dependence of the error in the solution via an adjoint problem. The objective of this second approach is to optimize the computation of a given functional of physical interest. The simulations are performed by using the code Nek5000 and three steady-state test cases are studied: a two-dimensional lid-driven cavity at Re = 7, 500, a two-dimensional flow past a cylinder at Re = 40, and a three-dimensional lid-driven cavity at Re = 2,000 with a moving lid tilted by an angle of 30 degrees. Finally, the efficiency of both error estimators is compared in terms of refinement patterns and accuracy on the functional of interest. In the case of the adjoint error estimators, the trend on the error of the functional is shown to be correctly represented up to a multiplicative constant.

42 ENGINEERING↗

SPACE: 3D parallel solvers for Vlasov-Maxwell and Vlasov-Poisson equations for relativistic plasmas with atomic transformations

A parallel, relativistic, three-dimensional particle-in-cell code SPACE has been developed for the simulation of electromagnetic fields, relativistic particle beams, and plasmas. In addition to the standard second-order Particle-in-Cell (PIC) algorithm, SPACE includes efficient novel algorithms to resolve atomic physics processes such as multi-level ionization of plasma atoms, recombination, and electron attachment to dopants in dense neutral gases. SPACE also contains a highly adaptive particle-based method, called Adaptive Particle-in-Cloud (AP-Cloud), for solving the Vlasov-Poisson problems. It eliminates the traditional Cartesian mesh of PIC and replaces it with an adaptive octree data structure. The code's algorithms, structure, capabilities, parallelization strategy, and performance have been discussed. Additionally, typical examples of SPACE applications to accelerator science and engineering problems are described.

43 PARTICLE ACCELERATORS↗

An improved fast multipole method for electrostatic potential calculations in a class of coarse-grained molecular simulations

This paper presents a novel algorithm to approximate the long-range electrostatic potential field in the Cartesian coordinates applicable to 3D coarse-grained simulations of biopolymers. In such models, coarse-grained clusters are formed via treating groups of atoms as rigid and/or flexible bodies connected together via kinematic joints. Therefore, multibody dynamic techniques are used to form and solve the equations of motion of such coarse-grained systems. In this article, the approximations for the potential fields due to the interaction between a highly negatively/positively charged pseudo-atom and charged particles, as well as the interaction between clusters of charged particles, are presented. These approximations are expressed in terms of physical and geometrical properties of the bodies such as the entire charge, the location of the center of charge, and the pseudo-inertia tensor about the center of charge of the clusters. Further, a novel substructuring scheme is introduced to implement the presented far-field potential evaluations in a binary tree framework as opposed to the existing quadtree and octree strategies of implementing fast multipole method. Using the presented Lagrangian grids, the electrostatic potential is recursively calculated via sweeping two passes: assembly and disassembly. In the assembly pass, adjacent charged bodies are combined together to form new clusters. Then, the potential field of each cluster due to its interaction with faraway resulting clusters is recursively calculated in the disassembly pass. The method is highly compatible with multibody dynamic schemes to model coarse-grained biopolymers. Since the proposed method takes advantage of constant physical and geometrical properties of rigid clusters, improvement in the overall computational cost is observed comparing to the tradition application of fast multipole method.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Implicit mesh discontinuous Galerkin methods and interfacial gauge methods for high-order accurate interface dynamics, with applications to surface tension dynamics, rigid body fluid–structure interaction, and free surface flow: Part I

In this two-part paper, a high-order accurate implicit mesh discontinuous Galerkin (dG) framework is developed for fluid interface dynamics, facilitating precise computation of interfacial fluid flow in evolving geometries. The framework uses implicitly defined meshes—wherein a reference quadtree or octree grid is combined with an implicit representation of evolving interfaces and moving domain boundaries—and allows physically prescribed interfacial jump conditions to be imposed or captured with high-order accuracy. Part one discusses the design of the framework, including: (i) high-order quadrature for implicitly defined elements and faces; (ii) high-order accurate discretisation of scalar and vector-valued elliptic partial differential equations with interfacial jumps in ellipticity coefficient, leading to optimal-order accuracy in the maximum norm and discrete linear systems that are symmetric positive (semi)definite; (iii) the design of incompressible fluid flow projection operators, which except for the influence of small penalty parameters, are discretely idempotent; and (iv) the design of geometric multigrid methods for elliptic interface problems on implicitly defined meshes and their use as preconditioners for the conjugate gradient method. Also discussed is a variety of aspects relating to moving interfaces, including: (v) dG discretisations of the level set method on implicitly defined meshes; (vi) transferring state between evolving implicit meshes; (vii) preserving mesh topology to accurately compute temporal derivatives; (viii) high-order accurate reinitialisation of level set functions; and (ix) the integration of adaptive mesh refinement. In part two, several applications of the implicit mesh dG framework in two and three dimensions are presented, including examples of single phase flow in nontrivial geometry, surface tension-driven two phase flow with phase-dependent fluid density and viscosity, rigid body fluid–structure interaction, and free surface flow. A class of techniques known as interfacial gauge methods is adopted to solve the corresponding incompressible Navier–Stokes equations, which, compared to archetypical projection methods, have a weaker coupling between fluid velocity, pressure, and interface position, and allow high-order accurate numerical methods to be developed more easily. Convergence analyses conducted throughout the work demonstrate high-order accuracy in the maximum norm for all of the applications considered; for example, fourth-order spatial accuracy in fluid velocity, pressure, and interface location is demonstrated for surface tension-driven two phase flow in 2D and 3D. Specific application examples include: vortex shedding in nontrivial geometry, capillary wave dynamics revealing fine-scale flow features, falling rigid bodies tumbling in unsteady flow, and free surface flow over a submersed obstacle, as well as high Reynolds number soap bubble oscillation dynamics and vortex shedding induced by a type of Plateau–Rayleigh instability in water ripple free surface flow. In conclusion, these last two examples compare numerical results with experimental data and serve as an additional means of validation; they also reveal physical phenomena not visible in the experiments, highlight how small-scale interfacial features develop and affect macroscopic dynamics, and demonstrate the wide range of spatial scales often at play in interfacial fluid flow.

97 MATHEMATICS AND COMPUTING↗

Implicit mesh discontinuous Galerkin methods and interfacial gauge methods for high-order accurate interface dynamics, with applications to surface tension dynamics, rigid body fluid–structure interaction, and free surface flow: Part II

Here, in this two-part paper, a high-order accurate implicit mesh discontinuous Galerkin (dG) framework is developed for fluid interface dynamics, facilitating precise computation of interfacial fluid flow in evolving geometries. The framework uses implicitly defined meshes—wherein a reference quadtree or octree grid is combined with an implicit representation of evolving interfaces and moving domain boundaries—and allows physically prescribed interfacial jump conditions to be imposed or captured with high-order accuracy. Part one discusses the design of the framework, including: (i) high-order quadrature for implicitly defined elements and faces; (ii) high-order accurate discretisation of scalar and vector-valued elliptic partial differential equations with interfacial jumps in ellipticity coefficient, leading to optimal-order accuracy in the maximum norm and discrete linear systems that are symmetric positive (semi)definite; (iii) the design of incompressible fluid flow projection operators, which except for the influence of small penalty parameters, are discretely idempotent; and (iv) the design of geometric multigrid methods for elliptic interface problems on implicitly defined meshes and their use as preconditioners for the conjugate gradient method. Also discussed is a variety of aspects relating to moving interfaces, including: (v) dG discretisations of the level set method on implicitly defined meshes; (vi) transferring state between evolving implicit meshes; (vii) preserving mesh topology to accurately compute temporal derivatives; (viii) high-order accurate reinitialisation of level set functions; and (ix) the integration of adaptive mesh refinement. In part two, several applications of the implicit mesh dG framework in two and three dimensions are presented, including examples of single phase flow in nontrivial geometry, surface tension-driven two phase flow with phase-dependent fluid density and viscosity, rigid body fluid–structure interaction, and free surface flow. A class of techniques known as interfacial gauge methods is adopted to solve the corresponding incompressible Navier–Stokes equations, which, compared to archetypical projection methods, have a weaker coupling between fluid velocity, pressure, and interface position, and allow high-order accurate numerical methods to be developed more easily. Convergence analyses conducted throughout the work demonstrate high-order accuracy in the maximum norm for all of the applications considered; for example, fourth-order spatial accuracy in fluid velocity, pressure, and interface location is demonstrated for surface tension-driven two phase flow in 2D and 3D. Specific application examples include: vortex shedding in nontrivial geometry, capillary wave dynamics revealing fine-scale flow features, falling rigid bodies tumbling in unsteady flow, and free surface flow over a submersed obstacle, as well as high Reynolds number soap bubble oscillation dynamics and vortex shedding induced by a type of Plateau–Rayleigh instability in water ripple free surface flow. In these last two examples compare numerical results with experimental data and serve as an additional means of validation; they also reveal physical phenomena not visible in the experiments, highlight how small-scale interfacial features develop and affect macroscopic dynamics, and demonstrate the wide range of spatial scales often at play in interfacial fluid flow.

97 MATHEMATICS AND COMPUTING↗

Simulation Of Plasma Processes--On The Integration Of Feature Simulation With Reactor Scale Models

Advances in both reactor and feature scale modeling have been achieved in plasma processing. Models are being used to address several practical issues in industry. However, accurate predictions of physical phenomena that occur during the process need an integrated multiscale approach that couples reactor scale to feature scale. The implementation of multiscale codes is still a challenge where robustness plays a critical role. This paper addresses the weakest points of such codes especially at the feature scale and provides proper choices for successful implementations. It focuses on the level set methods and fast marching algorithms implemented on quadtree (2D) and octree (3D) data structures and possible extensions of semi-lagrangian methods.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Point-in-convex polygon and point-in-convex polyhedron algorithms with O(1) complexity using space subdivision

There are many space subdivision and space partitioning techniques used in many algorithms to speed up computations. They mostly rely on orthogonal space subdivision, resp. using hierarchical data structures, e.g. BSP trees, quadtrees, octrees, kd-trees, bounding volume hierarchies etc. However in some applications a non-orthogonal space subdivision can offer new ways for actual speed up. In the case of convex polygon in E{sup 2} a simple Point-in-Polygon test is of the O(N) complexity and the optimal algorithm is of O(log N) computational complexity. In the E{sup 3} case, the complexity is O(N) even for the convex polyhedron as no ordering is defined. New Point-in-Convex Polygon and Point-in-Convex Polyhedron algorithms are presented based on space subdivision in the preprocessing stage resulting to O(1) run-time complexity. The presented approach is simple to implement. Due to the principle of duality, dual problems, e.g. line-convex polygon, line clipping, can be solved in a similarly.

97 MATHEMATICS AND COMPUTING↗

Region-oriented CT image representation for reducing computing time of Monte Carlo simulations

Purpose. We propose a new method for efficient particle transportation in voxelized geometry for Monte Carlo simulations. We describe its use for calculating dose distribution in CT images for radiation therapy. Material and methods. The proposed approach, based on an implicit volume representation named segmented volume, coupled with an adapted segmentation procedure and a distance map, allows us to minimize the number of boundary crossings, which slows down simulation. The method was implemented with the GEANT4 toolkit and compared to four other methods: One box per voxel, parameterized volumes, octree-based volumes, and nested parameterized volumes. For each representation, we compared dose distribution, time, and memory consumption. Results. The proposed method allows us to decrease computational time by up to a factor of 15, while keeping memory consumption low, and without any modification of the transportation engine. Speeding up is related to the geometry complexity and the number of different materials used. We obtained an optimal number of steps with removal of all unnecessary steps between adjacent voxels sharing a similar material. However, the cost of each step is increased. When the number of steps cannot be decreased enough, due for example, to the large number of material boundaries, such a method is not considered suitable. Conclusion. This feasibility study shows that optimizing the representation of an image in memory potentially increases computing efficiency. We used the GEANT4 toolkit, but we could potentially use other Monte Carlo simulation codes. The method introduces a tradeoff between speed and geometry accuracy, allowing computational time gain. However, simulations with GEANT4 remain slow and further work is needed to speed up the procedure while preserving the desired accuracy.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

Optimized generation of high resolution breast anthropomorphic software phantoms

Purpose: The authors present an efficient method for generating anthropomorphic software breast phantoms with high spatial resolution. Employing the same region growing principles as in their previous algorithm for breast anatomy simulation, the present method has been optimized for computational complexity to allow for fast generation of the large number of phantoms required in virtual clinical trials of breast imaging. Methods: The new breast anatomy simulation method performs a direct calculation of the Cooper's ligaments (i.e., the borders between simulated adipose compartments). The calculation corresponds to quadratic decision boundaries of a maximum a posteriori classifier. The method is multiscale due to the use of octree-based recursive partitioning of the phantom volume. The method also provides user-control of the thickness of the simulated Cooper's ligaments and skin. Results: Using the proposed method, the authors have generated phantoms with voxel size in the range of (25-1000 {mu}m){sup 3}/voxel. The power regression of the simulation time as a function of the reciprocal voxel size yielded a log-log slope of 1.95 (compared to a slope of 4.53 of our previous region growing algorithm). Conclusions: A new algorithm for computer simulation of breast anatomy has been proposed that allows for fast generation of high resolution anthropomorphic software phantoms.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

Parallel Lattice Subpaving Map (plsm)

Custom spatial subdivision of N-dimensional lattice region in GPU memory. An extension of the method of a hyper-octree is used to allow for arbitrary subdivision ratios in each dimension. In addition, the decision to refine (or select) a given sub-region is based on a user-provided callback, allowing for arbitrary refinement domains to be expressed either geometrically or programmatically.

Fackler, Philip↗

DGTile

SAND2022-12898 O DGTile is a lightweight C++17 adaptive mesh library meant to support explicit discontinuous Galerkin applications on high performance computing machines. DGTile uses a block-based adaptive mesh refinement approach, where the underlying mesh data structure is an octree in three dimensions, where each leaf node of the tree represents a Cartesian grid. Over each grid, DGTile provides modal discontinuous Galerkin basis functions to facilitate simulations. Sandia National Laboratories is a multimission laboratory managed and operated by National Technology & Engineering Solutions of Sandia, LLC, a wholly owned subsidiary of Honeywell International Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA0003525.

Granzow, Brian↗

automesh: Automatic mesh generation in Rust

automesh is an open-source Rust software program that uses a segmentation, typically generated from a 3D image stack, to create a finite element mesh, composed either of hexahedral (volumetric) or triangular (isosurface) elements. automesh converts between segmentation formats (.npy, .spn) and mesh formats (.exo, .inp, .mesh, .stl, .vtk). automesh can defeature voxel domains, apply Laplacian and Taubin smoothing, and output mesh quality metrics. automesh uses an internal octree for fast performance.

Hovey, Chad Brian [Sandia National Laboratories (S↗

Parallel fast gauss transform

We present fast adaptive parallel algorithms to compute the sum of N Gaussians at N points. Direct sequential computation of this sum would take O(N{sup 2}) time. The parallel time complexity estimates for our algorithms are O(N/n{sub p}) for uniform point distributions and O( (N/n{sub p}) log (N/n{sub p}) + n{sub p}log n{sub p}) for non-uniform distributions using n{sub p} CPUs. We incorporate a plane-wave representation of the Gaussian kernel which permits 'diagonal translation'. We use parallel octrees and a new scheme for translating the plane-waves to efficiently handle non-uniform distributions. Computing the transform to six-digit accuracy at 120 billion points took approximately 140 seconds using 4096 cores on the Jaguar supercomputer. Our implementation is 'kernel-independent' and can handle other 'Gaussian-type' kernels even when explicit analytic expression for the kernel is not known. These algorithms form a new class of core computational machinery for solving parabolic PDEs on massively parallel architectures.

99 GENERAL AND MISCELLANEOUS↗

Scalable parallel distance field construction for large-scale applications

Computing distance fields is fundamental to many scientific and engineering applications. Distance fields can be used to direct analysis and reduce data. In this paper, we present a highly scalable method for computing 3D distance fields on massively parallel distributed-memory machines. Anew distributed spatial data structure, named parallel distance tree, is introduced to manage the level sets of data and facilitate surface tracking overtime, resulting in significantly reduced computation and communication costs for calculating the distance to the surface of interest from any spatial locations. Our method supports several data types and distance metrics from real-world applications. We demonstrate its efficiency and scalability on state-of-the-art supercomputers using both large-scale volume datasets and surface models. We also demonstrate in-situ distance field computation on dynamic turbulent flame surfaces for a petascale combustion simulation. In conclusion, our work greatly extends the usability of distance fields for demanding applications.

97 MATHEMATICS AND COMPUTING↗

A Semi-Algebraic Two Level Solver

We develop a simple semi-algebraic 2-level solver built on traditional multigrid ideas. It is designed to be easily incorporated into existing simulation software. It exhibits good convergence for many classes of challenging problems including discontinuous diffusion, convection- diffusion, and Helmholtz equations. It has built-in structure that makes it simple to generalize in several interesting directions.

97 MATHEMATICS AND COMPUTING↗