Monday, December 20, 2010

Parallel Line Mouse Hinter Performance Improvements

Parallel Line historically was a problematic area. Excluding the parallel with axis code, the rest of code was at best problematic performance and correctness wise.
In the past we know how to test if your line was parallel with other line, but when we did extract the geometry of the shape was around the point of the shapes. In very old implementations we did match all points with all points, in pairs of two, which was the biggest section on profiling solver. So for a rectangle we would compare like 6 edges (four edges and diagonals). And for a box, eh, somelike 38 edges, having included all edges, internal and external diagonals. As around one month ago, parallelism computing was improved by just taking consecutive points on a shape (0,1), (1,2) (n-1, 0), so for a rectangle will compare with just 4 edges, and for a box, even some edges were erroneous, were just 8 to compare.
Today's change was two fold: correctness: we extract just edges, and not any edge, but edges that are straight, so a spline will not give to you parallel line to align with. In a similar manner, we also improve performance for sane cases: a rectangle and a parallelogram will have some edges that are parallel with each other (in our case two), so why not remove duplicates before are tested over and over again. Going back to a box shape, the comparison will be just for 3 axis, not 38. Another part is that the parallel data is specially prepared to not make any extra computation (in special creation of gp_Vec objects) that will improve the real time behavior.
Still not impressed? The initial "Lua gear", actually the Boo gear, will work with 20 instead of 160 edges to compare, this is done for 20 teeths (so close to 8x duplicates, in part easy to predict 4x, as 2x come from extrude and 2x from symmetrical OY shape). In general, is to be expected an improvement at least of 2x for 3D extruded shapes, but typically you will care more about design and less about time that a hinter may compute wrong parallel lines.

No comments: