Analysis of quadric-surface-based solid models

The author discusses data representations and analytical tools commonly used in solid modelers for three analysis operations: boundary evaluation, image generation, and mechanical property calculation. The methods described are generally applicable to solid models bounded by quadric surfaces (e.g. planes, cylinders, spheres, and cones). Only methods applicable to constructive solid geometry or boundary representation modelers are considered. The author concludes with a review of ongoing research into other analysis operations appropriate for solid modeling representations     

Implementation of two hidden-line algorithms

Two hidden-line elimination programs are described. One removes the hidden lines from vector-type projections of planar-faced 3D objects. This program implements the Loutrel algorithm which has been extended here to solids with multiply-connected faces. The other is applicable to solids bounded by sections of quadric surfaces (i.e. cylinders, cones, spheres, ellipsoids, paraboloids and hyperboloids) and represents an implementation of the Woon algorithm. The latter can be regarded as an extension of the Loutrel algorithm to curved-surface bodies. Both programs generate true, visible-line perspective projections for output on a digital plotter or a vector-type CRT display. The implementation of these algorithms for a variety of computer systems is described.     

Medical image segmentation, volume representation and registration using spheres in the geometric algebra framework

This paper presents an algorithm to model volumetric data and other one for non-rigid registration of such models using spheres formulated in the geometric algebra framework. The proposed algorithm for modeling, as opposite to the Union of Spheres method, reduces the number of entities (spheres) used to model 3D data. Our proposal is based in marching cubes idea using, however, spheres, while the Union of Spheres uses Delaunay tetrahedrization. The non-rigid registration is accomplished in a deterministic annealing scheme. At the preprocessing stage we segment the objects of interest by a segmentation method based on texture information. This method is embedded in a region growing scheme. As our final application, we present a scheme for surgical object tracking using again geometric algebra techniques.     

Applying geometric constraints for perfecting CAD models in reverse engineering

An important area of reverse engineering is to produce digital models of mechanical parts from measured data points. In this process inaccuracies may occur due to noise and the numerical nature of the algorithms, such as, aligning point clouds, mesh processing, segmentation and surface fitting. As a consequence, faces will not be precisely parallel or orthogonal, smooth connections may be of poor quality, axes of concentric cylinders may be slightly tilted, and so on. In this paper we present algorithms to eliminate these inaccuracies and create “perfected” B-rep models suitable for downstream CAD/CAM applications.Using a segmented and classified set of smooth surface regions we enforce various constraints for automatically selected groups of surfaces. We extend a formerly published technology of Benkő et al. (2002). It is an essential element of our approach, however, that we do not know in advance the set of surfaces that will actually get involved in the final constrained fitting. We propose local methods to select and synchronize “likely” geometric constraints, detected between pairs of entities. We also propose global methods to determine constraints related to the whole object, although the best-fit coordinate systems, reference grids and symmetry planes will be determined only by surface entities qualified as relevant. Lots of examples illustrate how these constrained fitting algorithms improve the quality of reconstructed objects.     

Inverse Displacement Mapping

Inverse displacement mapping is a variant of displacement mapping which does not actually perturb the geometry of the surface being mapped. It is thus a true texture mapping technique which can be applied during rendering without breaking viewing pipeline discipline. The method works by first projecting probing rays into texture space and solving for a ray-texture intersection there. Shadows can also be determined by mapping a probe from the intersection point towards the light source into texture space and seeing if an intersection results. Our implementation uses as much knowledge about the base surface as possible to speed up the ray-surface intersection calculation. We have limited our treatment to spheres, cones, cylinders and planes, and our rendering method to ray casting, in order to contain the scope of this work up to the present. The inverse displacement mapping technique can, however, be applied more widely, for example as part of a full ray-tracer, and also as part of the rendering pipeline for a wider class of smooth surfaces.     

Mesh Parametrization Driven by Unit Normal Flow

Based on mesh deformation, we present a unified mesh parametrization algorithm for both planar and spherical domains. Our approach can produce intermediate frames from the original meshes to the targets. We derive and define a novel geometric flow: ‘unit normal flow (UNF)’ and prove that if UNF converges, it will deform a surface to a constant mean curvature (CMC) surface, such as planes and spheres. Our method works by deforming meshes of disk topology to planes, and spherical meshes to spheres. Our algorithm is robust, efficient, simple to implement. To demonstrate the robustness and effectiveness of our method, we apply it to hundreds of models of varying complexities. Our experiments show that our algorithm can be a competing alternative approach to other state-of-the-art mesh parametrization methods. The unit normal flow also suggests a potential direction for creating CMC surfaces.     

