A boundary representation (BREP) is a data structure used to represent all things topological: 3D meshes, 2d vector curves, volumes, etc. This post is about what makes a good boundary representation for CAD, tailored to support complex curves in a mathematically intutive (and correct) way.

What Is A Curve

What is a curve? A curve is a multidimensional function that is parameterized with one variable.

Arc Length All The Things

The choice of the parameterization “t” variable is a complicated topic. For our purposes we want all curves to be parameterized with a world-space distance along the curve. This is called arc length parameterization. We cannot do this analytically for polynomial (e.g. bezier) curves but we can approximate it fairly accurately with lookup tables. This gives us a bunch of nice properties.

Math Fundamentals Of Arc Length Curves

As stated in the intro a curve maps a single scalar number to a multidimensional point. An arc length curve has a number of nice properties:

• The first derivative (the vector created from all the partial derivatives of ‘t’) has length 1.
• The second derivative is a vector perpendicular to the curve whose length is the curvature at that point.
• For 3d curves, the third derivative let’s you calculate the twist ($f”'(t) = binormal*twist – tangent*curvature$) (see the Frenet Serret frame).
• A shortcut in 2d: integrating $atan(dy/dx)$ gives you the curvature function.
• You can also use the generic curvature formula (using the curve’s native parameterization, not the arc length one we present to the world): $k(t) = \frac{(f_x'(t)f_y”(t)y – f_y'(t)f_x”(t))} { pow(f_x'(t)^2 + f_y'(t)^2, 3/2)}$

Data Structures

Now that we know what a curve is, we can write a basic set of fundamental interfaces.

Definitions

• Vertex: a point in space. Stores a list of segments that use a given vertex (that are “around the vertex”).
• Valence: the number of segments around a vertex.
• Handle: A point in space that’s internal to a specific curve type
• Segment: A curve segment. Has at least two vertices and zero or more handles.
• Polygon Corner: A half-edge belonging to the boundary of a polygon.
• Boundary: A boundary belonging to a polygon. Boundaries add or subtract based on their winding; clockwise boundaries create solid polygons while counterclockwise ones create holes.
• Polygon: A list of curve boundaries defining a polygon (also called a path).

Note: if we were going into higher dimensions (e.g. representing volumes) we would add more half data structures (e.g. half-polygons).

Data Structures

We will use typescript interfaces to describe our data structures.

Vertex

interface Vertex {
  position: point
  segments: Segment[]
  
  /** If the number of segments is 2, 
      returns the segment that isn't `segment`.
      Throws if the number of segments is not 2.
   */
  getOtherSegment(segment: Segment);
}

Handle

interface Handle {
  position: point
  ownerSegment: Segment
}

Segment

enum ClosestPointModes {
  /** find closest point to start */
  Start = 0,
  /** find closest point to end */
  End = 1,
  /** find closest point to input position */
  Closest = 2,
  /** find all points normal to position on the curve */
  All = 3
}

interface ClosestPointResult {
  s: number
  position: point
}

interface Segment {
  start: Vertex
  end: Vertex
  handles?: Handle[]

  /** the first corner in the radial list around this segment */
  corner?: Corner
  
  /** 
    returns the other vertex in this segment.
    throws if `vertex` does not belong to this segment.
  */
  getOtherVertex(vertex: Vertex): Vertex

  /** 
    evaluate this curve at arc length distance `s`.
    
    we use 's' instead of 't' to differentiate arc length
    parameterized code
  */
  evaluate(s: number): point

  /** first derivative */
  derivative(s: number): point
  /** second derivativie */
  derivative2(s: number): point
  /** curvature */
  curvature(s: number): point
  /** for 3d curves, twist */
  twist(s: number): point

  /** 
    Calculate curve at stroke offset `offset` on side of curve `side`.
    Note: this could be a generic utility function instead of a method.
   */
  evalAtStroke(s: number, side: 1 | -1, offset: number): {
    position: point
    /** derivative suitable for hermite interpolation */
    derivative: point
  }

  /* find closest point[s] on curve */
  closestPoint(mode: ClosestPointModes, position: point): ClosestPointResult[]  
}

Corner

Corners are circular doubly-linked list nodes in two lists, polygon boundaries and segments. We call the list of corners around a segment the “radial lists”.

interface Corner {
  vertex: Vertex
  /** the segment this corner belongs to */
  segment: Segment
  /** the boundary this corner belongs to */
  boundary: Boundary

  /** linked list node for the boundary this corner belongs to */
  boundaryNext?: this
  boundaryPrev?: this

  /** linked list for the radial list this corner belongs to */
  radialNext?: this
  radialPrev?: this
}

Boundary

interface Boundary {
  polygon: Polygon
  startCorner: Corner

  /** the number of corners in this boundary */
  readonly length: number
}

Polygon

interface Polygon {
  boundaries: Boundary[]
}

Practical Use Cases

Stroking A Curve

Given an arc length curve we can compute a stroke offset fairly easily. We can put more or less effort into this (e.g. eliminate cusps), but the simplest method is to compute a point offsetted from a curve along with a derivative we can use for hermite interpolation later:

This can be implemented as a generic function.