Polygon Table in Representing Polygons and Curve Representations

Part 1: Polygon Table for Representing Polygons

Polygon Surfaces

The most commonly used boundary representation (B-rep) for a 3D graphics object is a set of surface polygons that enclose the interior of the object. Many graphics systems store all object descriptions as a set of surface polygons because it simplifies and speeds up surface rendering and display.

Polygon Tables

A polygon table is the specification of polygon surfaces using vertex coordinates and other attributes. Polygon data tables are organized into two groups:

1. Geometric Tables
2. Attribute Tables

Geometric Tables

For storing geometric data, three lists are created:

1. Vertex Table

• Stores the coordinate values (x, y, z) for each vertex in the object.
• Example:

2. Edge Table

• Contains pointers back into the vertex table to identify the two vertices for each polygon edge.
• Example:

3. Polygon Table

• Contains pointers back into the edge table to identify the edges that form each polygon.
• Example:

Attribute Table

• Contains qualitative properties of each polygon surface such as:
  • Degree of transparency
  • Surface reflectivity
  • Color and texture information

Diagram of Polygon Table Structure

Vertex Table        Edge Table          Polygon Table
-----------         ----------          -------------
V1: (x1,y1,z1) <-- E1: V1,V2  <------ P1: E1,E2,E3
V2: (x2,y2,z2) <-- E2: V2,V3          P2: E3,E4,E5
V3: (x3,y3,z3) <-- E3: V3,V1

This hierarchical pointer structure allows efficient storage and retrieval of polygon geometry for rendering.

Part 2: Representations of Three Curves

1. Spline Curves

Definition: A spline refers to a flexible strip used to produce a smooth curve through a designated set of points. Mathematically, a spline curve is described using a piecewise cubic polynomial function.

Key Concepts:

• Several small weights are distributed along the length of the strip to hold it in position on a drafting table as the curve is drawn.
• The curve passes through or near a set of control points.
• A spline surface can be described with two sets of orthogonal spline curves.

Mathematical Representation: A piecewise cubic polynomial for a segment between two control points is:

P(t) = a*t³ + b*t² + c*t + d,   0 ≤ t ≤ 1

where a, b, c, d are coefficient vectors determined by boundary conditions.

Applications:

• Designing curve and surface shapes in graphics applications.
• Used in CAD/CAM, animation, and font design.

Diagram:

Control Points: P0, P1, P2, P3
         P1 *       * P2
           /         \
     P0 *               * P3
         \_____________/
           Spline Curve

2. Bezier Curves

Definition: A Bezier curve is a parametric curve defined by a set of control points. The curve is influenced by all control points but generally does not pass through the intermediate ones (only through the first and last).

Mathematical Representation: For n+1 control points P0, P1, ..., Pn, the Bezier curve is:

P(t) = Σ [C(n,k) * t^k * (1-t)^(n-k) * Pk],   0 ≤ t ≤ 1
       k=0 to n

where C(n,k) = n! / (k! * (n-k)!) are the Bernstein basis polynomials.

For a cubic Bezier curve (n=3):

P(t) = (1-t)³P0 + 3t(1-t)²P1 + 3t²(1-t)P2 + t³P3

Properties:

• The curve always passes through P0 and P3 (endpoints).
• The curve lies within the convex hull of the control points.
• Changing one control point affects the entire curve.

Diagram:

    P1 *----* P2
      /        \
P0 *            * P3
    \__Bezier__/

3. B-Spline Curves

Definition: A B-Spline (Basis Spline) curve is an extension of the Bezier curve that provides local control over the shape of the curve. Changing one control point affects only a portion of the curve.

Mathematical Representation:

P(t) = Σ Pi * Ni,k(t)
       i=0 to n

where:

• Pi are the control points
• Ni,k(t) are the B-Spline basis functions of order k
• The basis functions are defined recursively:

Ni,1(t) = 1,  if ti ≤ t < ti+1,   else 0

Ni,k(t) = [(t - ti) / (ti+k-1 - ti)] * Ni,k-1(t) + [(ti+k - t) / (ti+k - ti+1)] * Ni+1,k-1(t)

where $t_0, t_1, \ldots, t_{n+k}$ is the sequence of knot values that determines where and how the control points influence the curve.

Properties:

• Provides local control: moving one control point only changes the curve over a limited parameter range (roughly $k$ segments), unlike a Bezier curve where every control point affects the entire curve.
• The degree of the curve (order $k$) is independent of the number of control points, unlike a Bezier curve where the degree is always one less than the number of control points.
• Includes Bezier curves as a special case (a B-Spline with a single knot span and no interior knots reduces to a Bezier curve).
• Widely used in CAD systems and font outlines where localized editing of a complex curve is needed.

Diagram:

     P1 *        * P3
       /  \    /  \
 P0 *      \  /      * P4
      \_____\/______/
   (each control point only reshapes a local segment)

Summary

Together, the polygon table (vertex, edge, polygon and attribute lists) gives an efficient boundary representation for flat-faced 3D objects, while spline, Bezier, and B-Spline curves give three progressively more flexible ways to represent smooth curved surfaces: splines interpolate through control points with piecewise cubics, Bezier curves give a single polynomial influenced by every control point globally, and B-Splines add local control through their knot-based recursive basis functions, which is why B-Splines are preferred whenever a designer needs to edit part of a complex curve without disturbing the rest of it.