Adott egy klasszikus Breshenam vonalhúzó. Ez hibaértéket számol az alfa meghatározásához, az indulópontban és a végpontban ez a hiba 0 (tehát az alfa itt 255, egyáltalán nem átlátszó), a két pont között pedig megfelelően számítódik (és abból az alfa az "a" változóba).
Ezt kellene átalakítani úgy, hogy vegyen figyelembe egy induló és érkező hibaértéket. Tehát 0 helyett e0 hibaértékkel kéne indulnia, és 0 helyett e1 hibaértékre kéne érkeznie. Mindkét változó 0 és 255 közötti, az alábbi kód csak az e0 = 0 és e1 = 0 esetet kezeli most.
/* 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 */
err = dx*dx+dy*dy;
e2 = err == 0 ? 1 : 0xffff7fl/sqrt(err);
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;
}
}
}
Ha van kedve valakinek kibogarászni ezt, azért iszonyat hálás lennék (ha nagyon ráfeküdnék, biztos meg tudnám oldani, de az agyam most egy C fordító belső lelkivilágával van tele és nem akar átállni, folyton félreszámolom).
Egy Nyílt és Szabad Forráskódú projekthez kell, cserébe listáznám a megoldó nevét, mint kontributor és öregbíteném a hírnevét.
Hozzászólások
Utoljára 2004 környékén foglalkoztam C -vel, azóta csak java. Szóval, ha valami nagy baromság, akkor mea culpa.
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:
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.
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:
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:
Hanem ilyen:
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:
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:
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. :) )