CAGD/Algebraic Geometry

Overview

This is primarily a dive into the mathematics behind CAGD. There are a lot of special problems that arise when dealing with the curves we've already discussed. We are restricting ourselves to 2D representations since curves are only generally defined on a plane. This should, however, demonstrate the types of techniques that can be used to solve such problems.

Bezout's Theorem

This is arguably the base point for this entire lecture. It should explain the reason behind using the techniques in this section. Bezout's theorem states that a degree-n planar curve and a degree-m planar curve intersect in exactly mn points, properly counting complex intersections, multiple intersections and intersections at infinity. This is a very powerful theorem because of its far-reaching implications. The modifier "properly counting" is particularly relevant here. How we count those intersections is very important.

In a sense, the fundamental theorem of algebra is a special case of Bezout's theorem. This should underscore how incredibly powerful this theorem is.

Homogeneous Coordinates

A planar algebraic curve of degree-n is defined as:

$f(x,y)=\sum _{i+j\leq n}a_{ij}x^{i}y^{j}=0$

If we introduce another coordinate, we can gain a lot more versatility:

$f(X,Y,W)=\sum _{i+j+k=n}a_{ij}X^{i}Y^{j}W^{k}=0$

This makes every term degree n. Using this method, a Cartesian coordinate (x,y) can be expressed as (X/W, Y/W) for any homogeneous triple (X,Y,W). This might not look like anything helpful, since now we're just adding more information to our equations. However, this proves to be incredibly useful as we will see.

Intersection of 2 Circles

Let's take an example of two circles that intersect. The implicit equation of a circle is f(x,y)=(x-x_c)² + (y-y_c)² - r² = 0. This is clearly a second order curve. If Bezout's theorem holds, then two circles must intersect exactly 4 times. Let's use homogeneous coordinates to see how they intersect. The implicit homogeneous representation of a circle is:

$f(X,Y,W)=(X-x_{c}W)^{2}+(Y-y_{c}W)^{2}-r^{2}W^{2}=0$

Let's keep in mind that if a point located on this circle has the condition that W=0, then it corresponds to a point at infinity. If we were to draw two circles on a piece of paper, the maximum number of times that we would see an intersection would be 2. This doesn't seem correspond to Bezout's theorem, which dictates 4 intersections. If we look at the homogeneous circle definition above, we can see that every circle would intersect at points (1,i,0) and (1,-i,0). If you plug those values into the equation, you can see that it holds. These points are both complex and infinite. Since all circles would pass through those points, then we can say that any two circles will intersect at those infinite and complex points. If we also remember that two circles will intersect at two real points, then we get the 4 intersection points as given by Bezout's theorem.

Homogeneous Parameters

A parametric equation can also be expressed as a homogeneous equation. For a parametric set of equations x(t) and y(t), we can define t=T/U to get a homogeneous equation. Let's take the unit circle as an example:

$x(t)={\frac {-t^{2}+1}{t^{2}+1}},\,y(t)={\frac {2t}{t^{2}+1}}$

If we express it by replacing t=T/U, then we get:

$X(T,U)={\frac {-T^{2}+U^{2}}{T^{2}+U^{2}}},\,y(T,U)={\frac {2TU}{T^{2}+U^{2}}}$

This is very helpful because the parametric equation would require the domain to be $t\in [-\infty ,\infty ]$. In homogeneous parameters, the circle can be swept out using finite values.

Planar Curve Intersection

Coincidence of a Line and a Point

Some special notation can be used to describe lines. The implicit equation of a line is expressed as f(x,y) = ax+by+c = 0. In homogeneous notation, the equation becomes f(X,Y,W) = aX+bY+cW = 0. We could express this line as a 3-tuple or ordered triple: L(a,b,c). This notation allows us to define the implicit equation as the dot product between a point P(X,Y,W) and the line L(a,b,c):

$L(a,b,c)\cdot P(X,Y,W)=aX+bY+cW$

Thus, we can check if a point is on the line by seeing if the dot product of L(a,b,c) and P(X,Y,W) is 0.

Intersection of Two Lines

Representing the implicit equation of the line as an ordered triple has other advantages too. The definition of the dot product helped us to determine if points are coincident on a line, and the cross product can help us determine if 2 lines intersect. To simplify the explanation, let's take a very basic equation:

