Interpolating Curves

• Simplest case: given a list of points P₀, P₁, P₂, ..., draw a curve that passes through each of them in this order.
• Usually this is done by a polynomial function of degree the number of points - 1.
• We can also interpolate on subsets of points and concatenate the resulting curves.
• We can also impose the continuity of the derivative up to a certain point to insure the smoothness of the curve.
• The first derivative of the function defining the curve parametrically is the tangent to the curve. The second derivative gives us the curvature.

Bezier Curves
Some of the control points are used to define the tangent to the curve.

Spine Curves

• Curves with continuity of the second derivative (curvature) with local computations. The polynomial function is usually cubic.
• Each curve segment is defined by 4 control points, none of which is actually on the curve itself.
• B-splines: bi-cubic.

Surfaces

• Any interpolation type can be extended to surfaces by adding a second parameter (v or t).
• b_i(u) are called blending functions and they are similar to the interpolation functions defined for 3 points.
• The best known are the NURBS surfaces (nonuniform rational B-spline).

NURBS in OpenGL

GLUnurbsObj *nobj;
nobj = gluNewNurbsRendered();
gluBeginSurface(nobj);
gluNurbsSurface(nobj, 
  nrk, knots, nr, knots, du, dv, 
  points, 4, 4, surf_type);
gluEndSurface(nobj);
// type: GLU_MAP2_VERTEX_3

Triangulation

Def. Given a set of points or vertices V={v₁, v₂, ..., v_n}, find a set of triangles T={t₁, t₂, ..., t_m} such as:

• each triangle from T is based on vertices from V,
• for each triangle, no other point from V apart from its vertices can be found inside it,
• the triangles form a convex surface containing all the points in V triangle interiors do not intersect.

Lazy Algorithm

• Start with an arbitrary point.
• Find its two nearest neighbors.
• Add one point at a time.
• For each new point, add the triangles required for the surface to remain convex.

Open and Interesting Problems

• Finding an optimal triangulation for a given object in polynomial time, that minimizes the number of triangles, the total edge length, or the total surface area.
• For OpenGL: finding a minimal number of triangle strips covering the object.
• Resolution problems: reducing the number of triangles without losing details.
• Related problems: convex boundary for a given number of points, polygonal or circular (spherical).
• Object morphing: computing the number of flips required to convert one planar triangulation into another.
• Fast remeshing after a local change.