Computing non-self-intersecting offsets of NURBS surfaces

A new approach for the computation of non-self-intersecting offset surface of a single G₁ continuous NURBS surface has been presented. The approach recognizes special surfaces, i.e. planes, spheres, cones and cylinders, and offsets them precisely. An approximate offset surface within the specified tolerance is computed for a general free form surface. The method for a general free form surface consists of (1) sample offset surface based on second derivatives; (2) eliminate sample points which can give self-intersections; (3) surface fitting through the remaining sample points; and (4) removal of all the removable knots of the surface. The approach checks for self-intersections in the offset surface and removes the same automatically, if any. The non-self-intersecting offsets for surface of extrusion and surface of revolution are obtained by removing the self-intersections in the offset generator and profile curves respectively using point sampling, cleaning of sampled points, curve fitting and knot removal. The approach has better control on error. It generates offset surface with less number of control points and degree. The methodology works only for a class of problems where in the offset of a single G₁ surface is still a single connected surface without having any holes. The offset methodology has been demonstrated through three types of surfaces namely surface of revolution, surface of extrusion and a general free form surface. This approach has been extensively used in creation of offset surfaces of composite laminate components. The presented approach can also be used to check for self-intersections in any general surface and to remove the same, if any, with little modifications, as long as the cleaned surface is a single connected surface.     

Energy-based multi-view piecewise planar stereo

The piecewise planar model (PPM) is an effective means of approximating a complex scene by using planar patches to give a complete interpretation of the spatial points reconstructed from projected 2D images. The traditional piecewise planar stereo methods suffer from either a very restricted number of directions for plane detection or heavy reliance on the segmentation accuracy of superpixels. To address these issues, we propose a new multi-view piecewise planar stereo method in this paper. Our method formulates the problem of complete scene reconstruction as a multi-level energy minimization problem. To detect planes along principal directions, a novel energy formulation with pair-wise potentials is used to assign an optimal plane for each superpixel in an iterative manner, where reliable scene priors and geometric constraints are incorporated to enhance the modeling efficacy and inference efficiency. To detect non-principal-direction planes, we adopt a multi-direction plane sweeping with a restricted search space method to generate reliable candidate planes. To handle the multi-surface straddling problem of a single superpixel, a superpixel sub-segmenting scheme is proposed and a robust Pⁿ Potts model-like higher-order potential is introduced to refine the resulting depth map. Our method is a natural integration of pixel- and superpixel-level multi-view stereos under a unified energy minimization framework. Experimental results for standard data sets and our own data sets show that our proposed method can satisfactorily handle many challenging factors (e.g., slanted surfaces and poorly textured regions) and can obtain accurate piecewise planar depth maps.     

A random sampling strategy for piecewise planar scene segmentation

We investigate the problem of automatically creating 3D models of man-made environments that we represent as collections of textured planes. A typical approach is to automatically reconstruct a sparse 3D model made of points, and to manually indicate their plane membership, as well as the delineation of the planes: this is the piecewise planar segmentation phase. Texture images are then extracted by merging perspectively corrected input images. We propose an automatic approach to the piecewise planar segmentation phase, that detects the number of planes to approximate the scene surface to some extent, and the parameters of these planes, from a sparse 3D model made of points. Our segmentation method is inspired from the robust estimator ransac. It generates and scores plane hypotheses by random sampling of the 3D points. Our plane scoring function and our plane comparison function, required to prevent detecting the same plane twice, are designed to detect planes with large or small support. The plane scoring function recovers the plane delineation and quantifies the saliency of the plane hypothesis based on approximate photoconsistency. We finally refine all the 3D model parameters, i.e., the planes and the points on these planes, as well as camera pose, by minimizing the reprojection error with respect to the measured image points, using bundle adjustment. The approach is validated on simulated and real data.     

Recognizing 3D Objects Using Tactile Sensing and Curve Invariants

