Continuous Collision Detectionbetween Two 2D Curved-Edge Polygons under Rational Motions

摘要

This paper presents a novel approach which continuously detects the first collision between two curved-edge polygons moving under rational motions. Edges of the two polygons in this paper are planar curves, represented as conic splines, i.e. elliptic or parabolic sections. The curved-edge polygons are not confined to be convex and conic sections are only required to be GC~0 continuous. Motions of the polygons are modeled by interpolating between control points along motion trajectories. Our algorithm returns the first collision moment and collision position if there is a collision between the two moving polygons and returns no-collision otherwise. Collision condition of the two polygons moving under rational motions is represented as an univariate polynomial of time t. Bernstein form is used to improve the accuracy of solving the high degree polynomial. We also use bounding circles to improve the efficiency of our approach and compare our method with the PIVOT2D method and prove ours to be more accurate and faster.