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

Для скорости можно пройтись blur'ом каким-нибудь по краю круга.

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

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

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

Можно подробнее? Как определить, что точка крайняя? И насколько крайняя?

У меня собственный движок. Эффекты все писал вручную. Еще есть резон читать?

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

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

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

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

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

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

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

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

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

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

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

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

0 0 1
0 1 1
0 1 1

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

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

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

Можно для граничных точек вычислять по 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));
}

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

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

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

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

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

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

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

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

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

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

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

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

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

(в процедуре FillRoundInLand)

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

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

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

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

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

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

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

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

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

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

http://stackoverflow.com/questions/485800/algorithm-for-drawing-an-anti-alias...

Можно рисовать окружность большего радиуса 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);
}

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