Multi-dimensional dynamic programming in ruled surface fitting

• A multi-dimensional dynamic programming based ruled surface fitting scheme to a freeform rational surface.
• Providing solutions for the Ruled Surface Fitting (RSF) problem and the Ruled Surface Partitioning (RSP) problem in the discrete domain.
• Error-bound can be achieved by using the surface–surface composition technique.
• Highly parallel algorithms running on GPUs are employed to evaluate the multi-dimensional dynamic programming.

Ruled surfaces play an important role in many manufacturing and construction applications. In this work, we explore a multi-dimensional dynamic programming based ruled surface fitting scheme to a given freeform rational surface, SS. Considering two initial opposite boundaries of SS, sampled into a discrete piecewise linear polyline representation, the ruled surface fitting problem is reduced to a pairing-search between the polylines and elevations above the polylines, in the normal directions of SS. A four-dimensional dynamic programming   solution is sought for the four dimensions prescribed by the two polylines and the two elevation levels along the surface normals. This multi-dimensional dynamic programming is evaluated using highly parallel algorithms running on GPUs that ensures the best fit to the sampled data. In order to evaluate the fitting error with respect to SS, we derive a scheme to compute a bound from above on the maximal error between a bilinear surface patch (formed by two consecutive point-pairs) and its corresponding surface region on SS. Surface–surface composition is employed to extract the corresponding surface region on SS to compare against. Finally, the above ruled surface fitting approach is also extended into a discrete algorithm to find the non-isoparametric subdivision curve on SS when a discrete recursive piecewise-ruled surface fitting is considered. A five- or seven-dimensional dynamic programming solution is employed towards this end and once again, surface–surface composition is employed to extract the two subdivided patches as tensor products.