CAGD-banner.gif
On-Line Geometric Modeling Notes
VERTEX POINTS AND EDGE POINTS


Overview

The refinement process defined by the cubic uniform B-spline curve generates a sequence of control polygons that converges to the curve. This process be specified by examining the binary subdivision methods for the curve to obtain a unique set of control points that generates the subdivision. However, in the case of the cubic curve, there is another way to look at the generation of the points of a refined control polygon. Each of these points can be classified as either a ``vertex point'' or an ``edge point,'' and methods can be specified to calculate each point. This procedure turns out to be quite useful as they will allow us to directly calculate points on the limit curve without going through the refinement.

pdficonsmall.gif For a pdf version of these notes look here.


Classifying the Refinement Points

Suppose we are given a control polygon $ \left\{ {\bf P} _0, {\bf P} _1, {\bf P} _2, {\bf P} _3 \right\}$.

\includegraphics {figures/vertex-edge-1}

If we use the refinement method motivated by the binary subdivision of the curve, we generate a new control polygon shown below

\includegraphics {figures/vertex-edge-2}

We note that three of the new control points appear to lie at the midpoints of the three respective line segments. These points will be classified as ``edge points''. The other points all lie close to on of the vertices of the original control polygon, and will be called ``vertex points''.

In this light, if we denote the new control polygon generated by the binary subdivision method as $ \left\{ {\bf E} _0, {\bf V} _0, {\bf E} _1, {\bf V} _1, {\bf E} _2 \right\}$ then by combining and applying the splitting matrices that generate the binary subdivision of the curve we obtain

$\displaystyle \left[
\begin{array}{r}
{\bf E} _0 \\  {\bf V} _0 \\  {\bf E} _1 ...
...{r}
{\bf P} _0 \\  {\bf P} _1 \\  {\bf P} _2 \\  {\bf P} _3
\end{array}\right]
$

and so the edge points $ {\bf E} _0$, $ {\bf E} _1$ and $ {\bf E} _2$ are calculated by
$\displaystyle {\bf E} _0$ $\displaystyle =$ $\displaystyle \frac{1}{8}(4 {\bf P} _0 + 4 {\bf P} _1)$  
  $\displaystyle =$ $\displaystyle \frac{ {\bf P} _0 + {\bf P} _1}{2}$  
       
$\displaystyle {\bf E} _1$ $\displaystyle =$ $\displaystyle \frac{1}{8}(4 {\bf P} _1 + 4 {\bf P} _2)$  
  $\displaystyle =$ $\displaystyle \frac{ {\bf P} _1 + {\bf P} _2}{2}$  
       
$\displaystyle {\bf E} _2$ $\displaystyle =$ $\displaystyle \frac{1}{8}(4 {\bf P} _2 + 4 {\bf P} _3)$  
  $\displaystyle =$ $\displaystyle \frac{ {\bf P} _2 + {\bf P} _3}{2}$  

and indeed are the midpoints of the line segments connecting the original control points. These points are illustrated in the following figure:

\includegraphics {figures/curve-edge-points}

The $ {\bf V} _0$ and $ {\bf V} _1$ are calculated by

$\displaystyle {\bf V} _0$ $\displaystyle =$ $\displaystyle \frac{1}{8} ( {\bf P} _0 + 6 {\bf P} _1 + {\bf P} _2 )$  
  $\displaystyle =$ $\displaystyle \frac{1}{8} ( ( {\bf P} _0 + {\bf P} _1 ) + 4 {\bf P} _1 + ( {\bf P} _1 + {\bf P} _2 ))$  
  $\displaystyle =$ $\displaystyle \frac{1}{4} ( \frac{ {\bf P} _0 + {\bf P} _1}{2}
+ 2 {\bf P} _1
+ \frac{ {\bf P} _1 + {\bf P} _2}{2} )$  
  $\displaystyle =$ $\displaystyle \frac{1}{4} ( {\bf E} _0 + 2 {\bf P} _1 + {\bf E} _1 )$  
  $\displaystyle =$ $\displaystyle \frac{\frac{ {\bf E} _0 + {\bf P} _1}{2} + \frac{ {\bf P} _1 + {\bf E} _1}{2}}{2}$  
       
$\displaystyle {\bf V} _1$ $\displaystyle =$ $\displaystyle \frac{1}{8} ( {\bf P} _1 + 6 {\bf P} _2 + {\bf P} _3 )$  
  $\displaystyle =$ $\displaystyle \frac{1}{8} ( ( {\bf P} _1 + {\bf P} _2 ) + 4 {\bf P} _2 + ( {\bf P} _2 + {\bf P} _3 ))$  
  $\displaystyle =$ $\displaystyle \frac{1}{4} ( \frac{ {\bf P} _1 + {\bf P} _2}{2}
+ 2 {\bf P} _2
+ \frac{ {\bf P} _2 + {\bf P} _3}{2} )$  
  $\displaystyle =$ $\displaystyle \frac{1}{4} ( {\bf E} _1 + 2 {\bf P} _2 + {\bf E} _2 )$  
  $\displaystyle =$ $\displaystyle \frac{\frac{ {\bf E} _1 + {\bf P} _2}{2} + \frac{ {\bf P} _2 + {\bf E} _2}{2}}{2}$  

\includegraphics {figures/curve-vertex-points}

and it is seen that these are the midpoint of the line segment that joins the respective midpoints of the two line segments from the vertex point to the respective edge points. Therefore, we only need to be able to specify midpoints of line segments to be able to specify the refined control polygon.


An Example of the Refinement Algorithm

We illustrate the workings of this refinement algorithm via the following three figures. First consider a control polygon as is shown below.

\includegraphics {figures/cubic-refinement}

Calculate the edge and vertex points producing a refinement of the original control polygon.

\includegraphics {figures/cubic-refinement-1}

Assemble these points into a new control polygon and utilize it as input again to the refinement process - producing new edge and vertex points from this set of points.

\includegraphics {figures/cubic-refinement-2}

The general idea behind subdivision curves is to utilize the control points generated through refinement as input to another refinement operation, and then continue this process until a refinement is reached that accurately represents the curve to a desired resolution.

It is well known in the case of uniform B-spline curves that these refinement points converge in the limit to the curve itself.


Summary

In the case of cubic uniform B-spline curves we can consider the refinement procedure to consist of the generation of edge points and vertex points from a given set of control points - each of which can be generated by taking only the midpoints of line segments. This classification of the control points will become very useful in the direct calculation of points on the limit curve.


Bibliography

1
CATMULL, E., AND CLARK, J.
Recursively generated B-spline surfaces on arbitrary topological meshes.
Computer-Aided Design 10 (Sept. 1978), 350-355.


\begin{singlespace}
\noindent
\footnotesize\bfseries All contents copyright (c) ...
...ment, University of California, Davis \\
All rights reserved.
\end{singlespace}


Ken Joy
2000-11-28