This study investigates the impact of the invariance of feature vectors for partial-to-partial point set registration under translation and rotation of input point sets, particularly in the realm of techniques based on deep learning and Gaussian mixture models (GMMs). We reveal both theoretical and practical problems associated with such deep-learning-based registration methods using GMMs, with a particular focus on the limitations of DeepGMR, a pioneering study in this line, to the partial-to-partial point set registration. Our primary goal is to uncover the causes behind such methods and propose a comprehensible solution for that. To address this, we introduce an attention-based reference point shifting (ARPS) layer, which robustly identifies a common reference point of two partial point sets, thereby acquiring transformation-invariant features. The ARPS layer employs a well-studied attention module to find a common reference point rather than the overlap region. Owing to this, it significantly enhances the performance of DeepGMR and its recent variant, UGMMReg. Furthermore, these extension models outperform even prior deep learning methods using attention blocks and Transformer to extract the overlap region or common reference points. We believe these findings provide deeper insights into registration methods using deep learning and GMMs. Our source code and datasets are available at https://github.com/tatsy/DGRM-ARPS.git.

In this article, we present a self-prior-based mesh inpainting framework that requires only an incomplete mesh as input, without the need for any training datasets. Additionally, our method maintains the polygonal mesh format throughout the inpainting process without converting the shape format to an intermediate one, such as a voxel grid, a point cloud, or an implicit function, which are typically considered easier for deep neural networks to process. To achieve this goal, we introduce two graph convolutional networks (GCNs): single-resolution GCN (SGCN) and multi-resolution GCN (MGCN), both trained in a self-supervised manner. Our approach refines a watertight mesh obtained from the initial hole filling to generate a complete output mesh. Specifically, we train the GCNs to deform an oversmoothed version of the input mesh into the expected complete shape. The deformation is described by vertex displacements, and the GCNs are supervised to obtain accurate displacements at vertices in real holes. To this end, we specify several connected regions of the mesh as fake holes, thereby generating meshes with various sets of fake holes. The correct displacements of vertices are known in these fake holes, thus enabling training GCNs with loss functions that assess the accuracy of vertex displacements. We demonstrate that our method outperforms traditional dataset-independent approaches and exhibits greater robustness compared with other deep-learning-based methods for shapes that infrequently appear in shape datasets.

X-ray CT scanners, due to the transmissive nature of X-rays, have enabled the non-destructive evaluation of industrial products, even inside their bodies. In light of its effectiveness, this study introduces a new approach to accelerate the inspection of many mechanical parts with the same shape in a bin. The input to this problem is a volumetric image (i.e., CT volume) of many parts obtained by a single CT scan. We need to segment the parts in the volume to inspect each of them; however, random postures and dense contacts of the parts prohibit part segmentation using traditional template matching. To address this problem, we convert both the scanned volumetric images of the template and the binned parts to simpler graph structures and solve a subgraph matching problem to segment the parts. We perform a distance transform to convert the CT volume into a distance field. Then, we construct a graph based on Morse theory, in which graph nodes are located at the extremum points of the distance field. The experimental evaluation demonstrates that our fully automatic approach can detect target parts appropriately, even for a heap of 50 parts. Moreover, the overall computation can be performed in approximately 30 min for a large CT volume of approximately 2000×2000×1000 voxels.

In industrial manufacturing, reverse engineering, which can be applied to analyze or re-design, is an essential process, whereby scanned data of real objects are used to generate a CAD model. CAD data have various features such as fillets; therefore, robust and versatile reverse engineering is still difficult. Particularly, an adequate segmentation from real scanned data is challenging, and it is a major obstacle for reverse engineering. In this study, we propose an innovative segmentation from CT scanned data, wherein user-friendly segmentation is achieved by directly computing the curvature gradient from a CT sinogram. We used the proposed method to patch a B-spline surface onto each segmented region. The experimental results show that the proposed method offers robust, versatile, and user-friendly reverse engineering that is faster than conventional manual modeling. In addition, as it is supported by X-ray CT simulation, the proposed method can be applied to various surface mesh data without requiring any actual X-ray CT equipment.

