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.     

A review of deformable surfaces: topology, geometry and deformation

Deformable models have raised much interest and found various applications in the fields of computer vision and medical imaging. They provide an extensible framework to reconstruct shapes. Deformable surfaces, in particular, are used to represent 3D objects. They have been used for pattern recognition [Computer Vision and Image Understanding 69(2) (1998) 201; IEEE Transactions on Pattern Analysis and Machine Intelligence 19(10) (1997) 1115], computer animation [ACM Computer Graphics (SIGGRAPH'87) 21(4) (1987) 205], geometric modelling [61][Computer Aided Design (CAD) 24(4) (1992) 178], simulation [Visual Computer 16(8) (2000) 437], boundary tracking [ACM Computer Graphics (SIGGRAPH'94) (1994) 185], image segmentation [Computer Integrated Surgery, Technology and Clinical Applications (1996) 59; IEEE Transactions on Medical Imaging 14 (1995) 442; Joint Conference on Computer Vision, Virtual Reality and Robotics in Medicine (CVRMed-MRCAS'97) 1205 (1997) 13; Medical Image Computing and Computer-Assisted Intervention (MICCAI'99) 1679 (1999) 176; Medical Image Analysis 1(1) (1996) 19], etc. In this paper we propose a survey on deformable surfaces. Many surface representations have been proposed to meet different 3D reconstruction problem requirements. We classify the main representations proposed in the literature and we study the influence of the representation on the model evolution behavior, revealing some similarities between different approaches.     

Reconstructing Curves without Delaunay Computation

A new non-Delaunay-based approach is presented to reconstruct a curve, lying in 2- or 3-space, from a sampling of points. The underlying theory is based on bounding curvature to determine monotone pieces of the curve. Theoretical guarantees are established. The implemented algorithm, based heuristically on the theory, proceeds by iteratively partitioning the sample points using an octree data structure. The strengths of the approach are (a) simple implementation, (b) efficiency-experimental performance compares favorably with Delaunay-based algorithms, (c) robustness-curves with multiple components and sharp corners are reconstructed satisfactorily, and (d) potential extension to surface reconstruction.     

Surface Reconstruction Using Alpha Shapes

We describe a method for reconstructing an unknown surface from a set of data points. The basic approach is to extract the surface as a polygon mesh from an α-shape. Even though alpha shapes are generalized polytopes having complicated internal structures, we show that manifold surfaces, with or without boundaries, can be efficiently generated, and these surfaces completely describe the α-shapes to the extent that they are visible from outside. Unlike the original α-shapes, the polygonal surfaces can be easily simplified to yield compact models suitable for a variety of geometric modeling applications such as surface fitting.     

Order-k α-hulls and α-shapes

We introduce order-k α-hulls and α-shapes – generalizations of α-hulls and α-shapes. Being also a generalization of k-hull (known in statistics as “k-depth contour”), order-k α-hull provides a link between shape reconstruction and statistical depth. As a generalization of α-hull, order-k α-hull gives a robust shape estimation by ignoring locally up to k outliers in a point set. Order-k α-shape produces an “inner” shape of the set, with the amount of “digging” into the points controlled by k. As a generalization of k-hull, order-k α-hull is capable of determining “deep” points amidst samples from a multimodal distribution: it correctly identifies points which lie outside clusters of samples.The order-k α-hulls and α-shapes are related to order-k Voronoi diagrams in the same way in which α-hulls and α-shapes are related to Voronoi diagrams. This implies that order-k α-hull and α-shape can be readily built from order-k Voronoi diagram, and that the number of different order-k α-shapes for all possible values of α is proportional to the complexity of order-k Voronoi diagram.     

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.     

An application of algebraic topology to solid modeling in molecular biology

A recurring problem in solid modeling, computer graphics, and molecular modeling is the computation of the intersection of two objects. A general solution to this problem is obtained by applying two ideas of algebraic topology: (1) a chain complex, and (2) a boundary formula for the intersection of two objects. A general data structure for a chain complex made up of piecewise polynomial cells is described, as are algorithms for connectivity, containment and intersection. The basic ideas of this work are abstract, topological, and for the most part, independent of the shape and dimensionality of the objects. An application to structural molecular biology is presented. The application identifies convex and concave features of protein surfaces.     

On shape Delaunay tessellations

Shape Delaunay tessellations are a generalization of the classical Delaunay triangulation of a finite set of points in the plane, where the empty circle condition is replaced by emptiness of an arbitrary convex compact shape. We present some new and basic properties of shape Delaunay tessellations, concerning flipping, subgraph structures, and recognition.     

The slab dividing approach to solve the EuclideanP-Center problem

Givenn demand points on the plane, the EuclideanP-Center problem is to findP supply points, such that the longest distance between each demand point and its closest supply point is minimized. The time complexity of the most efficient algorithm, up to now, isO(n ² p–1· logn). In this paper, we present an algorithm with time complexityO(n ⁰(P)).     

The searching over separators strategy to solve some NP-hard problems in subexponential time

