Алгоритм антиалиасинговой линии

а в чем фишка, нельзя переключаться между алгоритмами в зависимости от угла?

Между какими алгоритмами? У меня есть только Ву. Знаете еще один алгоритм АА-линии?

а фчем проблема на 45 градусов вот эту тень по бокам самому пририсовать без всяких алгоритмов? А на 90 градусов наоборот отрубить Ву совсем, чтобы не было лишних «теней»

погуглил по «anti-aliasing line algorithms», нашел пару каких-то платных пдфок с описанием алгоритмов, забил

А где сам код?

точнее чуть подкорректировал код из википедии

а фчем проблема на 45 градусов вот эту тень по бокам самому пририсовать без всяких алгоритмов?

Да дело в том, что там все линии 3хточечные и выглядят лучше чем простой Ву.

Алгоритм в википедии явно подразумевает, что случай 45 градусов особый. Приведённый там код для наклонной линии когда dx > dy. Возможно, что в фотошопе именно 45 градусов обрабатывается отдельным алгоритмом. При малейшем отклонении от 45 твой алгоритм начинает нормально работать?

Вобщем, идея алгоритма в википедии описана, сам алгоритм боле-мене понятен. Впрочем, лично мне не совсем ясна его несимметричность. Скажем, наклонная dx>dy, по ву рисуется одна основная линия и одна выше или ниже «теневая», которая сглаживает. Логичнее было б рисовать две: сверху и снизу, пропорционально разделив яркости.

Возможно, что в фотошопе именно 45 градусов обрабатывается отдельным алгоритмом.

Если увеличить картинку что я прикрепил к ОП-посту, то тма видно что фотошоп *всегда* использует 3хточечное разделение.

При малейшем отклонении от 45 твой алгоритм начинает нормально работать?

Да зашибись он работает: (50, 50) -> (551, 550)
https://dl.dropboxusercontent.com/u/31471800/p2p/Screenshot - 27.11.2014 - 23...

Нормальный стандартный способ подавления алиасинга.

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

Не этот ли алгоритм? В котором явно диагональные иначе работают. http://www.codeproject.com/Articles/13360/Antialiasing-Wu-Algorithm

 if (DeltaX == DeltaY) {
    /* Diagonal line */
    do {
       X0 += XDir;
       Y0++;
       DrawPixel(pDC,X0, Y0, BaseColor);
    } while (--DeltaY != 0);
    return;
 }

Вобщем, для диагональных я бы предложил рисовать дополнительные линии по бокам заметно меньшей интенсивности. Скажем, по 15% от нужной. Условно примерно так:

  do {
     X0 += XDir;
     Y0++;
     DrawPixel(pDC,X0-1, Y0, BaseColor/6);
     DrawPixel(pDC,X0,   Y0, BaseColor);
     DrawPixel(pDC,X0+1, Y0, BaseColor/6);
  } while (--DeltaY != 0);

Привожу пример на том, что смог найт, свой конкретный код ты не привёл.

Вот еще примеры линий фотошопа (даже 90градусные оказывается имеют что-то типа «тени» Фишка? Бага? Издержки их алгоритма?):

А там точно холст без масштабирования?

Та загляни уже в сурцы GIMP.

Я так смотрю, что фотошоп делает его 3-х точечным, а Ву 2х
Знаете еще один алгоритм АА-линии?

Э... Кхм. Какие точки? Рисуешь по Брезенхему, только отображаешь не основную линию, а ещё и соседнюю с интенсивностью, равной накопленной погрешности. Получается антиалиасинг без накладных расходов. Интенсивность основной линии, кстати, тоже лучше брать не 100%, а 100% минус погрешность.

Скажем, наклонная dx>dy, по ву рисуется одна основная линия и одна выше или ниже «теневая», которая сглаживает

Ужас. А чем не подходит Брезенхем c переносом погрешности?

Банальный суперсэмплинг, например

Там у http://www.freetype.org/ есть алгоритмы сглаживания хорошие. Ещё у flash, adobe reader и т.д.

Та загляни уже в сурцы GIMP.

А как его заставить линию сглаживать?

Для глаз менее ибово.

Ужас. А чем не подходит Брезенхем c переносом погрешности?

