![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Алгоритм Брезенхема растрової дискретизації відрізкаПри побудові растрового образа відрізка необхідно, насамперед, установити критерії "гарної" апроксимації. Перша вимога полягає в тому, що відрізок повинен починатися й кінчатися в заданих крапках і при цьому виглядати суцільним і прямим (при досить високому дозволі дисплея цього можна домогтися). Крім того, яскравість уздовж відрізка повинна бути однакової й не залежати від нахилу відрізка і його довжини. Ця вимога виконати складніше, оскільки горизонтальні й вертикальні відрізки завжди будуть яскравіше похилих, а постійна яскравість уздовж відрізка знову ж досягається на вертикальних, горизонтальним і нахилених під кутом в 45° лініях. І, нарешті, алгоритм повинен працювати швидко. Для цього необхідно по можливості виключити операції з речовинними числами. З метою прискорення роботи алгоритму можна також реалізувати його на апаратному рівні.
Рис. 10.1. Растровий образ відрізка У більшості алгоритмів використовується покроковий метод зображення, тобто для знаходження координат чергової крапки растрового образа наращивается значення однієї з координат на одиницю растра й обчислюється збільшення іншої координати. Завдання полягає в побудові відрізка, що з'єднує на екрані крапки з координатами Тепер, уважаючи, що Варто помітити, що целочисленная координата Алгоритм Брезенхема побудови растрового образа відрізка був споконвічно розроблений для графобудівників, але він повністю підходить і для растрових дисплеїв. У процесі роботи залежно від кутового коефіцієнта відрізка наращивается на одиницю або
Рис. 10.2. Зв'язок кутового коефіцієнта з вибором пикселя На мал. 10.2 це ілюструється для відрізка з кутовим коефіцієнтом, що лежить у діапазоні від нуля до одиниці. З малюнка можна помітити, що якщо кутовий коефіцієнт На мал. 10.3 показано, яким образом будуються крапки растра для відрізка з тангенсом кута нахилу На мал. 10.5 наведена блок-схема алгоритму для випадку
Рис. 10.3. Пиксели, що належать розгорненню відрізка
Рис. 10.4. Графік зміни відхилення Приведемо загальний алгоритм Брезенхема, що враховує всі можливі випадки напрямку відрізка, розглянутого як вектор на координатній площині (на мал. 10.6 виділені чотири області й зазначені особливості алгоритму в кожній з них). В описі алгоритму використовуються наступні функції: swap (a, b): обмін значень змінних a, b;abs (a): абсолютне значення a;sign (a): 0, якщо a= 0, 1, якщо a>0, -1, якщо a<0;point (i, j) - ініціалізація крапки (i, j).Передбачається, що кінці відрізка
Рис. 10.5. Блок-схема однієї галузі алгоритму Брезенхема i=i1;j=j1;di=i 2-i1;dj=j 2-j1;s1=sign(i 2-i1);s2=sign(j 2-j1);di=abs(di);dj=abs(dj);if (dj>di) { swap(di,dj); c=1;} else c=0;e=2* dj-di; // Ініціалізація зсуву// Основний циклfor (l=0; l<di; l++){ point(i,j); while (e>=0) { if (c==1) i=i+s1; else j=j+s2; e= e-2*di; } if (c==1) j=j+s2; else i=i+s1; e=e+2*dj; }
Рис. 10.6. Чотири можливих напрямки відрізка
|