An approach for extracting non-manifold mid-surfaces of thin-wall solids using chordal axis transform

This paper proposes an approach for extracting non-manifold mid-surfaces of thin-wall solids using the chordal axis transform (CAT) (Prasad in CNLS Newsletter—Center for Nonlinear Studies, Los Alamos National Laboratory, vol 139, 1997). There is great demand for extracting mid-surfaces as it is used in dimension reduction. Quadros and Shimada previously used CAT in extracting 2-manifold mid-surfaces of a particular type of thin-wall solids. The proposed approach is an extension of the previous approach (Quadros and Shimada in 11th international meshing roundtable, 2002) in order to extract non-manifold mid-surfaces of general thin-wall solids. The three steps involved in extracting the mid-surface of a thin-wall solid are: (1) generating a tet mesh of a thin-wall solid without inserting interior nodes; (2) generating a raw mid-surface by smart cutting of tets; and (3) remeshing the raw mid-surface via smart clean-up. In the proposed approach, a discrete model (i.e., a tet mesh without any interior nodes) is used instead of working directly on a CAD model. The smart cutting of tets using CAT yields correct topology at the non-manifold region in the raw mid-surface. As the raw mid-surface is not directly suitable for engineering purposes, it is trimmed using a smart clean-up procedure and then remeshed. The proposed approach has been implemented using C++ in commercial ALGOR finite element analysis software. The proposed approach is computationally efficient and has shown effective results on industrial models.     

A highly solid model boundary preserving method for large-scale parallel 3D Delaunay meshing on parallel computers

In this paper, we propose a novel parallel 3D Delaunay triangulation algorithm for large-scale simulations on parallel computers. Our method keeps the 3D boundary representation model information during the whole parallel 3D Delaunay triangulation process running on parallel computers so that the solid model information can be accessed dynamically and the meshing results can be very approaching to the model boundary with the increase of meshing scale. The model is coarsely meshed at first and distributed on CPUs with consistent partitioned shared interfaces and partitioned model boundary meshes across processors. The domain partition aims at minimizing the edge-cuts across different processors for minimum communication cost and distributing roughly equal number of mesh vertices for load balance. Then a parallel multi-scale surface mesh refinement phase is iteratively performed to meet the mesh density criteria followed by a parallel surface mesh optimization phase moving vertices to the model boundary so as to fit model geometry feature dynamically. A dynamic load balancing algorithm is performed to change the partition interfaces if necessary. A 3D local non-Delaunay mesh repair algorithm is finally done on the shared interfaces across processors and model boundaries. The experimental results demonstrate our method can achieve high parallel performance and perfect scalability, at the same time preserve model boundary feature and generate high quality 3D Delaunay mesh as well.     

An algorithm for the medial axis transform of 3D polyhedral solids

The medial axis transform (MAT) is a representation of an object which has been shown to be useful in design, interrogation, animation, finite element mesh generation, performance analysis, manufacturing simulation, path planning and tolerance specification. In this paper, an algorithm for determining the MAT is developed for general 3D polyhedral solids of arbitrary genus without cavities, with nonconvex vertices and edges. The algorithm is based on a classification scheme which relates different pieces of the medial axis (MA) to one another, even in the presence of degenerate MA points. Vertices of the MA are connected to one another by tracing along adjacent edges, and finally the faces of the axis are found by traversing closed loops of vertices and edges. Representation of the MA and its associated radius function is addressed, and pseudocode for the algorithm is given along with recommended optimizations. A connectivity theorem is proven to show the completeness of the algorithm. Complexity estimates and stability analysis for the algorithms are presented. Finally, examples illustrate the computational properties of the algorithm for convex and nonconvex 3D polyhedral solids with polyhedral holes     

MATHSM: medial axis transform toward high speed machining of pockets

The pocketing operation is a fundamental procedure in NC machining. Typical pocketing schemes compute uniform successive offsets or parallel cuts of the outline of the pocket, resulting in a toolpath with C¹ discontinuities. These discontinuities render the toolpath quite impractical in the context of high speed machining (HSM).This work addresses and fully resolves the need for a C¹ continuous toolpath in HSM and offers MATHSM, a C¹ continuous toolpath for arbitrary C¹ continuous pockets. MATHSM automatically generates a C¹ continuous toolpath that consists of primarily circular arcs while maximizing the radii of the generated arcs and, therefore, minimizing the exerted radial acceleration. MATHSM is especially suited for machining of elongated narrow pockets.     

Medial axis lookup table and test neighborhood computation for 3D chamfer norms

