Segítségkérés algebrai számoláshoz

Utoljára 2004 környékén foglalkoztam C -vel, azóta csak java. Szóval, ha valami nagy baromság, akkor mea culpa.

#include <stdio.h>
#include <stdint.h>
#include <math.h>
#include <stdlib.h>

void setpixel(int x, int y, uint8_t r, uint8_t g, uint8_t b, uint8_t a);

/* c[4] - szín, RGBA
 * x0,y0 - induló koordináta
 * x1,y1 - vég koordináta
 * e0 - induló hibaérték (0 és 255 között)
 * e1 -vég hibaérték (0 és 255 között)
 */
void line(uint8_t c[4], int16_t x0, int16_t y0, int16_t x1, int16_t y1, int16_t e0, int16_t e1) {
    int sx = x0 < x1 ? 1 : -1, sy = y0 < y1 ? 1 : -1, x2, a;
    int dx = abs(x1-x0), dy = abs(y1-y0), err, e2;

    if(!c[3] || (x0 == x1 && y0 == y1)) return;

    /* ide kéne valami okosság, ez az e0 = 0 és e1 = 0 eset,
     * err - két pont Descartes távolságának négyzete
     * e2 - távolság reciproka */

    // Kis távolságértékek használata esetén (e0 és e1 figyelembevétele)
    if (e0 > 0 || e1 > 0) {
        err = dx * dx + dy * dy;          // Két pont közötti távolság négyzete
        e2 = err == 0 ? 1 : 0xffff7f / sqrt(err);   // Távolság reciprokának kiszámítása

        // Az e0 kezdő hibaérték és e1 vég hibaérték figyelembevétele
        dx = (dx * e2 * e0) / 255;
        dy = (dy * e2 * e1) / 255;
        err = dx - dy;
    } else {
        err = dx * dx + dy * dy;
        e2 = err == 0 ? 1 : 0xffff7f / sqrt(err);  // Ha e0 és e1 0, alapértékek
        dx *= e2;
        dy *= e2;
        err = dx - dy;
    }

    while(1) {
        a = err-dx+dy; if(a < 0) a = -a;
        a = 255 - (a >> 16);
        /* a legelső iterációban itt most az a-nak (255-e0)-nak kéne lennie, a legutolsóban pedig (255-e1)-nek */
        a = a * c[3] / 255;
        setpixel(x0, y0, c[0], c[1], c[2], a);
        e2 = err; x2 = x0;
        if(2*e2 >= -dx) {
            if(x0 == x1) break;
            if(e2+dy < 0xff0000l) {
                a = 255 - ((e2+dy) >> 16); a = a * c[3] / 255;
                setpixel(x0, y0 + sy, c[0], c[1], c[2], a);
            }
            err -= dy; x0 += sx;
        }
        if(2*e2 <= dy) {
            if(y0 == y1) break;
            if(dx-e2 < 0xff0000l) {
                a = 255 - ((dx-e2) >> 16); a = a * c[3] / 255;
                setpixel(x2 + sx, y0, c[0], c[1], c[2], a);
            }
            err += dx; y0 += sy;
        }
    }
}

void setpixel(int x, int y, uint8_t r, uint8_t g, uint8_t b, uint8_t a) {
    printf("Pixel at (%d, %d) - Color RGBA(%d, %d, %d, %d)\n", x, y, r, g, b, a);
}

int main() {

    uint8_t color[4] = {255, 0, 0, 255};

    int16_t x0 = 2, y0 = 2;
    int16_t x1 = 8, y1 = 8;
    int16_t e0 = 50, e1 = 200;

    printf("Drawing line from (%d, %d) to (%d, %d) with e0=%d and e1=%d:\n", x0, y0, x1, y1, e0, e1);
    line(color, x0, y0, x1, y1, e0, e1);

    return 0;
}

Output:
Drawing line from (2, 2) to (8, 8) with e0=50 and e1=200:
Pixel at (2, 2) - Color RGBA(255, 0, 0, 255)
Pixel at (2, 3) - Color RGBA(255, 0, 0, 220)
Pixel at (3, 2) - Color RGBA(255, 0, 0, 140)
Pixel at (3, 3) - Color RGBA(255, 0, 0, 105)
Pixel at (4, 2) - Color RGBA(255, 0, 0, 25)
Pixel at (5, 2) - Color RGBA(255, 0, 0, 166)
Pixel at (6, 2) - Color RGBA(255, 0, 0, 51)
Pixel at (7, 2) - Color RGBA(255, 0, 0, 192)
Pixel at (8, 2) - Color RGBA(255, 0, 0, 77)

de nem inkabb az a problemad, hogy a 2 vegpontot most int-ben kell megadni, pedig igazabol azok float-ok, mert nem feltetlen a racspontban lesz a vege? es akkor az alpha is jol szamolodna...

Tehát ha jól értem, akkor

