Растеризація кола

У комп'ютерній графіці, алгоритм середини кола — це алгоритм, який використовується для визначення точок, необхідних для растеризації кола. Алгоритм кола Брезенхейма^[en] є похідним від алгоритму середньої точки окружності. Алгоритм може бути узагальнений до конічних перетинів.^[1]

Алгоритм відноситься до роботи Pitteway^[2] і Van Aken.^[3]

Короткий виклад

Цей алгоритм відображає всі вісім октантів одночасно, починаючи з кожного напряму (0°, 90°, 180°, 270°) і проходить в обох напрямках, щоб дістатися до найближчого кратного 45° (45°, 135°, 225°, 315° ). Алгоритм може визначити, де зупинитися, тому що, коли у = х, це означає, що кут становить 45 °. Причина використання цих кутів показано на малюнку: В той час, як змінна у зростає, вона не пропускає жодного повтору значення у до досягнення 45 °. Таким чином, під час циклу, у збільшується на 1 кожної ітерації і х зменшується на 1, також х ніколи не перевищує 1 в одній ітерації. Це призводить до зміни під кутом 45 °, тому що це точка, в якій тангенс зростання = обертанню.

Друга частина проблеми - це визначник, він є набагато складнішим. Він визначає, коли потрібно зменшувати х. Це зазвичай відбувається після того, як були намальовані пікселі, так як він ніколи не опускається нижче радіусу на першому пікселі. Тому що в безперервній функції, функція для сфери є функцією для кола з радіусом, що залежить від z (або незалежно від третьої змінної), само собою зрозуміло, що алгоритм для дискретної (voxel) сфери буде також спиратися на цей алгоритм окружності середньої точки. Але при погляді на сферу, може здатися, що цілочисельний радіус деяких сусідніх кіл однаковий, але вона не буде мати точно таке ж коло, що примикає до себе, в тому числі півкулі. Замість цього, для кола того ж радіуса потрібен інший визначник, щоб крива могла прийти трохи ближче до центру, або сягати далі. Розглянуті кругові діаграми, що відносяться до Minecraft, як визначник, перераховані нижче, враховують тільки одну можливість.

Алгоритм

Мета алгоритму полягає в знаходженні шляху через піксельну сітку, використовуючи пікселі, які якомога ближче до вірного рішення $x^{2}+y^{2}=r^{2}$ . На кожному кроці, шлях розширено шляхом вибору суміжних пікселів, які задовольняють $x^{2}+y^{2}<=r^{2}$ ,але максимізує $x^{2}+y^{2}$ . Так як запропоновані пікселі є суміжними, арифметично обчислити останній вираз стає легше, тому що необхідні тільки бітові зрушення і доповнення.

Цей алгоритм починається з рівнянням кола. Для простоти припустимо, що центр кола знаходиться в $(0,0)$ . Розглянемо спочатку тільки перший октант і накреслити криву, яка починається в точці $(r,0)$ і малюється проти годинникової стрілки, досягаючи кута 45.

