c++ - 相交线与二次贝塞尔三角形

Question

我试图为我的 OpenCL 实时光线追踪器找到线段和二次贝塞尔三角形之间的交点。

这个问题Detect&find intersection ray vs. cubic bezier triangle谈论寻找射线和立方贝塞尔三角形之间的碰撞点，主要建议是尝试 segmentation 或张量积贝塞尔补丁。

我在几个地方读到过，当针对二次贝塞尔三角形测试线段时，您最终不得不求解一个二次方程，但我没有找到任何关于该方程实际是什么的信息，并且我开始怀疑这是不是真的。到目前为止，我试图找到它也没有成功 :P

有谁知道这是不是真的，或者除了使用 segmentation 或张量积贝塞尔曲线之外如何解决它？

这是二次贝塞尔三角形的方程式:

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

其中 S、T、U 是三角形的参数。您可以将 U 替换为 (1-S-T)，因为它们是重心坐标。

A,B,C 是三角形的角点，D,E,F 是边上的控制点。

super 难过这个!

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，数值方法和求解过程可能在数值上不稳定)。这就是有时推荐使用 segmentation 方法的原因。