CAGD/Primitives

Overview

Simple shapes, like those used in Euclidean geometry, can be represented in either 2D or 3D space. These primitives form the basis for CAGD as well for computer graphics. We will review vectors and lines, since we will be dealing with them a lot.

Since an understanding of these concepts is needed to fully understand CAGD, we will review them quickly. There are some techniques that will be presented here that we will use often in later sections. Whether these topics relate to 2D or 3D space will not be explicitly stated, however most topics do extend from 2D into 3D.

Definitions of Equations

This will serve as a reference for terms that we will use often in the discussion of CAGD.

• Parametric equations: a set of equations that rely on a common independent variable. Most often, we see equations of the type:

  $x={\frac {x(t)}{w(t)}},y={\frac {y(t)}{w(t)}}$, where t is the independent variable.

• Implicit equation: an equation that takes the form of a function of some variables equaling zero:

  $f(x,y)=0,ax+by+c=0$

• Explicit equation: a special case of parametric and implicit equations:

  $y=f(x)$

Although all types are seen in mathematical courses, explicit is the one most often seen and dealt with. Although explicit functions are useful, in CAGD it is more advantageous to deal with the parametric and implicit versions of the same equations for primitives.

Vectors

Vectors have the following properties:

• A vector is an entity with both direction and magnitude.
• Vectors can represent points. They represent them as a distance from the origin to that point. This is called an absolute position vector.
• Vectors can represent distance between 2 points as well. This is called a relative position vector. The vector ${\vec {\mathbf {P} }}_{2/1}=\mathbf {P} _{2}-\mathbf {P} _{1}.$
• Given 2 vectors P₁=(x₁,y₁,z₁) and P₂=(x₂,y₂,z₂), then P₁+P₂ = (x₁+x₂, y₁+y₂, z₁+z₂).
• Vectors can have a negative magnitude. This is equivalent to a vector with a positive magnitude with an opposite direction to the original vector.
• The magnitude (or norm) can be determined by $\left\vert P_{1}\right\vert ={\sqrt {x_{1}^{2}+y_{1}^{2}+z_{1}^{2}}}$.
• A unit vector, a vector with the same direction but magnitude 1, can be found by dividing the vector by its norm: ${\widehat {P}}_{1}={\frac {{\vec {P}}_{1}}{\left\vert {\vec {P}}_{1}\right\vert }}$.
• For Cartesian coordinate systems, the usual unit vectors in the x, y and z directions are ${\hat {i}},{\hat {j}},{\hat {k}}$, respectively.

Operations on Vectors

1. Dot Product: used in computing projections of one vector onto another vector.
   • ${\vec {P}}_{1}\cdot {\vec {P}}_{2}=\left\vert P_{1}\right\vert \left\vert P_{2}\right\vert \cos \theta$, where $\theta$ is the angle between vectors.
   • ${\vec {P}}_{1}\cdot {\vec {P}}_{2}=x_{1}x_{2}+y_{1}y_{2}+z_{1}z_{2}$
2. Cross Product: used in many applications, including finding an orthogonal vector to two other vectors.
   • $\left\vert {\vec {P}}_{1}\times {\vec {P}}_{2}\right\vert =\left\vert P_{1}\right\vert \left\vert P_{2}\right\vert \sin \theta$, where $\theta$ is the angle between vectors.
   • ${\vec {P}}_{1}\times {\vec {P}}_{2}={\begin{vmatrix}{\hat {\mathbf {i} }}&{\hat {\mathbf {j} }}&{\hat {\mathbf {k} }}\\x_{1}&y_{1}&z_{1}\\x_{2}&y_{2}&z_{2}\end{vmatrix}}$
   1. The area of a triangle with vertices at points $\mathbf {P} _{1},\mathbf {P} _{2},\mathbf {P} _{3}$ can be quickly solved using the cross product:
      • $A={\frac {\left\vert \mathbf {P} _{1/2}\times \mathbf {P} _{1/3}\right\vert }{2}}$. This can be derived from the definition of the cross product and trigonometry.

Lines

A line is the simplest kind of curve. There are many different ways to represent them:

• Parametric form: ${\begin{matrix}x(t)=x_{0}+x_{1}(t)\\y(t)=y_{0}+y_{1}(t)\end{matrix}}$
• Vector form: $P(t)=\left[{\begin{matrix}x(t)\\y(t)\end{matrix}}\right]=\left[{\begin{matrix}x_{0}+x_{1}(t)\\y_{0}+y_{1}(t)\end{matrix}}\right]=\left[{\begin{matrix}x_{0}\\y_{0}\end{matrix}}\right]+\left[{\begin{matrix}x_{1}\\y_{1}\end{matrix}}\right]t=A_{0}+A_{1}t$, where A₀ is a point on the line and A₁ is the direction of the line.
• Point-slope form: $y-y_{1}=m(x-x_{1}),m={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}$
• Explicit form: $y=mx+b$
• Implicit form: $ax+by+c=0$

Although these are all valid expressions for a line, the more useful forms for CAGD purposes are the implicit and parametric equations.

Affine Parametric Equation of a Line

In CAGD we like to have representations (equations) for things in a way that is independent of coordinate systems. These are called affine equations. For lines, affine equations mimic the parametric representations. Since 2 points define a line, all we need to find two points are two values of t. This allows us to define $\mathbf {P} (t_{0})=\mathbf {P} _{0},\mathbf {P} (t_{1})=\mathbf {P} _{1}$. For any arbitrary value of t, we can define the line as the following affine equation:

