Растеризация кривой второго порядка

@positron · Регистрация: 22.04.2010

Студворк — интернет-сервис помощи студентам

Есть функция, к примеру ax^2+bx+c, необходимо растеризовать ее с устранением ступенчатости. Подскажите каким алгоритмом это осуществлять?

Отобразить изображение функции в массиве пикселей.
P.S. заодно скажите как управлять цветом пикселя (в формате 0x00000000) с помощью сдвигов? К примеру:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const int threshold = 12;
unsigned int* pDest = (unsigned int*)data;
unsigned char src_r, src_g, src_b;
unsigned char add;
unsigned int pixel;
 
src_r = (0x00FF0000 & pSrc[x]) >> 16;
src_g = (0x0000FF00 & pSrc[x]) >> 8;
src_b = (0x000000FF & pSrc[x]);
 
add = rand() % threshold;
add *= (rand() % 2) ? (-1) : (1);
if((src_r > threshold) && (src_r < 255 - threshold))
{
    src_r += add;
}
if((src_g > threshold) && (src_g < 255 - threshold))
{
    src_g += add;
}
if((src_b > threshold) && (src_b < 255 - threshold))
{
    src_b += add;
}
pixel = 0xFF000000 | (src_r << 16) | (src_g << 8) | src_b;
pDest[y * width + x] = pixel;

@Nick Alte · 22.09.2010, 19:07

Во-первых, можно воспользоваться алгоритмами построения сглаженных линий или даже воспользоваться аппаратной поддержкой, через OpenGL. Далее - как обычно: строим массив точек и проводим соединяющие линии.
Во-вторых, можно решить задачу в лоб: определить в аналитическом виде функцию от координат пикселя, которая даёт интенсивность окраски пикселя в зависимости от того, насколько близко он расположен к кривой. Тут есть, конечно, сильная зависимость от отображаемой функции, что невыгодно отличает этот подход от первого. Зато картинка получится максимально точной.
Можно и скомбинировать эти подходы, реализовав алгоритм построения прямой линии со сглаживанием, вычисляющий интенсивность пикселей в зависимости от их близости к линии.

@positron · 22.09.2010, 19:13 **[ТС]**

Сообщение от Nick Alte

насколько близко он расположен к кривой.

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

@Nick Alte · 22.09.2010, 19:36

На практике придётся решать уравнения, что не всегда осуществимо. Надо будет выразить кривую параметрически (зависимость x и y от новой переменной t, простейший случай x = t, но он не всегда применим), взять частные производные, которые дадут вектор касательной, и найти к нему нормаль. Всё это в аналитическом виде. Получим уравнение прямой, перпендикулярной нашей кривой в точке t с коэффициентами, выраженными через t. Решив это уравнение опять же аналитически, мы сможем находить t по координатам данной точки (не точки на кривой, а любой точки в пространстве, лежащей на перпендикуляре), а из него уже найдём x, y наиболее близкой точки на кривой. Для некоторых кривых (например, для спирали) может быть множество решений, тогда надо выбрать ближайшую из точек. Ну а дальше остаётся банально найти расстояние между двумя точками.

@positron · 22.09.2010, 21:01 **[ТС]**

Звучит ну оочень сложно.. Попробую разобраться...

@Nick Alte · 22.09.2010, 22:40

Ну тогда поясню на примере.
Дана кривая y = A*x^2 + B*x + C
Выразим её параметрически: x = t y = A*t^2 + B*t + C
Вектор касательной в точке t: N(t) = {x'(t); y'(t)} = {1; 2*A*t + B} (это обычные производные dx/dt и dy/dt, не совсем то, что в мат. анализе называется частными производными).
Перпендикулярный ему вектор получаем перестановкой компонент и сменой знака у одного из них (любого): P(t) = {2*A*t + B; -1}
Уравнение прямой, параллельной вектору V = {D; E} выглядит так: D*x + E*y + F = 0
Подставив P(t), получаем уравнение перпендикуляра к точке t:
(2*A*t + B) * x - y + F = 0, при этом мы пока не знаем F. Воспользуемся тем фактом, что перпендикуляр заведомо проходит через точку x(t), y(t):
(2*A*t + B) * t - (A*t^2 + B*t + C) + F = 0 -> A*t^2 - C + F = 0 -> F = C - A*t^2
Окончательное уравнение перпендикуляра: (2*A*t + B) * x - y + C - A*t^2 = 0
Теперь, если нам по данной точке {X; Y} надо найти ближайшую точку на кривой, необходимо решить это уравнение относительно t (то есть, выразить t через X и Y):
(2*A*t + B) * X - Y + C - A*t^2 = 0 -> A*t^2 - 2*A*t*X - B*X + Y - C = 0
t(X, Y) = (2*A*X +- sqrt(4*A^2*X^2-4*A*(Y - B*X - C)) ) / (4*A)
Исходя из здравого смысла, у этого уравнения всегда должен иметься хотя бы один корень. Хотя, я мог и что-то напутать в своих выкладках.
В общем случае мы имеем два корня и две точки: {x(t1); y(t1)} и {x(t2); y(t2)}, которые легко можем посчитать по тем параметрическим формулам, с которых начали. Нам остаётся посчитать два расстояния R1 = {x(t1); y(t1)} - {X; Y} и R2 = {x(t2); y(t2)} - {X; Y} и выбрать наименьшее.

