[AD] [ alleg-Bugs-1692717 ] comment to polygon

["SourceForge.net" <noreply@xxxxxxxxxx>]

Bugs item #1692717, was opened at 2007-04-02 08:25
Message generated for change (Comment added) made by elias
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=105665&aid=1692717&group_id=5665

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: None
Group: None
Status: Open
Resolution: None
Priority: 5
Private: No
Submitted By: erno (scherno2000)
Assigned to: Nobody/Anonymous (nobody)
Summary: comment to polygon

Initial Comment:
1. rest(0) does not yield.
2. in fbcon.c console_users is incremented twice, but decremented only once.
3. If allegro application is run in console mode, and get_tty() returns 0 (running application from midnight commander), problems with threads created before fork().
4. If allegro application is run in console mode, from midnight commander, then the shell thinks the application is ended too early because of main process is killed in allegro initialization.

Please read the readme file in attached zip file.


----------------------------------------------------------------------

>Comment By: Elias Pschernig (elias)
Date: 2007-04-24 15:41

Message:
Logged In: YES 
user_id=32894
Originator: NO

I just committed your version to SVN (unmodified). Again, many thanks, I
wouldn't have thought polygon() would ever get fixed anymore :)

Oh, and btw., in case you have ideas how to get it to the previous speed,
please don't let anything stop you from implementing them.. but likely it's
not important, I tried it with a game which uses only polygon() for
graphics and couldn't notice any degradation.

----------------------------------------------------------------------

Comment By: erno (scherno2000)
Date: 2007-04-20 18:55

Message:
Logged In: YES 
user_id=1542934
Originator: YES

OK. I just proposed it because this functionality is already implemented,
just cannot be accessed.

----------------------------------------------------------------------

Comment By: Elias Pschernig (elias)
Date: 2007-04-20 17:39

Message:
Logged In: YES 
user_id=32894
Originator: NO

I see. And yes, drawing lines wouldn't be equivalent - but there's many
things which can't be done with Allegro's drawing primitives, so not sure
if there should be a polygon_ex like that. Would be worth discussing on the
mailing list though.

----------------------------------------------------------------------

Comment By: erno (scherno2000)
Date: 2007-04-20 17:32

Message:
Logged In: YES 
user_id=1542934
Originator: YES

I just wanted to say, if I'm drawing with the polygon(), and then I'm
drawing the edges with line(), then the edges overdraw the polygon and
possibly other edges.
I just wanted to say,if DRAW_MODE_XOR is set, the extended version I
proposed would not be equivalent with drawing the polygon and then the
edges, and more, the same result is very difficult to obtain.
Drawing just a polygonal line with the same color would be difficult too
by using just line() because of intersections and edge ends.

----------------------------------------------------------------------

Comment By: Elias Pschernig (elias)
Date: 2007-04-20 16:43

Message:
Logged In: YES 
user_id=32894
Originator: NO

What do you mean, edges are overdrawn with DRAW_MODE_XOR? Right now,
polygon() shouldn't do any overdrawing..

----------------------------------------------------------------------

Comment By: erno (scherno2000)
Date: 2007-04-20 14:50

Message:
Logged In: YES 
user_id=1542934
Originator: YES

The slowdown was expected because of the need of extended tests to make
the polygon() working for all the cases (concave and self intersecting
polygons too).
For convex polygons or not self intersecting polygons the algorithm could
be simplified.

About the extended version I proposed:
The drawing of filled polygon and then drawing the lines is not the same
with my proposition:
In "DRAW_MODE_XOR" mode the edges are overdrawn with polygon , and the
edge intersections and ends are three times overdrawn(polygon,and the edge
twice). The intersection of edges can be more pixels long.

In my proposition the inside of polygon is only drawn once, and the
polygonal line too. No color change at edge intersections and edge ends.
The _soft_poygon() works correctly.
You can view the difference between results by changing for testing
purpose in _soft_polygon() routine the color for edges (search the comment
"//drawing the edge" and below modify the color parameter for hfill()).

I don't want to change the behaviour of the current polygon() function,
just to have a polygon_ex() function too with an extra color parameter.


----------------------------------------------------------------------

Comment By: Elias Pschernig (elias)
Date: 2007-04-20 13:41

Message:
Logged In: YES 
user_id=32894
Originator: NO

About performance, I was drawing hexagons to a memory bitmap and measured
CPU time, results are:

30x30: 50%
300x300: 73%

