A framework for digital sunken relief generation based on 3D geometric models

Sunken relief is a special art form of sculpture whereby the depicted shapes are sunk into a given surface. This is traditionally created by laboriously carving materials such as stone. Sunken reliefs often utilize the engraved lines or strokes to strengthen the impressions of a 3D presence and to highlight the features which otherwise are unrevealed. In other types of relief, smooth surfaces and their shadows convey such information in a coherent manner. Existing methods for relief generation are focused on forming a smooth surface with a shallow depth which provides the presence of 3D figures. Such methods unfortunately do not help the art form of sunken reliefs as they omit the presence of feature lines. We propose a framework to produce sunken reliefs from a known 3D geometry, which transforms the 3D objects into three layers of input to incorporate the contour lines seamlessly with the smooth surfaces. The three input layers take the advantages of the geometric information and the visual cues to assist the relief generation. We have modified the existing techniques of line drawings and relief generation, and then combine them organically for this particular purpose.     

Real-time bas-relief generation from a 3D mesh

Most of the existing approaches to bas-relief generation operate in image space, which is quite time-consuming in practice. This paper presents a different bas-relief generation algorithm based on geometric compression and starting from a 3D mesh input. The feature details are first extracted from the original objects using a spatial bilateral filtering technique. Then, a view-dependent coordinate mapping method is applied to build the height domain for the current view. After fitting the compression datum plane, the algorithm uses an adaptive compression function to scale and combine the Z values of the base mesh and the fine details. This approach offers control over the level of detail, making it flexible for the adjustment of the appearance of details. For a typical input mesh with 100 k triangles, this algorithm computes a bas-relief in 0.214 s.     

Parallel decoupled terminal-edge bisection method for 3D mesh generation

We present a practical and stable algorithm for the parallel refinement of tetrahedral meshes. The algorithm is based on the refinement of terminal-edges and associated terminal stars. A terminal-edge is a special edge in the mesh which is the longest edge of every element that shares such an edge, while the elements that share a terminal-edge form a terminal star. We prove that the algorithm is inherently decoupled and thus scalable. Our experimental data show that we have a stable implementation able to deal with hundreds of millions of tetrahedra and whose speed is in between one and two order of magnitude higher from the method and implementation we presented (Rivara et al., Proceedings 13th international meshing roundtable, 2004).Maria-Cecilia Rivara and Carlo Calderon's work was partially supported by Fondecyt 1040713.Andriy Fedorov’s work is supported in part by ITR #ACI-0085969, and NGS #ANI-0203974.Nikos Chrisochoides’s work is supported in part by NSF Career Award #CCR-0049086, ITR #ACI-0085969, NGS #ANI-0203974, and ITR #CNS-0312980.     

An algorithm for automatic 2D finite element mesh generation with line constraints

In this study, an algorithm is designed specifically for automatic finite element (FE) mesh generation on the transverse structure of hulls reinforced by stiffeners. Stiffeners attached to the transverse structure are considered as line constraints in the geometry boundary. For the FE mesh generation used in this study, the line constraints are treated as boundaries and by that means the geometry domain attached to the line constraints is decomposed into sub-domains, constrained only by the closed boundaries. Then, the mesh can be generated directly on those sub-domains by the traditional approach. The performance of the proposed algorithm is evaluated and the quality of the generated mesh meets expectations.     

Skewed rotational symmetry detection from a 2D line drawing of a 3D polyhedral object

This paper introduces a new algorithm for detecting skewed rotational symmetry in a 2D line drawing of a 3D polyhedral object by locating the possibly-multiple symmetry axes. The drawing is converted into an edge–vertex graph from which the algorithm finds the faces of the object and the sets of topologically symmetric edges and vertices. It then checks that each set of vertices is rotationally symmetric geometrically by analyzing the distribution of the vertices around the circumference of the best-fit ellipse. The object is rotationally skewed symmetric if the best fit ellipses of all the vertex sets have parallel axes, equal ratio of major radius to minor radius and centers on the axis of rotation. A tolerance is used in the calculation to allow for inaccuracies in the line drawings. A set of experimental results is presented showing that the algorithm works well.     

High-quality 2D mesh generation without obtuse and small angles

In this paper, we present an efficient method to eliminate the obtuse triangles for high quality 2D mesh generation. Given an initialization (e.g., from Centroidal Voronoi Tessellation—CVT), a limited number of point insertions and removals are performed to eliminate obtuse or small angle triangles. A mesh smoothing and optimization step is then applied. These steps are repeated till a desired good quality mesh is reached. We tested our algorithm on various 2D polygonal domains and verified that our algorithm always converges after inserting a few number of new points, and generates high quality triangulation with no obtuse triangles.     

A new automated scheme of quadrilateral mesh generation for randomly distributed line constraints

This paper presents a new automated method of quadrilateral meshes with random line constraints which have not been fully considered in previous models. The authors developed a new looping scheme and a direct quadrilateral forming algorithm based on advanced front techniques. This generator overcomes the limitations of previous studies such as line constraint, unmeshed hole and mesh refinement. A qualitative test reveals that our algorithm is reliable and suitable at the field needed for very accurate results. The developed direct method to handle line-typed features automatically makes the multiple discretizations without any user interaction and modification.     