A general paradigm for recognizing 3D objects is offered, and applied to some geometric primitives (spheres, cylinders, cones, and tori). The assumption is that a curve on the surface, or a pair of intersecting curves, was measured with high accuracy (for instance, by a sensory robot). Differential invariants of the curve(s) are then used to recognize the surface. The motivation is twofold: the output of some devices is not surface range data, but such curves. Also, a considerable speedup is obtained by using curve data, as opposed to surface data which usually contains a much higher number of points.We survey global, algebraic methods for recognizing surfaces, and point out their limitations. After introducing some notions from differential geometry and elimination theory, the differential and semi-differential approaches to the problem are described, and novel invariants which are based on the curve's curvature and torsion are derived.     

Thin Structures in Image Based Rendering

We propose a novel method to handle thin structures in Image‐Based Rendering (IBR), and specifically structures supported by simple geometric shapes such as planes, cylinders, etc. These structures, e.g. railings, fences, oven grills etc, are present in many man‐made environments and are extremely challenging for multi‐view 3D reconstruction, representing a major limitation of existing IBR methods. Our key insight is to exploit multi‐view information. After a handful of user clicks to specify the supporting geometry, we compute multi‐view and multi‐layer alpha mattes to extract the thin structures. We use two multi‐view terms in a graph‐cut segmentation, the first based on multi‐view foreground color prediction and the second ensuring multiview consistency of labels. Occlusion of the background can challenge reprojection error calculation and we use multiview median images and variance, with multiple layers of thin structures. Our end‐to‐end solution uses the multi‐layer segmentation to create per‐view mattes and the median colors and variance to create a clean background. We introduce a new multi‐pass IBR algorithm based on depth‐peeling to allow free‐viewpoint navigation of multi‐layer semi‐transparent thin structures. Our results show significant improvement in rendering quality for thin structures compared to previous image‐based rendering solutions.     

Efficient RANSAC for Point-Cloud Shape Detection

In this paper we present an automatic algorithm to detect basic shapes in unorganized point clouds. The algorithm decomposes the point cloud into a concise, hybrid structure of inherent shapes and a set of remaining points. Each detected shape serves as a proxy for a set of corresponding points. Our method is based on random sampling and detects planes, spheres, cylinders, cones and tori. For models with surfaces composed of these basic shapes only, for example, CAD models, we automatically obtain a representation solely consisting of shape proxies. We demonstrate that the algorithm is robust even in the presence of many outliers and a high degree of noise. The proposed method scales well with respect to the size of the input point cloud and the number and size of the shapes within the data. Even point sets with several millions of samples are robustly decomposed within less than a minute. Moreover, the algorithm is conceptually simple and easy to implement. Application areas include measurement of physical parameters, scan registration, surface compression, hybrid rendering, shape classification, meshing, simplification, approximation and reverse engineering.     

The Use of Geometric Algebra for 3D Modeling and Registration of Medical Data

We present a new approach to model 2D surfaces and 3D volumetric data, as well as an approach for non-rigid registration; both are developed in the geometric algebra framework. The approach for modeling is based on marching cubes idea using however spheres and their representation in the conformal geometric algebra; it will be called marching spheres. Note that before we can proceed with the modeling, it is needed to segment the object we are interested in; therefore, we include an approach for image segmentation, which is based on texture and border information, developed in a region-growing strategy. We compare the results obtained with our modeling approach against the results obtained with other approach using Delaunay tetrahedrization, and our proposed approach reduces considerably the number of spheres. Afterward, a method for non-rigid registration of models based on spheres is presented. Registration is done in an annealing scheme, as in Thin-Plate Spline Robust Point Matching (TPS-RPM) algorithm. As a final application of geometric algebra, we track in real time objects involved in surgical procedures.

A Scanline Method for Solid Model Display

The modelling of solid objects is becoming increasingly important in the application of computer graphics to a wide variety of problems, such as CAD/CAM, simulation, and molecular modelling. A variety of methods for rendering solid objects exists, including 2-Buffer, Scanline and Ray Tracing. This paper is concerned with a scanline method for the production of still images of complex objects. The implementation of a scanline algorithm is discussed, in conjunction with a consideration of its performance in relation to the z-buffer method.
Many scanline methods cater only for a restricted class of primitives, such as polygons or spheres, whereas this implementation is a general purpose scanline algorithm capable of being extended to handle a variety of primitives. The primitives currently available are polygons, spheres, spheres swept along straight-line trajectories, and cylinders. Polygonal models of cubes, cones and cylinders are also available.
The approach is capable of dealing with "positive" and "negative" volumes, allowing objects with holes to be modelled and displayed. It has further been extended to cater for the inclusion of transparent objects into a scene, and consequently allows the modelling of coloured "glass" objects.     