Лично мне ничто никуда не подходит. Я не занимаюсь компьютерной графикой уже много лет, просто ещё какие-то знания остались.

Получается антиалиасинг без накладных расходов.

Не полученется. Почитайте как работает алгоритм Ву и Брезенхема. Нельзя просто взять и нарисовать Брезенхема поверх (вместо части) линии Ву. Потому что у точек по линии разная интенсивность и считаться они могут только парами.

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

Спасибо, надо будет над этим подумать.

Печально, но он требует много памяти и ресурсов для пересчета.

Нельзя просто взять и нарисовать Брезенхема поверх (вместо части) линии Ву. Потому что у точек по линии разная интенсивность и считаться они могут только парами.

Я не знаю, что такое Ву, но я всегда (лет 20 назад) рисовал сглаженные линии по Брезенхему без всяких пар и «линий сбоку». Сглаженная линия рисуется Брезенхемом в один проход, одной линией. Просто ставим на каждой итерации не один пиксель, а два. Один — обычный, второй — сбоку. Интенсивность первого убывает по мере нарастания ошибки, второго — увеличивается. Когда накопление ошибки доходит до максимума, переключающего одну из координат, «ошибочный» пиксель становится основным.

А GPU не можешь пользоваться? Тогда печально, конечно

Я не знаю, что такое Ву

Если что, то, что вы описали и есть Ву. Только интенсивность считается только по первому пикселю, а второй это 1-первый.

Я находил отличные бесплатные djvu от IBM каких-то лохматых годов (конец 70-х или даже раньше), но ничуть не утратившие своей актуальности поныне.

не будет у брезенхема гладкой мягкой линии, глянь какой антиальязинг у фотошопа - это точно не оригинальный брезенхем..

Я не знаю, что такое Ву, но я всегда (лет 20 назад) рисовал сглаженные линии по Брезенхему

Не бывает сглаженных линий по Брезенхему. Не предусматривал Брезенхем их. Как я понял Ву (поверхностно, не вникал): по «длинной» оси всегда есть «вторая точка» с обоих концов линии, которая откладывается на этой оси. Создаётся две линии: одна идёт из изначальных координат в смещённую точку на другом конце, вторая симметрично наоборот. Существует «правильная» дробная координата, в которой и есть «настоящий» цвет, но, поскольку, дробных координат не бывает, то от неё расчитывается дробное расстояние до соответствующих точек этой пары линий, на основании которого и распределяется интенсивность. И всё замечательно, кроме случая ровно 45 градусов, когда координата всегда не дробная и линию никак не «раздвоить». Этот случай, видимо, надо решить отдельно, размазав, видимо, на 3 линии.

глянь какой антиальязинг у фотошопа - это точно не оригинальный брезенхем..

Так я и не говорю, что у Шопа — Брезенхем. Там явно более хитрое извращение (именно извращение — полная ширина линии 2.8px). Я просто говорю, что Брезенхемом (или, как оказалось, это и зовётся Ву) можно сглаживать линии, при чём без лишних вычислительных затрат.

Не бывает сглаженных линий по Брезенхему

Я же говорю про дополнительное действие в рамках оригинального алгоритма. Суть алгоритма — смещение по накоплению ошибки — не меняется.

Создаётся две линии: одна идёт из изначальных координат в смещённую точку на другом конце, вторая симметрично наоборот.

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

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

Это никак не решает проблему 45 градусов, кстати. Там нет ошибки :)

Максим Шеманарев, мир его праху, создал одну из лучших библиотек по этой теме. - Anti-Grain Geometry. Код открыт.

кстати, юзать можно только версию 2.4, потому что 2.5 испорчена GPLем

Это никак не решает проблему 45 градусов, кстати. Там нет ошибки :)

Её можно ввести принудительно, если координаты считать не по центру пикселя, а по границе :)

Код покажешь? :) С демонстрацией картинки. Я б мож чего изобразил бы, если б не собирался щас свалить до вечера :)

Код покажешь? :)

Дайте ссылку на какую-нибудь JS-библиотеку, где можно крупномасштабно пиксели ставить на координатной сеточке. А то велосипедить ломает :) Не в файлик же писать в XXI веке...

испорчена GPLем