${\vec {A}}\times {\vec {B}}={\vec {C}}$

In the definition of the vector cross product, the result C is a vector that is perpendicular to both A and B. This means that if we take the dot product of C and A or B, the dot product will be zero. In our example, the arguments of the cross product A and B are ordered triples that represent lines. If the result C is something that, if "dotted" with either A or B, yields zero, then we could say that the ordered triple C is a point that lies on both lines A and B, or more precisely, the point of intersection of A and B. This would fit with Bezout's theorem, since there is only 1 intersection of 2 degree-1 curves. To sum up, the intersection point of two lines can be determined by the cross product:

${\vec {P}}(X,Y,W)={\vec {L}}_{1}(a_{1},b_{1},c_{1})\times {\vec {L}}_{2}(a_{2},b_{2},c_{2})$

Intersection of a Parametric and Implicit Curve

The points of intersection between a parametric and an implicit curve are fairly easy to find. If we have a parametric curve $\left\langle x(t),y(t)\right\rangle$ and an implicit curve $f(x,y)$, simply substitute the expressions for x and y with those for x(t) and y(t) to obtain a polynomial $g(t)=f(x(t),y(t))$. The roots of the resulting polynomial g(t) will be the intersection points for of the two curves.

$Ex:x(t)=2t-1,y(t)=8t^{2}-9t+1;f(x,y)=x^{2}+y^{2}-1$

Substitute:

${\begin{aligned}f(x(t),y(t))&=(2t-1)^{2}+(8t^{2}-9t+1)^{2}-1\\g(t)&=64t^{4}-144t^{3}+101t^{2}-22t+1\\Roots:t&=0.06118,0.28147,0.90735,1.0\end{aligned}}$

To get the Cartesian coordinates of the intersection points, simply plug the roots into the parametric curves.

Intersection of a Line and a Rational Bezier Curve

The intersection of a rational Bezier curve and a line can be made into a problem involving parametric and implicit curves. The line can be expressed in implicit form f(x)=ax+by+c=0. The rational Bezier curve is really just a set of Bernstein polynomials and is in a parametric form. The process of determining the intersection points is as follows:

1. Compute the dot product between the line and the Bezier control points.

   $f_{i}=ax_{i}w_{i}+by_{i}w_{i}+cw_{i}$

2. The dot products become the coefficients of a Bernstein polynomial.

   $f(t)=\sum _{i=0}^{n}f_{i}B_{i}^{n}(t)$

3. Compute the roots of the Bernstein polynomial and those are the parameter values of the Bezier curve that intersect with the line.

As you can see, the degree of the resulting Bernstein polynomial is the same degree as required by Bezout's theorem. A root finding algorithm for a Bernstein polynomial expressed as an explicit Bezier curve is simple to implement.

Implicitization and Inversion

There are really 2 ways to define planar curves: parametrically and implicitly. Parametric curves are great for plotting and computing the coordinates of points on the curve, but implicit curves help determine whether points are on the curve and if not, which side they are on. Conversion between from parametric to implicit curves can always be done, but conversion from implicit to parametric isn't always possible. In this section, we will discuss implicitization of parametric and polynomial curves.

Brute Force

Sometimes simple algebra can be used to solve for an implicit function given a parametric set of curves. Take the parametric degree-1 example:

${\begin{cases}x=t+2\\y=3t+1\\\end{cases}}$

We can solve for t in the first equation and substitute it in the second:

${\begin{aligned}&t=x-2\\&y=3(x-2)+1\\&f(x,y)=3x-y-5=0\end{aligned}}$

This implicit curve is equivalent to the parametric curve and contains the same set of points. So if we can find an implicit equation for the parametric curve for degree-1 curves, what about for degree-2 curves? Let take another example:

${\begin{cases}x=t^{2}+1\\y=t^{2}+2t-2\\\end{cases}}$

Here, we try the same approach as before:

${\begin{aligned}&t=\pm {\sqrt {x-1}}\\&y=({\sqrt {x-1}})^{2}\pm 2{\sqrt {x-1}}+2\\&f(x,y)=x^{2}-2xy+y^{2}-10x+6y+13=0\end{aligned}}$

