LINUX.ORG.RU

Алгоритм рисования сглаженной окружности.


0

1

Еще раз здравствуйте!

Ищу алгоритм рисования сглаженного круга. Сейчас рисую окружность так: беру квадрат со стороной 2r и внутри него каждую точку проверяю на вхождение в круг. Такое изображение рисуется достаточно быстро, но сглаживания нет вообще:

http://img829.imageshack.us/img829/6734/111umm.png (ссылка прямая)

Слышал, что можно как-то переделать алгоритм DDA-линии, но 1) Я никогда с ним не работал. 2) Там много вещественных операций (скорость важна).

Что посоветуете?

★★★

Последнее исправление: AlexCones (всего исправлений: 1)

Для крайних точек определяете какая часть пикселя попадает в круг и смешиваете в таких пропорциях цвет круга и цвет фона.

AIv ★★★★★
()

Недаво читал документацию по OpenGL, там есть раздел про сглаживание.
Рекомендую просмотреть, он не очень большой.

trex6 ★★★★★
()
Ответ на: комментарий от schizoid

Скорость от этого только проиграет - Blur - это вообще самый медленный эффект.

AlexCones ★★★
() автор топика

стандартный способ решения таких задач состоит в увеличени разрешения. Каждую точку разбить на множество точек, например 3×3. Для каждой такой подточки определять её попадание в круг (0 или 1) и потом их суммировать с коэффициентом 1/9. То есть вычислять долю попадания круга на точку-пиксель...

anonymous
()
Ответ на: комментарий от AlexCones

Вычисляете r - длину радиус-вектора точки (в смысле - ее центра). Если получаете модуль отклонения его от радиуса окружности |r-R|<0.5 - точка крайняя. Долю пикселя, попавшую внутрь окружности, по-честному, конечно, нужно через интеграл считать, но здесь сгодится и грубое линейное приближение. А можно и вообще приближенно считать эту долю равной R-0.5-r.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от anonymous

Так, алгоритм понятен. Но, насколько я понял, скорость вычислений увеличивается в 9 раз. Есть другой метод? Но за этот тоже спасибо!

AlexCones ★★★
() автор топика
Ответ на: комментарий от AlexCones

можно разрешение увеличивать только на тех точках, которые теоретически могут попасть на границу круга. Для других точек, отстоящих на почтительном расстоянии от границы, этого не надо. Тогда увеличение объёмов вычислений будет совсем небольшое.

anonymous
()
Ответ на: комментарий от Eddy_Em

Так, ясно, спасибо.

Правда в свете всего этого я не обратил внимания на одну вещь:

