7 replies to this topic

[Nils Pipenbrinck]

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

[Reedbeta]

The determinant of that matrix varies continuously as one moves the control points of the Bezier. One can continuously transform a curve from one without a loop to one with a loop, and the curve must pass through a cusp state during this transformation (it's the boundary between loop and non-loop). Therefore, if one curve with a loop has a negative Sylvester determinant, then all of them do (since all the curves with zero determinant have a cusp, this follows from the continuity).

[bignobody]

Sufferin' Succotash!

(sorry, couldn't help myself :lol: )

[.oisyn]

Stop using my matrix!

[Onikhaosifix]

Sufferin' Succotash!

lmao

[Nils Pipenbrinck]

Reedbeta,

The sign change when the bezier goes through the cusp into a loop-state is pretty obvious.

But do you have an idea if the sign is always positive when no loop exists? If this would be true, it would be a very very cool thing (for bezier rendering).

I think I'm going to dig deeper into that stuff as soon as I find the time. Maybe a little program that lets me play with the roots visually and show the matrix at the same time.

Btw folks,
what's up with that Sufferin' Succotash thing?

[Reedbeta]

I'm 99% sure that the determinant is always positive for no loop, negative for a loop, and zero for cusp points.

Btw for higher order Beziers there could be multiple loops, in which case (probably) the determinant is negative only for odd numbers (1, 3, 5, ...) of loops.

[bignobody]

Nils Pipenbrinck said:

Btw folks,
what's up with that Sufferin' Succotash thing?

It's Sylvester the Cat's "catch-phrase" from the Warner Brothers Looney Tunes cartoons. It's also important to say it with a heavy lisp.

As in "Thufferin' Thuccotash! That ReedBeta knows everything!" :lol:

Regards,