Constrained 3D shape reconstruction using a combination of surface fitting and registration

We investigate 3D shape reconstruction from measurement data in the presence of constraints. The constraints may fix the surface type or set geometric relations between parts of an object's surface, such as orthogonality, parallelity and others. It is proposed to use a combination of surface fitting and registration within the geometric optimization framework of squared distance minimization (SDM). In this way, we obtain a quasi-Newton like optimization algorithm, which in each iteration simultaneously registers the data set with a rigid motion to the fitting surface and adapts the shape of the fitting surface. We present examples to show the applicability of our method to constrained 3D shape fitting for reverse engineering of CAD models and to high accuracy fitting with kinematic surfaces, which include surfaces of revolution (reconstructed from fragments of archeological pottery) and spiral surfaces, which are fitted to 3D measurement data of shells. Our optimization algorithm can combine registration of multiple scans of an object and model fitting into a single optimization process which is shown to be superior to the traditional procedure, which first registers the data and then fits a model to it.     

Area-wide roof plane segmentation in airborne LiDAR point clouds

Most algorithms performing segmentation of 3D point cloud data acquired by, e.g. Airborne Laser Scanning (ALS) systems are not suitable for large study areas because the huge amount of point cloud data cannot be processed in the computer’s main memory. In this study a new workflow for seamless automated roof plane detection from ALS data is presented and applied to a large study area. The design of the workflow allows area-wide segmentation of roof planes on common computer hardware but leaves the option open to be combined with distributed computing (e.g. cluster and grid environments). The workflow that is fully implemented in a Geographical Information System (GIS) uses the geometrical information of the 3D point cloud and involves four major steps: (i) The whole dataset is divided into several overlapping subareas, i.e. tiles. (ii) A raster based candidate region detection algorithm is performed for each tile that identifies potential areas containing buildings. (iii) The resulting building candidate regions of all tiles are merged and those areas overlapping one another from adjacent tiles are united to a single building area. (iv) Finally, three dimensional roof planes are extracted from the building candidate regions and each region is treated separately. The presented workflow reduces the data volume of the point cloud that has to be analyzed significantly and leads to the main advantage that seamless area-wide point cloud based segmentation can be performed without requiring a computationally intensive algorithm detecting and combining segments being part of several subareas (i.e. processing tiles). A reduction of 85% of the input data volume for point cloud segmentation in the presented study area could be achieved, which directly decreases computation time.     

Parametric Surface Representation with Bump Image for Dense 3D Modeling Using an RBG-D Camera

When constructing a dense 3D model of an indoor static scene from a sequence of RGB-D images, the choice of the 3D representation (e.g. 3D mesh, cloud of points or implicit function) is of crucial importance. In the last few years, the volumetric truncated signed distance function (TSDF) and its extensions have become popular in the community and largely used for the task of dense 3D modelling using RGB-D sensors. However, as this representation is voxel based, it offers few possibilities for manipulating and/or editing the constructed 3D model, which limits its applicability. In particular, the amount of data required to maintain the volumetric TSDF rapidly becomes huge which limits possibilities for portability. Moreover, simplifications (such as mesh extraction and surface simplification) significantly reduce the accuracy of the 3D model (especially in the color space), and editing the 3D model is difficult. We propose a novel compact, flexible and accurate 3D surface representation based on parametric surface patches augmented by geometric and color texture images. Simple parametric shapes such as planes are roughly fitted to the input depth images, and the deviations of the 3D measurements to the fitted parametric surfaces are fused into a geometric texture image (called the Bump image). A confidence and color texture image are also built. Our 3D scene representation is accurate yet memory efficient. Moreover, updating or editing the 3D model becomes trivial since it is reduced to manipulating 2D images. Our experimental results demonstrate the advantages of our proposed 3D representation through a concrete indoor scene reconstruction application.