# determinant of the sylvester-matrix

7 replies to this topic

### #1Nils Pipenbrinck

Senior Member

• Members
• 597 posts

Posted 20 March 2006 - 09: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

### #2Reedbeta

DevMaster Staff

• 5307 posts
• LocationBellevue, WA

Posted 21 March 2006 - 01:44 AM

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).
reedbeta.com - developer blog, OpenGL demos, and other projects

### #3bignobody

Valued Member

• Members
• 155 posts

Posted 21 March 2006 - 09:56 PM

Sufferin' Succotash!

(sorry, couldn't help myself :lol: )
-bignobody
notsoftgames.com - Creator of Shlongg!

### #4.oisyn

DevMaster Staff

• Moderators
• 1842 posts

Posted 22 March 2006 - 12:57 AM

Stop using my matrix!
-
Currently working on: the 3D engine for Tomb Raider.

### #5Onikhaosifix

Valued Member

• Members
• 117 posts

Posted 22 March 2006 - 01:47 AM

Sufferin' Succotash!

lmao

### #6Nils Pipenbrinck

Senior Member

• Members
• 597 posts

Posted 22 March 2006 - 05:30 PM

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?

### #7Reedbeta

DevMaster Staff

• 5307 posts
• LocationBellevue, WA

Posted 22 March 2006 - 06:07 PM

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.
reedbeta.com - developer blog, OpenGL demos, and other projects

### #8bignobody

Valued Member

• Members
• 155 posts

Posted 22 March 2006 - 06:33 PM

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,
-bignobody
notsoftgames.com - Creator of Shlongg!

#### 1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users