That is, polygon() got quite a bit slower, but I'm for applying the patch
in any case, as the current polygon() is broken. And if anyone can provide
a patch to speed it up again we can just apply that patch. Myself, I'm not
really sure how polygon() works in general, it seems to walk the edges,
then create lists of horizontal segments and scramble them around somehow
and then draw some of them from time to time.. so I have no idea how to get
it back to the old speed.

----------------------------------------------------------------------

Comment By: Elias Pschernig (elias)
Date: 2007-04-20 13:06

Message:
Logged In: YES 
user_id=32894
Originator: NO

Cool, seems in the random triangle bounding box test, it reached
perfection. Guess I'll have to come up with a better test now, maybe bigger
polygons, and not only triangles.. :)

About the outline polygons, I guess it will be a bit complicated. Right
now everything is drawn with hline, but you would then need to draw the
leftmost and rightmost pixels in a different color. I'm also not sure what
would happen with self-intersecting polygons.

And in most cases where it would be useful, you can already first draw the
filled polygon, then draw over it with a series of line() commands.

----------------------------------------------------------------------

Comment By: erno (scherno2000)
Date: 2007-04-20 11:30

Message:
Logged In: YES 
user_id=1542934
Originator: YES

I used your test program, and found the bounding box error.
I only changed the edge->w calculation, the error was caused by rounding
errors.
I send the new diff file. 

Maybe it would be useful to define an extended version of polygon() with 2
color parameters, instead of one:
one for inside of polygon, and another for the edges. The only
modification in _soft_polygon() would be to give a new parameter color2 and
to change the edge drawing color to color2. If the color would be -1, then
the drawing could be ignored. This extended version could draw only the
inside of polygon if color2==-1, only the edges if color==-1, like now if
color==color2, or inside of polygon and eges with different colors.
 

File Added: temp.zip

----------------------------------------------------------------------

Comment By: Elias Pschernig (elias)
Date: 2007-04-19 17:36

Message:
Logged In: YES 
user_id=32894
Originator: NO

Thanks, I couldn't find anything resulting in a regression from the 4.2
version, so far. Will do a bit more testing and also again performance
testing, and if I can't find anything else and performance won't drop too
much, I'll commit it :)

If someone is interested, below is a code snippet which draws small random
triangles and does an automated test on them. The test only checks if the
polygon's bounding box is the same as a bounding box around the three
vertexes. The 4.2 version fails almost always, the latest patch only fails
sometimes.. so there is still room for improvement, but it's a lot better
than 4.2 in any case.

#include <allegro.h>
#include <stdio.h>

void draw(BITMAP *bmp)
{
    clear_to_color(bmp, 15);

    int x, y;
    for (y = 0; y < 480; y += 32)
    {
        for (x = 0; x < 640; x += 64)
        {
            int ix = x + 4;
            int iy = y + 4;
            int v[] = {
                ix + rand() % 56, iy + rand() % 24,
                ix + rand() % 56, iy + rand() % 24,
                ix + rand() % 56, iy + rand() % 24,
            };
            int xl = MIN(v[0], v[2]); xl = MIN(xl, v[4]);
            int yt = MIN(v[1], v[3]); yt = MIN(yt, v[5]);
            int xr = MAX(v[0], v[2]); xr = MAX(xr, v[4]);
            int yb = MAX(v[1], v[3]); yb = MAX(yb, v[5]);
            drawing_mode(DRAW_MODE_SOLID, NULL, 0, 0);
            line(bmp, v[0], v[1], v[2], v[3], 0);
            line(bmp, v[2], v[3], v[4], v[5], 0);
            line(bmp, v[4], v[5], v[0], v[1], 0);

            drawing_mode(DRAW_MODE_XOR, NULL, 0, 0);
            polygon(bmp, 3, v, 1);

            int outside = 0;
            int l = 0, t = 0, r = 0, b = 0;
            for (iy = 0; iy < 32; iy++)
            {
                for (ix = 0; ix < 64; ix++)
                {
                    int c = getpixel(bmp, x + ix, y + iy);
                    if (iy < 4 || iy >= 28 || ix < 4 || ix >= 60)
                    {
                        if (c != 15) outside++;
                    }
                    if (x + ix == xl && c == 1) l++;
                    if (y + iy == yt && c == 1) t++;
                    if (x + ix == xr && c == 1) r++;
                    if (y + iy == yb && c == 1) b++;
                }
            }
            int missing = (!l) + (!t) + (!r) + (!b);
            printf("%2d/%2d: %3d %3d %3d %3d %3d %3d: %d %d\n", x / 64, y
/ 32,
                v[0], v[1], v[2], v[3], v[4], v[5], outside, missing);

        }
    }
}

