“The support function of a surface” is a fundamental concept in mathematics and a crucial operation for algorithms in robotics, such as those for collision detection and grasp planning. It is possible to calculate the support function of a convex body in closed form. However, for complex continuous surfaces, especially non-convex ones, this calculation can be far more difficult, and no general solution is available so far. This limits the applicability of related algorithms. This paper presents a branch-and-bound (B&B) algorithm to calculate the support function of complex continuous surfaces. An upper bound of the support function over a surface domain is derived. While a surface domain is divided into subdomains, the upper bound of the support function over any subdomain is proved to be not greater than the one over the original domain. Then, as the B&B algorithm sequentially divides the surface domain by dividing its subdomain having a greater upper bound than the others, the maximum upper bound over all subdomains is monotonically decreasing and converges to the exact value of the desired support function. Furthermore, with the aid of the B&B algorithm, this paper derives new algorithms for the minimum distance between complex continuous surfaces and for globally optimal grasps on objects with continuous surfaces. A number of numerical examples are provided to demonstrate the effectiveness of the proposed algorithms.
Supplementary notes can be added here, including code and math.