Реализация Anti-aliasing.

lazybiz · 10.11.2010

В данной теме я бы хотел затронуть проблему рисования двухмерной векторной графики на дискретных мониторах, а именно то, как можно реализовать алгоритм Anti-Aliasing. Есть несколько вариантов Anti-Aliasing-га, например, одним из них, наиболее распространенным является Supersampling (это тот самый алгоритм с помощью которого один пиксель как бы обрабатывают несколько раз), но он слишком ресурсоёмок. Существует так же Perfect Anti-Aliasing (идеальный) - это тот который интересует меня больше всего. Если у кого есть какие-то идеи или предложения - буду рад выслушать. Так же могу сам привести несколько примеров если это вобще кого-то интересует. В общем, если кому интересно - буду рад поговорить на эту тему.

lazybiz · 10.11.2010

Думаю что George-а заинтересует данная тема, т.к. микрографика его фишка)

lazybiz · 10.11.2010

Вот что я к примеру имею ввиду:

lazybiz · 10.11.2010

Вот еще один пример полностью с исходным кодом, та же окружность но уже движется (если Вы это заметите)..
Это так сказать элементарная реализация...

* Исходный код лучше всего просматривать с tab size = 4

George · 11.11.2010

Уважаемый lazybiz , Вы опять общаетесь сами с собой?

О чем Вы говорите, меня давно не интересует! Мне это напоминает:
Turbo Basic 1.0 в расцвете DOS-а! Детский сад на форуме!
Color, Point, Circle, Sin, Cos и все это скомпелировать в *.exe,
голый, без иконки!
Займитесь лучше одеванием своих часиков, идея хорошая, но далеко
не закончена, я имею ввиду, что и дизайн надо сменить ...

lazybiz · 11.11.2010

George сказал(а):
О чем Вы говорите, меня давно не интересует!

Буду иметь в виду.

George сказал(а):
Мне это напоминает:
Turbo Basic 1.0 в расцвете DOS-а! Детский сад на форуме!

На сколько я помню тема о микрографике не далеко ушла...

George сказал(а):
и все это скомпелировать в *.exe,
голый, без иконки!

Да что ж вы заладили своими иконками, в мире существует и много других интересных вещей.

George сказал(а):
я имею ввиду, что и дизайн надо сменить ...

Можете что-то предложить?

vital · 11.11.2010

А я бы почитал об этих алгоритмах, реализации плюсах-минусах - если напишешь=) Поговорить не могу - ибо нихрена не знаю)

George · 11.11.2010

Ok ! С меня описание дизайна и графический пример, а Вы подумаете как,
это реализовать в Вашем алгоритме ...

lazybiz · 11.11.2010

George
Во-первых давайте перенесем эту дискуссию в соответствующую тему.
Во-вторых для начала покажите пока графический пример, мне хотелось бы посмотреть как Вы себе это представляете.