An algorithm for automatic 2D quadrilateral mesh generation with line constraints

Finite element method (FEM) is a fundamental numerical analysis technique widely used in engineering applications. Although state-of-the-art hardware has reduced the solving time, which accounts for a small portion of the overall FEM analysis time, the relative time needed to build mesh models has been increasing. In particular, mesh models that must model stiffeners, those features that are attached to the plate in a ship structure, are imposed with line constraints and other constraints such as holes. To automatically generate a 2D quadrilateral mesh with the line constraints, an extended algorithm to handle line constraints is proposed based on the constrained Delaunay triangulation and Q-Morph algorithm. The performance of the proposed algorithm is evaluated, and numerical results of our proposed algorithm are presented.     

Skeleton-enhanced line drawings for 3D models

We present a novel line drawing approach for 3D models by introducing their skeleton information into the rendering process. Based on the silhouettes of the input 3D models, we first extract feature lines in geometric regions by utilizing their curvature, torsion and view-dependent information. Then, the skeletons of the models are extracted by our newly developed skeleton extraction algorithm. After that, we draw the skeleton-guided lines from non-geometric regions through the skeleton information. These lines are combined with the feature lines to render the final line drawing result using the line optimization. Experimental results show that our algorithm can render line drawings more effectively with enhanced skeletons. The resulting artistic effects can capture the local geometries as well as the global skeletons of the input 3D models.     

Hexahedral mesh generation constraints

For finite element analyses within highly elastic and plastic structural domains, hexahedral meshes have historically offered some benefits over tetrahedral finite element meshes in terms of reduced error, smaller element counts, and improved reliability. However, hexahedral finite element mesh generation continues to be difficult to perform and automate, with hexahedral mesh generation taking several orders of magnitude longer than current tetrahedral mesh generators to complete. Thus, developing a better understanding of the underlying constraints that make hexahedral meshing difficult could result in dramatic reductions in the amount of time necessary to prepare a hexahedral finite element model for analysis. In this paper, we present a survey of constraints associated with hexahedral meshes (i.e., the conditions that must be satisfied to produce a hexahedral mesh). In presenting our formulation of these constraints, we will utilize the dual of a hexahedral mesh. We also discuss how incorporation of these constraints into existing hexahedral mesh generation algorithms could be utilized to extend the class of geometries to which these algorithms apply. We also describe a list of open problems in hexahedral mesh generation and give some context for future efforts in addressing these problems.     

Seams and wedges in plastering: A 3-D hexahedral mesh generation algorithm

This paper describes mesh correction techniques necessary for meshing an arbitrary volume with a completely hexahedral mesh. Specifically, it describes seams and wedges, mechanisms that overcome major hurdles encountered in the preliminary work on the plastering algorithm. The plastering algorithm iteratively projects layers of elements inward from a quadrilateral discretization of the volume's bounding faces. Seams and wedges resolve incompatibilities in the mesh and in the progressing boundary, thus ensuring the correct formation of a hexahedral mesh from the plastering algorithm.     

3D reconstruction of polyhedral objects from single parallel projections using cubic corner

This paper presents a direct method to recover the geometry of the 3D polyhedron depicted in a single parallel projection. It uses two sets of information, the list of faces in the object, obtained automatically from the drawing, and a user-identified cubic corner, to compute for the coordinates of the vertices in the drawing and thus establish the 3D geometry of the whole polyhedron. The algorithm exploits the topological structure of the polyhedron, implicit in the connectivities between the faces, resulting in a complexity that is linear in the number of faces. The method is extended to objects with no cubic corners as well. The algorithm works well for recovering objects from accurate line drawings, producing accurate 3D objects. A simple extension to the algorithm allows it to handle inaccurate drawings such as sketches, and produce 3D objects that are consistent with our human perception of the drawings.     

Finite element mesh generation

The capabilities of a geometric modeller are extended towards finite element analysis by a mesh generator which extracts all its geometric and topological information from the model. A coarse mesh is created and subsequently refined to a suitable finite element mesh, which accomodates material properties, loadcase and analysis requirements. The mesh may be optimized by adaptive refinement, ie according to estimates of the discretization errors.A survey of research and development in geometric modelling and finite element analysis is presented, then an implementation of a mesh generator for 3D curvilinear and solid objects is described in detail.     

Parallel adaptive mesh generation and decomposition

An important class of methodologies for the parallel processing of computational models defined on some discrete geometric data structures (i.e. meshes, grids) is the so calledgeometry decomposition or splitting approach. Compared to the sequential processing of such models, the geometry splitting parallel methodology requires an additional computational phase. It consists of the decomposition of the associated geometric data structure into a number of balancedsubdomains that satisfy a number of conditions that ensure the load balancing and minimum communication requirement of the underlying computations on a parallel hardware platform. It is well known that the implementation of the mesh decomposition phase requires the solution of a computationally intensive problem. For this reason several fast heuristics have been proposed. In this paper we explore a decomposition approach which is part of a parallel adaptive finite element mesh procedure. The proposed integrated approach consists of five steps. It starts with a coarse background mesh that isoptimally decomposed by applying well known heuristics. Then, the initial mesh is refined in each subdomain after linking the new boundaries introduced by its decomposition. Finally, the decomposition of the new refined mesh is improved so that it satisfies the objectives and conditions of the mesh decomposition problem. Extensive experimentation indicates the effectiveness and efficiency of the proposed parallel mesh and decomposition approach.     