@alex_x_x · 22.09.2010, 23:02

ищите реализации алгоритма Брезенхэма, там есть алгоритмы для прямых, окружностей и кривых

@positron · 22.09.2010, 23:59 **[ТС]**

Nick Alte, спасибо огромное, теперь понял, осталось проверить.
alex_x_x, метод брезенхема мне не совсем подходит, т.к. там не тот принцим сглаживания, который нужен мне.

@positron · 23.09.2010, 23:08 **[ТС]**

Ну в общем не очень то и получилось...
Вот такая функция получилась в итоге для определения расстояния:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
double distance(double a, double b, double c, double x, double y)
{
    double t1,t2,r1,r2,D;
    t1=(2.*a*x+pow(4.*pow(a,2.)*pow(x,2.)-4.*a*(y-b*x-c),0.5))/(4.*a);
    t2=(2.*a*x-pow(4.*pow(a,2.)*pow(x,2.)-4.*a*(y-b*x-c),0.5))/(4.*a);
    r1=pow(pow(t1,2.)+pow(a*pow(t1,2.)+b*t1+c,2.),0.5);
    r2=pow(pow(t2,2.)+pow(a*pow(t2,2.)+b*t2+c,2.),0.5);
        
    if(r1<r2)
        return r1;
    else
        return r2;*/
}

вот что получилось if(distance(0.01,1,10,x,y)<10):

а вот что при if(distance(0.01,0,1,x,y)<50)

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

что делать?

@Nick Alte · 24.09.2010, 17:33

Для начала надо было проверить мои выкладки - я вполне мог по пути что-то напутать.
Считать расстояние между точками надо правильно:
D ({x1; y1} - {x2; y2}) = sqrt((x2-x1)^2 + (y2-y1)^2)
Ну и написать функцию более внятно, примерно так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
double distance(double a, double b, double c, double x, double y)
{
    const double t1=( 2*a*x + sqrt(4*a*a*x*x - 4*a*(y-b*x-c)) )/(4*a);
    const double t2=( 2*a*x - sqrt(4*a*a*x*x - 4*a*(y-b*x-c)) )/(4*a);
    const double dx1 = x-t1;
    const double dx2 = x-t2;
    const double dy1 = y - (a*t1*t1+b*t1+c);
    const double dy2 = y - (a*t2*t2+b*t2+c);
    const double r1 = sqrt(dx1*dx1 + dy1*dy1);
    const double r2 = sqrt(dx2*dx2 + dy2*dy2);
    return std::min(r1, r2);   // Ну или   return (r1<r2)?r1:r2;                
}

Но выкладки всё равно проверь, я их наспех писал и мог что-то проглядеть.

@positron · 24.09.2010, 21:48 **[ТС]**

Ну в общем с вашей функцией лучше, но все равно неправильно (if(distance(0.01,0.1,10,x+1,y)<100))

Вывод формулы я проверял, вроде все правильно.

@Nick Alte · 25.09.2010, 18:11

Плохо проверял, я в уравнении прямой накосячил.
Уравнение прямой, параллельной вектору V = {D; E} выглядит так: E*x - D*y + F = 0
Тогда уравнение перпендикуляра x + (2*A*t + B) * y + F = 0
Подставив x(t), y(t) получим t + (2*A*t + B) * (A*t^2 + B*t + C) + F = 0
и F = - (2*A^2*t^3 + 3*A*t^2*B + (1+2*A*C+B^2)*t + B*C)
Получается кубическое уравнение, которое всегда имеет хотя бы один вещественный корень (что соответствует смыслу - для любой точки P0 на плоскости найдётся как минимум одна точка P1 на параболе, из которой можно провести перпендикуляр, проходящий через P0). Оно решается по формуле Кардано, ну и далее как раньше.

Далее, о закраске. Интенсивность должна зависеть от расстояния до кривой не пороговым образом. Простейший случай - линейная зависимость, когда для линии толщиной 2*r0 интенсивность закраски, измеряемая по шкале от 0 до 1 (от пустого пикселя до наиболее интенсивного) вычисляется как I(r) = (r<r0) ? (r0-r)/r0 : 0;

С цветом пикселя удобнее работать, "разобрав" его на отдельные целочисленные компоненты, которые после нужных преобразований приводятся в диапазон от 0 до 255 и "собираются" вместе.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline unsigned int clamp(int cc)
{
    if(cc<0)
        return 0;
    if(cc>255)
        return 255;
    return static_cast<unsigned int>(cc);
}
 
struct rgb {
    int r, g, b;
    rgb(unsigned char R, unsigned char G, unsigned char B): r(R), g(G), b(B) {}
    rgb(unsigned int color=0): r(color & 0xFF), g((color >> 8)&0xFF), b((color>>16)&0xFF) {}
    operator unsigned int () const {return clamp(r) | (clamp(g)<<8) | (clamp(b)<<16);}
}

