Алгоритм Ву — алгоритм для малювання ліній зі згладжуванням, був представлений в статті Ефективна техніка згладжування у липневому випуску видання Computer Graphics, а також в статті Швидке згладжування в червні 1992 в випуску Dr. Dobb's Journal.
Алгоритм Брезенхейма малює відрізок дуже швидко, але він не виконує згладжування. В додаток, він не може обробити ситуацію коли кінцеві точки мають не цілочисельні координати. Наївна спроба малювання зі згладжуванням вимагає багато часу, в той час як алгоритм Ву дуже швидкий (хоча й повільніший за алгоритм Брезенхейма).
Алгоритм
Горизонтальні та вертикальні лінії не вимагають ніякого згладжування, через це їх малювання виконується окремо. Для решти ліній алгоритм Ву проходить їх уздовж основної осі, підбираючи координати за неосновною віссю аналогічно з алгоритмом Брезенхейма. Відмінність складається в тому, що в алгоритмі Ву на кожному кроці встановлюється не одна, а дві точки. Наприклад, якщо основної віссю є Х, тоді розглядаються точки з координатами (х, у) і (х, у+1). В залежності від величини похибки, яка вказує як далеко відійшли піксели від ідеальної лінії за неосновною віссю, розподіляється інтенсивність між цими двома точками. Чим більше віддалена точка від ідеальної лінії, тим менша її інтенсивність. Значення інтенсивності двох пікселів завжди в сумі дає одиницю, тобто це є інтенсивність одного піксела, який точно потрапив на ідеальну лінію. Таке розподілення придасть лінії однакову інтенсивність по всій її довжині, створюючи при цьому ілюзію, що точки розташовані уздовж лінії не по дві, а по одній.
function plot(x, y, c) is plot the pixel at (x, y) with brightness c (where 0 ≤ c ≤ 1) function ipart(x) is return integer part of x function round(x) is return ipart(x + 0.5) function fpart(x) is return fractional part of x function rfpart(x) is return 1 - fpart(x) function drawLine(x1,y1,x2,y2) is dx = x2 - x1 dy = y2 - y1 if abs(dx) < abs(dy) then swap x1, y1 swap x2, y2 swap dx, dy end if if x2 < x1 swap x1, x2 swap y1, y2 end if gradient = dy / dx // handle first endpoint xend = round(x1) yend = y1 + gradient * (xend - x1) xgap = rfpart(x1 + 0.5) xpxl1 = xend // this will be used in the main loop ypxl1 = ipart(yend) plot(xpxl1, ypxl1, rfpart(yend) * xgap) plot(xpxl1, ypxl1 + 1, fpart(yend) * xgap) intery = yend + gradient // first y-intersection for the main loop // handle second endpoint xend = round (x2) yend = y2 + gradient * (xend - x2) xgap = fpart(x2 + 0.5) xpxl2 = xend // this will be used in the main loop ypxl2 = ipart (yend) plot (xpxl2, ypxl2, rfpart (yend) * xgap) plot (xpxl2, ypxl2 + 1, fpart (yend) * xgap) // main loop for x from xpxl1 + 1 to xpxl2 - 1 do plot (x, ipart (intery), rfpart (intery)) plot (x, ipart (intery) + 1, fpart (intery)) intery = intery + gradient end function
Зауваження: якщо на початку виявляється, що abs(dx) < abs(dy), тоді всі точки мають відображатись з переставленими x і y.
Див. також
Література
- Майкл Абраш (червень 1992). . Dr. Dobb's Journal. 17 (6): 139(7). Архів оригіналу за 1 березня 2010. Процитовано 31 липня 2010.
- Ву Сяолінь (липень 1991). Ефективна техніка згладжування. Computer Graphics. 25 (4): 143—152. .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algoritm Vu algoritm dlya malyuvannya linij zi zgladzhuvannyam buv predstavlenij v statti Efektivna tehnika zgladzhuvannya u lipnevomu vipusku vidannya Computer Graphics a takozh v statti Shvidke zgladzhuvannya v chervni 1992 v vipusku Dr Dobb s Journal Rozpodilennya intensivnosti pikselya v zalezhnosti vid vidstani do idealnoyi liniyi Demonstraciya algoritmu Vu Artefakti stisnennya v standarti jpeg z jogo dopomogoyu mozhlivo zrobiti chesnimi Malyuvannya liniyi zi zgladzhuvannyam iz vikoristannya algoritmu Vu Algoritm Brezenhejma malyuye vidrizok duzhe shvidko ale vin ne vikonuye zgladzhuvannya V dodatok vin ne mozhe obrobiti situaciyu koli kincevi tochki mayut ne cilochiselni koordinati Nayivna sproba malyuvannya zi zgladzhuvannyam vimagaye bagato chasu v toj chas yak algoritm Vu duzhe shvidkij hocha j povilnishij za algoritm Brezenhejma AlgoritmGorizontalni ta vertikalni liniyi ne vimagayut niyakogo zgladzhuvannya cherez ce yih malyuvannya vikonuyetsya okremo Dlya reshti linij algoritm Vu prohodit yih uzdovzh osnovnoyi osi pidbirayuchi koordinati za neosnovnoyu vissyu analogichno z algoritmom Brezenhejma Vidminnist skladayetsya v tomu sho v algoritmi Vu na kozhnomu kroci vstanovlyuyetsya ne odna a dvi tochki Napriklad yaksho osnovnoyi vissyu ye H todi rozglyadayutsya tochki z koordinatami h u i h u 1 V zalezhnosti vid velichini pohibki yaka vkazuye yak daleko vidijshli pikseli vid idealnoyi liniyi za neosnovnoyu vissyu rozpodilyayetsya intensivnist mizh cimi dvoma tochkami Chim bilshe viddalena tochka vid idealnoyi liniyi tim mensha yiyi intensivnist Znachennya intensivnosti dvoh pikseliv zavzhdi v sumi daye odinicyu tobto ce ye intensivnist odnogo piksela yakij tochno potrapiv na idealnu liniyu Take rozpodilennya pridast liniyi odnakovu intensivnist po vsij yiyi dovzhini stvoryuyuchi pri comu ilyuziyu sho tochki roztashovani uzdovzh liniyi ne po dvi a po odnij function plot x y c is plot the pixel at x y with brightness c where 0 c 1 function ipart x is return integer part of x function round x is return ipart x 0 5 function fpart x is return fractional part of x function rfpart x is return 1 fpart x function drawLine x1 y1 x2 y2 is dx x2 x1 dy y2 y1 if abs dx lt abs dy then swap x1 y1 swap x2 y2 swap dx dy end if if x2 lt x1 swap x1 x2 swap y1 y2 end if gradient dy dx handle first endpoint xend round x1 yend y1 gradient xend x1 xgap rfpart x1 0 5 xpxl1 xend this will be used in the main loop ypxl1 ipart yend plot xpxl1 ypxl1 rfpart yend xgap plot xpxl1 ypxl1 1 fpart yend xgap intery yend gradient first y intersection for the main loop handle second endpoint xend round x2 yend y2 gradient xend x2 xgap fpart x2 0 5 xpxl2 xend this will be used in the main loop ypxl2 ipart yend plot xpxl2 ypxl2 rfpart yend xgap plot xpxl2 ypxl2 1 fpart yend xgap main loop for x from xpxl1 1 to xpxl2 1 do plot x ipart intery rfpart intery plot x ipart intery 1 fpart intery intery intery gradient end function Zauvazhennya yaksho na pochatku viyavlyayetsya sho abs dx lt abs dy todi vsi tochki mayut vidobrazhatis z perestavlenimi x i y Div takozhAlgoritmi pobudovi vidrizka Algoritm Brezenhejma Algoritm DDA liniyiLiteraturaMajkl Abrash cherven 1992 Dr Dobb s Journal 17 6 139 7 Arhiv originalu za 1 bereznya 2010 Procitovano 31 lipnya 2010 Vu Syaolin lipen 1991 Efektivna tehnika zgladzhuvannya Computer Graphics 25 4 143 152 ISBN 0 89791 436 8