Я работаю с игровым движком, и моя задача - добавить код для моделирования разрушения жестких сеток.
Сейчас я работаю только над тем, чтобы разбить куб.
Я использую алгоритм Вороного, чтобы создать (реалистичный) тресканный осколок, и я использую метод полуплоскости, чтобы сгенерировать ячейку Вороного.
Теперь, как я делаю это для каждой начальной точки, я делаю плоскости, которые являются перпендикулярными биссектрисам (прямые черные линии на изображении) с остальными начальными точками, и вычисляю пересечения всех этих плоскостей, чтобы дать мне различные точки ( все оранжевые точки).
Я получил это далеко.
Из всех этих рассчитанных точек пересечения мне нужны только те, которые находятся ближе всего и включают начальную точку (точки, обведенные красным), и мне нужно отбросить все остальные.
Информация, которая у меня есть:
1) Плоские уравнения всех плоскостей (определяются нормированными нормальными векторами и их расстоянием от начала координат)
2) Точки пересечения (которые я рассчитал)
Кто-нибудь может помочь мне узнать, как я могу найти точки, обведенные красным?
источник
Ответы:
Следуя методу полуплоскости , вы обнаружите отрезки прямой относительно каждой другой точки и перпендикулярные биссектрисы каждой из этих
который вы затем пересекли, чтобы найти потенциальные вершины ячейки Вороного.
Теперь вы хотите исключить те, которые пересекают любую из «далеких» полуплоскостей, образованных биссектрисами.
Я покрасил «отдаленные» полуплоскости полупрозрачным синим для ясности.
Здесь две красные точки, обведенные кружком, проходят тест: они не находятся ни в одной полуплоскости. Не обведенная кружком красная точка не проходит, так как она находится внутри полуплоскости, образованной в направлении точки в правом верхнем углу.
Это фактически означает проверку, находится ли каждая точка на другой стороне каждой биссектрисы (относительно сайта Вороного) и отбрасывание тех, которые есть. (Остерегайтесь ошибок округления.)
источник
Вы можете просто перебрать ребра и отфильтровать все вершины, которые не находятся в одной полуплоскости с интересующей точкой.
В качестве оптимизации выполните итерацию от ближайших ребер до самых дальних. Я думаю, что вы можете даже фильтровать вершины при создании слайсов.
Это как разрезать пирог с бесконечным ножом, пока не останется только маленький кусочек с вишней на нем. Если вам нравятся аналогии. Просто обрежьте и посмотрите, какая часть будет взята, а какая будет отброшена.
источник