Re: [AD] Bug in arc()

["Eric Botcazou" <ebotcazou@xxxxxxxxxx>]

[I think that, for such patches that entirely revamp a big chunk of code,
using 'diff -c' instead of 'diff -u' might be better. But that's of course only
a personal opinion]

> Long ago we discussed a bug in arc() on [AL]. The attached patch is
> the same as I posted there, but with modifications suggested by Eric.
> (namely, using AL_PI instead of M_PI and allowing to use al_sincos()
> when it will be added).

Thanks for taking these into account.

> The routine is ~5% slower on my computer.

Never mind. Correctness is far more important here.

> The bugs were low precision when calculating angles and incorrect
> test for reaching the end of the arc. I uploaded my test program to
> http://home.student.uu.se/svsa1977/tmp/arctest.zip in case anyone
> needs it.

The bugs have indeed chilling effects in your test program! The patch looks
ok, except the following minor points:

+ /* polar_to_cartesian:
+  *  Does '*out_x = r * sin(a)', '*out_y = r * cos(a)', where r is an integer,
+  *  a is a fixed point angle, and *out_x and *out_y are integers.
+  */
+ static INLINE void _polar_to_cartesian(int r, fixed a, int *out_x, int *out_y)
+ {
+    double s, c;
+    double double_a = a * (AL_PI * 2 / (1 << 24));
+    s = sin(double_a);
+    c = cos(double_a);
+    s = -s * r;
+    c = c * r;
+    *out_x = (int)((c < 0) ? (c - 0.5) : (c + 0.5));
+    *out_y = (int)((s < 0) ? (s - 0.5) : (s + 0.5));
+ }

It looks like you swapped x and y in your header comment. And you didn't mention
either that y is flipped (here, not in do_arc). So I'd suggest to change the function
name to take this into account (and get rid of the formula in the header comment:
a single sentence in plain English is IMHO enough).

Moreover, underscored functions are reserved for global internal functions.

!    if (q > qe)
!       /* qe must come after q. */
!       qe += 4;
!    else if (q == qe)
!       /* If q==qe but the beginning comes after the end, make qe be
!        * strictly after q.
         */
+       if (((ang2&0xffffff) < (ang1&0xffffff)) ||
+    (((ang1&0xffffff) < 0x400000) && ((ang2&0xffffff) >= 0xc00000)))
+          qe += 4;

The (non-written ?) rule for Allegro is to count comments when deciding
whether to put {}.

!    while (TRUE) {
!       /* Change quadrant when needed.
!        * dx and dy determine the possible directions to go in in this
!        * quadrant, so they must be updated when we change quadrant.
         */

Is this 'in in' really needed ?

!       /* Are we in the final quadrant? */
        if (qe == q) {
!         /* Have we reached (or passed) the end point both in x and y? */
!         det = 0;
  
!         if (dy > 0) {
!      if (py >= ey)
!         det++;
!   }

Bad formatting.

!         if (dx > 0) {
!      if (px >= ex)
!         det++;
!   }

Ditto.

!        * These are reached by adding dx to px and/or adding dy to py.
!        * We need to find which of these points that gives the best
!        * approximation of the (square of the) radius.
!        */

Isn't 'that' superfluous here ?

!    /* Only draw last point if it doesn't overlap with first. */
!    if ((px != sx) || (py != sy) || (sq == qe))
!       proc(bmp, x+px, y+py, d);

...one.

--
Eric Botcazou
ebotcazou@xxxxxxxxxx