Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.94
positron
22 / 7 / 1
Регистрация: 22.04.2010
Сообщений: 105
22.09.2010, 18:51     Растеризация кривой второго порядка #1
Есть функция, к примеру 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
Эксперт С++
1591 / 983 / 116
Регистрация: 27.09.2009
Сообщений: 1,898
Завершенные тесты: 1
22.09.2010, 19:07     Растеризация кривой второго порядка #2
Во-первых, можно воспользоваться алгоритмами построения сглаженных линий или даже воспользоваться аппаратной поддержкой, через OpenGL. Далее - как обычно: строим массив точек и проводим соединяющие линии.
Во-вторых, можно решить задачу в лоб: определить в аналитическом виде функцию от координат пикселя, которая даёт интенсивность окраски пикселя в зависимости от того, насколько близко он расположен к кривой. Тут есть, конечно, сильная зависимость от отображаемой функции, что невыгодно отличает этот подход от первого. Зато картинка получится максимально точной.
Можно и скомбинировать эти подходы, реализовав алгоритм построения прямой линии со сглаживанием, вычисляющий интенсивность пикселей в зависимости от их близости к линии.
positron
22 / 7 / 1
Регистрация: 22.04.2010
Сообщений: 105
22.09.2010, 19:13  [ТС]     Растеризация кривой второго порядка #3
Цитата Сообщение от Nick Alte Посмотреть сообщение
насколько близко он расположен к кривой.
вот с этого места поподробнее, я об этом думал, но не смог придумать как определить расстояние от точки (в нашем случае пикселя) до кривой. Теоретически то все просто - провести нормаль через точку к кривой и найти расстояние, но на практике какие формулы использовать)
Nick Alte
Эксперт С++
1591 / 983 / 116
Регистрация: 27.09.2009
Сообщений: 1,898
Завершенные тесты: 1
22.09.2010, 19:36     Растеризация кривой второго порядка #4
На практике придётся решать уравнения, что не всегда осуществимо. Надо будет выразить кривую параметрически (зависимость x и y от новой переменной t, простейший случай x = t, но он не всегда применим), взять частные производные, которые дадут вектор касательной, и найти к нему нормаль. Всё это в аналитическом виде. Получим уравнение прямой, перпендикулярной нашей кривой в точке t с коэффициентами, выраженными через t. Решив это уравнение опять же аналитически, мы сможем находить t по координатам данной точки (не точки на кривой, а любой точки в пространстве, лежащей на перпендикуляре), а из него уже найдём x, y наиболее близкой точки на кривой. Для некоторых кривых (например, для спирали) может быть множество решений, тогда надо выбрать ближайшую из точек. Ну а дальше остаётся банально найти расстояние между двумя точками.
positron
22 / 7 / 1
Регистрация: 22.04.2010
Сообщений: 105
22.09.2010, 21:01  [ТС]     Растеризация кривой второго порядка #5
Звучит ну оочень сложно.. Попробую разобраться...
Nick Alte
Эксперт С++
1591 / 983 / 116
Регистрация: 27.09.2009
Сообщений: 1,898
Завершенные тесты: 1
22.09.2010, 22:40     Растеризация кривой второго порядка #6
Ну тогда поясню на примере.
Дана кривая 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
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
22.09.2010, 23:02     Растеризация кривой второго порядка #7
ищите реализации алгоритма Брезенхэма, там есть алгоритмы для прямых, окружностей и кривых
positron
22 / 7 / 1
Регистрация: 22.04.2010
Сообщений: 105
22.09.2010, 23:59  [ТС]     Растеризация кривой второго порядка #8
Nick Alte, спасибо огромное, теперь понял, осталось проверить.
alex_x_x, метод брезенхема мне не совсем подходит, т.к. там не тот принцим сглаживания, который нужен мне.
positron
22 / 7 / 1
Регистрация: 22.04.2010
Сообщений: 105
23.09.2010, 23:08  [ТС]     Растеризация кривой второго порядка #9
Ну в общем не очень то и получилось...
Вот такая функция получилась в итоге для определения расстояния:
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
Эксперт С++
1591 / 983 / 116
Регистрация: 27.09.2009
Сообщений: 1,898
Завершенные тесты: 1
24.09.2010, 17:33     Растеризация кривой второго порядка #10
Для начала надо было проверить мои выкладки - я вполне мог по пути что-то напутать.
Считать расстояние между точками надо правильно:
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
22 / 7 / 1
Регистрация: 22.04.2010
Сообщений: 105
24.09.2010, 21:48  [ТС]     Растеризация кривой второго порядка #11
Ну в общем с вашей функцией лучше, но все равно неправильно (if(distance(0.01,0.1,10,x+1,y)<100))
Растеризация кривой второго порядка

Вывод формулы я проверял, вроде все правильно.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.09.2010, 18:11     Растеризация кривой второго порядка
Еще ссылки по теме:

C++ Изобразите скатывание шарика по кривой
Отрисовка движения шарика по кривой C++
Алгоритм Рунге-Кутта для производной второго порядка C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Nick Alte
Эксперт С++
1591 / 983 / 116
Регистрация: 27.09.2009
Сообщений: 1,898
Завершенные тесты: 1
25.09.2010, 18:11     Растеризация кривой второго порядка #12
Плохо проверял, я в уравнении прямой накосячил.
Уравнение прямой, параллельной вектору 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);}
}
Yandex
Объявления
25.09.2010, 18:11     Растеризация кривой второго порядка
Ответ Создать тему
Опции темы

Текущее время: 16:15. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru