Lessons From Using Clipper
Posted On: 2021-08-02
Whenever I learn a new tool, I aim to document what I've learned on this blog, both for others' benefit as well as for my own (just in case I forget anything). For today's post, I'll be doing that for the polygon manipulation tool Clipper - covering three lessons I've learned through my own efforts and mistakes attempting to use it.
Order Matters
When offsetting a polygon, you can pass one or more paths to Clipper, and Clipper will use the combination of all those paths when creating the offset. A path is simply an ordered list of vertices (basically a connect-the-dots for the the shape you want to use.) If you're using one path, that's all you need: with the right vertices, Clipper will produce the right shape. When using multiple paths, however, things become quite different, as it's possible that two paths that individually work correctly will completely fail when combined together - all depending upon their orientation.
In Clipper, the orientation of a shape is determined by the combination of the order of the vertices and the direction of the y-plane (whether up is positive y or negative y). Since up is positive y in Unity, paths provided to Clipper should have their vertices ordered so that their vertices are in a counter-clockwise order - doing so will ensure that Clipper is able to combine the polygons together correctly. Perhaps just as important, however, is that any holes inside a polygon should be specified using the opposite orientation (that is, clockwise) in order for Clipper to correctly understand the shape. This is, perhaps, something that is best explained using pictures:
With the correct orientation, multiple paths will be treated by Clipper as one combined shape.
Opposite orientation is used to designate a hole inside of another path.
When a path has the incorrect orientation, Clipper will produce incorrect results.
One caveat for this: Clipper will do its best to guess the correct orientation when provided with values that don't make sense. In the case of a single path, this will produce the correct orientation (which is why even wrongly oriented paths work by themselves.) When there are multiple paths, Clipper will pick an arbitrary outer-most path*, assume that one is correct, and then adjust all other orientations appropriately. As a result, it is possible for one incorrectly oriented path to invert all the other paths - if that one happens to be picked by Clipper.
If Clipper picks the incorrectly oriented path, it will invert all others.
Configure Arc Tolerance
When offsetting paths, Clipper supports several different join types which control how Clipper combines multiple paths together. As I generally want smooth movement around corners, I've thus far been using the the "round" join type, which smooths out many of the sharp angles on my geometry. Technically, the results are only approximations of curves, as it's represented as a series of points, but by default this approximation is far more detailed than I need. In fact, some of the points generated so close together that inconsistencies in Unity's physics simulation were larger than the distances between two adjacent points.
Fortunately, Clipper supports customizing this behavior through the arc tolerance property. By default, Clipper uses the most precise settings possible, which, as mentioned earlier, is far more precise than my code can support. Slightly increasing the arc tolerance (ie. up to 10x its normal value) decreases vertex count without producing any visible differences in the resulting curve. For my use case, however, I can easily go much higher (ie. 200x), without any observable issues (the distance between points would still be less than the distance the character moves in a single physics step.)
Correctness Impacts Performance
From the outset, I chose the worst performing way to use Clipper: every physics step I am calculating an offset from a combination of every collider in the scene. Unsurprisingly, this produced noticeable performance issues - at first. What is interesting about that, however, is that the more functional issues I resolved, the more the the performance improved. Fixing orientation issues and correctly setting the arc tolerance massively improved performance, and those combined with some minor correctness tweaks* have improved things to the point where there's no observable difference whether or not Clipper is running.
The current performance is, honestly, much better than I had expected. Going into this, I expected that Clipper (or my post-processing to use the results) would be too slow to run every physics step, so I'd been considering some performance boosting options (such using Unity's Job system to parallelize it.) While I'm not ruling out making such optimizations in the future, I am rather pleased that I don't have to bite that off right away. In my experience, it's always better to optimize the actual use case than a hypothetical one - and the best way to figure out which use case is appropriate is through actual use.
Conclusion
As you can see, simple mistakes or overlooking some configuration settings will produce incorrect results. What's more, both generating and using those incorrect results will perform significantly worse than they would otherwise. I hope that these observations have been interesting for you - whether you're considering using Clipper yourself or simply interested in seeing how lessons are learned through using a new tool.