vital
Существует очень хорошая библиотека AGG (http://www.antigrain.com/) аналогов которой я пока не видел. Реализация AA на высшем уровне. Позволяет с высокой скоростью и качеством рисовать полигоны любой сложности. Изначально алгоритм был опубликован в libART, далее появился во FreeType, а потом уже в AGG. Точное описание алгоритма на всех просторах интернета я найти не смог. В данный момент пытаюсь разобраться в исходниках AGG.
Немного позже приведу несколько других примеров. Еще существует алгоритм для LCD мониторов с использованием Subpixel Rendering (пример фотографии LCD монитора ниже), который может в несколько раз улучшить даже идеальный Anti-Aliasing, но об этом немного позже...

Ссылка скрыта от гостей

На фотографии: слева - с Subpixel Rendering, справа - без

DarkKnight · 14.11.2010

George сказал(а):
О чем Вы говорите, меня давно не интересует! Мне это напоминает:
Turbo Basic 1.0 в расцвете DOS-а! Детский сад на форуме!
Color, Point, Circle, Sin, Cos и все это скомпелировать в *.exe,
голый, без иконки!

George, полностью с вами не согласен, детский сад - это Делфи запустить и нажать F9... B вот у нас и форма и оконный класс и даже иконка....

А в этом аля Дос-тип приложении, парень сам описывает оконный класс, регистрирует его, пишит обрабочит мессадж-рекций....
Это называется программирование - а вот первое, которое я привел(пример: Делфи), это можно отнести к конструктору детскому класса кубики-пирамидки....(зато там по-умолчанию есть hIcon)

И вообще зачем так говорить, это как минимум не прилично и как максимум не за что человека обидели...
И своим сообщением вы вводите в заблуждение не опытных пользователей, которые прочитая это посчитают этот подход не актуальным, хотя на самом деле это не так... Я когда проект на OpenGl или Directе пишу, я про иконку как то тоже в самом конце думаю...
Как говорит "Не нравиться топик - не смотрите его"

Rus59Wolf · 21.11.2010

Уважаемый georg опять все перепутал.У него спрашивали по каим формулам и алгоритмам строить дополнительные пиксели - полутона между черным квадратом и белым кругом для первого примера. Насчет детского сада также с ним не соглашусь - реализовать Anti-Aliasing прямо во время выполнения программы это очень и очень нужно. Особенно для 3д приложений.

Вот только не нужно оскорблять делфи, это весьма достойная вещь. Мне нравится именно за то что стандарты и примитивы берет на себя, позволяя не отвлекатся от реализации собственно алгоритма. Но собственно это вопрос вкусов, о которых, как вам известно, не спорят. Просто не очень вежливо говорить подобное.

lazybiz · 21.11.2010

DarkKnight125 сказал(а):
и как максимум не за что человека обидели...

Да я не из обидчивых. Нужно сильно постараться чтобы это сделать, и то не факт что получится. Но это уже не по теме.

DarkKnight125 сказал(а):
Как говорит "Не нравиться топик - не смотрите его"

Я бы немного перефразировал: Не нравится топик - не постите.

А теперь по теме:
Тот вариант, который я предоставил, можно назвать 2D RayTracing-ом. Векторов и лучей Вы там не найдете, т.к. весь алгоритм настолько прост что его просто нельзя не упростить.
Сегодня я постараюсь как можно лучше донести до Вас еще одну реализацию. О ней я упоминал в самом начале - это Super-Sampling.
Минутой позже выложу исходник как наглядный пример. Кстати этот вариант может использоваться так же для Motion Blurr, но опять же в реалтайме это будет происходить очень медленно. Кстати именно этот алгоритм используется в OpenGL, именно там я его первый раз и увидел.

Добавлено:

Rus59Wolf сказал(а):
Вот только не нужно оскорблять делфи

Да тут, собственно, оскорблений и не было... Кнайт просто сравнил буй с поплавком.

lazybiz · 21.11.2010

Как и обещал:

C++:

#include <windows.h>
#include <math.h>

#define				PI					(3.1415926535897932384626433832795)
#define				PI2					(PI * 2.0)

#define				W					128
#define				H					128
#define				SW					(W*4)
#define				SH					(H*4)

#define				R					(50)

typedef	unsigned long		u32;
typedef	float				f32;

static char			g_szWindowName[]	= "dib";
static char			g_szWindowClass[]	= "dib32";
static HINSTANCE	g_hInst;
static HWND			g_hWnd;

static BITMAPINFO	g_bi;
static u32 *		p_dib;

// взято из OpenGL
float	j15[] = {
0.285561f, 0.188437f,
0.360176f, -0.065688f,
-0.111751f, 0.275019f,
-0.055918f, -0.215197f,
-0.080231f, -0.470965f,
0.138721f, 0.409168f,
0.384120f, 0.458500f,
-0.454968f, 0.134088f,
0.179271f, -0.331196f,
-0.307049f, -0.364927f,
0.105354f, -0.010099f,
-0.154180f, 0.021794f,
-0.370135f, -0.116425f,
0.451636f, -0.300013f,
-0.370610f, 0.387504f };

void a_sincos_scale( float, float, float *, float * );
#pragma aux	a_sincos_scale =		\
"fsincos"						\
"fmul	st, st(2)"				\
"fstp	dword ptr [edx]"		\
"fmulp	st(1), st"				\
"fstp	dword ptr [eax]"		\
parm [8087] [8087] [eax] [edx]	\
modify [8087];

float inline q_circle_squared( int x, int y, float cx, float cy )
{
float	dx, dy;
dx = cx - x;
dy = cy - y;
return dx * dx + dy * dy;
}

long circle_15xjitter( int x, int y, float cx, float cy, float r0, float r1, float phase )
{
int		i, k, isec;
float	jx, jy, r0s, r1s, d;
long	sum;

r0s = r0 * r0;
r1s = r1 * r1;

for ( i = 0, sum = 0; i < (15<<1); i += 2 ) {

jx = cx + j15[i ];
jy = cy + j15[i+1];

isec = 0;
d = q_circle_squared( x, y, jx, jy );
if ( d < r0s ) isec = 1;
if ( !isec ) continue;

for ( k = 0; k < 6; k++ ) {
float	xsin, ycos;

a_sincos_scale( phase, r0, &xsin, &ycos );

if ( q_circle_squared( x, y, xsin+jx, ycos+jy ) < r1s ) {
isec = 0;
break;
}

phase += PI * 2 / 6;
}

if ( isec ) sum += 0x11;
}
return sum;
}

static void test( void )
{
u32			c;
int			x, y;
f32			cx, cy;
static f32	phase	= 0.0f;

cx = cos( phase ) * 10.0f + (W / 2);
cy = sin( phase ) * 10.0f + (H / 2);

for ( y = 0; y < H; y++ )
for ( x = 0; x < W; x++ ) {
c = circle_15xjitter( x, y, (f32)W / 2, (f32)H / 2, H-(H/10), H-(H/3), phase );
c = (c << 16) | (c << 8) | c;
p_dib[W * y + x] = c;
}

phase += 0.01f;
}

static LRESULT CALLBACK wnd_proc( HWND hWnd, UINT uMsg, WPARAM wParam, LPARAM lParam )
{
switch ( uMsg ) {
case WM_NCHITTEST: return HTCAPTION;

case WM_PAINT: {
PAINTSTRUCT	ps;
BeginPaint( hWnd, &ps );
StretchDIBits( ps.hdc, 0, 0, SW, SH, 0, 0, W, H, p_dib, &g_bi, DIB_RGB_COLORS, SRCCOPY );
EndPaint( hWnd, &ps );
} return 0;

case WM_KEYDOWN: if ( (int)wParam != VK_ESCAPE ) break;
case WM_DESTROY:
PostQuitMessage( 0 );
return 0;
}
return DefWindowProc( hWnd, uMsg, wParam, lParam );
}

int APIENTRY WinMain( HINSTANCE hInst, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow )
{
MSG			msg;
WNDCLASS	wc;
HDC			hdc;

g_hInst = hInst;

memset( &wc, 0, sizeof( WNDCLASS ) );
wc.style			= CS_OWNDC | CS_DBLCLKS;
wc.lpfnWndProc		= wnd_proc;
wc.hInstance		= hInst;
wc.lpszClassName	= g_szWindowClass;
wc.hCursor			= LoadCursor( NULL, IDC_ARROW );
RegisterClass( &wc );

g_hWnd = CreateWindowEx( WS_EX_TOPMOST,
g_szWindowClass, g_szWindowName, WS_POPUP | WS_VISIBLE,
(GetSystemMetrics( SM_CXSCREEN ) >> 1) - (SW >> 1),
(GetSystemMetrics( SM_CYSCREEN ) >> 1) - (SH >> 1),
SW, SH, NULL, NULL, hInst, NULL );

memset( &g_bi, 0, sizeof( BITMAPINFO ) );
g_bi.bmiHeader.biSize			= sizeof( BITMAPINFOHEADER );
g_bi.bmiHeader.biWidth			= W;
g_bi.bmiHeader.biHeight			= -H;
g_bi.bmiHeader.biPlanes			= 1;
g_bi.bmiHeader.biBitCount		= 32;
g_bi.bmiHeader.biCompression	= BI_RGB;

p_dib = malloc( W * H * 4 );

memset( &msg, 0, sizeof( MSG ) );
while ( msg.message != WM_QUIT ) {
if ( PeekMessage( &msg, NULL, 0, 0, PM_REMOVE ) ) {
TranslateMessage( &msg );
DispatchMessage( &msg );
} else {
memset( p_dib, 255, W * H * 4 );
test();
hdc = GetWindowDC( g_hWnd );
StretchDIBits( hdc, 0, 0, SW, SH, 0, 0, W, H, p_dib, &g_bi, DIB_RGB_COLORS, SRCCOPY );
ReleaseDC( g_hWnd, hdc );
Sleep( 50 );
}
}

free( p_dib );
DestroyWindow( g_hWnd );
UnregisterClass( g_szWindowClass, g_hInst );
return 0;
}

Это кстати самый медленный алгоритм из тех что я знаю.

Rus59Wolf · 22.11.2010

Здорово. А если коротко то как это работает на пальцах? Типа берем цвет точки потом сравниваем с соседними...

Извините, я не издеваюсь, мне просто безумно интересен сам алгоритм а не его исполнение на си

lazybiz · 24.11.2010

Rus59Wolf сказал(а):
Извините, я не издеваюсь...

Давайте только без этого)) Тут никто никому ничего не должен и не перед кем не провинялся)))

