Font Wizard Algorithm
Steps for creating 3d Font Models
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:
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:
Home 3d Graphics howard.trickey @ gmail.com