Nils Pipenbrinck
03-20-2006, 02:41 PM
I came across something strange:
While working on a thick bezier line renderer I used the sylvester matrix to detect cusps in my curves (these need special handling)
To get started: this is what I do:
Say you have two polynoms of dgree 2, a and a (in my case that was the first derivate of my bezier in x and y) that look like this:
g(t) = a2 t^2 + a1 t + a0
h(t) = b2 t^2 + b2 t + b0
The sylvester matrix looks like this:
| a2 a1 a0 0 |
| 0 a2 a2 a0 |
| b2 b1 b0 0 |
| 0 b2 b2 b0 |
A property of this matrix is, that if both polynoms, a and b have a common root, the determinant of the sylvester matrix is zero.
Now - if the first derivates of a bezier share a zero within 0..1 I have a cusp. This is easy to observe, and that was my idea why I started to look into that stuff in the first place.
The determinant of such a matrix is really cheap to calculate (expansion by minors on the first column, and then throw out all multiplies by zero of the minors gets a result with just 18 multiplies. that's almost as cheap as evaluating a bezier point).
During my tests I printed the determinant for a bezier where I moved the points around, and I found out (to my surprise), that for all my bezier-curves, whenever they form a loop (something else I have to detect) the determinant became negative. (positive for all others).
If this would be true for all beziers, it would be a very cool thing to know, but unfortunately the meaning of the determinant sign is nowhere documented (I did a really excessive google search). I'm not capable of doing a mathematical proof myself (I don't really get the theory of the sylvester matrices - they just work for me...).
Any idea what the sign of that determinant tells? It must have something to do with the number/permutation/constellation of roots of the two functions?
Nils
While working on a thick bezier line renderer I used the sylvester matrix to detect cusps in my curves (these need special handling)
To get started: this is what I do:
Say you have two polynoms of dgree 2, a and a (in my case that was the first derivate of my bezier in x and y) that look like this:
g(t) = a2 t^2 + a1 t + a0
h(t) = b2 t^2 + b2 t + b0
The sylvester matrix looks like this:
| a2 a1 a0 0 |
| 0 a2 a2 a0 |
| b2 b1 b0 0 |
| 0 b2 b2 b0 |
A property of this matrix is, that if both polynoms, a and b have a common root, the determinant of the sylvester matrix is zero.
Now - if the first derivates of a bezier share a zero within 0..1 I have a cusp. This is easy to observe, and that was my idea why I started to look into that stuff in the first place.
The determinant of such a matrix is really cheap to calculate (expansion by minors on the first column, and then throw out all multiplies by zero of the minors gets a result with just 18 multiplies. that's almost as cheap as evaluating a bezier point).
During my tests I printed the determinant for a bezier where I moved the points around, and I found out (to my surprise), that for all my bezier-curves, whenever they form a loop (something else I have to detect) the determinant became negative. (positive for all others).
If this would be true for all beziers, it would be a very cool thing to know, but unfortunately the meaning of the determinant sign is nowhere documented (I did a really excessive google search). I'm not capable of doing a mathematical proof myself (I don't really get the theory of the sylvester matrices - they just work for me...).
Any idea what the sign of that determinant tells? It must have something to do with the number/permutation/constellation of roots of the two functions?
Nils