This study proposes a 3D CAD system available on smart devices, which are now a part of everyday life and which are widely applied in various domains, such as education and robot industry. If an engineer has a new idea while traveling or on the move, or in the case of collaboration between more than two engineers, this 3D CAD system allows modeling to be performed in a rapid and simple manner on a smart device. This 3D CAD system uses the common multi-touch gestures associated with smart devices to keep the modeling operations simple and easy for users. However, it is difficult to input the precise geometric information to generate 3D CAD models by such gestures. It is also impractical to provide a full set of modeling operations on a smart device due to hardware limitations. For this reason, the system excludes several complicated modeling operations. This work provides a scheme to regenerate a parametric 3D model on a PC-based CAD system via a macro-parametrics approach by transferring the 3D model created on a smart device in an editable form to a PC-based CAD system. If fine editing is needed, the user can perform additional work on a PC after reconstruction. Through the developed system, it is possible to produce a 3D editable model swiftly and simply in the smart device environment, allowing for reduced design time while also facilitating collaboration. This paper discusses the first-ever system design of a 3D CAD system on a smart device, the selection of the modeling operations, the assignment of gestures to these operations, and use of operation modes. This is followed by an introduction of the implementation methods, and finally a demonstration of case studies using a prototype system with examples.

This paper proposes a novel approach, the sinogram polygonizer, for directly reconstructing 3D shapes from sinograms (i.e., the primary output from X-ray computed tomography (CT) scanners consisting of projection image sequences of an object shown from different viewing angles). To obtain a polygon mesh approximating the surface of a scanned object, a grid-based isosurface polygonizer, such as Marching Cubes, has been conventionally applied to the CT volume reconstructed from a sinogram. In contrast, the proposed method treats CT values as a continuous function and directly extracts a triangle mesh based on tetrahedral mesh deformation. This deformation involves quadratic error metric minimization and optimal Delaunay triangulation for the generation of accurate, high-quality meshes. Thanks to the analytical gradient estimation of CT values, sharp features are well approximated, even though the generated mesh is very coarse. Moreover, this approach eliminates aliasing artifacts on triangle meshes.

In segmentation for reverse engineering, an input triangular mesh is usually split into segments for each of which a parametric surface is generated. The segment boundaries must be smooth for fine surfaces to be generated, but today's segmentation methods cannot necessarily generate a sufficient level of smoothness. The authors of this paper were inspired by the work reported in, and here try to extend it to efficiently segment a mesh obtained by scanning an object. Fuzzy boundary curves between two neighboring regions are globally rectified using a graph cut approach in which new energy functions are constructed. However, some curves are still not smooth since there are no straight lines around them in the original scanned mesh models, although the corresponding physical curves are smooth. To achieve further smoothing, we split some triangles by adding points and edges based on virtual triangle subdivision and the graph cut approach. As a result, significant further straightening of boundaries is achieved with simple straightest geodesics.

Abstract We developed an interactive system to design a customized cover for a given three‐dimensional (3D) object such as a camera, teapot, or car. The system first computes the convex hull of the input geometry. The user segments it into several cloth patches by drawing on the 3D surface. This paper provides two technical contributions. First, it introduces a specialized flattening algorithm for cover patches. It makes each two‐dimensional edge in the flattened pattern equal to or longer than the original 3D edge; a smaller patch would fail to cover the object, and a larger patch would result in extra wrinkles. Second, it introduces a mechanism to verify that the user‐specified opening would be large enough for the object to be removed. Starting with the initial configuration, the system virtually “pulls” the object out of the cover while avoiding excessive stretching of cloth patches. We used the system to design real covers and confirmed that it functions as intended.

Abstract We propose a novel method for smoothing partition of unity (PU) implicit surfaces consisting of sets of non‐conforming linear functions with spherical supports. We derive new discrete differential operators and Laplacian smoothing using a spherical covering of PU as a grid‐like data structure. These new differential operators are applied to the smoothing of PU implicit surfaces. First, Laplacian smoothing is performed for the vector field defined by the gradient of the PU implicit surface, which is then updated to reflect the smoothing of the gradient field. This process achieves a method for noise robust surface reconstruction from scattered points.

We introduce a method for extracting boundary surfaces from volumetric models of mechanical parts by X-ray CT scanning. When the volumetric model is composed of two materials, one for the object and the other for the background (Air), these boundary surfaces can be extracted as isosurfaces using a contouring method such as Marching Cubes [Lorensen and Cline 1987]. For a volumetric model composed of more than two materials, we need to classify the voxel types into segments by material and use a generalized Marching Cubes algorithm that can deal with both CT values and material types. Here we propose a method for precisely classifying the volumetric model into its component materials using a modified and combined method of two well-known algorithms in image segmentation, region growing and Graph-cut. We then apply the generalized Marching Cubes algorithm to generate triangulated mesh surfaces. In addition, we demonstrate the effectiveness of our method by constructing high-quality triangular mesh models of the segmented parts.