Here, we obtain the an implicit equation, but it almost didn't work for us. It became slightly more complicated and the square root made things more complicated. Generally, there are solutions for cubic and some quartic curves, but past degree-4 there are no closed-form solutions. We need another more elegant way to do implicitization.

Polynomial Resultants

Resultants are an elegant way to determine if polynomials have a common root. Let's take 2 polynomials:

$f(t)=\sum _{i=0}^{n}a_{i}t^{i},g(t)=\sum _{i=0}^{n}b_{i}t^{i}$

Resultants for Factored Polynomials

The resultant of f(t) and g(t) is written R(f,g) and R(f,g) = 0 only if f(t) and g(t) have a common root. Let's illustrate this concept using factored polynomials:

$f(t)=(t-f_{1})(t-f_{2})(t-f_{3})\cdots (t-f_{m}),\quad g(t)=(t-g_{1})(t-g_{2})(t-g_{3})\cdots (t-g_{n})$

Here, it's easy to see if there are common roots, but it's also easy to understand how a resultant works. The resultant is defined as:

$R(f,g)=\prod _{i=1}^{m}\prod _{j=1}^{n}(f_{i}-g_{j})$

Since the resultant is a product of the difference of roots, if any of the roots are common between the polynomials, that difference will be zero and thus, the resultant will be zero. Let's take the following example:

$f(t)=t^{2}-7t+12=(t-3)(t-4),\quad g(t)=t^{2}-5t+6=(t-2)(t-3)$

$R(f,g)=(3-2)(3-3)(4-2)(4-3)=0$

Resultants with Degree-1 Polynomials

If we work with regular polynomials, the resultant will take a slightly different form. Let's start with the intersection of degree-1 polynomials:

$f(t)=a_{1}t+a_{0},\quad g(t)=b_{1}t+b_{0}$

If we use matrix algebra and homogeneous coordinates, the form becomes:

${\begin{bmatrix}a_{1}&a_{0}\\b_{1}&b_{0}\end{bmatrix}}{\begin{bmatrix}T\\U\end{bmatrix}}={\begin{bmatrix}0\\0\end{bmatrix}}$

From linear algebra, the matrix equation is only true if the determinant of the leftmost matrix is zero. This means:

${\begin{vmatrix}a_{1}&a_{0}\\b_{1}&b_{0}\end{vmatrix}}=a_{1}b_{0}-b_{1}a_{0}=0$

Let's try to construct the resultant by using the roots of the curves. The roots of these curves are:

$a_{1}t+a_{0}=0\Rightarrow t=-a_{0}/a_{1}$

$b_{1}t+b_{0}=0\Rightarrow t=-b_{0}/b_{1}$

Bezout's theorem states that there is exactly 1 intersection between the two polynomials, so the resultant would be the difference between the roots of the two polynomials:

$-a_{0}/a_{1}-(-b_{0}/b_{1})=0\Rightarrow a_{1}b_{0}-a_{0}b_{1}=0$

This yields the same resultant as using the matrix algebra. This proves the validity of the method. However, an intersection of two degree-1 curves is fairly simple.

Resultants with Degree-2 Polynomials

If we consider the following two degree-2 polynomials:

$f(t)=a_{2}t^{2}+a_{1}t+a_{0},\quad g(t)=b_{2}t^{2}+b_{1}t+b_{0}$

If we try to find the roots of the curves and subtract them, we would have a zero resultant if any of the roots are equal. Since there are two roots for each curve, there are 4 conditions that must be checked in order to see if any of the roots match. It would be easier to create a pair of degree-1 polynomials that will have a common root if f(t) and g(t) have a common root. We would create them like this:

${\begin{aligned}h_{1}(t)&=a_{2}g(t)-b_{2}f(t)\\&=a_{2}(b_{2}t^{2}+b_{1}t+b_{0})-b_{2}(a_{2}t^{2}+a_{1}t+a_{0})\\&=(2,1)t+(2,0)\\h_{2}(t)&=(a_{2}t+a_{1})g(t)-(b_{2}t+b_{1})f(t)\\&=(a_{2}t+a_{1})(b_{2}t^{2}+b_{1}t+b_{0})-(b_{2}t+b_{1})(a_{2}t^{2}+a_{1}t+a_{0})\\&=(2,0)t+(1,0)\\\end{aligned}}$

