Hi Laurent,
Did you consider adding a test with a completely degenerate path to make
sure that we don't have any state errors if all of the segments are
eaten by the "finite path" filter?
I like your approach. It is worth noting that:
- non-uniform scales are not common
- your "always overflow-filter path at device resolution" fixes the
issues with measuring overflow in user space that I pointed out in my
prior email and only does so at a likely small expense in terms of
non-uniform scale performance. Common cases will see no change (other
than the fact that you have new code in the path feeder).
With respect to the optimization that I gave a rough outline of. It is
true that:
- it should help eliminate all of the inverse transforms in the strokeTo
code
- the math is incomplete and would need some work
- it only targets the non-uniform case which may not be a high priority
- it would probably get rid of the entire TransformingPathConsumer
module, but that module is not complex or trouble-prone and seems to be
working fine
...jim
On 3/11/2016 2:14 PM, Laurent Bourgès wrote:
Jim,
Here is a webrev illustrating my 'simple' approach:
http://cr.openjdk.java.net/~lbourges/marlin/marlin-8144938.1/
Changes:
- MarlinRenderingEngine.strokeTo(): removed outat ie always call
src.getPathIterator(at) that ensures Marlin is working in device-space
coordinates; so pathTo() can filter out NaN / Infinity points
- TransformingPathConsumer2D: removed transformConsumer() and all its
related inner classes (simplification)
I will perform a MapBench benchmark focused on non-uniform
transformation to check the possible performance 'regression'.
Please give me your point of view on the NaN/Infinity overflow handling
that I think it is now correct as all path coordinates are in
the device-space.
I think you proposed an optimized approach to refine my solution and get
rid of all inverseDelta/delta transformations at all, does it ?
I am not sure to have understood all the maths here (after my first 2/3
reads) but it seems quite complex and I am a bit reluctant as computing
curve offsets or curved lengths seems to me very very tricky and
error-prone !
I think your advices are very interesting but I need more concrete
directions to try making changes myself in the Stroker / Dasher code.
What is the use case for non-uniform transformations ? how important is
it ? In other words, is it worth such effort ?
Do you have an alternative solution (simple) ?
Yes, if we can take a non-uniform transform and express the pen size
as a tilted ellipse, then we can supply the tilted ellipse
parameters to the stroker and it could perform device-space widening
of non-uniform pens. Basically, we have a method right now that
takes the dx,dy of a path and turns it into a unit vector, does a
simplistic 90 degree transform, and then scales it by the line
width. It looks something like (adapted from Stroker.computeOffset()):
mdx = dy / len(dx,dy) * halfwidth;
mdy = -dx / len(dx,dy) * halfwidth;
which is shorthand for:
(1) normalize dx,dy
(2) rotate dx,dy by 90 degrees
(3) multiply by half the transformed line width
What we'd need to do for the general case is:
(1) inverse delta transform to user space
(2) normalize dx,dy to unit vector
(3) rotate by 90 degrees
(4) scale by (half) user space line width
(5) transform back to device space
I agree.
(1) and (3) through (5) are all 2x2 transforms and they could be
able to be flattened into a single transform, but we have that pesky
normalize step at (2) that gets in the way. If not for that, we
could replace the contents of computeOffset with just a 2x2 matrix
multiply, but I punted when I looked at how to introduce the
normalization step. I'm pretty sure that (1) and (2) could be
swapped somehow because all we really have is an elliptical pen and
we should be able to take a normalized vector in device space and
compute a transform that rotates it to the proper orientation that
comes from "inverseTx, rotate90, Tx" and applies the proper scale,
but how to compute that? When done we'd just have a 2x2 matrix to
multiply by, but since the construction of that 2x2 matrix wasn't
immediately obvious from concatenating component matrices I punted
to other problems.
A bit lost, but globally I understand. Probably some degenated cases may
apperar (matrix inversion ?)
Another thing to consider is that dash length will vary based on
angle so we'd need a way to compute "user length of device dx,dy"
quickly. It's essentially computing "len(inverseTransform(dx,dy))",
which is:
udx = inverseMxx * dx + inverseMxy * dy;
udy = inverseMyx * dx + inverseMyy * dy;
return sqrt(udx * udx + udy * udy);
which is (renaming inverseM* to I*), and please check my math:
sqrt((Ixx * dx + Ixy * dy)^2 + (Iyx * dx + Iyy * dy)^2);
sqrt(Ixx*Ixx*dx*dx + 2Ixx*Ixy*dx*dy + Ixy*Ixy*dy*dy +
Iyx*Iyx*dx*dx + 2Iyx*Iyy*dx*dy + Iyy*Iyy*dy*dy);
sqrt( (Ixx*Ixx + Iyx*Iyx)*dx*dx +
2(Ixx*Ixy + Iyx*Iyy)*dx*dy +
(Ixy*Ixy + Iyy*Iyy)*dy*dy);
sqrt(K1 * dx * dx + K2 * dx * dy + K3 * dy * dy);
Will check later (as it is late here) but it looks correct.
For a uniform scale K1 == K3 == squared inverse scale and K2 == 0
and K1,K3 can then be factored out of the sqrt into a constant and
applied to the dash lengths instead.
which is only a little more complicated than a regular length
computation. Unfortunately, since the angle changes over the course
of a curve, it might prove a little tricky for the iterator that
computes the length of the dashes along the curve, but it could be
as simple as calling a different length method as it iterates.
It seems too simple to be true. I have doubts I can handle such changes
myself.
Besides, we should also check early if the transformation matrix
contains NaN or Infinity values avoiding the path iteration. I
advocate
it is an extreme case.
That could be a short-cut optimization, but it depends on how much
it costs compared to just letting the path degeneracy elimination
turn it all into a NOP segment by segment...
I agree this shortcut is only worth if it happens in reality...
To conclude tonight, I will run few benchmarks and am looking forward
your comments.
Cheers,
Laurent