A key function of polygonal modeling is the conversion of polygonal models to B-Rep. The C3D PolyShaper polygonal kernel can fit analytical surfaces such as a plane, cylinder, sphere, cone, or torus into a set of polygons. Recently we added the recognition of surfaces of revolution and extrusion. Let me tell you how we achieved this.
Fig. 1. Fitting a surface of extrusion
The problem is stated as follows: For a given polygonal mesh, we need to construct a surface that best fits the mesh. A sweep surface is defined by two objects: an axis of revolution or extrusion path and a plane curve, the generatrix. For a surface of revolution, the generatrix lies in the half-plane passing through the axis and extends to one side from the axis. For a surface of extrusion, it lies in a plane perpendicular to the trajectory. We will call such a plane a working plane.
First, we estimate the parameters of the sweep surface components: the axis of revolution, and the extrusion trajectory. We can obtain these parameters by analyzing the curvature or kinematic properties of the polygonal object. To compare the axes identified through different methods, we define a mismatch error. It is the total area of all polygons projected on the working plane. We select the axis with the smaller error.
When we know the parameters of the sweep surface, we can project the points of the original polygonal object onto the working plane and build a minimal spanning tree that passes through all vertices of the graph. For this, we first create a dense graph in which each vertex is connected by edges to a certain number of nearby vertices. If the number is too large, the computational cost of subsequent edge sorting would be too high. If the number is too small, the graph is more likely to become disconnected. Lack of connectivity is the lesser of two evils. Therefore, we first consider a small number of nearest neighbors and apply an iterative procedure to connect individual components into a spanning tree while increasing the number of nearest neighbors. To limit the runtime, we introduce a threshold of the maximum number of graph vertices. If there are more points in the initial mesh, the graph is created from a representative region of the mesh.
To construct the generatrix, we identify the path between the most distant vertices of the spanning tree. If this path passes through all the graph vertices, the final spline will also pass through all the points of the trajectory. If the tree has multiple branches, the generatrix is an approximation of the path identified in the tree. All the path points are used for the approximation. The figure shows a fragment of a spanning tree (edges are red) and a generatrix (blue).
Fig. 2. Spanning tree and generatrix
The FitSurfaceToGrid() function fits surfaces. The st_RevolutionSurface and st_ExtrusionSurface type values of MbSurfaceFitToGridParameters define whether a surface of revolution or extrusion is fitted. You can also specify the accuracy using the _tolerance value.
Fitting a surface of revolution. A C3D PolyShaper API call example:
const MbGrid * pGrid( nullptr ); // … const double tolerance = 0.001; const MbSurfaceFitToGridParameters params( st_RevolutionSurface, tolerance, {} ); MbSurfaceFitToGridResults results; FitSurfaceToGrid( *pGrid, params, results );
Fig. 3. Fitting a surface of revolution
The recognition of surfaces of revolution and extrusion is another addition to the reverse engineering features of C3D PolyShaper. With the new commands, developers will find it easier to convert scanned 3D models into B-Rep.
Pavel Starikov
Mathematican & Software developer, Polygonal modeling team
C3D Labs
