PDF to HTML5 conversion – No Even-Odd Winding Rule for filling shapes in HTML5?

This is part 3 on this subject. If you haven’t already read the other articles, please read part 1 to understand the winding problem, and part 2 to understand how we get around the problem.

So to recap quickly: HTML5 only supports the Non-Zero winding rule, however PDF supports both Non-Zero and Even-Odd rules. This means that we need to output shapes filled using the Even-Odd rule as images, otherwise they may not display correctly.

But outputting all shapes filled using the Even-Odd winding rule as images is inefficient, and would create lots of images that would be better suited to being a HTML5 shape.

So what criteria should we use? The first thing we should think about is what type of shape will get affected by using the Even-Odd rule opposed to the Non-Zero rule. The answer is that either there are two or more shapes that overlap each other, or that there is a single shape whose path crosses over itself at least twice.

Both of these properties are relatively easy to search for. To test if there are two shapes that overlap, we just need to store each closed path as a separate shape, then check all closed paths within the shape to see if they intersect with each other. Similarly, we can take each segment in the shape and see if it crosses another segment.

The problem with that is that it would be computationally heavy, and would ruin our performance.

My next thought was to think about what commands could produce a shape that overlaps itself. If you have two squares that overlap, that would be 8 lineTo commands. If those squares were triangles, that is 6 lineTo commands. If those triangles were circles, then there would only be 4 bezierCurveTo commands. So we can ignore any shape that has less than 4 commands. That will exclude some shapes, but it’s not incredibly helpful.

It is clear that there is no perfect answer here. Our best bet is a compromise. The best criteria that I could think of was to check if the shape has a closed loop within. We can search for this very quickly; just see if any of our commands draw to where the shape started. It’s not perfect, but it seems to work quite well!

Of course, this could all be avoided if HTML5 supported the Even-Odd winding rule for filling shapes!