A Survey of 3D Solid Reconstruction from 2D Projection Line Drawings

The reconstruction of a 3D object from its 2D projection(s) and its corresponding problem of 3D object recognition are two of the important research areas in the field of computer vision and artificial intelligence. Reconstruction involves determining the geometric and topological relationship of an object's atomic parts whereas recognition involves identifying an object by some form of template matching. Nagendra and Gujar¹ gave a survey of several papers on reconstruction of 3D object from its 2D views. In this paper we present a taxonomy of 3D object reconstruction from 2D projection line drawings. We base the classification on the number of 2D views of the 3D solid object, the degree of user interaction necessary for correct reconstruction, and the internal representation used in the reconstruction process. We discuss the basic issues associated with this problem, review the relevant literature and present topics for future research.     

Transformations between Pictures from 2D to 3D

This paper describes programs for 3-dimensional engraving. The programs use raster or vector images to create a 3D model and, subsequently, convert this model into a sequence of control commands for 3D engraving machines. Three programs have been developed. A program for engraving general 3D surfaces from grey-scale images, a program for preparing these grey-scale images from patterns and vector images, and a program for fast 2D engraving. A simple and fast preparation of the 3D model, a user-friendly environment, and small hardware requirements were the principal goals.     

一种新的六面体有限元网格算法

在有限元网格产生过程中,吸取弦须编织法中的STC概念,将六面体以节点剖分为基础的思想转变为以单元点为基础,建立了以单元生长为核心的剖分算法,以期解决节点拓扑结构在三维情况下的控制问题,对进一步实现稳定、全自动的六面体剖分具有很大的帮助。     

Intelligent finite element mesh generation

A knowledge-based and automatic finite element mesh generator (INTELMESH) for two-dimensional linear elasticity problems is presented. Unlike other approaches, the proposed technique incorporates the information about the object geometry as well as the boundary and loading conditions to generate an a priori finite element mesh which is more refined around the critical regions of the problem domain. INTELMESH uses a blackboard architecture expert system and the new concept of substracting to locate the critical regions in the domain and to assign priority and mesh size to them. This involves the decomposition of the original structure into substructures (or primitives) for which an initial and approximate analysis can be performed by using analytical solutions and heuristics. It then uses the concept of wave propagation to generate graded nodes in the whole domain with proper density distribution. INTELMESH is fully automatic and allows the user to define the problem domain with minimum amount of input such as object geometry and boundary and loading conditions. Once nodes have been generated for the entire domain, they are automatically connected to form well-shaped triangular elements ensuring the Delaunay property. Several examples are presented and discussed. When incorporated into and compared with the traditional approach to the adaptive finite element analysis, it is expected that the proposed approach, which starts the process with near optimal initial meshes, will be more accurate and efficient.     

Fully automatic and fast mesh size specification for unstructured mesh generation

A fully automatic surface mesh generation system is presented in this paper. The automation is achieved by an automatic determination of a consistent mesh size distribution, which is based on geometry rasterisation. The user specifies a minimal and maximal allowed mesh size, and a maximal allowed curvature angle for the complete geometry, or, rather, parts of it. Now, these local curvature and local characteristic lengths of the geometry are computed, which determine the local mesh size. These local mesh sizes are stored and smoothed in a Cartesian background mesh. Afterwards, the triangulation is generated by an advancing front triangulator: the local resolution of the surface triangulation is determined by the mesh sizes stored in the Cartesian background mesh. The object-oriented design and implementation is described. The complete system is very fast due to an efficient parallelisation based on MPI for computer systems with distributed memory.     

Skeleton-based computational method for the generation of a 3D finite element mesh sizing function

This paper focuses on the generation of a three-dimensional (3D) mesh sizing function for geometry-adaptive finite element (FE) meshing. The mesh size at a point in the domain of a solid depends on the geometric complexity of the solid. This paper proposes a set of tools that are sufficient to measure the geometric complexity of a solid. Discrete skeletons of the input solid and its surfaces are generated, which are used as tools to measure the proximity between geometric entities and feature size. The discrete skeleton and other tools, which are used to measure the geometric complexity, generate source points that determine the size and local sizing function at certain points in the domain of the solid. An octree lattice is used to store the sizing function as it reduces the meshing time. The size at every lattice-node is calculated by interpolating the size of the source points. The algorithm has been tested on many industrial models, and it can be extended to consider other non-geometric factors that influence the mesh size, such as physics, boundary conditions, etc.Sandia National Laboratory is a multiprogram laboratory operated by the Sandia Corporation, a Lockheed Martin Company, for the US Department of Energy under contract DE-AC04-94AL85000.