Линейная интерполяция по линии Брезенхэма

Я использую линейную интерполяцию для анимации объекта между двумя 2D-координатами на экране. Это довольно близко к тому, что я хочу, но из-за округления я получаю неровное движение. В ASCII-арте:

ooo
  ooo
    ooo
      oo

Обратите внимание, как он движется по сетке Манхэттена, а не поворачивает на 45 градусов. Что мне нужно, так это линейная интерполяция вдоль линии, которую создал бы алгоритм Брезенхэма:

oo
  oo
    oo
      oo

Каждому x соответствует только один y. (И поменяйте местами x/y на крутую линию)

Так почему бы мне просто не использовать алгоритм Брезенхэма? Я, конечно, мог бы, но этот алгоритм итеративный, и я хотел бы знать только одну координату вдоль линии.

Я собираюсь попытаться решить эту проблему, линейно интерполируя координату x, округляя ее до пиксельной сетки, а затем находя соответствующий y. (Опять же, поменяйте местами x/y для крутых линий). Однако независимо от того, как это решение сработает, меня будут интересовать другие предложения и, возможно, предыдущий опыт.


algorithm graphics graphics2d
person Johannes Hoff    schedule 11.09.2012    source источник
comment
Я бы сказал, что ваша идея с округлением кажется подходящей.   -  person Neil    schedule 11.09.2012
comment
Я не уверен, что другой вид округления исправит это. Вам действительно нужно округлить координаты до пиксельной сетки? Что вы используете для рендеринга?   -  person Qnan    schedule 11.09.2012
comment
@Qnan: Да, в этом случае мне нужно округлить до пиксельной сетки, так как я вставляю изображения. Pixel perfect — единственное, что будет хорошо смотреться.   -  person Johannes Hoff    schedule 11.09.2012

Ответы (3)


arrow_upward
6
arrow_downward

Алгоритм Брезенхэма для линий был введен, чтобы рисовать полную линию немного быстрее, чем обычно. У него есть два основных преимущества:

  • Он работает с целочисленными переменными
  • Он работает итеративно, что быстро при рисовании полной линии

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

Вместо этого вы можете использовать другой алгоритм, который приведет к той же строке. Например, DDA (цифровой дифференциальный анализатор). Это в основном тот же подход, который вы упомянули.

Первый шаг: вычислить наклон.

m = (y_end - y_start) / (x_end - x_start)

Второй шаг: рассчитайте шаг итерации, который просто:

i = x - x_start

Третий шаг: вычислить соответствующее значение y:

y = y_start + i * m
  = y_start + (x - x_start) * (y_end - y_start) / (x_end - x_start)
person Nico Schertler    schedule 11.09.2012
comment
Вы можете принять во внимание, что округление от 0,5 доходит до 1, что в принципе несправедливо. В результате получается несимметричная линия. В некоторых случаях этого избежать нельзя (например, при соединении угловых точек в сетке 2x3), но в других случаях можно (например, в сетке 5x3). Эту ошибку допускает даже стандартная программа для рисования Windows. Решением может быть переключение направления округления на 0,5 в середине строки. - person Palo; 11.10.2015
comment
.5 произойдет, если линия пройдет через середину двух соседних пикселей. Вы не можете однозначно решить для одного из них (т.е. один не более правильный, чем другой). Округление — это просто условность, а не ошибка. - person Nico Schertler; 11.10.2015
comment
Нет, в некоторых случаях это нормально, но в других случаях это приводит к асимметричной линии, которая выглядит некрасиво, и просто используя описанный выше метод, вы можете получить более подходящую и красивую визуализацию линии. Ведь это компьютерная графика, так что да, можно гордиться своими условностями... и выглядеть... некрасиво. - person Palo; 12.10.2015
comment
А, теперь я понял, что вы имеете в виду. Да, это верный подход. - person Nico Schertler; 13.10.2015

arrow_upward
0
arrow_downward

Вот решение, с которым я столкнулся:

public static Vector2 BresenhamLerp(Vector2 a, Vector2 b, float percent)
{
    if (a.x == b.x || Math.Abs(a.x - b.x) < Math.Abs(a.y - b.y))
    {
        // Didn't do this part yet. Basically, we just need to recurse
        // with x/y swapped and swap result on return
    }

    Vector2 result;
    result.x = Math.Round((1-percent) * a.x + percent * b.x);

    float adjustedPercent = (result.x - a.x + 0.5f) / (b.x - a.x);
    result.y = Math.Round((1-adjustedPercent) * a.y + adjustedPercent * b.y);

    return result;
}
person Johannes Hoff    schedule 11.09.2012

arrow_upward
0
arrow_downward

Это то, что я только что понял, будет работать. Наверное не самые красивые интерполяции, но это просто 1-2 прибавления float за итерацию на линии с одноразовым предрасчетом. Работает путем вычисления количества шагов на манхэттенской матрице.

А, и еще не ловит случай, когда линия вертикальная (dx=0)

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

void Brepolate( uint8_t* pColorBuffer, uint8_t cs, float xs, float ys, float zs, uint8_t ce, float xe, float ye, float ze )
{
    float nColSteps = (xe - xs) + (ye - ys);
    float fColInc = ((float)cs - (float)ce) / nColSteps;
    float fCol = cs;

    float dx = xe - xs;
    float dy = ye - ys;

    float fCol = cs;

    if (dx > 0.5)
    {
        float de = fabs( dy / dx );
        float re = de - 0.5f;

        uint32_t iY = ys;
        uint32_t iX;

        for (   uint32_t    iX = xs;
                            iX <= xe;
                            iX++ )
        {
            uint32_t off = surf.Offset( iX, iY );
            pColorBuffer[off] = fCol;
            re += de;
            if (re >= 0.5f)
            {
                iY++;
                re -= 1.0f;
                fCol += fColInc;
            }
            fCol += fColInc;
        }
    }
}
person antipattern    schedule 04.05.2017