Isotopic approximations and interval solids

Given a nonsingular compact two-manifold F without boundary, we present methods for establishing a family of surfaces which can approximate F so that each approximant is ambient isotopic to F. The methods presented here offer broad theoretical guidance for a rich class of ambient isotopic approximations, for applications in graphics, animation and surface reconstruction. They are also used to establish sufficient conditions for an interval solid to be ambient isotopic to the solid it is approximating. Furthermore, the normals of the approximant are compared to the normals of the original surface, as these approximating normals play prominent roles in many graphics algorithms.The methods are based on global theoretical considerations and are compared to existing local methods. Practical implications of these methods are also presented. For the global case, a differential surface analysis is performed to find a positive number ρ so that the offsets F_o(±ρ) of F at distances ±ρ are nonsingular. In doing so, a normal tubular neighborhood, F(ρ), of F is constructed. Then, each approximant of F lies inside F(ρ). Comparisons between these global and local constraints are given.     

A surface reconstruction algorithm for topology optimization

For mechanical structural design, topology optimization is often utilized. During this process, a topologically optimized model must be converted into a parametric CAD solid model. The key point of conversion is that a discretized shape of a topologically optimized model must be smoothed, but features such as creases and corners must be retained. Thus, a surface reconstruction algorithm to produce the parametric CAD solid model from a topologically optimized model is proposed in this paper. Our presented algorithm consists of three parts: (1) an enclosed isosurface geometry from which the topologically optimized model is generated, (2) features detected and (3) the parametric CAD solid model reconstructed as biquartic surface splines. In order to generate an enclosed isosurface model effectively, we propose an algorithm based upon the marching cubes method to detect elements intersected by an isosurface. After generating an enclosed isosurface model, we produce biquartic surface splines. By applying our algorithm to an enclosed isosurface model, it is possible to produce smoothed biquartic surface splines with features retained. Some examples are shown and the effectiveness of our algorithm is discussed in this paper.     

Design of phononic materials/structures for surface wave devices using topology optimization

We develop a topology optimization approach to design two- and three-dimensional phononic (elastic) materials, focusing primarily on surface wave filters and waveguides. These utilize propagation modes that transmit elastic waves where the energy is contained near a free surface of a material. The design of surface wave devices is particularly attractive given recent advances in nano- and micromanufacturing processes, such as thin-film deposition, etching, and lithography, which make it possible to precisely place thin film materials on a substrate with submicron feature resolution. We apply our topology optimization approach to a series of three problems where the layout of two materials (silicon and aluminum) is sought to achieve a prescribed objective: (1) a grating to filter bulk waves of a prescribed frequency in two and three dimensions, (2) a surface wave device that uses a patterned thin film to filter waves of a single or range of frequencies, and (3) a fully three-dimensional structure to guide a wave generated by a harmonic input on a free surface to a specified output port on the surface. From the first to the third example, the resulting topologies increase in sophistication. The results demonstrate the power and promise of our computational framework to design sophisticated surface wave devices.     

On surface reconstruction: A priority driven approach

To reconstruct an object surface from a set of surface points, a fast, practical, and efficient priority driven algorithm is presented. The key idea of the method is to consider the shape changes of an object at the boundary of the mesh growing area and to create a priority queue to the advancing front of the mesh area according to the changes. The mesh growing process is then driven by the priority queue for efficient surface reconstruction. New and practical triangulation criteria are also developed to support the priority driven strategy and to construct a new triangle at each step of mesh growing in real time. The quality and correctness of the created triangles will be guaranteed by the triangulation criteria and topological operations. The algorithm can reconstruct an object surface from unorganized surface points in a fast and reliable manner. Moreover, it can successfully construct the surface of the objects with complex geometry or topology. The efficiency and robustness of the proposed algorithm is validated by extensive experiments.     

Computational Geometry Education for Computer Graphics Students

The paper surveys main features of computational geometry and presents the argument that a course oriented to applied computational geometry should be a part of the computer graphics curriculum, as it teaches effective algorithmic methods and helps to develop abstract thinking. Possible contents of the course and forms suitable and interesting for computer graphics students are discussed. The students' feedback on such a course has been mostly positive.     

A performance index for topology and shape optimization of plate bending problems with displacement constraints

