Параметризация дуги квадратичной кривой Безье

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

Моя информация взята из этого документа WarpingTextToSplines, поэтому приведенный ниже код является моей интерпретацией псевдо -код.

Прежде всего, найдите (приблизительную) длину кривой и разделите ее на участки:

private void buildCurveTables()
{
    int curveSegments = 100;
    lengthTable = new float[curveSegments + 1];

    Vector3 previousPoint = GetBezierPoint(0, curvePoints[0], curvePoints[1], curvePoints[2]);

    float sum = 0;
    lengthTable[0] = 0;

    for (int i = 1; i < lengthTable.Length; i++)
    {
        Vector3 currentPoint = GetBezierPoint(i / (float) lengthTable.Length, curvePoints[0], curvePoints[1], curvePoints[2]);
        sum += Vector3.Distance(previousPoint, currentPoint);
        lengthTable[i] = sum;
        previousPoint = currentPoint;
    }

    totalCurveLength = sum;
}

Это хранит 100 значений длин вдоль кривой. Они используются позже для определения правильного положения на кривой для размещения сетки. Значение находится в таблице, используя это:

private float findPositionOnCurve(float u)
{
    float t; //Find t for the given u
    float targetArcLength = u * lengthTable[lengthTable.Length-1];

    //Debug.Log("u is: " + u);

    int index = Array.BinarySearch(lengthTable, targetArcLength);

    if (u >=1)
    {
        return 1;
    }

    if (index < 0)
    {
        index = ~index - 1;
        //No exact match found
        float lengthBefore = lengthTable[index];
        return (index + (targetArcLength - lengthBefore) / (lengthTable[index + 1] - lengthBefore)) / lengthTable.Length;
    }
    else
    {
        //Exact match found
        t = index / (float)lengthTable.Length - 1;
        //Debug.Log("Exact match, returning " + t);
        return t;
    }
}

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

 private Vector3 GetBezierPoint(float t, Vector3 start, Vector3 control, Vector3 end)
{
    //float x = (((1 - t) * (1 - t)) * start.x) + (2 * t * (1 - t) * control.x) + ((t * t) * end.x);
    //float y = (((1 - t) * (1 - t)) * start.y) + (2 * t * (1 - t) * control.y) + ((t * t) * end.y);
    //float z = (((1 - t) * (1 - t)) * start.z) + (2 * t * (1 - t) * control.z) + ((t * t) * end.z);
    //return new Vector3(x, y, z);

    //http://answers.unity3d.com/questions/990171/curve-between-lerps.html
    float rt = 1 - t;
    return rt * rt * start + 2 * rt * t * control + t * t * end;
}

ОБНОВЛЕНИЕ

Я также добавлю код, который я написал для создания экземпляров объектов на кривой, на случай, если я сделаю что-то глупое.

//Only try to curve the objects once the control point has been put down.
 if (curvedMode && createdCurveControlHandle)
 {
 Vector3 startOfCurve = getCurveStartPoint().transform.position;

 curvePoints = new Vector3[3] { startOfCurve, currentCurveControlHandle.transform.position, currentMousePosition };

 buildCurveTables();

//Lerp value is generated through a loop that generates 'n' number of 
objects based on the distance between the start and current mouse position
 float mappedLerp = findPositionOnCurve(lerpValue); 

 Vector3 pointTest = GetBezierPoint(mappedLerp, curvePoints[0], curvePoints[1], curvePoints[2]);

 nextPlacementLocationTarget = pointTest;

 nextPosition = Vector3.Lerp(startOfCurve, nextPlacementLocationTarget,mappedLerp);}

Вот несколько поисковых запросов lerp:

Lerp: 0.32 mappedLerp: 0.1659664
Lerp: 0.36 mappedLerp: 0.1896916
Lerp: 0.3999999 mappedLerp: 0.2143274
Lerp: 0.4399999 mappedLerp: 0.2399609
Lerp: 0.4799999 mappedLerp: 0.2667291
Lerp: 0.5199999 mappedLerp: 0.2948231
Lerp: 0.5599999 mappedLerp: 0.3244205

ДОПОЛНИТЕЛЬНОЕ ОБНОВЛЕНИЕ

После некоторой настройки и помощи пользователя SO «MBo» теперь у меня есть довольно равномерное распределение с использованием фиксированной длины из десяти объектов. Однако они по-прежнему распределяются больше к началу кривой.

Я обновил свой код, чтобы использовать создание таблицы и двоичный поиск, упомянутые во втором ответе на этот вопрос SO Как-достичь-равномерной-скорости-движения-на-кривой-Безье