int main(void)
{
    allegro_init();
    install_keyboard();
    install_timer();

    set_gfx_mode(0, 640, 480, 0, 0);
    RGB rgb = {63, 0, 0, 0};
    set_color(1, &rgb);

    BITMAP *b = create_bitmap(640, 480);

    while (1)
    {
        draw(b);
        blit(b, screen, 0, 0, 0, 0, 640, 480);
        int k = readkey();
        if ((k & 255) == 27) break;
    }
    return 0;
}


----------------------------------------------------------------------

Comment By: erno (scherno2000)
Date: 2007-04-19 14:46

Message:
Logged In: YES 
user_id=1542934
Originator: YES

I send a new version with overdraw corrected.
Please verify it.

File Added: temp.zip

----------------------------------------------------------------------

Comment By: Elias Pschernig (elias)
Date: 2007-04-15 14:07

Message:
Logged In: YES 
user_id=32894
Originator: NO

I didn't look at the code change, but in this version, some pixels get
overdrawn. Try e.g. adding this line before my last test polygon:

drawing_mode(DRAW_MODE_XOR, NULL, 0, 0);

This did work before that last change for the single line, so I guess you
just forgot to consider pixel overdraw when you simplified the algorithm
(?)

----------------------------------------------------------------------

Comment By: erno (scherno2000)
Date: 2007-04-13 16:12

Message:
Logged In: YES 
user_id=1542934
Originator: YES

I made the modification to show the single line too.
I simplified the algorithm.
Please check now.

File Added: temp.zip

----------------------------------------------------------------------

Comment By: Elias Pschernig (elias)
Date: 2007-04-12 15:05

Message:
Logged In: YES 
user_id=32894
Originator: NO

Wow, you're great! I looked at lots of random triangles, the one below
(i.e. all points lie on a horizontal line) was the only one which looked
unexpected. The current polygon() does it that way as well, so it wouldn't
be a big issue, maybe you have an idea about it? In any case, all other
triangles seemed perfect.

I also tried some translucent, self-intersecting and clipped polygons
(much less rigorously than the triangle test above though..), seems they
all keep working.

#include <allegro.h>

int main(void)
{
    allegro_init();
    install_keyboard();
    install_timer();

    set_gfx_mode(0, 640, 480, 0, 0);

    clear_to_color(screen, 15);

    int v[] = {
        10, 20,
        20, 20,
        30, 20,
    };
    putpixel(screen, v[0], v[1], 0);
    putpixel(screen, v[2], v[3], 0);
    putpixel(screen, v[4], v[5], 0);
    polygon(screen, 3, v, 12);

    readkey();

    return 0;
}

----------------------------------------------------------------------

Comment By: erno (scherno2000)
Date: 2007-04-12 14:31

Message:
Logged In: YES 
user_id=1542934
Originator: YES

OK.
 I corrected this too. I hope there are no more bugs.
I send attachment.
File Added: temp.zip

----------------------------------------------------------------------

Comment By: Elias Pschernig (elias)
Date: 2007-04-11 15:23

Message:
Logged In: YES 
user_id=32894
Originator: NO

The previous test now looks perfect, but I made some more tests, and look
for example at this:

#include <allegro.h>

int main(void)
{
    allegro_init();
    install_keyboard();
    install_timer();

    set_gfx_mode(0, 640, 480, 0, 0);

    clear_to_color(screen, 15);

    int v[] = {
        60, 43,
        30, 42,
        23, 40,
    };
    putpixel(screen, v[0], v[1], 0);
    putpixel(screen, v[2], v[3], 0);
    putpixel(screen, v[4], v[5], 0);
    polygon(screen, 3, v, 12);

    readkey();

    return 0;
}

Now, in the old version, it is missing the bottom pixels again, but it's
at least connected - so the patched version looks worse.

In any case, don't feel pushed to work on this, it may very well be that
the whole concept of the current polygon drawer is flawed, and fixing the
bottom pixels issue might even require a full rewrite.

----------------------------------------------------------------------

Comment By: erno (scherno2000)
Date: 2007-04-11 12:19

Message:
Logged In: YES 
user_id=1542934
Originator: YES

About polygon.c

I send corrected version for polygon.c in attachment.
I adjusted the offsets. If you can, make more tests.
File Added: temp.zip

