( dlaszlo | 2024. 10. 26., szo – 10:39 )

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. :) )