Algoritmul lui Wu este un algoritm pentru descompunerea unui segment într-un raster cu anti- aliasing . A fost propus de Wu Xiaolin ( Xiaolin Wu , de unde și numele bine stabilit al algoritmului în rusă) într-un articol publicat de revista Computer Graphics în iulie 1991 . Algoritmul combină dealiasing de înaltă calitate și viteza apropiată de cea a algoritmului lui Bresenham fără anti-aliasing.
Liniile orizontale și verticale nu necesită anti-aliasing, așa că sunt desenate separat. Pentru restul liniilor, algoritmul lui Wu le traversează de-a lungul axei principale , potrivindu -se coordonatele de-a lungul axei non-principale într-un mod similar cu algoritmul lui Bresenham. Diferența este că în algoritmul lui Wu, nu unul, ci două puncte sunt setate la fiecare pas. De exemplu, dacă axa principală este X , atunci sunt considerate puncte cu coordonatele (x, y) și (x, y + 1) . În funcție de mărimea erorii, care arată cât de departe au mers pixelii față de linia ideală de-a lungul axei minore, intensitatea este distribuită între aceste două puncte. Cu cât punctul este mai departe de linia ideală, cu atât este mai mică intensitatea acestuia. Valorile intensității a doi pixeli se adună întotdeauna la unul, adică aceasta este intensitatea unui pixel exact pe linia ideală. O astfel de distribuție va oferi liniei aceeași intensitate pe toată lungimea sa, creând în același timp iluzia că punctele sunt situate de-a lungul liniei nu în două, ci câte unul.
Implementare în pseudocod (numai pentru x-line):
funcția plot(x, y, c) este // desenează un punct cu coordonatele (x, y) // și luminozitatea c (unde 0 ≤ c ≤ 1) funcția ipart(x) este o parte întreagă returnată a lui x funcția round(x) este return ipart(x + 0.5) // rotunjirea la cel mai apropiat număr întreg funcția fpart(x) este returnarea unei părți fracționale a lui x funcția draw_line(x1,y1,x2,y2) este dacă x2 < x1 atunci swap (x1, x2) swap (y1, y2) end if dx:= x2 - x1 dy := y2 - y1 gradient:= dy ÷ dx // punctul de pornire al procesului xend:= rotund(x1) yend:= y1 + gradient × (xend - x1) xgapg:= 1 - fpart(x1 + 0,5) xpxl1:= xend // va fi folosit în bucla principală ypxl1:= ipart(yend) plot(xpxl1, ypxl1, (1 - fpart(yend)) × xgap) plot(xpxl1, ypxl1 + 1, fpart(yend) × xgap) intery:= yend + gradient // prima intersecție în y pentru buclă // tratează punctul final xend:= rotund(x2) yend:= y2 + gradient × (xend - x2) xgap:= fpart(x2 + 0,5) xpxl2:= xend // va fi folosit în bucla principală ypxl2:= ipart(yend) plot(xpxl2, ypxl2, (1 - fpart(yend)) × xgap) plot(xpxl2, ypxl2 + 1, fpart(yend) × xgap) // bucla principală pentru x de la xpxl1 + 1 la xpxl2 - 1 do plot(x, ipart(intery), 1 - fpart(intery)) plot(x, ipart(intery) + 1, fpart(intery)) intery := intery + gradient repetarea funcției de încheiere