相交線與二次貝塞爾三角形

Question

我正在嘗試爲我的OpenCL實時光線追蹤器找到線段與二次貝塞爾三角形之間的交點。

這個問題Detect&find intersection ray vs. cubic bezier triangle談到找到射線和立方貝塞爾三角形之間的碰撞點，主要推薦是嘗試細分或張量積bezier補丁。

我讀過幾個地方，當測試一個線段對二次貝塞爾三角形，你最終不得不解決一個二次方程，但我還沒有找到任何有關該方程實際是什麼的信息我開始懷疑它是否屬實。我試圖找到它也到目前爲止很短：P

有誰知道這是真的還是如何解決它除了使用細分或張量產品bezier補丁？

下面是二次貝塞爾三角形的方程式：

AS^2 + 2 * d 小號 T + 2 * E 小號 U + B * T 1 2 + 2 * F Ťù + C * U^2

其中S，T，U是三角形的參數。你可以用（1-S-T）替換U，因爲它們是重心座標。

A，B，C是三角形的拐角，D，E，F是沿着邊緣的控制點。

超級難倒這一個！

Answer 1

線路段具有參數方程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內時才存在。解決這個系統並不容易（可能的方法 - Gröbner basis，數值方法和解決方案過程可能在數值上不穩定）。這就是爲什麼有時建議細分方法的原因。