The skeletal structures of solid objects play an important role in medical and industrial applications. Given a volumetrically sampled solid object, our method extracts a nice-looking skeletal structure represented as a polygon mesh. The purpose is to achieve a noise-robust extraction of the skeletal mesh from a real-world object obtained using a scanning technology such as the CT scan method. We first approximate the input through a set of spherically supported polynomials that provide an adaptively smoothed intensity field, and then perform a polygonization process to find the extremal sheet of the field, which is regarded as a skeletal sheet in this research. In our polygonization, a subset of the weighted Delaunay tetrahedrization defined by a set of spherical supports is used as an adaptively sampled grid. The derivatives for detecting extremality are analytically evaluated at the tetrahedron vertices. We also demonstrate the effectiveness of our method by extracting skeletal meshes from noisy CT images.

Abstract A knitted animal is made of a closed surface consisting of several knitted patches knitted out of yarn and stuffed with cotton ( Fig. 1 ). We introduce a system to create a knitting pattern from a given 3D surface model (mainly designed for rotund animal models). A knitting pattern is an instructional diagram describing how to knit yarn to obtain a desired shape. Since the creation of knitting patterns requires special skill, this is difficult for nonprofessionals. Our system automates the process and allows anyone to obtain his or her original knitting patterns from a 3D model. The system first covers the surface of the model with parallel winding strips of constant width. The system then samples the strip at constant intervals to convert it into a knitting pattern. The result is presented in a standard visual format so that the user can easily refer it during actual knitting. We show several examples of knitted animals created using the system. Example of a knitted animal. A typical knitted animal consists of several circular and cylindrical patches. image

Summary form only given. X-ray CT (computed tomography) has experienced tremendous growth in industrial application in recent years, and acquiring information about the mechanical parts from CT data has been a great challenge for researchers. This paper presents a new method for the registration of a CT volumetric model of an assembly of parts with a CAD mesh model of a part of the assembly using ICP (iterative closest point) registration method. A few steps to extract feature points should be done as a preprocessing step of the volumetric model and the mesh model before applying the ICP registration algorithm, since the volumetric model and the mesh model are different in their data representation. This preprocessing step is important in order to unify the input of the ICP algorithm, and contributes to the robustness and the speed of the registration process.

This paper presents a method for computing distance fields from large volumetric models. Conventional methods have strict limits in terms of the amount of memory space available, as all volumetric models must be allocated to the random access memory (RAM) to compute distance fields. We resolve this problem through an out-of-core strategy. Our algorithm starts by decomposing volumetric models into small regions known as clusters, and distance fields are then computed by Local Distance Transform (LDT) and Inter-Cluster Propagation (ICP). LDT computes the distance transform for each cluster, and since it is independent, other clusters can also be saved to the storage medium. ICP propagates the distance at the boundary of the cluster to neighboring clusters to remove inconsistency in distance fields. In addition, we propose an efficient ordering algorithm based on the propagated distance to reduce LDT and ICP. This paper also demonstrates the results of distance transform from volumetric models with over a billion cells.

This paper describes a method for extracting surfaces from multi-material CT (computed tomography) data. Most contouring methods such as marching cubes algorithm assume that CT data are composed of only two materials. Some extended methods can extract surfaces from the multi-material (non-manifold) implicit representation. However, these methods are not directly applicable to CT data which are composed of three or more materials. There are two major problems that arise from fundamentals of CT. The first problem is that we have to use n(n - l)/2 threshold values for CT data contains n materials and select appropriately one threshold value for each boundary area. The second is that we cannot reconstruct only from CT data in which area three or more materials are adjacent each other. In this paper, we propose a method to solve the problems by using image analysis and demonstrate the effectiveness of the method with application examples construct polygon models from CT data of machine parts.

We propose “Attentive Workbench (AWB),” a new cell production system in which an intelligent system supports human workers. Using cameras, projectors, planar motor driven self-moving trays and other devices, the system supports workers from both physical and information aspects, recognizing worker’s condition and intention. This paper outlines AWB and deals with physical assembly support using self-moving parts trays. Two different schemes, centralized and decentralized, for controlling multiple parts trays are evaluated through experiments and simulations. The centralized control scheme is found to have the higher performance than the decentralized control scheme.

We have proposed "attentive workbench (AWB)", a new cell production system in which an intelligent system supports human workers. Recognizing worker's condition and intention, the system supports workers from both physical and information aspects. This paper deals with physical assembly support using self-moving parts trays. The system delivers necessary assembly parts to workers and clears finished products quickly. On transporting large products, multiple trays are subjected to form a rigid body working as a large single tray. In order to realize this arrangement of trays in real-time, a planning method based on the priority scheme and heuristic rule is proposed. The present method is evaluated through simulations. A demonstration of assembly support using real self-moving trays is shown.