$\mathbf {P} (t)={\frac {(t_{1}-t)\mathbf {P} _{0}+(t-t_{0})\mathbf {P} _{1}}{t_{1}-t_{0}}}$

This equation holds for any value of t. However, points inside the line segment bounded by P₀ and P₁ are bounded by $t_{0}\leq t\leq t_{1}$.

Implicit Equation of a Line

A line can alternatively be described as a point and a direction. If we define a point $P_{0}=(x_{0},y_{0})$ and a normal vector ${\hat {n}}=a{\hat {\mathbf {i} }}+b{\hat {\mathbf {j} }}$, we can construct an implicit equation for the line:

$(\mathbf {P} -\mathbf {P_{0}} )\cdot {\hat {n}}=0$,

where P is a point on that line. If the line goes through two known points, then a point P = (x,y,w) is on the line if:

${\begin{vmatrix}x&y&w\\x_{1}&y_{1}&w_{1}\\x_{2}&y_{2}&w_{2}\end{vmatrix}}=(y_{1}w_{2}-w_{1}y_{2})x+(w_{1}x_{2}-x_{1}w_{2})y+(x_{1}y_{2}-y_{1}x_{2})=0$

This corresponds with the implicit equation $ax+by+c=0$.

Distance of a Point to a Line

For this, we will start with the basic implicit form of a line:

$ax+by+c=0$

Putting it into slope-intercept form:

$y=-{\frac {a}{b}}x-{\frac {c}{b}}$

Putting that into a matrix:

$\left[{\begin{matrix}x\\y\end{matrix}}\right]=\left[{\begin{matrix}0\\-{\frac {c}{b}}\end{matrix}}\right]-{\frac {1}{b}}\left[{\begin{matrix}-b\\a\end{matrix}}\right]x$

The vector ${\vec {u}}=(-b,a)$ is parallel to that line, so the vector ${\vec {v}}=(a,b)$ is perpendicular. So if a vector from a point P₀ = (x₀,y₀) is ${\vec {r}}=\left[{\begin{matrix}x-x_{0}\\y-y_{0}\end{matrix}}\right]$:

$d={\frac {\left\vert {\vec {v}}\cdot {\vec {r}}\right\vert }{\vec {v}}}$

Expanding into variables:

$d={\frac {\left\vert ax+by+c\right\vert }{\sqrt {a^{2}+b^{2}}}}$

The absolute value of the numerator just serves to get a positive number. Often it's more useful to leave the absolute value off to know which side of the line it's on. That is called the signed distance equation.

Rotation of a Point About Any Line

Rotation is a fundamental part of any computer-aided design software. It can become really complex and the standard solution can involve a combination of seven 4x4 matrices. This technique is presented as a simple way to accomplish the same task with vector algebra. For most tasks, this isn't as efficient as a computational algorithm, but it should serve to show the concept of rotation.

Example for rotation of point P to P' about axis passing through A with direction n.

An axis is defined as a line passing through a specific point. We can do this with a point $\mathbf {A}$ and a vector ${\hat {n}}$. If we consider a vector from point A to P:

${\vec {S}}=P-A$

Let point B be the point of P projected onto the line. It will be the shortest distance between P and the line. We don't know the distance from A to B, so we use our S vector:

$\left\vert {\vec {S}}\right\vert \cos \phi =\left\vert B-A\right\vert$, where $\phi$ is the angle between the line and the vector S.

Since we don't know the angle offhand, we could find it by using the definition of the dot product:

${\vec {S}}\cdot {\hat {n}}=\left\vert {\vec {S}}\right\vert \left\vert {\hat {n}}\right\vert \cos \phi =\left\vert {\vec {S}}\right\vert \cos \phi$, since $\left\vert {\hat {n}}\right\vert =1.$

${\vec {S}}\cdot {\hat {n}}=\left\vert B-A\right\vert$

In order to get the vector from A to B (which we'll call ${\vec {B}}$), we use some basic vector algebra:

${\vec {B}}=A+[(P-A)\cdot {\hat {n}}]{\hat {n}}$

Now that we can go from A to B with a single vector, we now turn our attention to the points P and P' on the rotation plane. Let's let the vector ${\vec {u}}$ be defined from point B to point P and the vector ${\vec {r}}$ be defined from B to P'. Let's also define the vector ${\vec {v}}$ be defined as having the magnitude of r (or the length of u) , but rotated 90 degrees CCW such that ${\vec {u}}\cdot {\vec {v}}=0.$ If we let $\theta$ be the angle we are rotating P, we can set up the following relationship:

${\vec {r}}={\vec {u}}\cos \theta +{\vec {v}}\sin \theta$

This is really useful because all these vectors are ones we can easily find. The algorithm then becomes:

1. ${\vec {B}}=A+[(P-A)\cdot {\hat {n}}]{\hat {n}}$
2. ${\vec {u}}=P-B$
3. ${\vec {v}}={\hat {n}}\times {\vec {u}}$
4. ${\vec {r}}={\vec {u}}\cos \theta +{\vec {v}}\sin \theta$
5. $P'={\vec {B}}+{\vec {r}}$

As stated above, this algorithm is really only intended for human use. It doesn't provide any benefit in computational speed. Graphics cards and programs use rotation matrices to achieve a similar result. Because computers usually excel at performing many iterations of relatively simple tasks, the matrix method will be usually of more benefit.