This paper presents a performance index for topology and shape optimization of plate bending problems with displacement constraints. The performance index is developed based on the scaling design approach. This performance index is used in the Performance-Based Optimization (PBO) method for plates in bending to keep track of the performance history when inefficient material is gradually removed from the design and to identify optimal topologies and shapes from the optimization process. Several examples are provided to illustrate the validity and effectiveness of the proposed performance index for topology and shape optimization of bending plates with single and multiple displacement constraints under various loading conditions. The topology optimization and shape optimization are undertaken for the same plate in bending, and the results are evaluated by using the performance index. The proposed performance index is also employed to compare the efficiency of topologies and shapes produced by different optimization methods. It is demonstrated that the performance index developed is an effective indicator of material efficiency for bending plates. From the manufacturing and efficient point of view, the shape optimization technique is recommended for the optimization of plates in bending. Received November 27, 1998?Revised version received June 6, 1999     

Buoyancy Optimization for Computational Fabrication

This paper introduces a design and fabrication pipeline for creating floating forms. Our method optimizes for buoyant equilibrium and stability of complex 3D shapes, applying a voxel‐carving technique to control the mass distribution. The resulting objects achieve a desired floating pose defined by a user‐specified waterline height and orientation. In order to enlarge the feasible design space, we explore novel ways to load the interior of a design using prefabricated components and casting techniques. 3D printing is employed for high‐precision fabrication. For larger scale designs we introduce a method for stacking lasercut planar pieces to create 3D objects in a quick and economic manner. We demonstrate fabricated designs of complex shape in a variety of floating poses.     

A cell-transverse display algorithm for regular and rectilinear 3D grid data

This paper proposes an efficient direct imaging algorithm for constructing iso-surfaces from regular and rectilinear 3D grid data in scientific and engineering visualization. The basic idea is to generate and draw polygons simultaneously by processing the cells spanned by grids in decreasing order of distance from the current viewpoint. Iso-surfaces are generated in five or six tetrahedrons into which the cells are subdivided, and are sent to a graphics device or drawn into a frame buffer on the fly. The execution order of each of the tetrahedrons is identical and is determined by the current viewpoint. Since the algorithm does not need to store intermediate polyhedral data and does not require a depth buffer memory for hidden surface removal, it is applicable to a large quantity of data on a 3D grid, such as computed tomography (CT) data. It is also particularly powerful for semi-transparent display, because transparency calculation can be reduced to image compositing operations if the polygons are drawn in order of their z-depth from the current viewpoint.     

GPU Local Triangulation: an interpolating surface reconstruction algorithm

A GPU capable method for surface reconstruction from unorganized point clouds without additional information, called GLT (GPU Local Triangulation), is presented. The main objective of this research is the generation of a GPU interpolating reconstruction based on local Delaunay triangulations, inspired by a pre‐existing reconstruction algorithm. Current graphics hardware accelerated algorithms are approximating approaches, where the final triangulation is usually performed through either marching cubes or marching tetrahedras. GPU‐compatible methods and data structures to perform normal estimation and the local triangulation have been developed, plus a variation of the Bitonic Merge Sort algorithm to work with multi‐lists. Our method shows an average gain of one order of magnitude over previous research.     

Computing area filling contours for surfaces defined by piecewise polynomials

For contour plotting, bivariate polynomials are often used to interpolate between the data points. The polynomials are defined over triangular or rectangular domains and have continuous interfaces resulting from various interpolation schemes. In this paper the principal ideas of the Trip Algorithm are presented, which finds closed polygons for filling the area between contour lines. These polygons consist of points P defining the contours, intersections S with the boundary of the domain, and vertices V of the domain. The points P are computed successively by a nonlinear method that combines extrapolation and the regula falsi in order to adjust the distance between the points to the curvature of the contour. For the extrapolation, derivatives of Lagrange polynomials are used. Empirical parameters for the automatic step size control are given. Once the points S are determined, the method is independent of the type of the interpolation function f(x, y). Two examples for applications of the Trip Algorithm are presented: one from scattered data interpolation, the other from stress analysis by finite element methods.     

A framework for quad/triangle subdivision surface fitting: Application to mechanical objects