Rus59Wolf сказал(а):
Типа берем цвет точки потом сравниваем с соседними...

Нет, нет и нет. Тут это не при чем. Ничего мы ни с кем не сравниваем.

Если Вас интересует последний алгоритм - то я его не советую, он самый медленный и не качественный. Но раз Вам интересно то я постараюсь объяснить на одном пикселе:
Допустим мы имеем пиксель с координатами X = 4.21 и Y = 7.58. При обычной растеризации он будет рисоваться как один пиксель с координатами 4 и 7, если идет округление путем отброса дробной части. В итоге мы получим одну черную точку.
В этом же случае мы прибегаем к MultiSampling-гу. Т.е. одну точку мы рисуем X раз с яркостью 1/X прибавляя каждую новую точку к уже имеющемуся рисунку, смещая каждую координату на значения взятые из заранее подготовленной таблицы (которая в моем примере именуется как j15). По-сути это таблица может содержать случайные числа в пределах от -1 до 1, но лучшие результаты достигаются именно с теми, которые были подсчитаны специально.
Думаю что немного просветлил Ваш разум) Если что - спрашивайте.

Rus59Wolf · 24.11.2010

lazybiz сказал(а):
Давайте только без этого)) Тут никто никому ничего не должен и не перед кем не провинялся)))

