[RIC] Incorrect Polygon output

[spillerrec]

Today I started on implementing fill_shape for the RIC polygon opcode. However I found quite a bit of issues with the original implementation. This is what I expected as output for my ricfile "poly.ric":

poly.wanted.gif (729 Bytes) Viewed 5602 times

I created this image by drawing the outlines (i.e. without fill shape) and manually filling the polygons. However when I ran this file on the NXT this is what I got:

poly.nxt.gif (901 Bytes) Viewed 5602 times

(The red color is "wanted", the black overlay is "NXT".)
The non-filled polygon have XOR enabled, this shows that it draws some pixels multiple times. The upper-left polygon is an extreme case of this.
The three polygons to the right are just incorrectly filled, since the edges doesn't match up. The biggest issues is the missing corners though.
I got it to work quite a bit better in RICcreator, but the edges are still not perfect:

poly.riccreator.gif (814 Bytes) Viewed 5602 times

I'm a bit stuck here, the formula simply doesn't doesn't give the right results, but I don't know what I should replace it with...

I know how to fix the issue with XOR, but I'm not going to do it before I know it is going to be fixed in the firmware. The solution is simply to bothersome and because of the firmware size restrictions I'm not sure if it is even worth fixing.
I fixed another XOR issue though, not occurring in this test image. The attachment rules are quite annoying though, so I can't attach them to this post.

[spillerrec]

I have managed to get an almost exact result, I just have to fix a single special case.

John used a scan-line fill algorithm implemented by Darel Rex Finley (released in public domain (link) ).
Darel left out some exceptions which require special handling though, which is one of the reasons the results are sub-optimal. Another is that most drawing code doesn't take the merging options which exists in the NXT firmware in account, which require special handling for a few extra cases.

The most critical issue however lies in the very algorithm and surprisingly I couldn't find anyone who seems to care about this.
Since the algorithm is scan-line based, it draws one line at a time. It calculates the x-value to all the intersections with the polygon on that line. Then it sorts those x-values and connects them with lines using a check-pattern.
However consider this line:

line.gif (1.16 KiB) Viewed 5588 times

Notice how several pixels are drawn for each y-value. The algorithm just calculates one x-value, which is the one in the center.
If you need to fill from the left side, you have to calculate the pixel to the right, if you need to fill from the right side you need to calculate the pixel to the left. But when the algorithm calculates the value, it doesn't know which side needs to be filled!

To workaround this I simply calculate both values and store them in a struct, so the correct pixel can be decided when it starts drawing. I can't figure out how to calculate these two pixels however. (Right now I detect them with brute force, checking each pixel which works quite well, but it is ugly.)
Can anyone help me with how to calculate this? I tried a few things but it didn't quite work out... Once I get this sorted out I will finish my implementation up and make it more C/NXT friendly.

Here are my test files (now that I'm able to attach them):

rics.zip

(4.01 KiB) Downloaded 169 times

[afanofosc]

I am very interested in this but I have a hard time considering it to be a high priority issue. It only affects drawing over existing set pixels with XOR or NOT, right? Or maybe just XOR? And I haven't heard much in the way of feedback from people using the extended drawing abilities of the enhanced firmware so I kind of doubt polygon drawing is used much generally - and almost certainly extremely rarely, if ever, used in RIC files.

John Hansen

[spillerrec]

With unfilled polygons it is only an XOR issue, however with filled polygons it is quite different. There are a few XOR issues, but they are minor and easy to fix. The major issues appears with NORMAL, AND and OR too. Here is a closeup of a polygon in poly.ric which does not have XOR issues:

poly.gif (1.67 KiB) Viewed 5573 times

The red is expected, blue is actual, purple is both.
The edges and entire upper line isn't drawn at all. And pretty much all of the sides are calculated incorrectly. It is quite noticeable with polygons which intersects itself, as the sides often doesn't match up after the intersection.

And I haven't heard much in the way of feedback from people using the extended drawing abilities of the enhanced firmware so I kind of doubt polygon drawing is used much generally - and almost certainly extremely rarely, if ever, used in RIC files.

I have never really seen it used either (other than my own poly-line usage), but it does have quite some potential. I would like to try out a simple 3D implementation with it sometime, now that I actually know how 3D works.
Anyway, since nxtRICedit doesn't support polygons (or ellipses), just creating those in RIC files has been difficult.

[afanofosc]

Can you post a small NXC program that draws this polygon either filled or unfilled? I assume that outside of RIC drawing it is as wrong as it is inside RIC drawing.

John Hansen

[spillerrec]

Yes, it is the same.

Code: Select all

task main(){
 LocationType points[] = { {51, 11}, {59, 32}, {45, 32}, {68, 17}, {68, 5}, {80, 30} };

 for(;;){
   ClearScreen();
   PolyOut( points );
   Wait( 500);
   while( !ButtonPressed( BTNCENTER, false ) );
   ClearScreen();
   PolyOut( points, DRAW_OPT_FILL_SHAPE );
   Wait( 500);
   while( !ButtonPressed( BTNCENTER, false ) );
 }
}

Apparently I had XOR turned on when creating the image in my previous post, but as you will see it is just one pixel that is different with XOR.

[afanofosc]

I am inclined to just live with these flaws in the polygon drawing support that I added to the enhanced NBC/NXC firmware. Do you think there are strong arguments for not just living with them? It would save both of us a good deal of time and energy and the huge sea of polygon-drawing users of the enhanced NBC/NXC firmware will likely not be very annoyed.

John

[spillerrec]

I have now written an implementation which renders filled polygons as the expected result. It shouldn't be too difficult to port this code to C (from C++). So is there a reason not to fix it?
There is one thing to note however. I use the following two functions to calculate the pixels in a line:

Code: Select all

int line_x( int x1, int y1, int dx, int dy, int y ){
	return (int)( (double)( dx * ( y - y1 )) / (double)dy + x1 + 0.5 );
}
int line_y( int x1, int y1, int dx, int dy, int x ){
	return line_x( y1, x1, dy, dx, x );
}

While I believe they are correct, they are not creating the exact same output as the firmware in a few cases. So if exacts results are wanted, either these functions needs to be adjusted to match LineOut(), or LineOut() needs to be adjusted to match these functions.


I'm also trying to fix the XOR issues with unfilled polygons, however I just started on this so no results yet.