Quickly Approximating the Distance Between Two Objects

A method of quickly approximating the distance between two objects (one smaller, regarded as a point; the other larger and complexly shaped) has been devised for use in computationally simulating motions of the objects for the purpose of planning the motions to prevent collisions. The method is needed because computer-based-graphics techniques that have been used heretofore to make such estimates entail amounts of computation that are excessively large for purposes of the simulations. The method, denoted tree-based model learning, is an integral combination of (1) decision-tree techniques upon which several machine learning techniques have been based and (2) a relatively accurate function-approximation technique. Each node of a decision tree corresponds to a partition of the problem domain — in this case, starting with one node representing a large cubic volume centered on the large object and dividing and subdividing it, at symmetry planes, into successively smaller cubes. Each branch of the tree represents a rule-based decision selecting one of the child nodes of a parent node. The smallest subdivisions (leaf nodes) contain coefficients of a quadric equation that estimates the distance between the objects.