Quote:Original post by grhodes_at_work
I would comment that the polynomial formulation is for Bezier curves of a specific order (cubic ones?). Could be sufficient for Brad's case, I would imagine. I haven't seen the treatment, but I would assume it involves finding the roots to that polynomial? In itself nontrivial for 9th order, which is where calculus begins to come into play.
To test only if there is an intersection, you do not need to compute the roots of the 9th degree polynomial. You can use Sturm sequences to count how many roots are in the domain [0,1] of the polynomial. Constructing the polynomial in the first place, constructing the Sturm sequence, and applying the root-counting test involves only addition and multiplication. If robustness is important, you can implement the Sturm sequence approach using exact arithmetic, converting the floating-point coefficients of the 9th degree polynomial to rational numbers.
To read an interesting post on the topic, there is a *closed form* solution for testing. Search comp.graphics.algorithms for:
From: "Przemyslaw Koprowski" <org@siggraph.pkoprowski>
Subject: Closed-form of Bezier intersection test
Date: Sunday, February 12, 2006 3:17 PM