X1,Y1-X2,Y2-be akarsz húzni egy vonalat,
de A1-A2-ből is kell egy átmenet, annyi lépésben, amennyi pont kikerül a képernyőre.

Nekem neked magyarázom a vonalhúzót, hanem magamnak is leírom, hogy értsük meg mi történik:

A feladat itt, hogy az X vagy Y irányokból az egyikből mindig minden iterációban egyet lépünk.
A másik két irányból, meg amikor szükséges, akkor valamennyit.

Tehát van egy vonal:

XX....
..XX..
....XX

itt például X irányba mindig 1-et lépünk, Y irányba meg időnként.

Így lehet amúgy 8 irány ez alapján egy X-Y vonalhúzóval.

\ 1|2 /
 \ | /
8 \|/ 3
---+----    
7 /|\ 4
 / | \
/ 6|5 \

Tehát például az 5-ös iránynál:

Y irányba mindig egyet lépünk, dy-szor (y0-y1 közötti különbség). Az x0-x1 között a különbség dx:

dy = abs(y0 - y1)
dx = abs(x0 - x2)
for (y = y0; y < y1; y++) {
}

A Breshenam algoritmus lényege, hogy egész számokat használ. Emiatt bevezet egy "hibát" az legyen mondjuk err. Tehát a dx az kisebb most mint a dy (5-ös irány). Ha az err-hez hozzáadogatjuk a dx-et, és az eléri a dy-t, a vonalhúzó algoritmus szerint akkor kell az aktuális x értéket léptetni egyel, az err-ből pedig kivonni a dy-t. És a történet indul újra, de már a korrigált értékkel, mert megmaradt az err-ben a "hiba" ami a túlcsordulással keletkezett.

Azért, hogy ne ilyen legyen egy vonal:

X.....
.XXX..
....XX

Hanem ilyen:

XX....
..XX..
....XX

Az err kezdeti értéke a dy / 2

--

Gondoljuk tovább a rutint:
Ha Te A1-ből A2-be akarsz ugyanilyen módon vonalat húzni, neked akkor is az X vagy az Y irányba kell minden iterációban lépni egyet. Tehát például:

x0 = 0
y0 = 0
A0 = 0

x1 = 10
y1 = 2
A1 = 255

A probléma, ha ezt is a Bresenham algoritmussal közelítjuk meg, hogy ha az err2-höz (ami az alfához tartozik) adogatod hozzá a dA-t, van olyan eset is, amikor többször is túlcsordul dy-on (amerre mindig 1-et lépsz). (például a fenti paraméterek).

Itt ezt az irányt nem Bresenham algoritmussal kellene megoldani, hanem ha jól tudom DDA-nak hívják azt, amikor a kezdő A0-hoz egy tört részt is tartalmazó számot adogatsz hozzá minden iterációban.

Hogy ne kelljen float-okkal számolnod, és gyors legyen, ezt úgy szokták megoldani, hogy ha pl dy-szor kell az A-t növelned A0-ból A1-be, akkor dA-t felszorozzák, és ezt osztják le dy-el, tehát pl:

pl: n = (dA << 16) / dy

n a növekmény, ez az a szám, amivel minden iterációban növelned kell az a-t. Így az alsó 16 bit-ben lesz a törtrész, a felső 8 bitben (16-23-ig) pedig az A értéke.

Szerintem kombinálnod kell ezt a két algoritmust. PC-n egy osztás belefér.

Elvileg olyan nem fordul elő, hogy ha 0-255-ig akarsz egy átmenetet, akkor túlcsorduljon és a legutolsó pont megint 0 legyen, mert 255-lesz. (nem tud, mert tört részeket kezelsz az alsó 16 bitben).

Remélem nem írtam nagy hülyeségeket, még nem ittam meg a kávémat. :D A C rutinon jojózott a szemem. :)

(Még egy felvetés: nem tudom, hogy PC-n a Bresenham algoritmus a gyorsabb-e, vagy egyáltalán számít-e ez, lehet hogy simán mehetnél ezzel a másodikkal X vagy Y irányba is.
Ebben nincsenek elágazások sem elvileg, és csak egy plusz osztás az ára. - de ezt nem tudom, csak eszembe jutott. :) )

Azt hiszem [hogy] értem: nem egész koordinátáról (A+B/2 szeretnél indulni.

Tehát az kell neked, hogy a mostani algoritmus milyen értékeket vesz fel középen, és ezzel kell indulni.

A legegyszerűbb megoldás az lenne, hogy az (A+B)/2-ből visszaszámolod A-t (B ismert), és onnan indulsz, de csak A+B/2-től hívod a setpixel-t. Esetleg csak a legelső egész koordinátáig mész vissza.

A helyes megoldás pedig valóban az, hogy megérted az algoritmust és akkor tudod hogy milyen err, e2-vel kell indulni. (Ebben esetleg segíthet ha kiíratod (A+B)/2 környékén ezeket.