Calculate the horizon of a curved face?

Question

I need to find the 2 points of the visual horizon, of a curved face.

I have:

• XYZ of the 4 corner points
• XYZ of the 2 curved edge bezier points

And I need to calculate either:

• XY of the horizon points
• XYZ of the horizon points

Answer 1

First off you have to convert your 3D beziers to 2D. If I remember right it's sufficient to project the curves just like you project 3D points for rendering.

Afterwards you have to find the extrema of the curves.

A small HowTo:

Convert your bezier-curve from bezier representation to a polyonomial of the form

  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.

Now you build the first derivation of the curve (easy as it's a polynomail). This will give you a quadratic equation. Solve these for the roots and discard all roots that are outside the 0..1 range. Again finding the roots is easy as it's just a quadratic polynomial.

You how have a bunch of roots. Plug all these back into the original bezier curve, evaluate their position and you get a bunch of points. The extrema - if exist - will be among these points.

Now all you have to do is to search for the one with the highest (or lowest - dunno how your coordinate system looks like) y-coordinate.

Note that you may not get an extrema at all. This happends if your bezier is for example a straight line. In these cases you may want to include the first and last bezier control point in your extrema search as well.

---

EDIT:

You've asked how to turn the bezier into a polynomial. Well, you start with the normal bezier curve equation:

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

(x0 to x3 are the x-values of the four control-points of the curve).

Then you multiply out all terms one after another and sort them by the powers of t. Unfortunately I don't have my math package running on the computer I'm writing on, and I'm to lazy to do it on paper :-) So if anyone has mathlab running, could you please edit this answer and add the expanded version?

Anyway, since you're not really interested in the polynomial but just the derivate of it things are a bit easier. You can get the coefficients directly (here shown for x only):

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]);

Using these three values (A,B,C) the polynomial of the first derivate looks like this:

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

Now plug A,B and C into a root solver for quadratic polynomials and you're done. For reference I use the solver C-code below:

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;
}