Chamfer distances are discrete distances based on the propagation of local distances, or weights, defined in a mask. The medial axis, i.e. the centers of maximal balls (balls which are not contained in any other ball), is a powerful tool for shape representation and analysis. The extraction of maximal disks is performed in the general case by testing the inclusion of a ball in a local neighborhood with covering relations usually represented by lookup tables.The proposed method determines if a mask induces a norm and in this case, computes the lookup tables and the test neighborhood based on geometric properties of the balls of chamfer norms, represented as H-polytopes. The method does not need to repeatedly scan the image space, and improves the computation time of both the test neighborhood detection and the lookup table computation.     

A hybrid ant colony optimization approach for finite element mesh decomposition

This paper examines the application of the ant colony optimization algorithm to the partitioning of unstructured adaptive meshes for parallel explicit time-stepping finite element analysis. The concept of the ant colony optimization technique for finding approximate solutions to combinatorial optimization problems is described.The application of ant colony optimization for partitioning finite element meshes based on triangular elements is described.A recursive greedy algorithm optimization method is also presented as a local optimization technique to improve the quality of the solutions given by the ant colony optimization algorithm. The partitioning is based on the recursive bisection approach.The mesh decomposition is carried out using normal and predictive modes for which the predictive mode uses a trained multilayered feed-forward neural network which estimates the number of triangular elements that will be generated after finite elements mesh generation is carried out.The performance of the proposed hybrid approach for the recursive bisection of finite element meshes is examined by decomposing two mesh examples.     

A novel parallel approach for 3D seismological problems

The large spatial scale associated with the modelling of strong ground motion in three dimensions requires enormous computational resources. For this reason, the simulation of soil shaking requires high-performance computing. The aim of this work is to present a new parallel approach for these kind of problems based on domain decomposition technique. The main idea is to subdivide the original problem into local ones. It allows to investigate large-scale problems that cannot be solved by a serial code. The performance of our parallel algorithm has been examined analysing computational times, speed-up and efficiency. Results of this approach are shown and discussed.     

Exploration trees on highly complex scenes: A new approach for 3D segmentation

A new strategy for automatic object extraction in highly complex scenes is presented in this paper. The method proposed gives a solution for 3D segmentation avoiding most restrictions imposed in other techniques. Thus, our technique is applicable on unstructured 3D information (i.e. cloud of points), with a single view of the scene, scenes consisting of several objects where contact, occlusion and shadows are allowed, objects with uniform intensity/texture and without restrictions of shape, pose or location. In order to have a fast segmentation stopping criteria, the number of objects in the scene is taken as input. The method is based on a new distributed segmentation technique that explores the 3D data by establishing a set of suitable observation directions. For each exploration viewpoint, a strategy [3D data]-[2D projected data]-[2D segmentation]-[3D segmented data] is accomplished. It can be said that this strategy is different from current 3D segmentation strategies. This method has been successfully tested in our lab on a set of real complex scenes. The results of these experiments, conclusions and future improvements are also shown in the paper.     

A multimodal approach for 3D face modeling and recognition using 3D deformable facial mask

We present a multimodal approach for face modeling and recognition. The algorithm uses three cameras to capture stereo images, two frontal and one profile, of the face. 2D facial features are extracted from one of the frontal images and a dense disparity map is computed from the two frontal images. Using the extracted 2D features and their corresponding disparities, we compute their 3D coordinates. We next align a low resolution 3D mesh model to the 3D features, re-project its vertices onto the frontal 2D image and adjust its profile silhouette vertices using the profile view image. We increase the resolution of the resulting 2D model at its center region to obtain a facial mask model covering distinctive features of the face. The 2D coordinates of the vertices, along with their disparities, result in a deformed 3D mask model specific to a given subject’s face. Our method integrates information from the extracted facial features from the 2D image modality with information from the 3D modality obtained from the stereo images. Application of the models in 3D face recognition, for 112 subjects, validates the algorithm with a 95% identification rate and 92% verification rate at 0.1% false acceptance rate.

A new subdivision based approach for piecewise smooth approximation of 3D polygonal curves

