logoalt Hacker News

akoboldfryingtoday at 2:51 AM2 repliesview on HN

This was interesting, thanks. Was hoping to see a bit more about type hinting, but there's already a lot here.

A question about efficiency: IIUC, in your initial bitmap rastering implementation, you process a row of target bitmap pixels at once, accumulating a winding number count to know whether the pen should be up or down at each x position. It sounds like you are solving for t given the known x and y positions on every curve segment at every target pixel, and then checking whether t is in the valid range [0, 1). Is that right?

Because if so, I think you could avoid doing most of this computation by using an active edge list. Basically, in an initial step, compute bounds on the y extents of each curve segment -- upper bounds for the max y, lower bounds for the min y. (The max and min y values of all 3 points work fine for these, since a quadratic Bezier curve is fully inside the triangle they form.) For each of the two extents of each curve segment, add a (y position, reference to curve segment, isMin) triple to an array -- so twice as many array elements as curve segments. Then sort the array by y position. Now during the outer rendering loop that steps through increasing y positions, you can maintain an index in this list that steps forward whenever the next element crosses the new y value: Whenever this new element has isMin=true, add the corresponding curve segment to the set of "active segments" that you will solve for; whenever it's false, remove it from this set. This way, you never need to solve for t on the "inactive segments" that you know are bounded out on the y axis, which is probably most of them.


Replies

necovektoday at 8:01 AM

If I understood you correctly, this might be an issue if you have multiple strokes (so multiple mins and maxes that you need to stay within) on a row of pixels (think all strokes of an N).

show 1 reply
Mikhail_Edoshintoday at 7:48 AM

Thanks, I've bookmarked an article recently that I thought was about that, but haven't read it yet. Your explanation lays a very good foundation to understand that technique.