Унифицированный B-сплайн с использованием алгоритма Дебора

Question

У меня есть очень простой случай, в котором мне нужно нарисовать один равномерный B-сплайн-сегмент степени 2 (4 контрольные точки), и я пытаюсь реализовать алгоритм Дебора в C # (https://en.wikipedia.org/wiki/De_Boor%27s_algorithm), но яЯ сталкиваюсь с проблемой, и никакие чтения и исследования не помогли мне узнать, что происходит.

В моем случае у меня есть только 4 контрольные точки (p1, p2, p3 и p4), определенные вМассив Point []. Поэтому мне нужен только сегмент кривой между точками p2 и p3. Поэтому я построил равномерный массив узлов без ведущих и конечных узлов [0, 1, 2, 3] - в основном я могу просто использовать iв этом случае, но я делаю это ради соблюдения формулы. Я построил реализацию рекурсивной формулы из Википедии:

Что выглядит так:

    Point deBoor(int i, int k, float t, int[] knots)
    {
        //i - knot span index
        //k - degree
        // t - time [0-knots.Length-1]
        //knots - the knots array
        if (k == 0) return points[knots[i]]/3f;
        return ((t - knots[i]) / (knots[i + k] - knots[i])) * deBoor(i, k - 1, t, knots) + ((knots[i + k + 1] - t) / (knots[i + k + 1] - knots[i + 1])) * deBoor(i + 1, k - 1, t, knots);
    }

Я пытаюсь получить точку с помощью метода deBoor следующим образом:

float t = time * (points.Length - 1); //time ranges from 0 to 1
int[] knots = new int[] { 0, 1, 2, 3 };
point = deBoor(0, 2, t, knots);

К сожалению, результат, который я получаю,Неправильно. Это изображение показывает, как выглядят мои контрольные точки.Айк, что я ожидаю получить и что на самом деле я получаю:

Я смотрел на другие реализации, как эта: https://gist.github.com/soraphis/61ee9185416ee23d0d40 и оникажется, что все делают одно и то же, просто по-разному кодируются.Я пытался скопировать их решения, но получил еще худшие результаты.Все это заставляет меня думать, что я упускаю что-то мучительно очевидное.

Answer 1

Вы, кажется, путаете узлы и контрольные точки.Есть несколько вещей, которые нам нужно улучшить в вашем решении, чтобы оно работало.

Функции с нулевым градусом

Как уже отмечалось @fang, ваше решение для k==0 странно.Я предлагаю заменить

if (k == 0) return points[knots[i]]/3f;

на что-то более близкое к исходной формуле, например,

if (k==0)
{
  if (t <= knots[i] && t < knots[i+1])
    return 1;
  else
    return 0;
}

Вектор узла

Как также отметил @fang, для квадратичного сплайнас четырьмя контрольными точками вам нужно семь узлов.Вы упомянули, что вам нужны единообразные узлы, и, исходя из ожидаемого изображения, я бы порекомендовал

int[] knots = new float[] {0, 1/6, 2/6, 3/6, 4/6, 5/6, 1};

Обратите внимание, что узлы теперь находятся в диапазоне от 0 до 1;это означает, что t и time будут одинаковыми, то есть

float t = time; //time ranges from 0 to 1 and so does t

Если вы настаиваете на том, что ваши узлы равны int с (что, ИМХО, способствовало вашей путанице), используйте

int[] knots = new int[] { 0, 1, 2, 3, 4, 5, 6 };
float t = time * 6; //time ranges from 0 to 1 and t from 0 to 6

Обратите внимание, что порядок обмена: t должен быть time масштабирован для охвата всего диапазона узлов.

Оценка

Алгоритм Де Бура оценивает один B-spline , т. Е. Одна из базовых функций (некоторые люди используют противоречивую номенклатуру и используют слово B-spline для всей функции сплайна, а не только для одной из базовых функций; это иногда приводит к путанице).

Неформально говоря, для данной t ваша функция deBoor дает вам коэффициент i -ой контрольной точки, который является скаляром .Следовательно, возвращаемое значение deBoor должно быть float или double или чем-то похожим и, конечно, не point.

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

point value = deBoor(0, 2, t, knots) * points[0]
  + deBoor(1, 2, t, knots) * points[1]
  + deBoor(2, 2, t, knots) * points[2]
  + deBoor(3, 2, t, knots) * points[3];

Обратите внимание, что * обозначает умножение на float и point (вам может потребоваться перегрузить такой оператор), а + обозначаетсумма двух point с (опять же, может потребоваться перегрузка оператора).Я не очень разбираюсь в C #, так что может быть более элегантный способ записать это;например, я предлагаю вам использовать петлю for.

Если вы все еще не уверены, я рекомендую сначала ознакомиться с кривыми Безье, а затем перейти к B-сплайнам.Относительно краткое введение можно найти, например, здесь .Картины выполнены в стиле 90-х годов, но идеи по-прежнему актуальны и представлены в понятной и лаконичной форме.