I recently added text support to the scad-clj 3D modeling library and encountered an interesting bug:
See that 4? No hole! Why?!? All the other holes are there…
First, let’s look at how you get the outline of some text in a font in Java:
1 2 3 4 5 6 7 8 9 10
We end up with a
PathIterator that traces along the outline of the character. This code uses the version of
getPathIterator that specifies “flatness”, which means that we get back a path strictly made up of straight line segments that approximate the curves.
Characters that are made from a single filled polygon are relatively easy; there is a single path and the bounded area is what gets filled:
The complexity comes when the path crosses over itself or if it is discontinuous and contains multiple outlines:
The JavaDocs for PathIterator explain a bit about how to actually determine what is inside the path. All of the fill areas are determined using the
WIND_EVEN_ODD rule: a point is in the fill area if it is contained by an odd number of paths.
For example, the dotted zero is made up of three paths:
- The outline of the outside of the oval
- The outline of the inside of the oval
- The outline of the dot
The points inside #1 but outside #2 are in 1 area and the points inside #3 are inside 3 areas.
For each path, we need to count how many other paths contain it. One way is to use
java.awt.geom.Path2D.Double to make a Shape and then use the
contains(double x, double y) method to see if any of the points from the other paths are in it.
I incorrectly assumed that each Shape contained at least one of the points that define it’s outline. It usually does, which is why all the other holes were properly rendered, but it doesn’t for some shapes, including triangles in certain orientations!
The JavaDoc for Shape says that a point is considered to lie inside a Shape if and only if:
- It lies completely inside the Shape boundary or
- It lies exactly on the Shape boundary and the space immediately adjacent to the point in the increasing X direction is entirely inside the boundary or
- It lies exactly on a horizontal boundary segment and the space immediately adjacent to the point in the increasing Y direction is inside the boundary.
The three points defining the triangle that form the hole in 4 don’t meet any of these criteria, so instead of counting as being in 2 paths (itself and the outer outline), it was counted as being in 1. The fix was to explicitly define a path as containing itself.