Я прошел и проверил это так много раз, что у меня начинает сходить с ума. Я не уверен, что моя математика отключена, поэтому я что-то неправильно понимаю.

Большинство мешей на кривой вначале сгруппированы, затем через некоторое время они начинают выравниваться.

Если у кого-то есть идеи или предложения, буду очень признателен.

Спасибо


person Tony    schedule 04.08.2017    source источник


Ответы (1)


Ваша математика Безье и построение таблиц выглядят нормально. Но поиск странный.

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

alow := 0;
ahigh := A.Count - 1;
while ahigh - alow > 1 do begin
  j := (ahigh + alow) div 2;
  if Value <= A[j] then
    ahigh := j
  else
    alow := j;
end;

Если вы размещаете объекты вдоль кривой по порядку (например, символы текста), то линейный поиск может быть более эффективным — вы всегда двигаетесь вперед, поэтому следующий поиск начинается с текущего индекса:

i = 0  // or current index
while (A[i] < Value) && (i < A.Length)
   i++

Обратите внимание, что распределение параметра t по длине дуги Безье может быть весьма неравномерным. Пример показывает две кривые, обе с параметром t-шага 1/8. t=0,5 соответствует 0,28 полной длины во втором случае.

введите здесь описание изображения

А теперь даже точки длины дуги в диапазоне 0,05..0,95 (relativelength = 0.05 + i / 10.0). Я использовал 2D куб Безье, но принципиальной разницы нет.

введите здесь описание изображения

person MBo    schedule 04.08.2017
comment
Спасибо за информацию. Я только что попытался изменить поиск, используя код из этого поста SO; gamedev.stackexchange.com/questions/5373/ Однако я все еще вижу много группировок на кривой. - person Tony; 04.08.2017
comment
Вы проверили lengthTable значения на гладкость? - person MBo; 04.08.2017
comment
Как выглядит ваш Безье? Контрольная точка сильно смещена в одну сторону? Отметим, что распределение t-параметра по длине резко различается для этих двух кривых: (0,0),(100,50),(200,0) и (0,0),(-5,50),(200, 0) - person MBo; 05.08.2017
comment
Я пробовал с кривыми, похожими на оба ваших примера. Оба имеют больше точек, сгруппированных ближе к началу кривой. Они выравниваются на расстоянии, но это всегда начало кривой, где они наиболее сгруппированы. - person Tony; 05.08.2017
comment
Я не вижу вопиющих ошибок глазами (кроме разделов обновления, которые эксплуатируют какое-то отображение?). Здесь i / (float) lengthTable.Lengthнужно использовать curveSegments делитель, но ошибка небольшая. Странен ли результат и для (0,0),(100,0),(200,0)? - person MBo; 05.08.2017
comment
Что ж, я только что изменил код на i / (float) curvePoints.Length, и теперь распределение в начале лучше в начале и более сгруппировано по мере увеличения длины. Рисование кривой по прямой линии, как вы предложили, выглядит нормально, но в начале кривой все еще далеко до многих точек. - person Tony; 05.08.2017
comment
Не могли бы вы создать lengthTable для прямой линии, curvePoints = 10 и показать ее? Если таблица в порядке, значит, в вашей процедуре поиска скрывается ошибка. - person MBo; 05.08.2017
comment
На данный момент, из-за того, как я все настроил, я могу создать кривые только с тремя точками. Однако на этом снимке экрана показана короткая кривая по прямой линии с 10 размещенными вдоль нее объектами. puu.sh/x25Qe/cd27bd4794.png - person Tony; 05.08.2017
comment
Да, это недостаток. Я добавил результат моей быстрой реализации, выглядит нормально. Вы смотрели на саму таблицу (до поиска)? - person MBo; 05.08.2017
comment
Хм, ну теперь я не знаю, где искать. Я только что попытался использовать фиксированное значение пяти объектов, и они неравномерно распределены. Интервал стал намного лучше, но он по-прежнему неравномерно распределен. Спасибо за всю вашу помощь, хотя, действительно ценю это! - person Tony; 05.08.2017
comment
I'm not sure where to look: Просто распечатайте lengthTable содержимое - person MBo; 05.08.2017
comment
Я только что создал новую кривую и распечатал таблицу длин, она доступна здесь; pastebin.com/bAF7DjYW - person Tony; 05.08.2017
comment
Давайте продолжим обсуждение в чате. - person Tony; 05.08.2017