determinant of the sylvester-matrix

B91eae75cd6245bd8074bd0c3f1cc495
0
Nils_Pipenbrinck 101 Mar 20, 2006 at 21:41

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

7 Replies

Please log in or register to post a reply.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Mar 21, 2006 at 01:44

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). ;)

1959b9a5d7a4ad8b8114fec82f602e85
0
bignobody 101 Mar 21, 2006 at 21:56

Sufferin’ Succotash!

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

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Mar 22, 2006 at 00:57

Stop using my matrix!

B23fde3625b5611b7f6b4df8a6bf87ec
0
Onikhaosifix 101 Mar 22, 2006 at 01:47

Sufferin’ Succotash!

lmao

B91eae75cd6245bd8074bd0c3f1cc495
0
Nils_Pipenbrinck 101 Mar 22, 2006 at 17:30

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?

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Mar 22, 2006 at 18:07

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.

1959b9a5d7a4ad8b8114fec82f602e85
0
bignobody 101 Mar 22, 2006 at 18:33

@Nils Pipenbrinck

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,