This paper presents an algorithm dealing with the data reduction and the approximation of 3D polygonal curves. Our method is able to approximate efficiently a set of straight 3D segments or points with a piecewise smooth subdivision curve, in a near optimal way in terms of control point number. Our algorithm is a generalization for subdivision rules, including sharp vertex processing, of the Active B-Spline Curve developed by Pottmann et al. We have also developed a theoretically demonstrated approach, analysing curvature properties of B-Splines, which computes a near optimal evaluation of the initial number and positions of control points. Moreover, our original Active Footpoint Parameterization method prevents wrong matching problems occurring particularly for self-intersecting curves. Thus, the stability of the algorithm is highly increased. Our method was tested on different sets of curves and gives satisfying results regarding to approximation error, convergence speed and compression rate. This method is in line with a larger 3D CAD object compression scheme by piecewise subdivision surface approximation. The objective is to fit a subdivision surface on a target patch by first fitting its boundary with a subdivision curve whose control polygon will represent the boundary of the surface control polyhedron.     

A new design concept: 3D to 2D textile pattern design for garments

‘The word “fashion” is synonymous with the word “change”. Fashion begins with fabrics and fabrics begin with colour’. This famous remark/definition of ‘fashion’ must now be revised in the era of digital technology. In this paper, we propose a novel print design concept, from 3D garments to 2D textiles. By taking advantage of the cutting-edge developments in surface parameterisation, cloth simulation and texture assignment, we develop a computer system that allows designers to create figure-flattering prints directly onto 3D garments, and will output 2D pattern pieces with matched texture that are ready for digital printing and garment production. It reverses the traditional design process from 2D fabrics to 3D garments. The results produced by the proposed method guarantee textural continuity in both garment and pattern pieces. It not only releases apparel makers from the tedious work of matching texture along seams, but also provides users with a new tool to create one-of-a-kind fashion products by designing personalised prints.     

A novel distance estimation approach for 3D localization in wireless sensor network using multi dimensional scaling

Node localization is very important in Wireless Sensor Network (WSN) and distance estimation between pairs of nodes is the prerequisite for localization and thus the applicability of the reported events. The paper proposes a novel distance estimation algorithm to estimate distances of each node to every other node in the network. The main contribution of the paper is the definition of a dissimilarity matrix representing the distance of each node to every other node in the network. MDS based localization algorithm is used to determine coordinates of the node in a local coordinate system and Helmert Transformation is used to convert the local coordinates of the node into a global coordinate system. The effect of various parameters affecting the performance of proposed algorithm is also presented in the paper. Finally, the efficiency of the proposed algorithm is established through the simulation results.     

A grid generator for 3-D explosion simulations using the staircase boundary approach in Cartesian coordinates based on STL models

In this paper, an automatic grid generator based on STL models is proposed. The staircase boundary treatment is implemented to handle irregular geometries and the computation domain is discretized using a regular Cartesian grid. Using the grid generator, staircase grids that are suitable for fast and accurate finite difference analysis could be generated. Employing the slicing algorithm in RP technologies [1], the STL models are sliced with a set of parallel planes to generate 2D slices after the STL files obtained from a CAD system undergo topology reconstruction. To decrease the staircase error (increase accuracy) and enhance working efficiency, the cross-section at the middle of the layer is taken to represent the cross-section of whole layer. The scan line filling technique of computer graphics [2] is used to achieve grid generation after slicing. Finally, we demonstrate an application of the introduced method to generate staircase grids, which allows successful FDM simulation in the field of explosion. The example shows that the automatic grid generator based on STL models is fast and gives simulation results that are in agreement with practical observations.     

Visual learning and recognition of 3D objects using two-dimensional principal component analysis: A robust and an efficient approach

Inspired by the conviction that the successful model employed for face recognition [M. Turk, A. Pentland, Eigenfaces for recognition, J. Cogn. Neurosci. 3(1) (1991) 71-86] should be extendable for object recognition [H. Murase, S.K. Nayar, Visual learning and recognition of 3-D objects from appearance, International J. Comput. Vis. 14(1) (1995) 5-24], in this paper, a new technique called two-dimensional principal component analysis (2D-PCA) [J. Yang et al., Two-dimensional PCA: a new approach to appearance based face representation and recognition, IEEE Trans. Patt. Anal. Mach. Intell. 26(1) (2004) 131-137] is explored for 3D object representation and recognition. 2D-PCA is based on 2D image matrices rather than 1D vectors so that the image matrix need not be transformed into a vector prior to feature extraction. Image covariance matrix is directly computed using the original image matrices, and its eigenvectors are derived for feature extraction. The experimental results indicate that the 2D-PCA is computationally more efficient than conventional PCA (1D-PCA) [H. Murase, S.K. Nayar, Visual learning and recognition of 3-D objects from appearance, International J. Comput. Vis. 14(1) (1995) 5-24]. It is also revealed through experimentation that the proposed method is more robust to noise and occlusion.