An Origamic Architecture (OA) is a folded sheet of perforated paper from which a three-dimensional structure "pops up" when it is opened. It is similar to a "pop-up story book", but its unique feature is that it is made purely by cutting a single piece of paper. Because of this limitation, designing an OA requires considerable experience. We propose a computerised method which assists design of OAs. An OA is modelled using a set of planar polygons. This model must satisfy the conditions required of a valid, realisable OA. A unique point of our method is the application of Boolean set operations to the polygons on the unfolded pattern to guarantee that the model can be made from a single sheet of paper. We also present a procedure for checking the model's validity. Additionally, we propose methods for creating openings, for generating unfolded patterns, and for displaying folding animation. We have implemented a system based on these methods and demonstrated its usefulness for creating OA. Our system allows designers to intuitively design OA models and to easily generate the unfolded patterns.

As part of the goal of automatic creation of B-rep models of engineering objects from freehand sketches, we seek to take a single line drawing (with hidden lines removed), and from it deduce an initial 3D geometric realisation of the visible part of the drawn object. Junction and line labels, and provisional depth coordinates, are key parts of this frontal geometry. Many methods for producing frontal geometry only work correctly for drawings of trihedral objects. However, nontrihedral k-vertices commonly occur in engineering objects. We analyse the performance of a line-labelling method applied to k-vertices, and show why methods ignoring geometric considerations are inadequate. We give a new approach which produces both junction labels and provisional depth coordinates without any prior knowledge. Our results show that even a naive implementation outperforms previous methods.

In this paper we propose methodologies and algorithms of NC cutter path generation for subdivision surfaces. We select Loop surface as the subdivision surface. A path plan including rough cut and finish-cut is developed based on LoD (level of detail) property of the subdivision surface. We generate a coarse mesh that covers the limit surface to implement rough cut. For finish-cut we use ball-end mills and offset cutter contact positions to generate cutter location. In these two steps we use a Z-map model and a collision detection and correction method is presented for the interference-free of these two steps. We implement our methods and present machining results. All of these two kinds of cutter paths are computed rapidly and automatically.

This paper describes an algorithm for contouring a medial surface from CT (computed tomography) data of a thin plate structure. Thin plate structures are common in mechanical structures such as car body shells. When designing the thin plate structures in CAD (computer aided design) and CAE (computer aided engineering) systems, their shapes are usually represented as surface models associated with their thickness values. In this research we are aiming at extracting medial surface models of a thin plate structure from its CT data so as to be used in CAD and CAE systems. However, in such CT data, each voxel in region around the medial surface can not be classified inside or outside, so we can not easily apply iso-surfacing method to contour the medial surface. From the above motives, we first extract medial cells (cubes comprising eight neighboring voxels) from the CT data using a skeletonization method so as to apply marching cubes algorithm to extract the medial surface. It is not, however, guaranteed that the marching cubes algorithm can contour those medial cells (in short, not "marching cubeable"). We developed cell operations which correct topological connectivity so as to guarantee such marching cubeability. We then apply our method to assign virtual signs to the voxels to apply the marching cubes algorithm. And last, we map thicknesses of thin plate structure to the triangle meshes as textures. A prototype system is developed to show some experimental results.

This paper presents an algorithm for interactive character animation with kinematic constraints with limited computational time. In order to reduce necessary computation, the animation is not created by procedural algorithm but synthesized by deforming and concatenating short motion examples, each consisting of a sequence of postures. A keyframe placed between two consecutive motion examples is deformed by using inverse kinematics so that it satisfies given constraints. The motion examples between the keyframes are deformed to ensure continuity of postures in position and velocity. We parameterize each posture as a set of particles in an orthogonal coordinate system. The inverse kinematics method with the particle representation realizes fast and stable deformation of keyframe postures, and the deformation of motion examples are calculated on a frame-by-frame basis by decomposing a whole-body deformation into per-particle deformations. We present some examples of character animations synthesized at an interactive rate by this algorithm.

