drawPolygon() from AAPolyScan.c doesn't render the last scanline of most polygons

[abainbridge]

There was previous discussion of this bug in #32

The reprocase is almost any polygon. I'll illustrate with a diamond shape.

The wrong logic hits when we're processing the final subpixel row in the main loop of drawPolygon(). Here's a picture showing which vertices vLeft, vNextLeft, vRight and vNextRight point to when we start the final iteration of the loop. The current subpixel row is highlighted in red.

The first code in the loop is while (y == VnextLeft->y). The condition is true, so we move vNextLeft on to vertex 3 - ie the left side we're walking is about to start going backwards up the right side of the poly. The next statements are, if (VnextLeft == Vright) return. The condition is true, so we exit the function. We should not exit because this scanline has a bunch of partially covered pixels in it that we haven't rendered yet. Instead we should break from this while loop and then do the "done, mark uncovered part of last scanline" code below, which already includes a return.

In all my testing, that "done, mark uncovered part of last scanline" code block is never executed. I think I've convinced myself the code is unreachable because of the if (VnextLeft == Vright) return above. Once I replaced the return with a break it is called but renders the last scanline one pixel too low. That is because the for-loop setting all the sub-pixel extents to -1 had the side-effect of incrementing y. So we need to add a -1 in the renderScanline() call. Because of the off-by-one bug here, I'm even more confident this code was unreachable in the original GG version.

One more change is needed. The if (VnextLeft == Vright) return that I removed had a comments saying all y's same? and (null) polygon. With it removed, if we pass in a poly with the same y value for all vertices, the function no longer terminates. The simplest fix for this I can see is to store y before the main loop (ie the minimum y of the poly), and change if (VnextLeft == Vright) return to:

if (VnextLeft == Vright) {
    if (y == minY) /* all y's same?  */
        return; /* (null polygon) */
    break;
}

Here's AAPolyScan.c with my fixes: AAPolyScan.zip

[abainbridge]

Here is the test harness with which I tested these changes: aa_poly_test11.zip

It is a Visual Studio 2013 project. It should be able to be imported into any newer version. There are 7 test cases. You can switch between them by pressing space when the program is running. You can alter the position of the poly by subpixel amounts by pressing the cursor keys. Ctrl++ and Ctrl+- zoom in and out. The last test is a fuzz test which randomly generates a new convex poly every time you press return. The random poly is rendered by the GG code and another simpler un-antialiased rasterizer. You can hold down return and watch as hundreds of random polys are generated and rendered.

[erich666]

It sounds like you've done due diligence on your proposed improvements to the code. I'm sorry I can't find Jack C. Morrison - last trace).

I tried out your new code *test11" and noticed one oddity. Zooming up the first test (chevron), I noticed this gap. This also happen with "test6", so perhaps this is expected behavior, that the two trapezoids are rendered separately and composited together, or something?

Reading the article itself, it seems like it should not have this sort of gap. Looking over the data in aa_poly_test.c, it seems like the chevron is defined without any gap. Is there some other phenomenon going on here? I decided to try the original code in its place, and new code is definitely better overall. Here's the original next to the new code, at the same zoom level (49 ctrl-+'s):

So, I conclude the new code's a lot better. If you have any insight into why there's still a lighter gap between the two "wings" of the chevron at certain zoom levels, great. Whatever the case, the new code works better, so I'd be happy to accept a pull request (or, if you prefer, I could just put your new AAPolyScan.c in place. I'm tempted to add the nice Visual Studio framework to the code, though - thoughts?).

[abainbridge]

I think the slight gap you noted is due to the way I'm painting the pixels. I'm doing alpha blending. When the bottom scanline of the first polygon is rendered it has, say, an alpha value of 50%. So in the resulting pixels' colors, 50% of the background color remains.

Then the top scanline of the second polygon is rendered over the top of the same pixels. It will also have an alpha value of 50%. After this pass of alpha blending the resulting pixel color will still have 25% of the original background color, when it ought to be 0%.

The bug here is that I shouldn't be doing alpha blending. I think the correct scheme would have to do a first pass, rasterizing both polygons into an alpha buffer, using additive blending, then a second pass to calculate the pixel color using the alpha buffer. I think there might even be a reference to this problem in the original text. I'm away from my computer and books at the moment so can't check.

On Mon, Oct 30, 2023, at 8:13 PM, Eric Haines wrote:

It sounds like you've done due diligence on your proposed improvements to the code. I'm sorry I can't find Jack C. Morrison - last trace https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=687920).

I tried out your new code *test11" and noticed one oddity. Zooming up the first test (chevron), I noticed this gap. This also happen with "test6", so perhaps this is expected behavior, that the two trapezoids are rendered separately and composited together, or something?

image https://user-images.githubusercontent.com/803995/279182959-7771c111-88da-4e4b-91d1-e6298eb13285.png

Reading the article itself, it seems like it should not have this sort of gap. Looking over the data in aa_poly_test.c, it seems like the chevron is defined without any gap. Is there some other phenomenon going on here? I decided to try the original code in its place, and new code is definitely better overall. Here's the original next to the new code, at the same zoom level (49 ctrl-+'s): image https://user-images.githubusercontent.com/803995/279183229-04b6c2b8-fa64-4e80-8f38-13e1a24791c7.png image https://user-images.githubusercontent.com/803995/279183281-cbcda69b-bd0d-4672-a7c3-eafd9a2be8ea.png

So, I conclude the new code's a lot better. If you have any insight into why there's still a lighter gap between the two "wings" of the chevron at certain zoom levels, great. Whatever the case, the new code works better, so I'd be happy to accept a pull request.

— Reply to this email directly, view it on GitHub https://github.com/erich666/GraphicsGems/issues/35#issuecomment-1785962934, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABGA3JKCVFO5HTNCOUAPWGDYCAC7JAVCNFSM6AAAAAA5VZN556VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTOOBVHE3DEOJTGQ. You are receiving this because you authored the thread.Message ID: @.***>

[erich666]

Oh, good, I was guessing it was two separate alpha blends. The original code definitely doesn't have that as a reason, and shows how your latest code is superior.

Anyway, good to know this about your viewer (and probably a reason to leave it out; that said, if you wanted to make a repo for it, I'd be happy to link to it somehow, maybe adding a comment line to the original code, near the top?).

[erich666]

I decided to take your new code in to fix this issue, noting this by adding a comment at the top: https://github.com/erich666/GraphicsGems/commit/4b8d63d7adca3f65f6a6023859eb753725923bf5 - let me know if you think more needs to be done. Thanks for all your diligence on this issue.

[abainbridge]

I don't think any more needs to be done. The diff looks good to me. Thanks for merging it.

On Sun, Nov 5, 2023, at 4:52 PM, Eric Haines wrote:

I decided to take your new code in to fix this issue, noting this by adding a comment at the top:4b8d63d - let me know if you think more needs to be done. Thanks for all your diligence on this issue.

— Reply to this email directly, view it on GitHub https://github.com/erich666/GraphicsGems/issues/35#issuecomment-1793789306, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABGA3JJJWK44NGEOWX3MHQDYC6Y4TAVCNFSM6AAAAAA5VZN556VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTOOJTG44DSMZQGY. You are receiving this because you authored the thread.Message ID: @.***>