Получение нормали для точки на кривой Безье на самом деле довольно прямолинейно, поскольку нормали просто перпендикулярны касательной функции (ориентированы в плоскости направления движения кривой), а касательная функция кривой Безье на самом деле просто еще одна кривая Безье, на 1 порядок ниже. Найдем нормаль кубической кривой Безье. Обычная функция, где (a,b,c,d) — координаты кривой в одном измерении:
function computeBezier (t, a, b, c, d) {
return a * (1-t)³ + 3 * b * (1-t)² * t + 3 * c * (1-t) * t² + d * t³
}
Обратите внимание, что кривые Безье симметричны, единственная разница между t
и 1-t
заключается в том, какой конец кривой представляет «начало». Использование a * (1-t)³
означает, что кривая начинается с a
. Использование a * t³
вместо этого заставит его начинаться с d
.
Итак, давайте определим быструю кривую со следующими координатами:
a = (-100,100,0)
b = (200,-100,100)
c = (0,100,-500)
d = (-100,-100,100)
![просто трехмерная кривая](https://i.stack.imgur.com/Xginn.jpg)
Чтобы получить нормаль для этой функции, нам сначала понадобится производная:
function computeBezierDerivative (t,a,b,c,d) {
a = 3*(b−a)
b = 3*(c-b)
c = 3*(d-c)
return a * (1-t)² + 2 * b * (1-t) * t + c * t²
}
Сделанный. Вычисление производной до глупости просто (фантастическое свойство кривых Безье).
Теперь, чтобы получить нормаль, нам нужно взять нормализованный вектор касательной с некоторым значением t
и повернуть его на четверть оборота. Мы можем повернуть его в нескольких направлениях, поэтому еще одно ограничение состоит в том, что мы хотим повернуть его только в плоскости, которая определяется касательным вектором, а касательный вектор «прямо рядом с ним», на бесконечно малом расстоянии друг от друга.
Касательный вектор для любой кривой Безье формируется просто путем взятия любых имеющихся у вас измерений и их оценки по отдельности, поэтому для трехмерной кривой:
| computeBezierDerivative(t, x values) | |x'|
Tangent(t) = | computeBezierDerivative(t, y values) | => |y'|
| computeBezierDerivative(t, z values) | |z'|
Опять же, довольно просто вычислить. Чтобы нормализовать этот вектор (или фактически любой вектор), мы просто выполняем деление вектора на его длину:
|x'|
NormalTangent(t) = |y'| divided by sqrt(x'² + y'² + z'²)
|z'|
Итак, давайте нарисуем их зеленым цветом:
![наша кривая с касательными, вычисленными во многих точках](https://i.stack.imgur.com/URfl4.jpg)
Единственный трюк теперь состоит в том, чтобы найти плоскость, в которой можно повернуть вектор касательной, чтобы превратить касательную в нормаль. Мы знаем, что можем использовать другое значение t, сколь угодно близкое к тому, которое нам нужно, и превратить его во второй касательный вектор, чертовски близкий к той же точке, для нахождения плоскости с произвольной точностью, поэтому мы можем сделать это:
Учитывая исходную точку f(t1)=p
, мы берем точку f(t2)=q
с t2=t1+e
, где e — небольшое значение, например 0,001, — эта точка q
имеет производную q' = pointDerivative(t2)
, и, чтобы упростить нам задачу, мы перемещаем этот касательный вектор чуть-чуть на p-q
, так что оба вектора "начинаются" с p
. Довольно просто.
Однако это эквивалентно вычислению первой и второй производной в точке p
, а затем формированию второго вектора путем сложения этих двух вместе, поскольку вторая производная дает нам изменение касательной в точке, поэтому добавление вектора второй производной к вектору вектор первой производной дает нам два вектора на плоскости в точке p
без необходимости поиска соседней точки. Это может быть полезно для кривых с разрывами производной, т. е. для кривых с выступами.
Теперь у нас есть два вектора, исходящие из одной и той же координаты: наша настоящая касательная и касательная «следующей» точки, которая настолько близка, что вполне может быть одной и той же точкой. К счастью, из-за того, как работают кривые Безье, эта вторая касательная никогда не совпадает, но немного отличается, и «слегка отличается» — это все, что нам нужно: если у нас есть два нормализованных вектора, начинающихся в одной и той же точке но указывая в разные стороны, мы можем найти ось, вокруг которой нам нужно повернуть одну, чтобы получить другую, просто взяв перекрестное произведение между ними, и, таким образом, мы можем найти плоскость, через которую проходят они оба.
Порядок имеет значение: мы вычисляем c = тангенс₂ × тангенс₁, потому что, если мы вычислим c = тангенс₁ × тангенс₂, мы будем вычислять ось вращения и результирующие нормали в «неправильном» направление. Исправить это буквально просто «взять вектор, умножить на -1» в конце, но зачем исправлять постфактум, когда мы можем сделать это правильно, здесь. Давайте посмотрим на эти оси вращения синим цветом:
![наша кривая с добавленной осью перекрестного произведения](https://i.stack.imgur.com/B0Zul.jpg)
Теперь у нас есть все необходимое: чтобы превратить наши нормализованные касательные векторы в векторы нормалей, все, что нам нужно сделать, это повернуть их вокруг только что найденных осей на четверть оборота. Если мы повернем их в одну сторону, мы получим нормали, если мы повернем их в другую сторону, мы получим нормали, обращенные назад.
Для произвольного вращения вокруг оси в 3D эта работа, возможно, кропотлива, но несложна, а четверть оборота вообще особенные тем, что они сильно упрощают математику: чтобы повернуть точку вокруг нашей оси вращения c, получается матрица вращения:
| c₁² c₁*c₂ - c₃ c₁*c₃ + c₂ |
R = | c₁*c₂ + c₃ c₂² c₂*c₃ - c₁ |
| c₁*c₃ - c₂ c₂*c₃ + c₁ c₃² |
Где индексы 1, 2 и 3 на самом деле являются просто компонентами x, y и z нашего вектора. Так что это все еще легко, и все, что осталось, это матрично повернуть нашу нормализованную касательную:
n = R * Tangent "T"
Который:
| T₁ * R₁₁ + T₂ * R₁₂ + T₃ * R₁₃ | |nx|
n = | T₁ * R₂₁ + T₂ * R₂₂ + T₃ * R₂₃ | => |ny|
| T₁ * R₃₁ + T₂ * R₃₂ + T₃ * R₃₃ | |nz|
И у нас есть вектор(ы) нормалей, которые нам нужны. Идеально!
За исключением того, что мы можем сделать лучше: поскольку мы работаем не с произвольными углами, а с прямыми углами, мы можем использовать существенное сокращение. Точно так же, как вектор c был перпендикулярен обеим касательным, наша нормаль n перпендикулярна как c, так и регулярному касательному, поэтому мы можно использовать векторное произведение во второй раз, чтобы найти нормаль:
|nx|
n = c × tangent₁ => |ny|
|nz|
Это даст нам точно такой же вектор с меньшими затратами.
![Наша кривая с нормалями!](https://i.stack.imgur.com/xmIHj.jpg)
И если нам нужны внутренние нормали, это тот же вектор, просто умножьте на -1:
![Наша кривая с внутренними нормалями](https://i.stack.imgur.com/Orla8.jpg)
Довольно легко, если вы знаете трюки! И, наконец, поскольку код всегда полезен, его суть заключается в Программа, которую я использовал, чтобы убедиться, что говорю правду.
Что, если нормальные люди ведут себя очень странно?
Например, что, если мы используем трехмерную кривую, но она плоская (например, все координаты z
равны 0)? Вещи внезапно делают ужасные вещи. Например, давайте посмотрим на кривую с координатами (0,0,0), (-38,260,0), (-25,541,0) и (-15,821,0):
![введите здесь описание изображения](https://i.stack.imgur.com/f2Uuj.png)
Точно так же особенно извилистые кривые могут давать довольно закрученные нормали. Глядя на кривую с координатами (0,0,0), (-38,260,200), (-25,541,-200) и (-15,821,600):
![введите здесь описание изображения](https://i.stack.imgur.com/IVjq2.png)
В этом случае нам нужны нормали, которые вращаются и скручиваются как можно меньше, что можно найти с помощью алгоритма кадра, минимизирующего вращение, например, описанного в разделе 4 или "Вычисление кадров, минимизирующих вращение" (Wenping Wang, Bert Jüttler, Dayue Zheng, и Ян Лю, 2008 г.).
Реализация их 9-строчного алгоритма требует немного больше работы на обычном языке программирования, таком как Java/Processing:
ArrayList<VectorFrame> getRMF(int steps) {
ArrayList<VectorFrame> frames = new ArrayList<VectorFrame>();
double c1, c2, step = 1.0/steps, t0, t1;
PointVector v1, v2, riL, tiL, riN, siN;
VectorFrame x0, x1;
// Start off with the standard tangent/axis/normal frame
// associated with the curve just prior the Bezier interval.
t0 = -step;
frames.add(getFrenetFrame(t0));
// start constructing RM frames
for (; t0 < 1.0; t0 += step) {
// start with the previous, known frame
x0 = frames.get(frames.size() - 1);
// get the next frame: we're going to throw away its axis and normal
t1 = t0 + step;
x1 = getFrenetFrame(t1);
// First we reflect x0's tangent and axis onto x1, through
// the plane of reflection at the point midway x0--x1
v1 = x1.o.minus(x0.o);
c1 = v1.dot(v1);
riL = x0.r.minus(v1.scale( 2/c1 * v1.dot(x0.r) ));
tiL = x0.t.minus(v1.scale( 2/c1 * v1.dot(x0.t) ));
// Then we reflection a second time, over a plane at x1
// so that the frame tangent is aligned with the curve tangent:
v2 = x1.t.minus(tiL);
c2 = v2.dot(v2);
riN = riL.minus(v2.scale( 2/c2 * v2.dot(riL) ));
siN = x1.t.cross(riN);
x1.n = siN;
x1.r = riN;
// we record that frame, and move on
frames.add(x1);
}
// and before we return, we throw away the very first frame,
// because it lies outside the Bezier interval.
frames.remove(0);
return frames;
}
Тем не менее, это работает очень хорошо. С примечанием, что рамка Френе является «стандартной» касательной/осью/нормальной рамкой:
VectorFrame getFrenetFrame(double t) {
PointVector origin = get(t);
PointVector tangent = derivative.get(t).normalise();
PointVector normal = getNormal(t).normalise();
return new VectorFrame(origin, tangent, normal);
}
Для нашей плоской кривой теперь мы видим идеально работающие нормали:
![введите здесь описание изображения](https://i.stack.imgur.com/rc4Wv.png)
А в неплоской кривой вращение минимально:
![введите здесь описание изображения](https://i.stack.imgur.com/ynJep.png)
И, наконец, эти нормали можно равномерно переориентировать, вращая все векторы вокруг связанных с ними касательных векторов.
person
Mike 'Pomax' Kamermans
schedule
23.08.2014