No abstract uploaded!

3-D CAD models are an important digital resource in the manufacturing industry. 3-D CAD model retrieval has become a key technology in product lifecycle management enabling the reuse of existing design data. In this paper, we propose a new method to retrieve 3-D CAD models based on 2-D pen-based sketch inputs. Sketching is a common and convenient method for communicating design intent during early stages of product design, e.g., conceptual design. However, converting sketched information into precise 3-D engineering models is cumbersome, and much of this effort can be avoided by reuse of existing data. To achieve this purpose, we present a user-adaptive sketch-based retrieval method in this paper. The contributions of this work are twofold. First, we propose a statistical measure for CAD model retrieval: the measure is based on sketch similarity and accounts for users’ drawing habits. Second, for 3-D CAD models in the database, we propose a sketch generation pipeline that represents each 3-D CAD model by a small yet sufficient set of sketches that are perceptually similar to human drawings. User studies and experiments that demonstrate the effectiveness of the proposed method in the design process are presented.

The huge number of points scanned from pipeline plants make the plant reconstruction very difficult. Traditional cylinder detection methods cannot be applied directly due to the high computational complexity. In this paper, we explore the structural characteristics of point cloud in pipeline plants and define a structure feature. Based on the structure feature, we propose a hierarchical structure detection and decomposition method that reduces the difficult pipeline-plant reconstruction problem in IR3 into a set of simple circle detection problems in IR2. Experiments with industrial applications are presented, which demonstrate the efficiency of the proposed structure detection method.

We present an evolution method for designing the styling curves of garments. The procedure of evolution is driven by aesthetics-inspired scores to evaluate the quality of styling designs, where the aesthetic considerations are represented in the form of streamlines on human bodies. A dual representation is introduced in our platform to process the styling curves of designs, based on which robust methods for realizing the operations of evolution are developed. Starting from a given set of styling designs on human bodies, we demonstrate the effectiveness of set evolution inspired by aesthetic factors. The evolution is adaptive to the change of aesthetic inspirations. By this adaptation, our platform can automatically generate new designs fulfilling the demands of variations in different human bodies and poses.

In this paper, we investigate how to topologically and geometrically characterize the intersection relations between a movable convex polygon and a set  of possibly overlapping polygons fixed in the plane. More specifically, a subset   is called an intersection relation if there exists a placement of that intersects, and only intersects, . The objective of this paper is to design an efficient algorithm that finds a finite and discrete representation of all of the intersection relations between and . Past related research only focuses on the complexity of the free space of the configuration space between and  and how to move or place an object in this free space. However, there are many applications that require the knowledge of not only the free space, but also the intersection relations. Examples are presented to demonstrate the rich applications of the formulated problem on intersection relations.

In this paper, we consider the problem of approximating the longest path in a grid graph that possesses a square-free 2-factor. By (1) analyzing several characteristics of four types of cross cells and (2) presenting three cycle-merging operations and one extension operation, we propose an algorithm that finds in an n-vertex grid graph G, a long path of length at least 5/6 n + 2. Our approximation algorithm runs in quadratic time. In addition to its theoretical value, our work has also an interesting application in image-guided maze generation.

In the research of computer vision and machine perception, 3D objects are usually represented by 2-manifold triangular meshes M. In this paper, we present practical and efficient algorithms to construct iso-contours, bisectors, and Voronoi diagrams of point sites onM, based on an exact geodesic metric. Compared to euclidean metric spaces, the Voronoi diagrams onMexhibit many special properties that fail all of the existing euclidean Voronoi algorithms. To provide practical algorithms for constructing geodesicmetric- based Voronoi diagrams onM, this paper studies the analytic structure of iso-contours, bisectors, and Voronoi diagrams onM. After a necessary preprocessing of model M, practical algorithms are proposed for quickly obtaining full information about iso-contours, bisectors, and Voronoi diagrams on M. The complexity of the construction algorithms is also analyzed. Finally, three interesting applications—surface sampling and reconstruction, 3D skeleton extraction, and point pattern analysis—are presented that show the potential power of the proposed algorithms in pattern analysis.

We study the combinatorial complexity of Voronoi diagram of point sites on a general triangulated 2-manifold surface, based on the geodesic metric. Given a triangulated 2- manifold T of n faces and a set of m point sites S = {s1, s2, . . . , sm} ∈ T, we prove that the complexity of Voronoi diagram VT (S) of S on T is O(mn) if the genus of T is zero. For a genus-g manifold T in which the samples in S are dense enough and the resulting Voronoi diagram satisfies the closed ball property, we prove that the complexity of Voronoi diagram VT (S) is O((m + g)n).

A natural metric in 2-manifold surfaces is to use geodesic distance. If a 2-manifold surface is represented by a triangle mesh T , the geodesic metric on T can be computed exactly using computational geometry methods. Previous work for establishing the geodesic metric on T only supports using half-edge data structures; i.e., each edge e in T is split into two halves (he1, he2) and each half-edge corresponds to one of two faces incident to e. In this paper, we prove that the exact-geodesic structures on two halfedges of e can be merged into one structure associated with e. Four merits are achieved based on the properties which are studied in this paper: (1) Existing CAD systems that use edge-based data structures can directly add the geodesic distance function without changing the kernel to a half-edge data structure; (2) To find the geodesic path from inquiry points to the source, the MMP algorithm can be run in an onthe- fly fashion such that the inquiry points are covered by correct wedges; (3) The MMP algorithm is sped up by pruning unnecessary wedges during the wedge propagation process; (4) The storage of the MMP algorithm is reduced since fewer wedges need to be stored in an edge-based data structure. Experimental results show that when compared to the classic half-edge data structure, the edge-based implementation of the MMP algorithm reduces running time by 44% and storage by 29% on average.

This paper studies the Voronoi diagrams on 2-manifold meshes based on geodesic metric (a.k.a. geodesic Voronoi diagrams or GVDs), which have polyline generators. We show that our general setting leads to situations more complicated than conventional 2D Euclidean Voronoi diagrams as well as point-source based GVDs, since a typical bisector contains line segments, hyperbolic segments and parabolic segments. To tackle this challenge, we introduce a new concept, called local Voronoi diagram (LVD), which is a combination of additively weighted Voronoi diagram and line-segment Voronoi diagram on a mesh triangle. We show that when restricting on a single mesh triangle, the GVD is a subset of the LVD and only two types of mesh triangles can contain GVD edges. Based on these results, we propose an efficient algorithm for constructing the GVD with polyline generators. Our algorithm runs in O(nNlogN) time and takes O(nN) space on an n-face mesh with m generators, where N = max{m,n}. Computational results on real-world models demonstrate the efficiency of our algorithm.