Обнаружить и найти пересечение луча против кубического треугольника Безье

Question

При написании редактора моделей, помимо включения трассировки лучей, я могу подумать о паре операций, в которых я хотел бы найти очень хорошее приближение к точке пересечения между лучом и треугольным участком Безье.

Как это сделать? Я знаю несколько способов, но, вероятно, есть лучшие.

Точные потребительные случаи: я мог бы использовать один Безье треугольник патч в качестве опорной поверхности для рисования детализированных фигур с помощью мыши. Я мог бы также хотеть определить точку расщепления от такого патча.

Если для этого есть исходный код на C, я бы тоже хотел это увидеть. Возможно, даже используйте его вместо того, чтобы катить мой собственный код.

Answer 1

Я бы посоветовал вам внедрить Треугольное отсечение Безье (PDF).

Однако другой возможностью будет преобразование вашего треугольного патча в паттерн Безье с тензорным произведением. Преимущество этого заключается в том, что поддержка Безье для тензорного продукта намного больше, поэтому вы с большей вероятностью найдете некоторый код, который сможете использовать. Преобразование простое:

• Просмотр вашего треугольного патча как серии из n + 1 строк контрольных точек (где n - степень)
  • Первая строка имеет 1 контрольную точку, а каждая строка имеет на 1 контрольную точку больше, чем последняя
• Теперь обработайте каждую строку как кривую Безье соответствующей степени (от 0 до n)
• Степень повышения каждого ряда до степени n
  • Каждая строка теперь будет иметь n + 1 контрольных точек, образуя сетку контрольных точек n + 1 на n + 1
• Эта сетка точек, взятая в виде n-го пятна Безье, представляет собой поверхность, идентичную вашему треугольнику

Для нахождения точек пересечения это должно работать просто отлично. Однако ваш патч с тензорным произведением вырожден (у вас совпадают точки на одном конце), поэтому вы можете столкнуться с некоторыми числовыми проблемами при приближении к вырожденному углу. Кроме того, отображение обратно в треугольную область может сделать такие вещи, как наложение текстуры, немного сложнее. Поэтому я бы посоветовал вам использовать более прямую треугольную обрезку Безье, если вы не возражаете против реализации.

Answer 2

Я не знаком с треугольным патчем Безье, но если он всегда может содержаться в треугольнике, то, если луч пересекает треугольник, он тоже должен пересекать кривую внутри него.

Если вышеприведенное верно, то вы можете искать кривую между двумя вершинами, сторона которых пересекает луч, для точки, достаточно близкой к лучу. Я думаю, что вы можете выполнить бинарный поиск по параметру кривой в этой области, чтобы получить эту точку.