سؤال

I'm trying to find the intersection between a line segment and a quadratic bezier triangle for my OpenCL real time raytracer.

This question Detect&find intersection ray vs. cubic bezier triangle talks about finding the collision point between a ray and a cubic bezier triangle and the main recomendations are to try subdivision, or tensor product bezier patches.

I've read in a few places that when testing a line segment against a quadratic bezier triangle, that you just end up having to solve a quadratic equation, but I haven't found any information on what that equation actually is and am starting to wonder if it's true. My attempts to find it also have come up short so far :P

Does anyone know if this is true or how to solve it besides using subdivision or tensor product bezier patches?

Here's the equation for a quadratic bezier triangle:

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

Where S,T,U are the parameters to the triangle. You could replace U with (1-S-T) since they are barycentric coordinates.

A,B,C are the corners of the triangle, and D,E,F are the control points along the edges.

Super stumped on this one!

هل كانت مفيدة؟

المحلول

Line segment has parametric equation P = P0+(P1-P0)*v=P0+d*v, where v is parameter [0..1] To find intersection with brute force, you have to solve system of three quadratic equations like

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

This system has 8 possible solutions, and intersection(s) exists only if resulted v,s,t lie in range 0..1 simultaneously. It's not easy to solve this system (possible approaches - Gröbner basis, numerical methods, and solution process might be numerically unstable). That is why subdivision method is sometimes recommended.

نصائح أخرى

when your bezier patch has more than 3 sides, ray-intersection is no longer analytic (even if the splines on the side are only quadratic) and a precise enough iterative approach is significantly slower. Bezier patches are pathetic in terms of performance due to inherent recursion, you may want to do FFT for fourier-patches instead. Shadertoy.com [iq] has various "twisted cube intersection"s (that are not iterated by sphere-tracking==raymarching, which is efficient, but also causes MANY low-precision-cases-artifacts, where ever convergence of iteration is too slow).

yes, triangular-bezierpatch intersections has only analytic quadratic complexity (with quadratic beziers on the borders), but it involves some pre-computation (unless it is already in barycentric coordinates), that significantly lower the resulting precision (barycentric adds 1 division globally, and sums up over all domains)

This was solved (poorly, as in it has 1 error case and too low precision) on shadertoy in opengl in 2019: https://www.shadertoy.com/view/XsjSDt and i optimized it slightly (fixed precision issues, added camera and culling): https://www.shadertoy.com/view/ttjSzw + https://www.shadertoy.com/view/wlSyzd also see, https://www.reddit.com/r/askmath/comments/sfn8mk/analytic_intersection_ray/

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى StackOverflow
scroll top