Synthesis of Spatially and Intrinsically Constrained Curves Using Simulated Annealing

Abstract

A general technique is presented for automatic generation of B-spline curves in a spatially constrained environment, subject to specified intrinsic shape properties. Spatial constraints are characterized by a distance metric relating points on the curve to polyhedral models of obstacles which the curve should avoid. The shape of the curve is governed by constraints based on intrinsic curve properties such as parametric variation and curvature. To simultaneously address the independent goals of global obstacle avoidance and local control of intrinsic shape properties, curve synthesis is formulated as a combinatorial optimization problem and solved via simulated annealing. Several example applications are presented which demonstrate the robustness of the technique. The synthesis of both uniform and nonuniform B-spline curves is also demonstrated. An extension of the technique to general sculptured surface model synthesis is briefly described, and a preliminary example of simple surface synthesis presented.