Возникла задача в редакторе реализовать вырезку одной фигуры из другой в 3Д. Алгоритм не разбирал изначально, знал что понадобится вырезать двумерные фигуры друг из друга и поэтому для начала реализовал класс, который вырезает из одного многоугольника другой, в результате чего получается несколько новых многоугольников (все выпуклое). Не сложная задача, но возился с ней долго...
Так вот сделал и теперь перехожу к основному вопросу. Алгоритм вырезания 3Д объектов.
Для начала объясню как у меня выглядит объект.
Объект - это совокупность выпуклых многоугольников (полигонов). Все вершины каждого многоугольника лежат в одной плоскости. В принципе тут все просто.
Теперь расскажу что я придумал и в чем сложности, чтобы Вы не подумали, что я бездельничую и сам ничего не пытаюсь делать =)
Мой алгоритм примерно таков.
Для каждой стороны ЗАДАННОГО объекта (ЗО) ищем пересечение с гранями ВЫРЕЗАЕМОГО объекта (ВО). При этом ищутся все точки пересечения граней ВО с плоскостью, где лежит сторона ЗО.
Сторона - выпуклый многоугольник, точки кот. леж. в одной плоскости.
Грань - одна грань стороны.
Собрав все точки, которые получились при пересечениях и спроецировав на плоскость- у нас есть ВЫРЕЗАЕМАЯ фигура (ВФ). Спроецировав на плоскость сторону ЗО получаем ЗАДАННУЮ фигуру (ЗФ). Тоже 2Д фигура, которая будет обрезана с помощью ВФ.
Теперь уже имеющимся алгоритмом вырезаем ВЗ из ЗФ. Получается обрезанная фигура, которую мы из проекции выносим в 3Д на место обрезанной стороны.
И так для каждой стороны.
Все вышесказанное будет работать только в том случае, если сторону пересекает одна какая-то выпуклая часть объекта. То есть, к примеру, сторону пересекает конус, который в вышеописанном случае вырежется нормально. Если, к примеру, два конуса пересекают одну сторону - тогда в проекции у нас будет 2 многоугольника, которые программа будет пытаться соедить в один.
Вопрос тут такой. Как сказать программе, какие из пересеченных точек составляют каждую фигуру?
Вот тут находится некоторая иллюстрация:
Алгоритм вырезания одной фигуры из другой
На рисунке 2 конуса пересекают сторону. Как видно глазу, точки пересечения образуют 2 четырехугольника. Как объяснить программе, что эти четыре точки именно ДВА четырехугольника, а НЕ ОДИН непонятный многоугольник.
Повторюсь, что несмотря на то, что конусы далеко друг от друга - это один объект.