Đang chuẩn bị liên kết để tải về tài liệu:
Efficient Collision Detection for Animation and Robotics Part 9

109 if we think of the graph of the distance function in Rn . This is a surface S in R n and if we follow the extrema of distance on this surface, the roadmap of this paper is exactly a roadmap in the sense of 18 and 19 . The silhouette curves of 18 correspond to the freeway curves of this paper, and the linking curves correspond to bridges. Recall the basic property required of roadmaps: +1 De nition A subset of R of a set S satis es the roadmap condition if every connected component of S contains a single. | 109 if we think of the graph of the distance function in R . This is a surface s in R l and if we follow the extrema of distance on this surface the roadmap of this paper is exactly a roadmap in the sense of 18 and 19 . The silhouette curves of 18 correspond to the freeway curves of this paper and the linking curves correspond to bridges. Recall the basic property required of roadmaps De nition A subset of R of a set s satis es the roadmap condition if every connected component of s contains a single connected component of R. For this de nition to be useful there is an additional requirement that any point in s can easily reach a point on the roadmap. There is one minor optimization that we take advantage of in this paper. That is to trace only maxima of the distance function rather than both maxima and minima. This can also be applied to the original roadmap. For those readers not familiar with the earlier papers we give here an informal sketch of the completeness proof. We need some notation rst. Let s denote the surface in R 1 which is the graph of the distance function. s is an n-dimensional set and is semi-algebraic if con guration space is suitably parametrized. This simply means that it can be de ned as a boolean combination of inequalities which are polynomials in the con guration space parameters. One of the coordinates in con guration space R becomes the sweep direction. Let this direction be Xỵ. Almost any direction in OS will work and heuristics can be used to pick a direction which should be good for a particular application. When we take slices of the distance surface S they are taken normal to the Xi coordinate so S I a means s Xỵ a . Also for a point p in R l Xi p is the aq-coordinate of p. The other coordinate we are interested in is the distance itself which we think of as the height of the distance surface. So for a point p in R l h p is the value of the distance at this con guration. no For this paper we use a slightly di erent de nition of .