заметано

lazybiz сказал(а):
Допустим мы имеем пиксель с координатами X = 4.21 и Y = 7.58. При обычной растеризации он будет рисоваться как один пиксель с координатами 4 и 7, если идет округление путем отброса дробной части. В итоге мы получим одну черную точку.
В этом же случае мы прибегаем к MultiSampling-гу. Т.е. одну точку мы рисуем X раз с яркостью 1/X прибавляя каждую новую точку к уже имеющемуся рисунку, смещая каждую координату на значения взятые из заранее подготовленной таблицы (которая в моем примере именуется как j15). По-сути это таблица может содержать случайные числа в пределах от -1 до 1, но лучшие результаты достигаются именно с теми, которые были подсчитаны специально.

А Х координатный и Х - количество прорисовок точек это разные числа? По логике разные... Получение дробных координат - я на столь низком уровне никогда не работал, но вообще идею понял - если ее скрестить с рендером то в принципе получится оно, только оптимизировать нужно.

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

можно про это поподробнее, если не сложно, плюс вы говорили про другие алгоритмы - если не сложно то опишите также попростому, без примеров кода...

lazybiz · 24.11.2010

Rus59Wolf сказал(а):
А Х координатный и Х - количество прорисовок точек это разные числа?

Да. Конечно. Не усмотрел немного...

Rus59Wolf сказал(а):
Перебор пикселей как идет? Если пост рендерный то тупо перебирать весь экран.......

Этот алгоритм применяется к сцене целиком (Full-Scene AA). Через часок попробую скинуть пример, где вся сцена представляется как один пиксель.

Rus59Wolf сказал(а):
плюс вы говорили про другие алгоритмы - если не сложно то опишите также попростому

С этим немного позже. Пока времени не хватает...

lazybiz · 24.11.2010

Проще некуда. Вся суть в функции render_aa_pixel(). Для наглядности изображение увеличено в 4 раза.

C++:

#include <windows.h>
#include <math.h>

#define	W				128
#define	H				128
#define	SW				(W*4)
#define	SH				(H*4)

typedef	unsigned long		u32;
typedef	float				f32;

static char			g_szWindowName[]	= "dib";
static char			g_szWindowClass[]	= "dib32";
static HWND		g_hWnd;

static BITMAPINFO	g_bi;
static u32 *		p_dib;

