Lofting/Skinning/Surface Reconstruction

Introduction
Lofting (also called skinning and surface reconstruction) can be an essential algorithm when doing geometric modeling, terrain building, and segmentation (medical imaging.) This project involves developing a permutation of the algorithm which will be useful as a geometric modeling tool. Permutations for terrain and surface reconstruction will not be addressed in this project.

In the past, I have developed a few lofting algorithms. One of which ships in Designer's Workbench. A friend would like a lofting tool for his real-time geometric modeler package, and I have decided to look into the algorithm once again.

The concept of lofting is simply connecting two polygonal contours together with a triangular mesh, producing a surface. For the basic cases, it is extremely simple. Extreme differences in the size of geometry, and orientation can begin to complicate the matter. Then branching in geometry and holes can increase the complexity.

Lofting can be used to create complicated objects projected along paths with varying cross sections. Extruding along a path is an extremely simple case of lofting along it. Lofting can also be used to produce surfaces of revolution where the silhouette changes during the revolution.

A triangular mesh (blue) generated by lofting between two circles (red) of 16 and 32 vertices.

For this project, we will deal only with the non-branching version of lofting. Why? The purpose of this tool is for geometric modeling. The algorithms for lofting which support branching are not as flexible when it comes to non-parallel contours. Branching also isn't as much of an issue in this domain as it is in surface reconstruction.

Basic Non-Branching Algorithm
There are probably an infinite number of ways to do the basic lofting algorithm. The end goal typically can steer what ways work best. What is an acceptable surface? This is defined by the domain in which we choose to apply the tool. In general though, we are shooting to produce surfaces that are homeomorphic to a cylinder.

The first phase of this project involved building a version of basic algorithm. The basic algorithm can handle constructing a surface between two contours, no branching and no holes. Scale and orientation issues are handled fairly easily. It is extremely powerful as a modeling tool, once you begin to think in terms of lofting.

Basic Lofting can be broken in two important sections:

  • Correspondence
  • Tiling
More advanced lofting also has a section on branching.
Quick and dirty canyon built by lofting between hand built cross sections.
Correspondence
Correspondence is matching the contours that should be connected and in the case of the angled contours how they match up. In a non-branching algorithm, it easy to know what contours should be connected but it is difficult to know how to line them up, because we permit non-parallel non-overlapping contours. (These traits are what makes the algorithm useful for geometric modeling.)

My version of the basic algorithm correlates the contours, trying to minimize differences in geometry size and shape by generating a warped "contour" space. This warped contour space contains the contours lined up for tiling.

Tiling
Tiling is generating the triangle strip. The algorithm requires a goal function or metric to make decisions as to what vertices to connect into triangles. My version minimizes edge length in warped space. It provides good results for the likely scenarios in geometric modeling. The algorithm maintains information such that it could also use metric based in the original model space along with warped space metrics.

Results
The image to the right illustrates the algorithm lofting between circles of different radius, different numbers of segments making up the circle and different spacings. In this case, the contours are parallel but that is not a requirement for the algorithm. From this, it is obvious how easy it is to model a fuselage with this tool. Accurate wings can also be build easily by using wing cross sections.
Lofting between circles of different sizes and numbers of segments.
The image to the right illustrates the basic algorithm lofting non-parallel contours. Each of the contours is at an angle to the others. Each contour has a different geometry: triangle, square, and pentagon. Notice how the resulting triangular mesh is homeomorphic to a cylinder. The algorithm takes special pains to prevent collapsing.

In my implementation of the algorithm, it makes every attempt to reorient contours such that the initial winding order of the contour is unimportant with respect to generating the lofted meshes.

Lofting from a triangle to a square to a pentagon all at angles to each other.
Optimizing Pass
Due to the fact that tiling is done in a warped space, it is quite possible that an optimization pass could improve on the tiling. [Meyer94] discusses a local optimization which uses a goal function to swap edges in the tiling, if possible, to minimize or maximize the goal function. This type of refinement could improve the tiling, if some cases are found where the edge selection done in warped space does not prove to be a good choice in model space. I may add this when I find some good example cases.

Geo Modeler Plug-in
I have taken the work from this project, plus a couple improvements, and implemented it as a plug-in for Geo, a geometric modeling and animation package for the vis-sim industry. (See Carbon Graphics for more info about Geo.)

The tool permits lofting between open and closed contours, producing triangles all properly oriented to face out of the shape. To the right are images of the plug-in in action in Geo 0.9.9.7.

References:

There are piles of references for lofting, dating all the way back to 1977 and Fuchs' original paper. The following are just the references mentioned in this document:
[Meyer94] - Meyers, David, "Reconstruction of Surfaces from Planar Contours", Dissertation, University of Washington.

Lofting between a number of circles, and polygons. Simply illustrates the tool functioning in Geo

Lofting between open and closed polygons, properly managing the gaps.
glenn@raudins.com