Step 1. Contours
The
contours for the letters are translated from TrueType form into closed piecewise
Bezier cubic splines. Here are the contours for an Arial "B".
TrueType characters use quadratic Bezier splines, and a process known as degree elevation turns them into cubics with exactly the same curves and on-curve points.
The contours are analyzed to see which ones are inside which other ones, to partition them into "pieces", each consisting of an outer contour and the other contours that are inside it. Using the filling rules of TrueType fonts, we can find points that are representative of holes (used in the next step). Each piece is handled separately in the remaining steps. Our "B" has only one piece, but an "i" would have two.
Step 2. Triangulation
Treating the
curves as straight line segments for now, the polygons are triangulated using a
procedure known as Constrained
Delaunay Triangulation. A Delaunay
Triangulation (DLT) of a set of points divides the plane into triangles (joining
all of the points) such that no point is inside the circumcircle of any other
triangle. A constrained DLT does as good a job as possible while making sure
that certain user-specified edges are in the triangulation (in our case, the
polygon edges).
I chose this triangulation because I thought it would lead to triangles with not-so-extreme angles in it. I wrote a simple triangulator that works by cutting off "ears" (triangles with two boundary edges and one diagonal), and then postprocessed the triangulation to swap (non-boundary) edges that violated the DLT condition.
Step 3. Quadrilateralization
Animation:Master patches render best if they are quadrilaterals rather than triangles, so the next step is to remove as many edges as possible from the triangulated polygon, to create quadrilaterals. There are several constraints:
- Only remove inner edges, not boundary ones.
- Remove at most one edge from a triangle, else pentagons will arise.
- Don't remove an edge that makes a resulting quadrilateral concave.
In addition, some edges are better to remove than others. It is better to create quadrilaterals whose maximum interior angle is small. It is better to remove edges from points that have a lot of edges attached to them already (A:M doesn't render well at high-density joins).
The method I
used to remove edges was to make an Edge
Removal Graph, with
vertices representing triangles in the triangulation, and edges joining
triangles that share an edge. Each edge is weighted according to the
desirability of removing that edge. If removing a shared edge between two
triangles would create a concave quadrilateral, the edge between those
triangle-representing-vertices is omitted from the edge removal
graph.
Next I find a Maximum Weighted Matching in the edge removal graph. The edges in the matching tell which triangles in the original triangulation are to be merged into quadrilaterals by removing the shared edge. No two edges in a matching touch the same vertex, so using a matching ensures that all our constraints are met. Using a maximum matching is a heuristic to help us end up with a nice looking set of quadrilaterals. Maximum Weighted Matching is a hard problem. I used some properties of the structure of the edge removal graph in our circumstances to make it more efficient, but even so, if the number of triangles is too big (currently, around 75) I just punt and use a greedy method to do the matching.
Step 4. Bevels
To make
bevels along the front and/or back edges, the contours are inset by the bevel
amount (before the above closing steps). I inset rather than outset because I
want to respect the silhouette desired by the font designer.
The inset edges should have a perpendicular distance from the original edges equal to the bevel amount. You get this by moving the vertices inward along the angle bisectors by an amount that requires a little trigonometry to figure out. Unfortunately, doing this blindly may cause the inset polygon to cross itself if the bevel amount is too big. Currently I do do it blindly, but in future I intend to calculate intersections of the angle bisectors and go from there (the ultimate result of this is a Straight Skeleton, which can lead to a stone-carved-letter look; see this paper for a discussion of straight skeletons). condition.
Step 5. Rounded Bevels
To
make rounded bevels, a careful adjustment of the tangent directions and
magnitudes along the side splines is needed. The pictures shows a detail of a
birdseye view of our B, showing rounded bevels.
I can also do side bevels now. To do them, the non-smooth vertices of the non-inset polygons are split into two vertices, cutting off the corner. Each of them is connected to the corresponding inset vertex, giving a triangle at the corner. Again, rounding the side bevels requires careful tangent matching.
Final Result
The
result of all of this is shown here, as textured with Andy
Whittock's
metallic material plugin: