Как найти точки соприкосновения 2-ух фигур в 3Д с помощью алгоритма SAT?
Подскажите метод/алгоритм, который в связке с SAT (Separation Axis Theorem) сможет высчитать не только коллизию 2 выпуклых многоугольников, но и найдёт все точки соприкосновения. Мне в идеале найти в общем полигон пересечения фигур.
Красная область - площадь соприкосновения, которую мне надо найти
Я примерно думаю это должно быть так: Надо определить тип соприкосновения для 2 фигур, она может касаться как и стороной, так и гранью, так и точкой. Затем при конечном анализе уже найти фигуру, которая будет описывать общую фигуру 2 плоскостей.
Это и будет той самой площадью соприкосновения.
Ответы (1 шт):
Я реализовал нахождение площади соприкосновения 2 многоугольников. Я использовал метод нахождения и решения коллизии SAT (Separation Axis Theorem), следовательно я имел минимальную дистанцию (separation), и пространственные дистанции (грани) вдоль вектора выталкивания от точки 0 0 0 (Я в 2Д делал проекции на линию по формуле ab/|b|, и находил коллизию в 1Д, то я сохранял эти проекции). Далее я определял из какого объекта я выталкиваю другой объект, и из этого находил точку коллизии. Имея эту точку и вектор выталкивания можно получить плоскость коллизии. Затем проецируя на неё 2 многоугольника, можно отсортировать вершины, что лежат на плоскости (или очень близки). Затем через алгоритм Sutherland-Hodgman, который из двух 2Д многоугольников можно найти один, который будет площадью перекрытия. Эта площадь перекрытия будет площадью пересечения (касания) в 2Д. Затем инверсивной матрицей можно получить набор 3Д точек, который и будет этой площадью.
Алгоритм возможно не лучший, его можно довести до ума, просто это самый простой алгоритм действий что-бы получить заведомый результат.
Проблемы могут возникнуть на этапе реализации алгоритма Sutherland-Hodgman, так-как этот алгоритм предназначен для роботы с многоугольниками, но не как не с линиями и точками.