----------------------------------------------------------------------

Comment By: erno (scherno2000)
Date: 2007-04-10 17:05

Message:
Logged In: YES 
user_id=1542934
Originator: YES

Yes, this is a problem. The things get worse if the triangle is more
elongated. 

{
 10,10,
 50,20,
 30,30
}


I think this is because of  offset added in fill_edge_structure() that are
different if edge->dx is positive or negative. I think the problem can be
solved adjusting the offset, if direction is negative.
I have no more time today, I will test it tomorrow.


----------------------------------------------------------------------

Comment By: Elias Pschernig (elias)
Date: 2007-04-10 16:30

Message:
Logged In: YES 
user_id=32894
Originator: NO

Actually, played some more with it, and this patch doesn't fix the
problem, e.g. the following polygon now looks worse than before.. do you
have any ideas why?

#include <allegro.h>

int main(void)
{
    allegro_init();
    install_keyboard();
    install_timer();

    set_gfx_mode(0, 640, 480, 0, 0);

    clear_to_color(screen, 0);

    int v[] = {
        10, 10,
        30, 20,
        10, 30
    };
    polygon(screen, 3, v, 12);

    readkey();

    return 0;
}

----------------------------------------------------------------------

Comment By: Elias Pschernig (elias)
Date: 2007-04-10 16:12

Message:
Logged In: YES 
user_id=32894
Originator: NO

I think I understand. In my tests, polygon() got slightly slower by this -
I wonder if there's a way to fix it in a way which doesn't cause a
slowdown.

I committed it in any case, having polygon finally work correctly is more
important than being fast. Now as for possible glitches in old programs who
work around the bug - we can just revert if it turns out to be a real
problem.

----------------------------------------------------------------------

Comment By: erno (scherno2000)
Date: 2007-04-10 15:29

Message:
Logged In: YES 
user_id=1542934
Originator: YES

I try to describe the main idea in my loop:

The old _show_polygon() works fine excepting the bottom lines or vertices,
where are missing points, or horizontal lines.
You can imagine the same polygon mirrored by a horizontal axis. Then every
bottom will be top, and every top will be bottom. The same algorithm will
give correct results for every line, that is not bottom on the mirrored
polygon, or equivalently, not on the top of the original polygon.
Making an union of drawn segments of corresponding lines of original and
mirrored polygons, will give correct results for any case.
The algorithm makes exactly this:
The first
  if(edge->bottom != c)
  {
    up=1-up;
  }
simulates drawing like in original algorithm ignoring bottoms(they were
discarded before in original algorithm), if up==1 then is must be drawn,
else no.

The second
  if(edge->top != c)
  {
    dn=1-dn;
  }
simulates drawing of the same line, but viewed as the mirrored polygon.
The bottom of mirrored polygon is top on the original.
If dn==1 should draw, else no.

The next if checks if the union of up and dn is a beginning of a
horizontal line(if last up+dn==0 and current up+dn!=0) then must begin a
new line and x is saved.
If last up+dn!=0 and current up+dn==0, then line ends, and it will really
draw in the bitmap from saved x to the endpoint.

I hope you understand my not too good English.

----------------------------------------------------------------------

Comment By: Elias Pschernig (elias)
Date: 2007-04-10 13:41

Message:
Logged In: YES 
user_id=32894
Originator: NO

The result of the polygon test looks nice, I'm not sure I follow the
change though.. could you describe what was wrong in the edge loop and how
you fixed it?

----------------------------------------------------------------------

Comment By: Milan Mimica (mmimica)
Date: 2007-04-10 13:11

Message:
Logged In: YES 
user_id=1171214
Originator: NO

Commited the fix for the display_switch_lock() problem. Thanks!

----------------------------------------------------------------------

Comment By: erno (scherno2000)
Date: 2007-04-10 12:16

Message:
Logged In: YES 
user_id=1542934
Originator: YES

I agree with you.
I corrected the polygon.c, now should be correct.
I sent the new polygon.c and the diff file too, with the test program.

About console: I discovered another dependency: when set_gfx_mode is
called, then console mus't be already initialized, because
display_switch_lock uses __al_linux_console_fd.
I corrected this by defining the sys_linux_save_console_state() and
sys_linux_restore_console_state() in lsystem.c.

For files see the attachment.

File Added: temp.zip

----------------------------------------------------------------------

Comment By: Elias Pschernig (elias)
Date: 2007-04-06 09:51

Message:
Logged In: YES 
user_id=32894
Originator: NO