In this paper we present a new framework for subdivision surface approximation of three‐dimensional models represented by polygonal meshes. Our approach, particularly suited for mechanical or Computer Aided Design (CAD) parts, produces a mixed quadrangle‐triangle control mesh, optimized in terms of face and vertex numbers while remaining independent of the connectivity of the input mesh. Our algorithm begins with a decomposition of the object into surface patches. The main idea is to approximate the region boundaries first and then the interior data. Thus, for each patch, a first step approximates the boundaries with subdivision curves (associated with control polygons) and creates an initial subdivision surface by linking the boundary control points with respect to the lines of curvature of the target surface. Then, a second step optimizes the initial subdivision surface by iteratively moving control points and enriching regions according to the error distribution. The final control mesh defining the whole model is then created assembling every local subdivision control meshes. This control polyhedron is much more compact than the original mesh and visually represents the same shape after several subdivision steps, hence it is particularly suitable for compression and visualization tasks. Experiments conducted on several mechanical models have proven the coherency and the efficiency of our algorithm, compared with existing methods.     

Mixed Fourier-Laguerre Spectral and Pseudospectral Methods for Exterior Problems Using Generalized Laguerre Functions

In this paper, we develop the mixed spectral and pseudospectral methods for two-dimensional exterior problems, by using the scaled generalized Laguerre functions. Some basic results on the mixed Fourier-Laguerre orthogonal approximation and Gauss-type interpolation are established, which play important roles in the related spectral and pseudospectral methods. As an example, we propose the mixed spectral and pseudospectral schemes for a model problem. The convergence of proposed schemes are proved. Numerical results demonstrate the spectral accuracy efficiency of this new approach. This work is supported in part by NSF of China, N.10771142, the National Basic Research Project N.2005CB321701, SF of Shanghai N.075105118, The Shanghai Leading Academic Discipline Project N.T0401 and The Fund for E-institute of Shanghai Universities N.E03004.     

Localized Delaunay Refinement for Volumes

Delaunay refinement, recognized as a versatile tool for meshing a variety of geometries, has the deficiency that it does not scale well with increasing mesh size. The bottleneck can be traced down to the memory usage of 3D Delaunay triangulations. Recently an approach has been suggested to tackle this problem for the specific case of smooth surfaces by subdividing the sample set in an octree and then refining each subset individually while ensuring termination and consistency. We extend this to localized refinement of volumes, which brings about some new challenges. We show how these challenges can be met with simple steps while retaining provable guarantees, and that our algorithm scales many folds better than a state‐of‐the‐art meshing tool provided by CGAL.     

As‐Killing‐As‐Possible Vector Fields for Planar Deformation

Cartoon animation, image warping, and several other tasks in two‐dimensional computer graphics reduce to the formulation of a reasonable model for planar deformation. A deformation is a map from a given shape to a new one, and its quality is determined by the type of distortion it introduces. In many applications, a desirable map is as isometric as possible. Finding such deformations, however, is a nonlinear problem, and most of the existing solutions approach it by minimizing a nonlinear energy. Such methods are not guaranteed to converge to a global optimum and often suffer from robustness issues. We propose a new approach based on approximate Killing vector fields (AKVFs), first introduced in shape processing. AKVFs generate near‐isometric deformations, which can be motivated as direction fields minimizing an “as‐rigid‐as‐possible” (ARAP) energy to first order. We first solve for an AKVF on the domain given user constraints via a linear optimization problem and then use this AKVF as the initial velocity field of the deformation. In this way, we transfer the inherent nonlinearity of the deformation problem to finding trajectories for each point of the domain having the given initial velocities. We show that a specific class of trajectories — the set of logarithmic spirals — is especially suited for this task both in practice and through its relationship to linear holomorphic vector fields. We demonstrate the effectiveness of our method for planar deformation by comparing it with existing state‐of‐the‐art deformation methods.     

A Bi‐Directional Procedural Model for Architectural Design

It is a challenge for shape grammars to incorporate spatial hierarchy and interior connectivity of buildings in early design stages. To resolve this difficulty, we developed a bi‐directional procedural model: the forward process constructs the derivation tree with production rules, while the backward process realizes the tree with shapes in a stepwise manner (from leaves to the root). Each inverse‐derivation step involves essential geometric‐topological reasoning. With this bi‐directional framework, design constraints and objectives are encoded in the grammar‐shape translation. We conducted two applications. The first employs geometric primitives as terminals and the other uses previous designs as terminals. Both approaches lead to consistent interior connectivity and a rich spatial hierarchy. The results imply that bespoke geometric‐topological processing helps shape grammar to create plausible, novel compositions. Our model is more productive than hand‐coded shape grammars, while it is less computation‐intensive than evolutionary treatment of shape grammars.