In this paper we propose a new strategy for designing algorithms, called the searching over separators strategy. Suppose that we have a problem where the divide-and-conquer strategy can not be applied directly. Yet, also suppose that in an optimal solution to this problem, there exists a separator which divides the input points into two parts,A _d andC _d, in such a way that after solving these two subproblems withA _d andC _d as inputs, respectively, we can merge the respective subsolutions into an optimal solution. Let us further assume that this problem is an optimization problem. In this case our searching over separators strategy will use a separator generator to generate all possible separators. For each separator, the problem is solved by the divide-and-conquer strategy. If the separator generator is guaranteed to generate the desired separator existing in an optimal solution, our searching over separators strategy will always produce an optimal solution. The performance of our approach will critically depend upon the performance of the separator generator. It will perform well if the total number of separators generated is relatively small. We apply this approach to solve the discrete EuclideanP-median problem (DEPM), the discrete EuclideanP-center problem (DEPC), the EuclideanP-center problem (EPC), and the Euclidean traveling salesperson problem (ETSP). We propose algorithms for the DEPM problem, the DEPC problem, and the EPC problem, and we propose an algorithm for the ETSP problem, wheren is the number of input points.This research work was partially supported by the National Science Council of the Republic of China under Grant NSC 79-0408-E007-04.     

The Minkowski sum of a simple polygon and a segment

We show that the Minkowski sum of a simple polygon with n edges and a segment has at most 2n−1 edges, and that this bound is tight in the worst case.     

A shape adaptive motion control system with application to robotic polishing

This paper presents a new shape adaptive motion control system that integrates part measurement with motion control. The proposed system consists of four blocks: surface measurement; surface reconstruction; tool trajectory planning; and axis motion control. The key technology used in surface measurement and surface reconstruction is the spatial spectral analysis. In the surface measurement block, a new spectral spectrum comparison method is proposed to determine an optimal digitizing frequency. In the surface reconstruction block, different interpolation methods are compared in the spatial spectral domain. A spatial spectral B-spline method is presented. In the tool trajectory planning block, a method is developed to select a motion profile first and then determine tool locations according to the reconstructed surface in order to improve the accuracy of the planned toolpath. Based on the proposed methods, a software package is developed and implemented on the polishing robot constructed at Ryerson University. The effectiveness of the proposed system has been demonstrated by the experiment on edge polishing. In this experiment, the shape of the part edges is measured first, and then constructed as a wire-frame CAD model, based on which the tool trajectory is planned to control the tool to polish the edges.     

Generation of configuration space obstacles: The case of moving algebraic curves

We present algebraic algorithms to generate the boundary of planar configuration space obstacles arising from the translatory motion of objects among obstacles. Both the boundaries of the objects and obstacles are given by segments of algebraic plane curves.Research supported in part by NSF Grant MIP-85-21356 and a David Ross Fellowship. An earlier version of this paper appeared in theProceedings of the 1987 IEEE International Conference on Robotics and Automation, pp. 979–984.     

The drawability problem for minimum weight triangulations

A graph is minimum weight drawable if it admits a straight-line drawing that is a minimum weight triangulation of the set of points representing the vertices of the graph. We study the problem of characterizing those graphs that are minimum weight drawable. Our contribution is twofold: We show that there exist infinitely many triangulations that are not minimum weight drawable. Furthermore, we present non-trivial classes of triangulations that are minimum weight drawable, along with corresponding linear time algorithms that take as input any graph from one of these classes and produce as output such a drawing. One consequence of our work is the construction of triangulations that are minimum weight drawable but not Delaunay drawable – that is, not drawable as a Delaunay triangulation.     

Coverage and connectivity issues in wireless sensor networks: A survey

Sensing coverage and network connectivity are two of the most fundamental problems in wireless sensor networks. Finding an optimal node deployment strategy that would minimize cost, reduce computation and communication overhead, be resilient to node failures, and provide a high degree of coverage with network connectivity is extremely challenging. Coverage and connectivity together can be treated as a measure of quality of service in a sensor network; it tells us how well each point in the region is covered and how accurate is the information gathered by the nodes. Therefore, maximizing coverage as well as maintaining network connectivity using the resource constrained nodes is a non-trivial problem. In this survey article, we present and compare several state-of-the-art algorithms and techniques that aim to address this coverage–connectivity issue.     

Boolean operations for 3D simulation of CNC machining of drilling tools

This paper addresses the simulation of drilling tools CNC machining. It describes a novel approach for the computation of the boundary representation of the machined tools. Machining consists of a sequence of boolean operations of difference between the tool and the grinding wheels through time. The proposed method performs the dynamic boolean operations on cross sections of the tool and it reconstructs the 3Dmodel by tiling between the cross sections. The method is based on classical computational geometry algorithms such as intersection tests, hull computations, 2D boolean operations and surface tiling. This approach is efficient and it provides user control on the resolution of the operations.     

Settling the bound on the rectilinear link radius of a simple rectilinear polygon

We improve the best known bound on the rectilinear link radius of a simple rectilinear polygon with respect to its rectilinear link diameter. The new bound is tight and is compatible with the known bound on the (regular) link radius of a (regular) simple polygon with respect to its (regular) link diameter. The previous bound on the rectilinear link radius of a simple rectilinear polygon was proven by Nilsson and Schuierer in 1991.