Заполнение квадратичной Безье

Проходи битмап по y-координате. Если сканирующая линия и твоя кривая пересеклись, вычисляй координаты пересечения слева и справа. Заливай этот отрезок. PROFIT

man scanline fill

Проходи битмап по Х-координате и заливай отрезок от точки на прямой AC до точки на кривой

Заполняй сверху вниз: для каждого x от A до C вычисляешь y. Затем все пиксели ниже зарисовываешь.

Начни с точки (A+B+C)/3. Потом от неё во стороны делай заливку, пока не пересечёшь границу.

Проходи битмап по Х-координате

Классический scanline делают по y-координате. Обычно строк (пикселей по вертикали) меньше чем столбцов, считать меньше. Хотя хз что там у ТС

Eddy_Em, MyTrooName, buddhist

Дело в том, что AC в большинстве случаев не параллельна OX.

Во пример кривой: https://dl.dropboxusercontent.com/u/31471800/p2p/Screenshot - 01.09.2014 - 15...

Я так полагаю, что при сканлайне если решать уравнение кривой относительно Х на данной У, то будет проблема
1) Решать уравнение третьей степени для каждой строки попахивает оверхедом
2) Корней может быть несколько, например в таком случае: https://dl.dropboxusercontent.com/u/31471800/p2p/Screenshot - 01.09.2014 - 15... , т.е. простыня кода со всеми описанными случаями будет до Китая.

AC в большинстве случаев не параллельна OX

Построй ее, и будет у тебя дополнительная кривая.

Решать уравнение третьей степени для каждой строки попахивает оверхедом

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

Если хочешь, чтобы это не зависело от фона — придется решать. Но в чем проблема численного решения полиномиального уравнения?

Но в чем проблема численного решения полиномиального уравнения?

В том, что на одно такое решение потребуется 30-50 действий. Умножаем на количество строк и получаем 9000+.

Да не нужны там никакие уравнения! Просто пробегаешься по одной координате, вычисляя другую координату для прямой и безье. И между ними закрашиваешь.

Вариант 2: просто рисуешь прямую и кривую, а потом между ними закрашиваешь любым алгоритмом.

И вообще, какое нафиг нахождение пересечения, когда у тебя прямая горизонтальна? :)

Тебе просто нужны абсциссы двух точек на кривой.

Да не нужны там никакие уравнения! Просто пробегаешься по одной координате, вычисляя другую координату для прямой и безье. И между ними закрашиваешь.

Уравнение квадратичной кривой: https://upload.wikimedia.org/math/f/3/2/f32d4e05be3416029b522ea40a65edc3.png сами посчитаете, сколько нужно действий, чтобы по Y вычислить X кривой?

когда у тебя прямая горизонтальна? :)

Где?

Вариант 2: просто рисуешь прямую и кривую, а потом между ними закрашиваешь любым алгоритмом.

Боюсь, что вы заразились главной болезнью ЛОРа - сообщениенечитательством:

Методы затравки не подходят - создавать новую текстуру а потом ее удалять слишком долго.

Едрена вошь! Ты кривую как рисуешь? Считаешь же? Считаешь! Ну вот одновременно и заполняй!!!!!!!!!!!!!!!!!!!!!!

Какую текстуру? Ты о чем вообще?

Тут телепатов нет. Объясняй подробней.

Для каждого y ты проводишь горизонтальную прямую

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

1) из точек A, B, C выбираем самую левую. не ограничивая общности, считаем, что это не B (иначе, s/левую/правую). ну и далее, не ограничивая общности считаем, что это A (A <-> C)

2) от точки A идем вправо по одному пикселю. т.е. двигаем вертикальную прямую слева направо. строим точки отрезка и кривой на этой прямой (или, если отрезок кончился (а рано или поздно он кончится), то начинаем строить кривую со второго конца). проводим через эти точки вертикальный отрезок (заливка)

3) когда отрезок уже кончился и две точки на кривой сошлись, заканчиваем

замена s/левую/правую решается преобразованием координат

в пункте 2 есть 2 варианта: вертикальная прямая пересекает отрезок и кривую, или же кривую в двух местах

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

Я уже думал о таком. Но там реально негде получать на каждом y координату по x. Код.

Как негде? А что такое SmlImageDrawLine? Она ж рисует кривую! Или это из левой библиотеки? Ну так свою функцию напиши, там же вообще как 2 пальца об асфальт!!!

В общем, не выдумывай на пустом месте проблем.

Как негде? А что такое SmlImageDrawLine? Она ж рисует кривую!

Прямую. Моя. Вы мне предлагаете смержить код этой функции в код рисования заполненной кривой и там, получая X и Y получать X прямой на данном Y а дальше использовать заполнение как по scanline?

сколько нужно действий, чтобы по Y вычислить X кривой?

примерно 3-4 сложения, с учетом того, что на предыдущем пикселе у тебя уже посчитано

Это как? Там же не просто коэффициент, а парабола.

dy = a*((x+dx)^2-x^2) + b*dx

dx = 1

dy = a*(2x+1) + b

а теперь считаешь ddy:

ddy = a(2(x+1)+1-2x-1)=2a, кажись

таким образом:

y0 = f(x);
y = f(++x);
dy = y-y0;
cout << y0 << y;

while(...) {
    ++x;
    ddy = 2*a;
    dy += ddy;
    y += dy;
    cout << y;
}    

может, где натупил, но идея такая. итого, в цикле только два сложения. ну три, если x тоже нужен

если решать уравнение кривой относительно Х на данной У, то будет проблема

1) Решать уравнение третьей степени для каждой строки попахивает оверхедом

Да это лет 15 назад на обычных PC того времени уже не было проблемой. А на видеокартах с ускорением того же времени эти кривые безье можно было заливать пачками, с градиентами.

Может тебе посмотреть в сторону OpenGL? Или если хочется руками, найди книжку по компьютерной графике годов 90-х, там все должно быть

Эта идея отыскивается в Гугле по «finite differences», кстати.

Тебе же уже написали, ты ведь рисуешь и кривую и отрезок. Тебе нужно для каждого y, где есть точки кривой или отрезка, посчитать минимальный и максимальный x. Дальше просто зарисовываешь горизонтальный отрезок между двумя иксами.

Может тебе посмотреть в сторону OpenGL?

Нет. Я не хочу зависеть от оборудования\других библиотек. Сейчас мне нужен только xlib + опционально fontconfig.

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

Да вот искал, находится только современный шлак