Hi Jim.
> Then hopefully we can get to something with better memory and CPU costs.
I re-implemented the AA rasterizer twice more, with saving memory in
mind. The first version used a completely different algorithm for computing
crossings: It didn't do it incrementally. It just computed the t value
where B(t)-CurrentScanline=0 using newton's method, then it computed
the x value at this t, and that's the crossing. Because all our curves
were monotonic in x and y, we could guarantee that there was exaclty one
such t per scanline per curve. The initial x0 in Newton's method was
(scanline - y0)/(y1-y0) (where y1 and y0 are the y extrema of the curve).
This could be computed incrementally using just one addition per scanline,
and it worked very nicely in minimizing the iterations in Newton's method.
However, there still had to be at least one iteration, which came with at
least one multiplication and one division per scanline, which is much more
expensive than what adaptive forward differencing was doing. However, it
was still a bit faster than the adaptive forward differencing version,
probably since it didn't need to allocate ridiculous amounts of memory.
The memory usage of this was far better than anything we had had until then,
because for storing crossings it only needed 4*n bytes, where n is
the highest number of crossings on any scanline, as opposed to
4*numScanlines*n, which is what I had before. Since we store curves, instead
of the lines produced by flattening curves, this storage is also reduced by a
lot.
But then I found a way to implement adaptive forward differencing AND save
memory. So, what I have now has the same memory usage described above, but
it's also a little faster (even now, that I haven't optimized it at all).
The webrev containing this isn't up yet (but everything else in the last
webrev link I sent is pretty much the same as what I have now on my machine,
so feel free to look at Stroker.java).
> Can the untransform be eliminated in the case of scaling? (Whether just
> for uniform scaling, or maybe even for non-uniform scaling with no
> rotation or shearing?)
I'm glad you bring this up. I thought a bit about this, and the only thing
that causes problems in Stroker is that for some transformations, if we
feed Stroker the transformed curve, the width will not be constant throughout
the curve. Therefore we can eliminate the untransforming for every matrix
that keeps these lengths constant. This turns out to be any constant multiples
of orthogonal matrices. So, if the transformation is A=[[a,b],[c,d]], all we
have to do is check for a*b==-c*d && a*a+c*c==b*b+d*d. If this is the case,
we can just make the pathIterator of the shape do the transforming, and we can
forget all about it (which is great, since what's hurting us is the
transformation
of our output paths, not the untransformation of the input).
So, to answer your question, we can't eliminate the untransforming for non
uniform scalings, but we can eliminate it for rotations, uniform transforms,
and even for shears of the form [[1,b],[-b,1]].
> You rock then! A bug should be filed on closed JDK. Can you file it or
> send me your test case and I'll do it?
I filed it. Bug id: 6987950.
> > Thank you,
>
> Ummm... Thank *you*. You're doing all the good work here, I'm just
> sitting back, throwing out tiny crumbs of past experience and watching
> the ensuing woodchips fly with awe. I've had on my wish list for some
> time to be able to eliminate these last few closed source holdouts, but
> the quality of the Ductus code was so high that I never got motivated to
> try. Who knows now... ;-)
Well, I couldn't have done it without your help, so
Thank you,
Denis.
- "Jim Graham" wrote:
> Hi Denis,
>
> On 9/27/2010 7:43 AM, Denis Lila wrote:
> > Hi Jim.
> >> How much faster? I'm worried about this, especially given our
> tiled
> >> approach to requesting the data. What was the bottleneck before?
> >> (It's been a while since I visited the code - we weren't computing
> the
> >> crossings for every curve in the path for every tile being
> generated
> >> were we?)
> >
> > Not much faster. I'm working on someting better.
>
> > I'm not sure about the bottleneck, but what we were doing
> before is:
> > 1. Flatten (by subdividing) every curve so that we deal only with
> lines.
> > 2. Add each line to a list sorted by y0. When end_rendering was
> called
> > for each scanline we found the crossings of the scanline and every
> line
> > in our line list, which we used to compute the alpha for that
> scanline's
> > pixel row. All this would be put into RLE encoded temporary storage
> and it
> > would be read back and converted into tile form by
> PiscesTileGenerator.
> >
> > Speaking of which, would it not be better to get rid of
> PiscesCache and
> > just keep a buffer with the current tile row in Renderer.java. This
> would
> > be possible because the specification for AATileGenerator says the
> i