The notation used here is $(i,j)=a_{i}b_{j}-a_{j}b_{i}={\begin{vmatrix}a_{i}&a_{j}\\b_{i}&b_{j}\end{vmatrix}}$. The resultant R(f,g) then can be expressed in a matrix form:

$R(f,g)={\begin{vmatrix}(2,1)&(2,0)\\(2,0)&(1,0)\end{vmatrix}}$

Resultants with Degree-3 Polynomials

If we consider the following two degree-3 polynomials:

$f(t)=a_{3}t^{3}+a_{2}t^{2}+a_{1}t+a_{0},\quad g(t)=b_{3}t^{3}+b_{2}t^{2}+b_{1}t+b_{0}$

We will use a similar method to the one employed above by creating 3 degree-2 polynomials that have a common root if f(t) and g(t) have a common root. The polynomials are created thus:

${\begin{aligned}h_{1}(t)&=a_{3}g(t)-b_{3}f(t)\\&=a_{3}(b_{3}t^{3}+b_{2}t^{2}+b_{1}t+b_{0})-b_{3}(a_{3}t^{3}+a_{2}t^{2}+a_{1}t+a_{0})\\&=(3,2)t^{2}+(3,1)t+(3,0)\\h_{2}(t)&=(a_{3}t+a_{2})g(t)-(b_{3}t+b_{2})f(t)\\&=(3,1)t^{2}+[(3,0)+(2,1)]t+(2,0)\\h_{3}(t)&=(a_{3}t^{2}+a_{2}t+a_{1})g(t)-(b_{3}t^{2}+b_{2}t+b_{1})f(t)\\&=(3,0)t^{2}+(2,0)t+(1,0)\\\end{aligned}}$

As well, we can set up a matrix equation:

${\begin{bmatrix}(3,2)&(3,1)&(3,0)\\(3,1)&(3,0)+(2,1)&(2,0)\\(3,0)&(2,0)&(1,0)\\\end{bmatrix}}{\begin{Bmatrix}t^{2}\\t\\1\end{Bmatrix}}={\begin{bmatrix}0\\0\\0\\\end{bmatrix}}$

The resultant of the matrix is the determinant of the leftmost matrix:

$R(f,g)={\begin{vmatrix}(3,2)&(3,1)&(3,0)\\(3,1)&(3,0)+(2,1)&(2,0)\\(3,0)&(2,0)&(1,0)\\\end{vmatrix}}$

It must be noted here that the resultant only determines the existence of a root, not what that value is or how many common roots there are. For that, we need to solve the set of linear equations above.

Implicitization of Parametric Equations

So we've covered how resultants can be used to find out if two polynomials have common roots. We can apply this same technique to parametric curves if we create two auxiliary polynomials, p(x,t) and q(y,t), that satisfy the same relationships as the parametric equations of the curve:

$p(x,t)=w(t)x-x(t),\quad q(y,t)=w(t)y-y(t)$

These polynomials are just implicit versions of the parametric curves. p(x,t) and q(y,t) are zero when the x, y and t relationships satisfy the equations $x={\frac {x(t)}{w(t)}},y={\frac {y(t)}{w(t)}}$. Using these auxiliary polynomials, we can find one implicit equation that completely describes the parametric curve. Let's take the following example of a parabola:

${\begin{cases}x=t^{2}+1\\y=t^{2}+2t-2\\\end{cases}}$

We begin by constructing the auxiliary polynomials:

$p(x,t)=-t^{2}+(x-1),\quad q(y,t)=-t^{2}-2t+(y+2)$

We then construct the resultant:

$R(f,g)={\begin{vmatrix}(2,1)&(2,0)\\(2,0)&(1,0)\\\end{vmatrix}}===={\begin{vmatrix}2&x-y-3\\x-y-3&2x-2\\\end{vmatrix}}$

Notice how we ended up with polynomials in the matrix instead of just numbers. The determinant of the matrix will form an implicit equation that will describe the curve:

$f(x,y)=={\begin{vmatrix}2&x-y-3\\x-y-3&2x-2\\\end{vmatrix}}=-x^{2}+2xy-y^{2}+10x-6y-13$

This equation is the implicitization of the parametric curve.