Ага. Испорчена. А потом эти люди размазывая кулаком сопли по чумазому лицу ноют что им, дескать, систему не переустановить на каком-нибудь неиспорченном ГПЛем Андроиде.

Поэксперементировал с коэффициентами. В общем с тремя точками получается, весовые коэффициенты 0.2/0.7/0.1, обрабатывается группами по 4 пикселя, области обработки имеют площади 1х0.5/1х1/1х0.5, скриншот: https://dl.dropboxusercontent.com/u/31471800/p2p/0.2-0.7-0.1.png Если вам нужно, в «личку» кину ссылку на статью, если напишу.

Я не очень понял. Весовые коэффициенты должны зависеть от положения пикселя относительно линии.

Окей, как с вам кинуть ссылку когда напишу статью? Просто не хочу свой бложик сильно пиарить, тем паче нa ЛОРе.

aivanov(собака)keldysh(точка)ru

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

Парни, кажется я придумал хороший алгоритм, но сейчас у меня ночь, а завтра пары. Часов в 5 вечера по киевскому времени скину вам код если все получится.

Я Вам сюда отвечу;-)

ИМНО наиболее Ъ путь, это вычисление веса пикселя на основе расстояния от центра пикселя до линии (в евклидовой метрике, а не как у Вас по вертикали или горизонтали, наск я понял Вашу статью). Расстояние считается как скалярное произведение двух 2D векторов, это дешевая операция.

Для вычисления веса нужна весовая ф-я. Самыми подходящими являются т.н. лямбда-функции, которые строятся рекурсивно. Следующая функция строится как результат фильтрации предыщуей скользящим окном. L0 это П-образный импульс. L1 это треугольный импульс. L2 это шапочка с непрерывной первой производной, и т.д.

Мы для подавления алиасинга юзаем вот такую (это то ли L2 то ли L3, уже забыл а разбираться сейчас некогда).

        inline double sign(double x) { return (x<0.)?-1.:1.; }
        inline double Lambda3m1(double x) { //-2<x<2; -0.5<f<0.5
                const double ax = fabs(x), sx = sign(x);
                if( ax>=2. ) return 0.5*sx;
                const double xx = x*x, xxx = x*xx, xxxx = xx*xx, x1 = x, x2 = ax*x, x3 = xxx, x4 = ax*xxx;
                if( ax>=1. ) return -(1./6.)*sx+(4./3.)*x1-1*x2+(1./3.)*x3-(1./24.)*x4;
                return (2./3.)*x1-(1./3.)*x3+(1./8.)*x4;
        }

Такой подход работает для любых углов наклона. Отдельный вопрос как выбирать пиксели для проверки;-) Ну и из общих соображений, чем шире шаблон тем глаже визуально линия.

Итак парни, извините за задержку, оказалось чуть труднее чем думал. Я реализовал только часть алгоритма когда линия идем под углом от 0 до -Pi/4(я там напутал с углом, короче линия идет в низ не более чем под 45 градусов к Ох)

Я писал на Qt, верхняя линия моя, ниже пример AA от Qt ещё ниже просто линия. https://github.com/theGABS/AntiAliathingLine

Сам алгоритм такой, представляем что линия имеет ширину в один пиксель, дальше вычисляем для каждого пикселя какая часть линии заходит на этот пиксель - находим площадь, максимум 1 - значит альфа = S/1 = S

Сам алгоритм такой, представляем что линия имеет ширину в один пиксель, дальше вычисляем для каждого пикселя какая часть линии заходит на этот пиксель - находим площадь, максимум 1 - значит альфа = S/1 = S

Этот алгоритм имеет проблему при угле 45 градусов, там попадание в пиксель абсолютно точное, с чего и началась тема.

Как вариант, надо считать яркости пикселей не только в целых точках, для угла 45 градусов подошёл бы шаг в половину пикселя.

Что??? Код пробовал смотреть? Все там нормально.

Парни, я как всегда немного напутал в коде(пропустил деление на двое в одном месте кода) Залил на гитхаб исправленную версию кода. https://github.com/theGABS/AntiAliathingLine П.С. в этот раз там рисуется линия под углом 45 градусов.

код смотреть не пробовал, картинок нет :)

Не осилил добавление картинок на гитХаб. http://itmages.ru/image/view/2086291/cc2ef778