Новые блоги и статьи Все статьи Все блоги /
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .

@Nick Alte 1675 / 1047 / 174 Регистрация: 27.09.2009 Сообщений: 1,945
	22.09.2010, 19:07
	Во-первых, можно воспользоваться алгоритмами построения сглаженных линий или даже воспользоваться аппаратной поддержкой, через OpenGL. Далее - как обычно: строим массив точек и проводим соединяющие линии. Во-вторых, можно решить задачу в лоб: определить в аналитическом виде функцию от координат пикселя, которая даёт интенсивность окраски пикселя в зависимости от того, насколько близко он расположен к кривой. Тут есть, конечно, сильная зависимость от отображаемой функции, что невыгодно отличает этот подход от первого. Зато картинка получится максимально точной. Можно и скомбинировать эти подходы, реализовав алгоритм построения прямой линии со сглаживанием, вычисляющий интенсивность пикселей в зависимости от их близости к линии. 1

@Nick Alte 1675 / 1047 / 174 Регистрация: 27.09.2009 Сообщений: 1,945
	22.09.2010, 19:36
	На практике придётся решать уравнения, что не всегда осуществимо. Надо будет выразить кривую параметрически (зависимость x и y от новой переменной t, простейший случай x = t, но он не всегда применим), взять частные производные, которые дадут вектор касательной, и найти к нему нормаль. Всё это в аналитическом виде. Получим уравнение прямой, перпендикулярной нашей кривой в точке t с коэффициентами, выраженными через t. Решив это уравнение опять же аналитически, мы сможем находить t по координатам данной точки (не точки на кривой, а любой точки в пространстве, лежащей на перпендикуляре), а из него уже найдём x, y наиболее близкой точки на кривой. Для некоторых кривых (например, для спирали) может быть множество решений, тогда надо выбрать ближайшую из точек. Ну а дальше остаётся банально найти расстояние между двумя точками. 1

@positron 22 / 7 / 2 Регистрация: 22.04.2010 Сообщений: 105
	22.09.2010, 21:01 [ТС]
	Звучит ну оочень сложно.. Попробую разобраться... 0

@Nick Alte 1675 / 1047 / 174 Регистрация: 27.09.2009 Сообщений: 1,945
	22.09.2010, 22:40
	Ну тогда поясню на примере. Дана кривая y = Ax^2 + Bx + C Выразим её параметрически: x = t y = At^2 + Bt + C Вектор касательной в точке t: N(t) = {x'(t); y'(t)} = {1; 2At + B} (это обычные производные dx/dt и dy/dt, не совсем то, что в мат. анализе называется частными производными). Перпендикулярный ему вектор получаем перестановкой компонент и сменой знака у одного из них (любого): P(t) = {2At + B; -1} Уравнение прямой, параллельной вектору V = {D; E} выглядит так: Dx + Ey + F = 0 Подставив P(t), получаем уравнение перпендикуляра к точке t: (2At + B) * x - y + F = 0, при этом мы пока не знаем F. Воспользуемся тем фактом, что перпендикуляр заведомо проходит через точку x(t), y(t): (2At + B) * t - (At^2 + Bt + C) + F = 0 -> At^2 - C + F = 0 -> F = C - At^2 Окончательное уравнение перпендикуляра: (2At + B) * x - y + C - At^2 = 0 Теперь, если нам по данной точке {X; Y} надо найти ближайшую точку на кривой, необходимо решить это уравнение относительно t (то есть, выразить t через X и Y): (2At + B) X - Y + C - At^2 = 0 -> At^2 - 2AtX - BX + Y - C = 0 t(X, Y) = (2AX +- sqrt(4A^2X^2-4A(Y - BX - C)) ) / (4A) Исходя из здравого смысла, у этого уравнения всегда должен иметься хотя бы один корень. Хотя, я мог и что-то напутать в своих выкладках. В общем случае мы имеем два корня и две точки: {x(t1); y(t1)} и {x(t2); y(t2)}, которые легко можем посчитать по тем параметрическим формулам, с которых начали. Нам остаётся посчитать два расстояния R1 = {x(t1); y(t1)} - {X; Y} и R2 = {x(t2); y(t2)} - {X; Y} и выбрать наименьшее. 2

@alex_x_x бжни 2473 / 1684 / 135 Регистрация: 14.05.2009 Сообщений: 7,162
	22.09.2010, 23:02
	ищите реализации алгоритма Брезенхэма, там есть алгоритмы для прямых, окружностей и кривых 0

@positron 22 / 7 / 2 Регистрация: 22.04.2010 Сообщений: 105
	22.09.2010, 23:59 [ТС]
	Nick Alte, спасибо огромное, теперь понял, осталось проверить. alex_x_x, метод брезенхема мне не совсем подходит, т.к. там не тот принцим сглаживания, который нужен мне. 0

@positron 22 / 7 / 2 Регистрация: 22.04.2010 Сообщений: 105
	24.09.2010, 21:48 [ТС]
	Ну в общем с вашей функцией лучше, но все равно неправильно (if(distance(0.01,0.1,10,x+1,y)<100)) Вывод формулы я проверял, вроде все правильно. 0