Rendering a bezier curve on the GPU
category: code [glöplog]
Errata: (of last paragraph) we have to proof that:
f(t1).f(t1) <= f(t3).f(t3) and f(t2).f(t2) <= f(t3).f(t3)
f(t1).f(t1) <= f(t3).f(t3) and f(t2).f(t2) <= f(t3).f(t3)
Anyway, I've put a more detailed idea for the proof here:
https://www.shadertoy.com/view/MdXBzB in the comment section, mainly because it has editing function and I've already spotted a bit more errors in my post here ;)
https://www.shadertoy.com/view/MdXBzB in the comment section, mainly because it has editing function and I've already spotted a bit more errors in my post here ;)
Ok, I think the proof is actually simpler than I thought.
Read more in a shader, but in short...
First, as I said, we can show that t_2 <= t_3 <= t_1.
Then, we know that |f(t_2)|^2, |f(t_3)|^2, |f(t_1)|^2 are all local extrema of |f(t)|^2.
Therefore we have only two cases:
1. |f(t_2)|^2 and |f(t_1)|^2 are local minima and |f(t_3)|^2 is local maximum
2. |f(t_2)|^2 and |f(t_1)|^2 are local maxima and |f(t_3)|^2 is local minimum
To exclude case 2 we just have to use second derivative test (via Fermat's theorem),
and second derivative is parabola that is always opening up (unless our curve is straight).
And that's it, we are only left with case 1, and since |f(t_3)|^2 is local maximum, obviously it cannot be global minimum.
Read more in a shader, but in short...
First, as I said, we can show that t_2 <= t_3 <= t_1.
Then, we know that |f(t_2)|^2, |f(t_3)|^2, |f(t_1)|^2 are all local extrema of |f(t)|^2.
Therefore we have only two cases:
1. |f(t_2)|^2 and |f(t_1)|^2 are local minima and |f(t_3)|^2 is local maximum
2. |f(t_2)|^2 and |f(t_1)|^2 are local maxima and |f(t_3)|^2 is local minimum
To exclude case 2 we just have to use second derivative test (via Fermat's theorem),
and second derivative is parabola that is always opening up (unless our curve is straight).
And that's it, we are only left with case 1, and since |f(t_3)|^2 is local maximum, obviously it cannot be global minimum.
And again using a bit better language (damn pouet editing):
Final sketch of the proof (more detailed):
We know that |f(t)|^2 has local extrema at t_1, t_2 and t_3, as solution to f(t).f'(t) = 0
We proof that in our cubic formula: t_2 <= t_3 <= t_1 (that is actually true for all cubic polynomials).
Therefore we have only two cases:
1. We have local minima at t_2 and t_1 and local maximum at t_3
2. We have local maxima at t_2 and t_1 and local minimum at t_3
To exclude case 2 we just have to use second derivative test (via Fermat's theorem),
and second derivative of |f(t)|^2 is parabola that is always opening up (unless our curve is straight).
And that's it, we are only left with case 1, and since we have local maximum at t_3, obviously it cannot be global minimum.
Final sketch of the proof (more detailed):
We know that |f(t)|^2 has local extrema at t_1, t_2 and t_3, as solution to f(t).f'(t) = 0
We proof that in our cubic formula: t_2 <= t_3 <= t_1 (that is actually true for all cubic polynomials).
Therefore we have only two cases:
1. We have local minima at t_2 and t_1 and local maximum at t_3
2. We have local maxima at t_2 and t_1 and local minimum at t_3
To exclude case 2 we just have to use second derivative test (via Fermat's theorem),
and second derivative of |f(t)|^2 is parabola that is always opening up (unless our curve is straight).
And that's it, we are only left with case 1, and since we have local maximum at t_3, obviously it cannot be global minimum.
https://www.shadertoy.com/view/MdXBzB
is a more detailed variant of
https://www.shadertoy.com/view/MtscRM
Euclidean distance to cubic planar bezier (with 3 CVs it is always planar) requires solving a quadratic function (3 roots, of whom one can be ignored).
You then calculate the squared distance between any point and the first 2 roots to get the closest of 3 symmetric points on the quadratic_bezier=parabola to any point on a plane of the bezier.
----
Quadratic (and higher exponent) bezier requires solving higher roots, or approximation with lower degree beziers:, or heuristic spheretracking-raymarching approaches.
as always, bezier can be solved recursively. likely even for "distance of point to bezier"
is a more detailed variant of
https://www.shadertoy.com/view/MtscRM
Euclidean distance to cubic planar bezier (with 3 CVs it is always planar) requires solving a quadratic function (3 roots, of whom one can be ignored).
You then calculate the squared distance between any point and the first 2 roots to get the closest of 3 symmetric points on the quadratic_bezier=parabola to any point on a plane of the bezier.
----
Quadratic (and higher exponent) bezier requires solving higher roots, or approximation with lower degree beziers:, or heuristic spheretracking-raymarching approaches.
as always, bezier can be solved recursively. likely even for "distance of point to bezier"
ollj: oh man, we meet again here. You copied my shader over, added ugly colors and just compressed it / minified by hand. What's the point?
I have demonstrated that calculating 2 roots is enough already, so what are you still obsessing about?
And your "proof" is what, let see:
Okaaay, cubic function (this is what you mean I guess) can have at most 1 local minimum, not 2.
Moreover what you are optimizing (trying to find global minimum) is quartic function not cubic. And a way to find all extrema (that include minima) in a quartic function (quartic polynomial) is to find roots of a cubic polynomial (a derivative).
So what are you even talking about?
I have demonstrated that calculating 2 roots is enough already, so what are you still obsessing about?
And your "proof" is what, let see:
Quote:
analytic proof: cubic curve can only have 2 local minima.
simpler proof: a ray can intersect a cubic spline only twice, never more than 2 times,
Okaaay, cubic function (this is what you mean I guess) can have at most 1 local minimum, not 2.
Moreover what you are optimizing (trying to find global minimum) is quartic function not cubic. And a way to find all extrema (that include minima) in a quartic function (quartic polynomial) is to find roots of a cubic polynomial (a derivative).
So what are you even talking about?
the comprssion was the main thing.