We propose a new method for producing unfolded papercraft patterns of rounded toy animal figures from triangulated meshes by means of strip-based approximation. Although in principle a triangulated model can be unfolded simply by retaining as much as possible of its connectivity while checking for intersecting triangles in the unfolded plane, creating a pattern with tens of thousands of triangles is unrealistic. Our approach is to approximate the mesh model by a set of continuous triangle strips with no internal vertices. Initially, we subdivide our mesh into parts corresponding to the features of the model. We segment each part into zonal regions, grouping triangles which are similar topological distances from the part boundary. We generate triangle strips by simplifying the mesh while retaining the borders of the zonal regions and additional cut-lines. The pattern is then created simply by unfolding the set of strips. The distinguishing feature of our method is that we approximate a mesh model by a set of continuous strips, not by other ruled surfaces such as parts of cones or cylinders. Thus, the approximated unfolded pattern can be generated using only mesh operations and a simple unfolding algorithm. Furthermore, a set of strips can be crafted just by bending the paper (without breaking edges) and can represent smooth features of the original mesh models.

A new algorithm is proposed for calculating the approximate shortest path on a polyhedral surface. The method mainly uses Dijkstra's algorithm and is based on selective refinement of the discrete graph of a polyhedron. Although the algorithm is an approximation, it has the significant advantages of being fast, easy to implement, high approximation accuracy, and numerically robust. The approximation accuracy and computation time are compared between this approximation algorithm and the extended Chen and Han (1990) (ECH) algorithm that can calculate the exact shortest path for non-convex polyhedra. The approximation algorithm can calculate shortest paths within 0.4% accuracy to roughly 100-1000 times faster than the ECH algorithm in our examples. Two applications are discussed of the approximation algorithm to geometric modeling.

An algorithm for calculating the minimum distance between non-convex polyhedra is described. A polyhedron is represented by a set of triangles. In calculating the distance between two polyhedra, it is important to search efficiently the pair of the triangles which gives the pair of closest points. In our algorithm discrete Voronoi regions are prepared as voxels around a non-convex polyhedron. Each voxel is given the list of triangles which have the possibility of being the closest to the points in the voxel. When a triangle on the other object is intersecting a voxel, the closest triangles can be efficiently searched from this list on the voxel. The algorithm has been implemented, and the results of distance computations show that it can calculate the minimum distance between non-convex polyhedra composed of a thousand triangles at interactive rates.

We present a general method for automatically reconstructing a network of B-spline patches based on the Doo-Sabin subdivision surface. This method consists of two parts, surface fitting and surface construction. In surface fitting, mesh simplification based on QEM (Quadric Error Metrics) is used and a control mesh that approximates a Doo-Sabin subdivision surface is constructed. In surface construction, we define a B-spline surface using a surface spline method; and a constructed network of B-spline patches is guaranteed G/sup 1/ continuous. In addition, this method has the advantage of enabling the user to select detail levels of the control mesh by utilizing a mesh simplification process.

The objective of this research is to apply the subdivision surface for surface fitting problems when generating surfaces from data points or polyhedral models. The basic idea is to use the subdivision limit position (SLP) to adapt the control mesh of the subdivision surface to the data points. This method is not a time consuming process involving global optimization. It does, however, fail to capture local characteristics of data points. Consequently, the proposed method is not suitable for generating a surface that precisely interpolates the data points, but it will be useful for quickly generating a surface that captures the overall shape constituted by the data points. A prototype system hers been developed to demonstrate several examples for purposes of evaluating the proposed method.

An algorithm for simulating a simultaneous collision impulse with friction working at multiple collision points between three dimensional rigid bodies is described. The authors also state that lasting collisions at small intervals will occur under some dynamic conditions and cause a decline in the simulation speed, and the method for avoiding this phenomenon is described.

We propose a 3D mesh dragging method useful for intuitive, efficient geometric modeling of free form polygonal models. With our method, the user can drag a part of a triangular mesh and change its position and orientation. This method is based on an adaptive remeshing procedure which evaluates the deformation of faces by dragging and properly modifies them by deleting or splitting with local topological operations. Therefore the mesh is automatically adjusted for dragging, and irregularity caused by dragging onto the mesh is no longer a concern. In addition, this method is local to the dragged portion, so its computation is efficient. We describe our adaptive remeshing method and demonstrate some dragging examples.

Recently, animations with deforming objects are frequently used in various computer graphics applications. Metamorphosis (or morphing) of three dimensional objects can realize a shape transformation between two or more existing objects. We present a new algorithm for 3D geometric metamorphosis between two objects based on the harmonic map. Our algorithm is applicable for arbitrary polyhedra that are homeomorphic to the three dimensional sphere or the two dimensional disk. In our algorithm, each of the two 3D objects is first embedded to the circular disk on the plane. This embedded model has the same graph structure as its 3D objects. By overlapping those two embedded models, we can establish a correspondence between the two objects. Using this correspondence, intermediate objects between two objects are easily generated. The user only specifies a boundary loop on an object and a vertex on that boundary which control the interpolation.