Hi Denis,
On 8/24/2010 3:35 PM, Jim Graham wrote:
As far as flattening at the lowest level when doing scanline conversion,
I like the idea of using forward differencing as it can create an
algorithm that doesn't require all of the intermediate storage that a
subdividing flattener requires. One reference that describes the
technique is on Dr. Dobbs site, though I imagine there are many others:
http://www.drdobbs.com/184403417;jsessionid=O5N5MDJRDMIKHQE1GHOSKH4ATMY32JVN
Just to provide a basic overview...
You can iterate a line with a constant delta-T using:
x += dx;
y += dy;
Similarly, you can iterate a quad curve with a constant delta-T using:
dx += ddx;
x += dx;
dy += ddy;
y += dy;
and a cubic using:
ddx += dddx;
dx += ddx;
x += dx;
ddy += dddy;
dy += ddy;
y += dy;
There are then techniques to apply to evaluate the dd[d]x and dd[d]y to
see if the curve is "flat enough" for your particular needs. If it
isn't flat enough, then some simple math performed on the d* variables
can double or halve the sampling rate for a localized portion of the
curve. Once you pass the curvy section, you can then reduce the
sampling rate again by examining the d* variables.
Done right, this could probably be integrated at the innermost loop of
the renderer to reduce its storage requirements for curves, but that
would mean the inner loop would have to switch on the curve type to
determine which sampling equations apply (though you could simply have
quads have ddd[xy] = 0 and lines have dd[d][xy] = 0 and use a single set
of code perhaps without too much performance impact). Otherwise, this
could simply be used to flatten and produce edges with less intermediate
storage (and faster hopefully)...
...jim
