Алгоритми Брезенхема растрової дискретизації окружності й еліпса

Алгоритм зображення окружності трохи складніше, ніж побудова відрізка. Ми розглянемо його для випадку окружності радіуса із центром на початку координат. Перенесення його на випадок довільного центра не становить праці. При побудові растрового розгорнення окружності можна скористатися її симетрією щодо координатних осей і прямих . Необхідно згенерувати лише одну восьму частину окружності, а інші її частини можна одержати шляхом відображень симетрії. За основу можна взяти частина окружності від 0 до 45° у напрямку за годинниковою стрілкою з вихідною точкою побудови . У цьому випадку координата окружності є монотонно убутною функцією координати .

Рис. 10.7. Найближчий пиксель при русі по окружності

При обраному напрямку руху по окружності є тільки три можливості для розташування найближчого пикселя: на одиницю вправо, на одиницю долілиць і по діагоналі долілиць (мал. 10.7). Вибір варіанта можна здійснити, обчисливши відстані до цих крапок і вибравши мінімальне з них:

Алгоритм можна спростити, перейшовши до аналізу знаків величин . При діагональна крапка лежить усередині окружності, тому найближчими крапками можуть бути тільки діагональна й права. Тепер досить проаналізувати знак вираження . Якщо , вибираємо горизонтальний крок, у противному випадку - діагональний. Якщо ж , то визначаємо знак , і якщо , вибираємо діагональний крок, у противному випадку - вертикальний. Потім обчислюється нове значення , причому бажано мінімізувати обчислення не тільки цієї величини, але й величин на кожному кроці алгоритму. Шляхом нескладних перетворень можна одержати для першого кроку алгоритму, що .

Після переходу в крапку по діагоналі нове значення обчислюється по формулі , при горизонтальному переході , при вертикальному - .

Таким чином, алгоритм малювання цієї частини окружності можна вважати повністю описаним (блок-схема його наведен на мал. 10.8). Всі її частини, що залишилися, будуються паралельно: після одержання чергової крапки можна инициализировать ще сім крапок з координатами .

Для побудови растрового розгорнення еліпса з осями, паралельними осям координат, і радіусами скористаємося канонічним рівнянням

яке перепишемо у вигляді

На відміну від окружності, для якої було досить побудувати одну восьму її частину, а потім скористатися властивостями симетрії, еліпс має тільки дві осі симетрії, тому прийде будувати одну чверть всієї фігури. За основу візьмемо дугу, що лежить між крапками й у першому квадранті координатної площини.

Рис. 10.8. Блок-схема побудови восьмої частини окружності

У кожній крапці еліпса існує вектор нормалі, що задається градієнтом функції . Дугу розіб'ємо на дві частини: перша - з кутом між нормаллю й горизонтальною віссю більше 45° (тангенс більше 1) і друга - з кутом, меншим 45° (мал. 10.9). Рух уздовж дуги будемо здійснювати в напрямку за годинниковою стрілкою, починаючи із крапки . Уздовж всієї дуги координата є монотонно убутною функцією від , але в першій частині вона убуває повільніше, ніж росте аргумент, а в другий - швидше. Тому при побудові растрового образа в першій частині будемо збільшувати на одиницю й шукати відповідне значення , а в другий - спочатку зменшувати значення на одиницю й визначати відповідне значення .

Напрямок нормалі відповідає вектору

Звідси знаходимо тангенс кута нахилу вектора нормалі: . Дорівнюючи його одиниці, одержуємо, що координати крапки розподілу дуги на вищевказані частини задовольняють рівності . Тому критерієм того, що ми переходимо до другої області в целочисленных координатах, буде співвідношення , або, переходячи до целочисленным операцій, .

Рис. 10.9. Дві області на ділянці еліпса

Рис. 10.10. Схема переходу в першій і другій областях дуги еліпса

При переміщенні уздовж першої ділянки дуги ми з кожної крапки переходимо або по горизонталі, або по діагоналі, і критерій такого переходу нагадує той, котрий використовувався при побудові растрового образа окружності. Перебуваючи в крапці , ми будемо обчислювати значення . Якщо це значення менше нуля, то додаткова крапка лежить усередині еліпса, отже, найближча крапка растра є , у противному випадку це крапка (мал. 10.10а).

На другій ділянці дуги можливі перехід або по діагоналі, або по вертикалі, тому тут спочатку значення координати y зменшується на одиницю, потім обчислюється й напрямок переходу вибирається аналогічно попередньому випадку (мал. 10.10б).

Залишається оптимізувати обчислення параметра , помноживши його на 4 і представивши у вигляді функції координат крапки. Тоді для першої половини дуги маємо

Для другої половини дуги одержимо

Всі дуги, що залишилися, еліпса будуються паралельно: після одержання чергової крапки , можна инициализировать ще три крапки з координатами . Блок-схему не приводимо через прозорість алгоритму.