Рассчитать горизонт изогнутой грани? - PullRequest
Новая
       27

Рассчитать горизонт изогнутой грани?

3 голосов
/ 21 февраля 2009

Мне нужно найти 2 точки визуального горизонта изогнутой грани.

У меня есть:

  • XYZ из 4 угловых точек
  • XYZ из двух точек Безье изогнутой кромки

И мне нужно вычислить либо:

  • XY точек горизонта
  • XYZ точек горизонта

1 Ответ

4 голосов
/ 21 февраля 2009

Прежде всего вы должны конвертировать ваши 3D-Безье в 2D. Если я правильно помню, достаточно проецировать кривые так же, как вы проецируете 3D-точки для рендеринга.

После этого вы должны найти экстремумы кривых.

Небольшой HowTo:

Преобразование вашей кривой Безье из представления Безье в многочлен вида 

  x(t) = a*t^3 + b*t^2 + c*t + d
  y(t) = e*t^3 + f*t^2 + g*t + g

  Here t is your interpolation variable that goes from 0 to 1.
  a to d are the coefficients for the curve along the x-axis
  e to g are the coefficients for the curve along the y-axis.

Теперь вы строите первый вывод кривой (это легко, поскольку это полиномиальная почта). Это даст вам квадратное уравнение. Решите их для корней и отбросьте все корни, которые находятся за пределами диапазона 0..1. Снова найти корни легко, поскольку это просто квадратичный полином.

У вас, как есть куча корней. Вставьте все это обратно в исходную кривую Безье, оцените их положение, и вы получите кучу баллов. Экстремумы - если они существуют - будут среди этих точек.

Теперь все, что вам нужно сделать, - это найти ту, у которой самая высокая (или самая низкая - не знаю, как выглядит ваша система координат) y-координата.

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

EDIT:

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

 x(t) = x0 * (1-t)³ + 3*x1*(1-t)²*t + 3*x2*(1-t)*t² +x3*t³

(от x0 до x3 - значения x четырех контрольных точек кривой).

Затем вы умножаете все члены один за другим и сортируете их по степеням t. К сожалению, у меня не работает мой математический пакет на компьютере, на котором я пишу, и мне лень делать это на бумаге :-) Поэтому, если у кого-то работает mathlab, не могли бы вы отредактировать этот ответ и добавить расширенный версия

В любом случае, поскольку вы на самом деле не интересуетесь полиномом, а просто производным от него, все немного проще. Вы можете получить коэффициенты напрямую (здесь показано только для x): 

A = 3.0f*(x[1] - x[0]);
B = 6.0f*(x[2] - 2.0f*x[1] + x[0]);
C = 3.0f*(x[3] - 3.0f*x[2] + 3.0f *x[1] - x[0]);

Используя эти три значения (A, B, C), многочлен первого производного выглядит следующим образом: 

  x(t) = A*t^2 + B*t + C

Теперь подключите A, B и C к корневому модулю для квадратичных полиномов, и все готово. Для справки я использую C-код решателя ниже: 

int GetQuadraticRoots (float A, float B, float C, float *roots)
{
  if ((C < -FLT_EPSILON) || (C > FLT_EPSILON))
  {
    float d,p;
    // it is a cubic:
    p = B*B - 4.0f * C*A;
    d = 0.5f / C;
    if (p>=0)
    {
      p = (float) sqrt(p);
      if ((p < -FLT_EPSILON) || (p > FLT_EPSILON))
      {
        // two single roots:
        roots[0] = (-B + p)*d;
        roots[1] = (-B - p)*d;
        return 2;
      } 
      // one double root:
      roots[0] = -B*d;
      return 1;
    } else {
      // no roots:
      return 0;
    }
  } 
  // it is linear:
  if ((B < -FLT_EPSILON) || (B > FLT_EPSILON))
  {
    // one single root:
    roots[0] = -A/B;
    return 1;
  }
  // it is constant, so .. no roots.
  return 0;
}
...