METHOD AND APPARATUS FOR DETERMINING MUTUAL INTERSECTION OF MULTIPLE CONVEX SHAPES

摘要

A solution is proposed for efficiently determining whether or not a set of elements (such as convex shapes) in a multi-dimensional space mutually intersects. The solution may be applied to elements in any closed subset of real numbers for any number of spatial dimensions of the multi-dimensional space. The solutions provided herein include iterative processes for calculating the point displacement from boundaries of the elements (shapes), and devices for implementing the iterative process(es). The processes and devices herein may be extended to abstract (functional) definitions of convex shapes, allowing for simple and economical representations. As an embodiment of the present invention, an object called a “void simplex” may be determined, allowing the process to terminate even earlier when found, thereby avoiding unnecessary computation without excess memory requirements.

主权项

1. A method for determining object-collisions in coordinate space, the method comprising:
i) receiving an input target point and a set of data comprising a plurality of elements representing a plurality of objects in a coordinate space; ii) initializing a search point and a subset of elements from the set of data; iii) determining, from the set of data, at least one element from the plurality of elements with the largest signed distance from the search point; iv) comparing the distance to a threshold; v) verifying a presence of a mutual intersection between elements of the set of data when the distance is equal to or less than the threshold; when the distance is greater than the threshold: v) appending the at least one element to the subset; vi) determining an intersection of the elements in the subset; vii) creating a new search point based on the intersection of the elements in the subset; viii) revising the subset based on the new search point; and ix) iteratively repeating steps iii)-viii) with new search point.