/* 15 jitter points */
float	j15[] = {
0.285561f, 0.188437f,
0.360176f, -0.065688f,
-0.111751f, 0.275019f,
-0.055918f, -0.215197f,
-0.080231f, -0.470965f,
0.138721f, 0.409168f,
0.384120f, 0.458500f,
-0.454968f, 0.134088f,
0.179271f, -0.331196f,
-0.307049f, -0.364927f,
0.105354f, -0.010099f,
-0.154180f, 0.021794f,
-0.370135f, -0.116425f,
0.451636f, -0.300013f,
-0.370610f, 0.387504f };

static void render_aa_pixel( void )
{
static f32	phase = 0.0f;
f32		x, y;

memset( p_dib, 255, W * H * 4 );

x = cos( phase ) * 40 + (W/2);
y = sin( phase ) * 40 + (H/2);

for ( int i = 0; i < 15; i++ ) {
p_dib[W * (int)floor( y + j15[i*2+1] ) + (int)floor( x + j15[i*2] )] -= 0x111111;
}

phase += 0.005f;
}

static LRESULT CALLBACK wnd_proc( HWND hWnd, UINT uMsg, WPARAM wParam, LPARAM lParam )
{
switch ( uMsg ) {
case WM_NCHITTEST: return HTCAPTION;

case WM_PAINT: {
PAINTSTRUCT	ps;
BeginPaint( hWnd, &ps );
StretchDIBits( ps.hdc, 0, 0, SW, SH, 0, 0, W, H, p_dib, &g_bi, DIB_RGB_COLORS, SRCCOPY );
EndPaint( hWnd, &ps );
} return 0;

case WM_KEYDOWN: if ( (int)wParam != VK_ESCAPE ) break;
case WM_DESTROY:
PostQuitMessage( 0 );
return 0;
}
return DefWindowProc( hWnd, uMsg, wParam, lParam );
}

int APIENTRY WinMain( HINSTANCE hInst, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow )
{
MSG			msg;
WNDCLASS	wc;
HDC			hdc;

memset( &wc, 0, sizeof( WNDCLASS ) );
wc.style			= CS_OWNDC | CS_DBLCLKS;
wc.lpfnWndProc		= wnd_proc;
wc.hInstance		= hInst;
wc.lpszClassName	= g_szWindowClass;
wc.hCursor		= LoadCursor( NULL, IDC_ARROW );
RegisterClass( &wc );

g_hWnd = CreateWindowEx( WS_EX_TOPMOST,
g_szWindowClass, g_szWindowName, WS_POPUP | WS_VISIBLE,
(GetSystemMetrics( SM_CXSCREEN ) >> 1) - (SW >> 1),
(GetSystemMetrics( SM_CYSCREEN ) >> 1) - (SH >> 1),
SW, SH, NULL, NULL, hInst, NULL );

memset( &g_bi, 0, sizeof( BITMAPINFO ) );
g_bi.bmiHeader.biSize		= sizeof( BITMAPINFOHEADER );
g_bi.bmiHeader.biWidth		= W;
g_bi.bmiHeader.biHeight		= -H;
g_bi.bmiHeader.biPlanes		= 1;
g_bi.bmiHeader.biBitCount		= 32;
g_bi.bmiHeader.biCompression	= BI_RGB;

p_dib = new u32 [W * H];

memset( &msg, 0, sizeof( MSG ) );
while ( msg.message != WM_QUIT ) {
if ( PeekMessage( &msg, NULL, 0, 0, PM_REMOVE ) ) {
TranslateMessage( &msg );
DispatchMessage( &msg );
} else {
render_aa_pixel();
hdc = GetWindowDC( g_hWnd );
StretchDIBits( hdc, 0, 0, SW, SH, 0, 0, W, H, p_dib, &g_bi, DIB_RGB_COLORS, SRCCOPY );
ReleaseDC( g_hWnd, hdc );
Sleep( 50 );
}
}

delete [] p_dib;
DestroyWindow( g_hWnd );
UnregisterClass( g_szWindowClass, hInst );
return 0;
}

Rus59Wolf · 13.04.2011

жаль что тема умерла, хочется еще

Все сервисы Codeby

Поиск

Поиск

Реализация Anti-aliasing.

lazybiz

lazybiz

lazybiz

Вложения

lazybiz

Вложения

George

lazybiz

vital

George

lazybiz

Вложения

DarkKnight

Rus59Wolf

lazybiz

lazybiz

Rus59Wolf

lazybiz

Rus59Wolf

lazybiz

lazybiz

Вложения

Rus59Wolf