Primitive-based segmentation for triangulated surfaces

Sacchi, R., 2001. Primitive-based segmentation for triangulated surfaces. PhD, Nottingham Trent University.

10183399.pdf - Published version

Download (33MB) | Preview


Numerous fields of applications require a digital model to be produced from a physical object, for example in computer-aided design of appliance casings, manufacture of engineering components and virtual reality. A digital description allows changes in design and manipulation of the data, where it would be, for example, too expensive, too dangerous, or too time-consuming to do the same in the physical world. In order to obtain data from the physical object, coordinate measuring devices record data either by contact-less or by contact measurement, and in many cases the result yields an unstructured point cloud. Before the surface of a digitised object can be manipulated interactively, it must be reconstructed from the (possibly unstructured) set of points. With structured points the generation of a triangulated surface is relatively straightforward. To generate an initial triangulated surface out of the unstructured point cloud sophisticated methods have been established. The present project aims to achieve the next important step in surface reconstruction, namely to segment the triangulated surface into parts of simple geometric primitives, in particular of the following: plane, sphere, cylinder, cone, and torus. Such segmentation enables engineers to manipulate data for design purposes more quickly, because connected point sets, rather than individual points, will be affected. Subsequently the data can be used for "rapid prototyping", i.e. the manufacture of a physical model from a digital description.

In order to obtain a segmentation of a triangulated surface the approach for the extraction of geometric primitives used in this project has been based on a "region growing" method. It attempts to grow small initial seed regions satisfying a "homogeneous shape" criterion within a given tolerance. Each time the growing process yields a sufficiently large connected set of triangles a new segment of a geometric primitive with its corresponding characteristic parameters and boundary curves is identified. An additional source of shape information about triangulated surfaces is an estimate of curvature for each triangle. Curvature information allows the selection of appropriate seed regions, and it allows good initial estimates of characteristic parameters to be found. This is important because the growing process under preservation of shape involves numerical optimisation, whereby the initial f characteristic parameters are adjusted as the region grows.

Methods of curvature estimation for triangulated surfaces have been investigated. Curvature estimation algorithms for triangulated surfaces have been developed and evaluated for both synthetic data (for which curvature values are known) and "real" data. They compare favourably with other curvature estimation algorithms suitable for discrete data. A formula for the sign of curvature has been found in the literature to give sometimes a wrong result and an appropriate correction has been suggested.

Algorithms for region growing have been established which are based on the curvature estimates obtained. Techniques have been developed for determination of initial characteristic parameters for planes, spheres, cylinders, cones, and tori using the estimated curvature, when only very small seed regions are available. Further work has established how characteristic parameters of segments of geometric primitives can be adjusted by region growing formulated as a minimax optimisation problem.

A fast method for the extraction of planar patches on a triangulated surface has been developed which is faster than the numerical approaches needed for the more complicated geometric primitives. This extraction employs a new, simple geometric method that exploits the asymptotic behaviour of an "expanded triangle" used to represent the plane. This method cannot only be applied to triangulated surfaces but also to any data representation that provides adjacency information. Results from the extraction involving all types of the above geometric primitives have been evaluated on "real" data. For many simple objects successful segmentation has been achieved and it is expected that further refinement of the developed algorithms will enhance their performance.

Item Type: Thesis
Creators: Sacchi, R.
Date: 2001
ISBN: 9781369316049
Divisions: Schools > School of Science and Technology
Record created by: Linda Sullivan
Date Added: 24 Sep 2020 15:39
Last Modified: 16 Aug 2023 11:09

Actions (login required)

Edit View Edit View


Views per month over past year


Downloads per month over past year