Швидкий напрямок (базисний вектор з великим збільшенням значення) є напрямком змінної $y$ . Алгоритм завжди робить крок в позитивному напрямі(вгору) $y$ , а іноді робить крок в повільному напрямі (від'ємний $x$ напрямок).

З рівняння кола виходить перетворене рівняння $x^{2}+y^{2}-r^{2}=0$ , де $r^{2}$ обчислюється тільки один раз під час ініціалізації.

Нехай точки на колі - це послідовність координат вектора в точці (в звичайному базисі). Точки пронумеровані відповідно до порядку, в якому точка креслиться з $n=1$ і присвоюється першій точці $(r,0)$ .

Для кожної точки, має місце наступне:

{\begin{aligned}x_{n}^{2}+y_{n}^{2}=r^{2}\end{aligned}}

Це може бути змінено таким чином:

{\begin{aligned}x_{n}^{2}=r^{2}-y_{n}^{2}\end{aligned}}

А також для наступної точки:

{\begin{aligned}x_{n+1}^{2}=r^{2}-y_{n+1}^{2}\end{aligned}}

Оскільки наступна точка завжди буде принаймні на один піксель вище, ніж в минулому, це правда, що:

{\begin{aligned}y_{n+1}^{2}&=(y_{n}+1)^{2}\\&=y_{n}^{2}+2y_{n}+1\end{aligned}}

{\begin{aligned}x_{n+1}^{2}=r^{2}-y_{n}^{2}-2y_{n}-1\end{aligned}}

Таким чином, переробки наступної точки-рівняння рекурсивним шляхом заміни одного $x_{n}^{2}=r^{2}-y_{n}^{2}$ :

{\begin{aligned}x_{n+1}^{2}=x_{n}^{2}-2y_{n}-1\end{aligned}}

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

Остаточні координати рахуються шляхом додавання середньої точки координат. Ці цілочисленні доповнення не обмежують налаштування продуктивності^[en], так як ці квадратні (корінь) обчисленняв, свою чергу, можуть бути позбавлені у внутрішньому циклі. Знову ж, нуль в перетвореному рівнянні кола замінюється терміном помилки.

Ініціалізація терміна помилки виводяться з зміщення ½ пікселя на старті. До перетину з перпендикулярною лінією, це не призводить до накопиченого значенням $r$ в термінах помилки, так що це значення використовується для ініціалізації.

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

Варіант з цілочисельною основою арифметики

Так само, як і алгоритм Брезенхейма, цей алгоритм може бути оптимізований для цілих чисел на основі математики. Шляхом симетріъ, якщо алгоритм обчислить пікселі для одного октанта, вони можуть бути відображені симметрично, щоб отримати весь круг.

Ми почнемо з визначення похибки радіуса, яка складає різницю між точним уявленням окружності і центральною точкою кожного пікселя (або будь-яка інша довільна математична точка на пікселі). Для кожного пікселя з центром в точці $(x_{i},y_{i})$ , похибка радіусу визначається як:

RE(x_{i},y_{i})=\left\vert x_{i}^{2}+y_{i}^{2}-r^{2}\right\vert

Для ясності, ця формула для окружності отримується для початку координат, але алгоритм може бути змінений для будь-якого місця. Буде корректно почати з точки $(r,0)$ на позитивній осі Х. Оскільки радіус буде цілим числом пікселів, очевидно, похибка радіусу буде дорівнювати нулю:

RE(x_{i},y_{i})=\left\vert r^{2}+0^{2}-r^{2}\right\vert =0

Через те, що вона починається в першому позитивному Октанті, це буде крок у напрямку найбільшої, так сказати, подорожі, у напрямку Y, таким чином, зрозуміло, що $y_{i+1}=y_{i}+1$ . Окрім того, оскільки це стосується тільки цього Октанту, значення X має тільки два варіанти: залишитися таким же, як раніше ітерувати(збільшити), або зменшити на 1. Змінна рішення може бути створена, шляхом визначення, чи буде справедливо наступне:

RE(x_{i}-1,y_{i}+1)<RE(x_{i},y_{i}+1)

Якщо ця нерівність виконана, то виконується така дія $(x_{i}-1,y_{i}+1)$ ; якщо ні, то $(x_{i},y_{i}+1)$ . Отже, як визначити, чи є це нерівність? Почнемо з визначення похибки радіуса:

{\begin{array}{lcl}RE(x_{i}-1,y_{i}+1)&<&RE(x_{i},y_{i}+1)\\\left\vert (x_{i}-1)^{2}+(y_{i}+1)^{2}-r^{2}\right\vert &<&\left\vert x_{i}^{2}+(y_{i}+1)^{2}-r^{2}\right\vert \\\left\vert (x_{i}^{2}-2x_{i}+1)+(y_{i}^{2}+2y_{i}+1)-r^{2}\right\vert &<&\left\vert x_{i}^{2}+(y_{i}^{2}+2y_{i}+1)-r^{2}\right\vert \\\end{array}}

Абсолютне значення функції не допомагає, тому піднесемо до квадрату з обох сторін, так як квадрат будь-якого числа завжди позитивний:

{\begin{array}{lcl}\left[(x_{i}^{2}-2x_{i}+1)+(y_{i}^{2}+2y_{i}+1)-r^{2}\right]^{2}&<&\left[x_{i}^{2}+(y_{i}^{2}+2y_{i}+1)-r^{2}\right]^{2}\\\left[(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1)+(1-2x_{i})\right]^{2}&<&\left[x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1\right]^{2}\\\left(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1\right)^{2}+2(1-2x_{i})(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1)+(1-2x_{i})^{2}&<&\left[x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1\right]^{2}\\2(1-2x_{i})(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1)+(1-2x_{i})^{2}&<&0\\\end{array}}

SТак як х > 0, термін $(1-2x_{i})<0$ , таким чином під час ділення ми отримуємо:

{\begin{array}{lcl}2\left[(x_{i}^{2}+y_{i}^{2}-r^{2})+(2y_{i}+1)\right]+(1-2x_{i})&>&0\\2\left[RE(x_{i},y_{i})+Y_{Change}\right]+X_{Change}&>&0\\\end{array}}

Таким чином, критерій рішення змінюється від використання операцій з плаваючою комою, до простого цілочисельного додавання, віднімання, і біту зсуву (для операції множення на 2 ). Якщо $2(RE+Y_{Change})+X_{Change}>0$ , то ми зменшуємо значення X. Якщо $2(RE+Y_{Change})+X_{Change}\leq 0$ , то зберігаємо таке ж значення X. Знову ж, відображаємо ці точки на всіх октантах, отримуючи повне коло результатів.

Приклад на С

Вищезгаданий алгоритм реалізований на мові програмування C, і показаний нижче. Починаючи з точки $(r,0)$ , він перераховує точки в порядку проти годинникової стрілки для першого октанта, одночасно відображаючи точки до інших октантів.

void drawcircle(int x0, int y0, int radius)
{
    int x = radius;
    int y = 0;
    int err = 0;

    while (x >= y)
    {
        putpixel(x0 + x, y0 + y);
        putpixel(x0 + y, y0 + x);
        putpixel(x0 - y, y0 + x);
        putpixel(x0 - x, y0 + y);
        putpixel(x0 - x, y0 - y);
        putpixel(x0 - y, y0 - x);
        putpixel(x0 + y, y0 - x);
        putpixel(x0 + x, y0 - y);

        if (err <= 0)
        {
            y += 1;
            err += 2*y + 1;
        }
        if (err > 0)
        {
            x -= 1;
            err -= 2*x + 1;
        }
    }
}

Приклад на JavaScript

Реалізація, яка малює коло на сторінці HTML5 (тільки для освітніх цілей, є кращі способи малювати кола на сторінках).

const CHANNELS_PER_PIXEL = 4; //rgba

function drawCircle (x0, y0, radius, canvas) {
	var x = radius;
	var y = 0;
	var decisionOver2 = 1 - x;   // Decision criterion divided by 2 evaluated at x=r, y=0
	var imageWidth = canvas.width;
	var imageHeight = canvas.height;
	var context = canvas.getContext('2d');
	var imageData = context.getImageData(0, 0, imageWidth, imageHeight);
	var pixelData = imageData.data;
	var makePixelIndexer = function (width) {
		return function (i, j) {
			var index = CHANNELS_PER_PIXEL * (j * width + i);
			//index points to the Red channel of pixel 
			//at column i and row j calculated from top left
			return index;
		};
	};
	var pixelIndexer = makePixelIndexer(imageWidth);
	var drawPixel = function (x, y) {
		var idx = pixelIndexer(x,y);
		pixelData[idx] = 255;	//red
		pixelData[idx + 1] = 0;	//green
		pixelData[idx + 2] = 255;//blue
		pixelData[idx + 3] = 255;//alpha
	};

	while (x >= y) {
		drawPixel(x + x0, y + y0);
		drawPixel(y + x0, x + y0);
		drawPixel(-x + x0, y + y0);
		drawPixel(-y + x0, x + y0);
		drawPixel(-x + x0, -y + y0);
		drawPixel(-y + x0, -x + y0);
		drawPixel(x + x0, -y + y0);
		drawPixel(y + x0, -x + y0);
		y++;
		if (decisionOver2 <= 0) {
			decisionOver2 += 2 * y + 1; // Change in decision criterion for y -> y+1
		} else {
			x--;
			decisionOver2 += 2 * (y - x) + 1; // Change for y -> y+1, x -> x-1
		}
	}

	context.putImageData(imageData, 0, 0);
}

Малювання неповних октантів

Наведені вище реалізації завжди малюють тільки повні октанти або кола. Щоб намалювати тільки певну дугу від кута $\alpha$ до $\beta$ , алгоритму необхідно спочатку обчислити координати $x$ і $y$ цих кінцевих точок, де необхідно вдатися до обчислень тригонометричного або квадратного кореня (див. Квадратний корінь). Потім алгоритм Бресенхейма виконується по всьому Октанту або по колу і встановлює пікселі тільки в тому випадку, якщо вони потрапляють в потрібний інтервал. Після закінчення цієї дуги, алгоритм може бути припинений достроково.

Якщо кути задані як схили, то немає необхідності в тригонометрії або квадратних коренях: просто перевірте, що $y/x$ , знаходиться між бажаними нахилами.

Узагальнення

Також можна використовувати ту ж саму концепцію для растеризації параболи, еліпса, або будь-якої іншої двовимірної кривої.^[4]

References

↑ Donald Hearn; M. Pauline Baker. Комп'ютерна графіка. Prentice-Hall. ISBN 978-0-13-161530-4. Архів оригіналу за 7 липня 2014. Процитовано 25 квітня 2017.
↑ Pitteway, M.L.V., «Алгоритм для креслення еліпса або гіперболи з цифровими плоттерами», Computer J., 10(3) November 1967, pp 282—289
↑ Van Aken, J.R., «Ефективний алгоритм для креслення еліпса», CG&A, 4(9), September 1984, pp 24-35
↑ Краса алгоритму Брезенхейма: проста реалізація для побудови ліній, кіл, еліпсів і кривих Безьє. Архів оригіналу за 30 квітня 2017. Процитовано 25 квітня 2017.

Зовнішні посилання

Малювання кола - Стаття про малювання кіл, яка походить від простої схеми до ефективної
Алгоритм окружності в деяких мовах програмування [Архівовано 5 травня 2017 у Wayback Machine.]

[HearnBaker1994-1] Donald Hearn; M. Pauline Baker. Комп'ютерна графіка. Prentice-Hall. ISBN 978-0-13-161530-4. Архів оригіналу за 7 липня 2014. Процитовано 25 квітня 2017.

[2] Pitteway, M.L.V., «Алгоритм для креслення еліпса або гіперболи з цифровими плоттерами», Computer J., 10(3) November 1967, pp 282—289

[3] Van Aken, J.R., «Ефективний алгоритм для креслення еліпса», CG&A, 4(9), September 1984, pp 24-35

[4] Краса алгоритму Брезенхейма: проста реалізація для побудови ліній, кіл, еліпсів і кривих Безьє. Архів оригіналу за 30 квітня 2017. Процитовано 25 квітня 2017.

[1]

[2]

[3]

[4]