Задача — при рисовании freeform (как в Paint'е) чтобы получалась линия не "дерганная", а сглаженная.
По-русски, видимо, это будет интерполяция кривой при большом количестве точек? Или рисовалки, в которых получаются "плавные" линии, просто бОльшую часть точек игнорируют?

Господа, ткните носом, пожалуйста — куда смотреть?

Здравствуйте, Зверёк Харьковский, Вы писали:

ЗХ>Задача — при рисовании freeform (как в Paint'е) чтобы получалась линия не "дерганная", а сглаженная.
ЗХ>По-русски, видимо, это будет интерполяция кривой при большом количестве точек? Или рисовалки, в которых получаются "плавные" линии, просто бОльшую часть точек игнорируют?

ЗХ>Господа, ткните носом, пожалуйста — куда смотреть?

Ключевые слова: antialiasing, McSeem2, antigrain geometry

Здравствуйте, Кодт, Вы писали:

ЗХ>>Задача — при рисовании freeform (как в Paint'е) чтобы получалась линия не "дерганная", а сглаженная.
ЗХ>>По-русски, видимо, это будет интерполяция кривой при большом количестве точек? Или рисовалки, в которых получаются "плавные" линии, просто бОльшую часть точек игнорируют?

К>Ключевые слова: antialiasing, McSeem2, antigrain geometry

Подозреваю, что вопрос не об этом. Вопрос о том, как аппроксимировать набор точек с шумом последовательностью гладких кривых или одной кривой большого порядка. В AGG такого нет пока что.
Можно, например, предложить для начала вот это:
http://astronomy.swin.edu.au/~pbourke/curves/bezier/

/*
   General Bezier curve
   Number of control points is n+1
   0 <= mu < 1    IMPORTANT, the last point is not computed
*/
XYZ Bezier(XYZ *p,int n,double mu)
{
   int k,kn,nn,nkn;
   double blend,muk,munk;
   XYZ b = {0.0,0.0,0.0};

   muk = 1;
   munk = pow(1-mu,(double)n);

   for (k=0;k<=n;k++) {
      nn = n;
      kn = k;
      nkn = n - k;
      blend = muk * munk;
      muk *= mu;
      munk /= (1-mu);
      while (nn >= 1) {
         blend *= nn;
         nn--;
         if (kn > 1) {
            blend /= (double)kn;
            kn--;
         }
         if (nkn > 1) {
            blend /= (double)nkn;
            nkn--;
         }
      }
      b.x += p[k].x * blend;
      b.y += p[k].y * blend;
      b.z += p[k].z * blend;
   }

   return(b);
}

Но здесь каждая точка требует O(N^2) вычислений. То есть, для всей кривой будет O(N^2 * K).

Здравствуйте, Кодт, Вы писали:

ЗХ>>Задача — при рисовании freeform (как в Paint'е) чтобы получалась линия не "дерганная", а сглаженная.
ЗХ>>По-русски, видимо, это будет интерполяция кривой при большом количестве точек? Или рисовалки, в которых получаются "плавные" линии, просто бОльшую часть точек игнорируют?

ЗХ>>Господа, ткните носом, пожалуйста — куда смотреть?

К>Ключевые слова: antialiasing, McSeem2, antigrain geometry

Умный, да?
AGG-ом я пользуюсь уже полгода
Но тут другая задача — понадобилось мне сделать очень простенький граф. редактор (по сути — только freehand рисование). И вот в нем нужна эта самая плавность. То есть — если в Paint'e карандашиком рисовать — линия получается "дерганная", а, скажем, в Corel Draw — плавная дуга. Меня интересует не уровень одного пиксела (ступеньки), а общая картинка.

Понятно объяснил? Или нарисовать, что я имею в виду?

Здравствуйте, McSeem2, Вы писали:

MS>Здравствуйте, Кодт, Вы писали:

ЗХ>>>Задача — при рисовании freeform (как в Paint'е) чтобы получалась линия не "дерганная", а сглаженная.
ЗХ>>>По-русски, видимо, это будет интерполяция кривой при большом количестве точек? Или рисовалки, в которых получаются "плавные" линии, просто бОльшую часть точек игнорируют?

К>>Ключевые слова: antialiasing, McSeem2, antigrain geometry

MS>Подозреваю, что вопрос не об этом. Вопрос о том, как аппроксимировать набор точек с шумом последовательностью гладких кривых или одной кривой большого порядка.


MS>Можно, например, предложить для начала вот это:

Ага, про Безье знаю. Просто думал, может чего проще есть?

ЗЫ: пользуясь случаем хочу принести публичную благодарность автору AGG от Радиоастрономического Института Академии Наук Украины за неоценимую помощь его библиотеки в отображении сканов радиотелескопов УРАН-1 и др.

Здравствуйте, Зверёк Харьковский, Вы писали:

ЗХ>Ага, про Безье знаю. Просто думал, может чего проще есть?

Безье не работает толком. Во-первых, жутко тормозно, во-вторых, скорее всего не то, что надо, в-третьих, проблемы с числовой стабильностью. Выражение double munk = pow(1.0 — mu, (double)n); при больших степенях и mu близким к 1 банально обращатся в 0.
http://www.antigrain.com/stuff/general_bezier2.zip
Хотя, конечно колбасит ее весьма забавно.

Надо что-то простое, типа эмуляции притяжения. В химическом скетчере я сделал "легкое" сглаживание для лассо:

            x0 = m_molPointerX;
            y0 = m_molPointerY;
            if (m_coordNumPoints > 1)
            {
               lp = m_coordBuffer + m_coordNumPoints * 2 - 4;
               x1 = lp[0];
               y1 = lp[1];
               x2 = (x1 + x0) / 2.0;
               y2 = (y1 + y0) / 2.0;
               lp[2] = x2;
               lp[3] = y2;
            }
            m_coordBuffer[m_coordNumPoints * 2]     = x0;
            m_coordBuffer[m_coordNumPoints * 2 + 1] = y0;
            m_coordNumPoints++;

И вообще, можно тривиально усреднять соседние точки (отдельно по X и Y), после чего пройтись по результату кубическим сплайном, если есть желание.
Сейчас проверю — интересно. Тем более, пятница-вечер. Работа не вааще не прет...

http://antigrain.com/stuff/bspline3.zip

Идея проста — усредняем кординаты трех точек и записываем результат во временный буфер. Для крайних точек усредняем только две.

Повторяем операцию N раз.

Мы убрали высокочастотный шум, но не добавили новых точек для гладкости. Добавляем при помощи любой интерполяции, например, bspline.

Здравствуйте, McSeem2, Вы писали:

ЗХ>>Ага, про Безье знаю. Просто думал, может чего проще есть?

MS>Безье не работает толком. Во-первых, жутко тормозно, во-вторых, скорее всего не то, что надо, в-третьих, проблемы с числовой стабильностью. Выражение double munk = pow(1.0 — mu, (double)n); при больших степенях и mu близким к 1 банально обращатся в 0.
MS>http://www.antigrain.com/stuff/general_bezier2.zip
MS>Хотя, конечно колбасит ее весьма забавно.

Во! поэтому и не хотелось Безье!

MS>Надо что-то простое, типа эмуляции притяжения. В химическом скетчере я сделал "легкое" сглаживание для лассо:
Глянул сейчас в скетчере — это уже "почти". Но все равно несколько угловато.

MS>И вообще, можно тривиально усреднять соседние точки (отдельно по X и Y), после чего пройтись по результату кубическим сплайном, если есть желание.
О! Слово "сплайн" мне знакомо... Вот это уже похоже ближе к телу.

MS>Сейчас проверю — интересно. Тем более, пятница-вечер. Работа не вааще не прет...

Здравствуйте, McSeem2, Вы писали:

MS>http://antigrain.com/stuff/bspline3.zip

MS>Идея проста — усредняем кординаты трех точек и записываем результат во временный буфер. Для крайних точек усредняем только две.

MS>Повторяем операцию N раз.

MS>Мы убрали высокочастотный шум, но не добавили новых точек для гладкости. Добавляем при помощи любой интерполяции, например, bspline.

Вот это уже совсем почти-почти то что надо. Проблема — при быстром рисовании (получается большая ломанная из небольшого кол-ва точек) интерполирующая линия далековато от ломанной...
Как это можно поправить?

Здравствуйте, Зверёк Харьковский, Вы писали:

ЗХ>Вот это уже совсем почти-почти то что надо. Проблема — при быстром рисовании (получается большая ломанная из небольшого кол-ва точек) интерполирующая линия далековато от ломанной...
ЗХ>Как это можно поправить?

Можно попробовать тривиальный метод. Дробим длинные сегменты на более короткие. Сейчас проверю.

ЗХ>Вот это уже совсем почти-почти то что надо. Проблема — при быстром рисовании (получается большая ломанная из небольшого кол-ва точек) интерполирующая линия далековато от ломанной...
ЗХ>Как это можно поправить?

Да, добавление точек вполне себе работает. Но вообще-то, разных методов аппроксимации — завались. Этот — чисто простейший, наколенно-доморощенный.
Вот, например: http://www.rsdn.ru/Forum/Message.aspx?mid=696322&only=1

Автор: peterbes
Дата: 27.06.04

http://www.ibiblio.org/e-notes/Splines/Intro.htm

добавление точек:

    virtual void on_mouse_move(int x, int y, unsigned flags)
    {
        if(flags & agg::mouse_left)
        {
            if(m_path.total_vertices())
            {
                double x1, y1;
                m_path.vertex(m_path.total_vertices() - 1, &x1, &y1);
                double d = agg::calc_distance(x1, y1, x, y);
                const double min_dist = 10.0;
                if(d > min_dist)
                {
                    double k = 0.0;
                    double dd = min_dist / d;
                    while(k < 0.99)
                    {
                        m_path.line_to(x1 + (x - x1) * k, y1 + (y - y1) * k);
                        k += dd;
                    }
                }
            }

            m_path.line_to(x, y);
            force_redraw();
        }
    }

Сабж. Не знаю, что б я без тебя делаль
С меня — пиво

Здравствуйте, Зверёк Харьковский, Вы писали:

ЗХ>Задача — при рисовании freeform (как в Paint'е) чтобы получалась линия не "дерганная", а сглаженная.


Если еще актуально, глянь
http://www.simdesign.nl/Components/DouglasPeucker.html

Здравствуйте, MBo, Вы писали:

MBo>Если еще актуально, глянь
MBo>http://www.simdesign.nl/Components/DouglasPeucker.html

Да, кстати, весьма интересно. А потом полигон интерполируем кубическим сплайном. Получаем то же самое, но очень гладкое и красивое

ЗХ> Задача — при рисовании freeform (как в Paint'е) чтобы
ЗХ> получалась линия не "дерганная", а сглаженная.

Ну мужик насмешил, дёрганная линия я такого никогда не слышал.
))

Хочешь рисовать красиво ставь себе Platform SDK и рисуй через GDI+