Представьте себе картинку. Будем говорить, что мы её рисуем поверх другой. Прзрачный цвет для неё возьмем розовым (0xFF00FF, например). Теперь нужно нарисовать на картинке (которая залита «прозрачным» цветом) круг с антиалясингом. Если смешивать цвета в пропорции (любой), то розовый перестанет быть розовым и у круга появится светло-розовый ободок по окружности. Если просто рисовать «промежуточные» точки круга как часть от 0xFFFFFF, то появляется риск сделать «загадить» вокруг круга территорию другим цветом (например, если мы нарисовали прямоугольник, а поверх него сглаженный круг.

Как бы избежать таких «ляпов»?

AlexCones ★★★
() автор топика
Ответ на: комментарий от AlexCones

если часть пикселя розовая от фона, а часть белая от круга, то естественно цвет пикселя станет светлорозовым. Каким же ему ещё быть?

anonymous
()
Ответ на: комментарий от anonymous

Т.е. проблему адо решать на уровень выше? Пилить отдельную прозрачность для каждого пикселя или маски?

AlexCones ★★★
() автор топика
Ответ на: комментарий от AlexCones

Я бы не морочил себе голову и использовал openGL. Ну, а как происходит смешение цветов, можно прочитать в openGL book, либо в вики поискать.

Кстати, можно не цвета смешивать у краевых пикселей, а изменять их прозрачность, пропорционально доле пикселя, находящейся внутри окружности.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от AlexCones
0 0 1
0 1 1
0 1 1

если моим способом считать, то никакой проблемы нет.

В данном примере будет итого = 4/9 розового цвета + 5/9 белого цвета. Цвет это вектор (r, g, b).

anonymous
()
Ответ на: комментарий от AlexCones

Почитайте openGL, тогда поймете: сначала вы вычисляете цвет пикселя для слоя, в котором вы его рисуете, затем, проходя от нижнего слоя к верхнему, используя значения альфа-канала и цвета, вычисляете текущий цвет пикселя после наложения.

Eddy_Em ☆☆☆☆☆
()

Можно для граничных точек вычислять по 4 субпикселя с небольшим смещением, затем усреднять.

У меня скругленные углы рисуются так (но тут текстура генерируется, не в реальном времени):

Ref<Texture> GraphicsUtil::generateRoundCornerTexture (int radius, int color)
{
	int bgraColor = 0x00000000;
	((unsigned char *)&bgraColor)[0] = ((unsigned char *)&color)[2];
	((unsigned char *)&bgraColor)[1] = ((unsigned char *)&color)[1];
	((unsigned char *)&bgraColor)[2] = ((unsigned char *)&color)[0];
	int alpha = ((unsigned char *)&bgraColor)[3] = ((unsigned char *)&color)[3];

	int realSize = nearestPowerOfTwo (radius);
	Ref<std::vector<byte> > pixelData (new std::vector<byte> (realSize * realSize * 4, 0));
	int *colorData = (int *)pixelData->data ();
	for (int ix = 0; ix < radius; ix++)
	{
		for (int iy = 0; iy < radius; iy++)
		{
			int vx = radius - ix;
			int vy = radius - iy;

			float vlen = sqrt ((float)(vx * vx + vy * vy));
			if (vlen >= radius + 2)
				continue;
			if (vlen <= radius - 2)
				colorData[ix + iy * realSize] = bgraColor;

			int factor = 0;
			for (float ipx = -2; ipx < 2; ipx++)
			{
				for (float ipy = -2; ipy < 2; ipy++)
				{
					float px = vx + ipx * 0.25f;
					float py = vy + ipy * 0.25f;
					vlen = sqrt (px * px + py * py);
					if (vlen <= radius)
						factor++;
				}
			}
			int a = ((factor * 255 / 16) * alpha) / 255;

			colorData[ix + iy * realSize] = (bgraColor & 0x00ffffff) | (a << 24);
		}
	}

	return Ref<Texture> (new Texture (pixelData, radius, radius, realSize, realSize));
}
note173 ★★★★★
()
Ответ на: комментарий от anonymous

Уважаемый анонимус, проблема то не в том, чтобы подобрать пропорцию, а в том, чтобы не «смешиваться» с фоном, дабы не выпилить ненароком прозрачность : http://img580.imageshack.us/img580/6153/anon.png ---

В общем я понял - либо запиливаю слои и прозрачность отдельного пикселя, либо пилю примитив с долей от 0xFFFFFF.

Спасибо всем!

AlexCones ★★★
() автор топика
Ответ на: комментарий от AlexCones

Да. Там описываются их алгоритмы сглаживания, как все работает, как определяется заполнение пикселя и т.п.

trex6 ★★★★★
()

> беру квадрат со стороной 2r и внутри него каждую точку проверяю на вхождение в круг

зачем каждую-то точку?

(скорость важна)

Пользуйся симметрией и там фактом, что если точка попала в круг, то все точки до любой из осей симметрии квадрата тоже будут в круге

При этом комбинируй целочисленный алгоритм рисования окружности со способом, предложенным анонимусом (каждый пиксель представить в виде квадрата 9х9)

unC0Rr ★★★★★
()
Ответ на: комментарий от unC0Rr

Пользуйся симметрией

Тьфу блин, вот чувствовал, что там можно в 4 раза быстрее все делать. Спасибо!

AlexCones ★★★
() автор топика
Ответ на: комментарий от AlexCones

Да какое там в 4, во много-много. Если ты в горизонтальной линии знаешь точку окружности, то ты уже про все точки на этой линии знаешь, находятся ли они в круге. А если при этом точку на окружности определять при помощи целочисленного метода рисования окружности, алгоритм ускоряется на порядки.

Готовую реализацию можно посмотреть тут (на паскале).

unC0Rr ★★★★★
()

Мультисемплинг уже предлагали?

buddhist ★★★★★
()

>беру квадрат со стороной 2r и внутри него каждую точку проверяю на вхождение в круг

OMFG… Что же будет ещё лет 20 спустя? Мне уже страшно.

Всех срочно сажать на 2МГц машины, чтобы воочию видеть, как оно «рисуется достаточно быстро».

Надеюсь (тему ещё не читал) в алгоритм Брезенхема уже ткнули?

KRoN73 ★★★★★
()
Ответ на: комментарий от anonymous

>Каждую точку разбить на множество точек, например 3×3

Ышшо один совет.

В алгоритме Брезенхема накопление ошибки указывает на смещение от точных координат точки. Так что сразу становится известно относительное значение в текущей точке и соседней. Так что вместо одной точки со 100% уровнем просто ставим две с промежуточными уровнями. Даже восьмибитный процессор на Бейсике справится.

KRoN73 ★★★★★
()
Ответ на: комментарий от KRoN73

>Надеюсь (тему ещё не читал) в алгоритм Брезенхема уже ткнули?

Тему дочитал. Я совсем в унынии. Дайте мне руку с 14-ю пальцами и другой газ для дыхания.

KRoN73 ★★★★★
()

Можно рисовать окружность большего радиуса r+p, где прозрачность включается для слоя (r,r+p]. Например так

int p = 3; // 3 pixel smoothing
int di = r*r, dp = (r+p)*(r+p), a, w;
for(i=-r-p;i<=r+p;i++) for(j=-r-p;j<=r+p;j++)
{
w = i*i+j*j;
if(w>=dp) continue;
// alpha channel by simplest «linear» formula
a = w<=di ? 255 : 255*(dp-w)/(dp-di);
plot_point(x+i,y+j,a);
}

abalakin ★★
()
Ответ на: комментарий от abalakin

Практически так и сделал, только чуть иначе.

AlexCones ★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.