Линия пересечения против квадратичного треугольника Безье

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

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

Я читал в нескольких местах, что при тестировании отрезка линии по сравнению с квадратичным треугольником Безье вам просто приходится решать квадратное уравнение, но я не нашел никакой информации о том, что это за уравнение на самом деле, и начинаю интересно, правда ли это. Мои попытки найти его пока не увенчались успехом: P

Кто-нибудь знает, правда ли это или как решить эту проблему, кроме использования патчей Безье для подразделения или тензорного продукта?

Вот уравнение квадратного треугольника Безье:

AS^2 + 2*DST + 2*ESU + B*T^2 + 2*FTU + C*U^2

Где S, T, U - параметры треугольника. Вы можете заменить U на (1-S-T), поскольку они являются барицентрическими координатами.

A, B, C - углы треугольника, а D, E, F - контрольные точки по краям.

Супер тупик на этом!


c++ math raytracing bezier
person Alan Wolfe    schedule 25.03.2014    source источник
comment
Поскольку это касается поиска формулы, а не алгоритма C ++ того же самого, возможно, лучше спросить на math.stackexchange.com?   -  person Jongware    schedule 26.03.2014

Ответы (1)


arrow_upward
0
arrow_downward

Отрезок линии имеет параметрическое уравнение P = P0+(P1-P0)*v=P0+d*v, где v - параметр [0..1] Чтобы найти пересечение с помощью грубой силы, вам необходимо решить систему трех квадратных уравнений, например

x0+dx*v=AxS^2 + 2*Dx*S*T + 2*Ex*S*U + Bx*T^2 + 2*Fx*T*U + Cx*U^2

Эта система имеет 8 возможных решений, и пересечение (я) существует только в том случае, если приведенные v, s, t одновременно лежат в диапазоне 0..1. Решить эту систему непросто (возможные подходы - базис Грёбнера, численные методы, и процесс решения может быть численно нестабильным). Поэтому иногда рекомендуется метод подразделения.

person MBo    schedule 26.03.2014
comment
О, это прискорбно. У меня сложилось впечатление, что, поскольку он квадратичный, это будет проще. Я подробнее рассмотрю упомянутые вами подходы. Большое спасибо за информацию. - person Alan Wolfe; 27.03.2014