Ray-Plane Intersection Check

The other day while working on my thesis research, I came across the need to compute whether the slung-load’s line was in collision with an obstacle, and compute it very efficiently.  This certainly isn’t a novel application; however, I couldn’t easily find an algorithm online and it’s not worth the effort to learn and install a library for this one thing.  So I came up with a little solution and want to make it available for whomever it might help.

First I’ll set up the problem, show the mathematics behind the solution, then the code in C that I used to implement it.

Setup

Assumptions:

  • The slung-load line can be treated as a three-dimensional line segment.
  • All obstacles can be represented as groups of two-dimensional rectangles with an arbitrary position and orientation in three-dimensional space.
  • The three-dimensional coordinates of the corner of the rectangle are known, as well as the two ends of the line segments. A normal vector for the plane is defined, along with two additional unit orthogonal basis vectors align with the perpendicular edges of the rectangle.  The length and width of the rectangle are also known. This information is obviously redundant but it was the format I had available.
  • The actual point of intersection isn’t important, as long as a collision is detected.

We will define the inputs as vectors \vec{P} and \vec{L} as the positions of the pivot and load, \vec{p}_c as the corner of the rectangle, \vec{p}_n the normal vector, \vec{p}_l and \vec{p}_w the unit vectors defining the edges of the rectangle, and l and w as the length and width of the rectangle.

rayplane

Solution

k_p = n^T (\vec{P} - \vec{p}_c)

k_l = n^T (\vec{L} - \vec{p}_c)

k_p and k_l represent the multiples of the normal vector the pivot and load are away from the plane’s surface.  If they have the same sign, then both points are on one side of the plane and there is no collision–no further computation required.

If the two points are on opposite sides of the plane, then the point of intersection lay on the line segment \vec{L} - \vec{P}.  Further, this point divides the line segment into portions proportional to k_p and k_l.

\vec{p}_x = \vec{P} + \frac{k_p}{k_p+k_l} (\vec{L} - \vec{P})

So we do end up with the point of intersection. We need to project that point of intersection onto the basis vectors of the edges, and check if the point lay inside the rectangle.

l_{check} = (\vec{p}_x - \vec{p}_c)^T \vec{p}_l

w_{check} = (\vec{p}_x - \vec{p}_c)^T \vec{p}_w

If l_{check} and w_{check} are greater than zero and less than l and w respectively, there is a collision, and otherwise there is none.

Implementation in C


static bool planeIntersect(
    double P[3],
    double L[3],
    struct treeObstacleQuad_ref plane )
{
    double rp[3], rl[3], isect[3], kp, kl;
    int ii;

    // Presume there is no collision
    bool colliding = false;

    for( ii = 0; ii < 3; ii++ ) {
      rp[ii] = P[ii]
          - plane.corner[ii];
      rl[ii] = L[ii+6]
          - plane.corner[ii];
      }

      kp = plane.normal[0]*rp[0]
         + plane.normal[1]*rp[1]
         + plane.normal[2]*rp[2]; 

      kl = plane.normal[0]*rl[0]
         + plane.normal[1]*rl[1]
         + plane.normal[2]*rl[2]; 

      if( kp*kl > 0 )
      {
          return colliding;
      } else {
          for( ii = 0; ii < 3; ii++ )
           isect[ii] = rp[ii] 
                     + ( rl[ii] - rp[ii] )
                     * fabs( kp ) 
                     / ( fabs( kp ) + fabs( kl ) );

          double a, b;
          a = isect[0]*plane.horizontal[0]
            + isect[1]*plane.horizontal[1]
            + isect[2]*plane.horizontal[2];
          b = isect[0]*plane.vertical[0]
            + isect[1]*plane.vertical[1]
            + isect[2]*plane.vertical[2];

          if( a > 0
           && a < plane.length
           && b > 0
           && b < plane.width )
                colliding = true;

      }

      return colliding;
}

Thoughts on the FAA’s sUAS NPRM

About a month ago, the FAA released its first Notice of Proposed Rulemaking (NPRM) for UAS, and thus far I’ve held off on writing about it, both because I wanted to have some time to digest it, and also because I had several other competing priorities (not least my thesis proposal!)  But now with the benefit of a month or so to take a look at it and mull it over, I’d like to present a few thoughts on the proposed rules. I will try to refrain from  expressing a firm opinion on any specific rule because I realize I don’t have the full perspective of the industry or of the FAA.

Summary of the NPRM Narrative

The proposed rules only apply to small UAS (sUAS), which are defined by law as those weighing less than 55 pounds. Larger UAS will still have to operate under the current rules which require a Certificate of Authorization (a COA, for government-owned/operated UAS) or a special airworthiness certificate (for private/commercial UAS).  These rules are proposed based upon the passage of the 2012 FAA Modernization and Reform Act–though these rules, and the rules for larger UAS, are far behind the timeline required by the law. The FAA is specifically considering sUAS first because they pose a lower safety risk than larger UAS, and they want to keep costs low for small businesses and operators who are trying to take advantage of the low cost of the aircraft themselves.

The proposed rules would allow for routine commercial operation of small UAS under the following conditions:

  • Aircraft must remain in visual line-of-sight (VLOS) of the operator at all times using vision aided only by normal eyeglasses. There is a thorough discussion of what constitutes line of sight, and they are still allowing for some use of first-person video (FPV), but there is a bit of flexibility in the definition.
  • The aircraft cannot operate over people not involved in the operation.
  • Daylight operations only (from sunrise to sunset).
  • The aircraft must be capable of a maximum airspeed of 100 mph.
  • Operations have a ceiling of 500 feet above ground level.
  • The weather must allow for a minimum of 3 miles of visibility.
  • Flights in controlled airspace (near airports) must have permission from local air traffic control.
  • sUAS must yield right of way to all other aircraft.
  • Operators can only fly a single aircraft at a time.
  • Aircraft are subject to FAA inspection at any time.
  • Aircraft must be registered with the FAA and be marked with their number.
  • Accidents which cause injury or property damage must be promptly reported to the FAA.
  • Operator qualfications:
    • The operator would certify themselves as being free of medical conditions which would interfere with their ability to operate safely.
    • Pass an examination for aeronautical knowledge, with a renewal every 2 years.
    • Pass a TSA background check.
    • Age 17 or older.
    • Obtain an sUAS class airman certificate which never expires.

An important element of these rules is that they would NOT apply to model aircraft operators, as mandated in the 2012 law.  However, in order to qualify as a model aircraft, the aircraft must be operated for recreational or hobby purposes, in accordance with community-based safety guidelines (e.g. the American Model Association), be less than 55 pounds unless certified by that organization, and notifying local ATC if flown within 5 miles of an airport.

An additional element of the narrative, which is not yet incorporated in the proposed text of the rule is the creation of what is called “micro UAS” classification, which would allow for an even lower-cost rule compliance and would apply to very small UAS now commonly sold in malls and toy stores.  Specifically:

  • The aircraft would weigh 4.4 pounds or less and be made of “frangible” materials–i.e. they break when it crashes, such as foam, paper, or wood.
  • The aircraft would be limited to 400 feet above ground in uncontrolled airspace, fly in line of sight, be flown manually (rather than using any kind of autopilot), and fly less than 30 knots.
  • The operator would be required to have a certificate but no knowledge exam would be required (kind of like a fishing license).

Importantly, this micro UAS class would only apply to people not flying under the model aircraft exception.

What Happens Now

The FAA has requested comments on these proposed rules by April 24th, 2015, and it’s anticipated to be one of the most commented upon NPRM in history. Once the comment period closes, the FAA must analyze the comments and incorporate them based upon the amount of public support for the comment and logic/evidence supporting each comment.  They revise the proposed rule to be a final draft rule.   Unfortunately, there appears to be no required timeline for analyzing and preparing a final draft set of rules.  On one hand, the FAA is under political pressure to expedite the rulemaking, as they are already in violation of the 2012 law; on the other hand, it took them this long to propose the rules, it could be a similarly long time before the revised final rules come out.  At the very fastest, the rules could be ready in a year; other sources estimate it will be more like two years. If there are elements of the final draft which are not a “logical outgrowth” of the original proposed rule or comments, then another comment period will be opened. Otherwise, the final rule will be published and effective 30 days after publications.

Likely Comments and/or Changes

As I said, this is likely to be one of the most commented-upon proposed rules in history, for several reasons.  First of all, there are a very wide variety of stakeholders who will be affected by these rules: model aircraft operators, privacy advocates, farmers, photographers, real estate agents, private pilots, airlines, and of course Amazon, just to name a few.  Second, this NPRM is a preview of what the rulemaking for larger UAS might look like–which will have much higher stakes for the future of American aviation.  There will be comments on every aspect of the rule; here are a few of the ones I anticipate to draw the most:

  • FPV and the VLOS requirement. The maintenance of line of sight operation is by far the most restrictive element of all the rules.  The FAA’s primary concern in this area is maintaining the ability to see-and-avoid; operators on the other hand will feel that FPV or possibly automatic sense-and-avoid techniques will be sufficient to maintain safety. It’s hard to say how operators will recommend adjusting the rules, and harder still to know how much the FAA will budge on this rule.
  • The micro UAS class. It’s unusual that the proposed micro UAS class is discussed in the narrative, but not specifically mentioned in the text of the proposed rule.  I’m not sure how that will play out.  Another specific question is, at what size does an object cease to be an aircraft? Is a baseball in the micro UAS category? A paper airplane? An insect-sized UAS? I anticipate that many comments will argue that devices in this micro UAS category should be free of all regulation other than the prohibition against careless and reckless operation.
  • Daytime VFR. Many of the potential applications of these aircraft are at night.  Two easy examples are uses in agriculture (for example, monitoring for predators) or as mobile security cameras for guarding private property. Moreover, the likelihood of collisions with people or other aircraft is reduced at night.  This is closely related to the VLOS requirement and may be solved with adjusted line of sight rules.
  • Age requirement. When you consider that the FAA allows children of age 14 to solo gliders and balloons, and age 16 to solo powered aircraft, requiring sUAS operators to be 17 or older seems excessive.
  • Distinction of airspace ownership or land characteristics. The new rules mention nothing of the distinction between, for example, downtown Chicago and a rural farmer’s field.  Agricultural operators, for example, may argue that over their own land and under the regulation’s ceiling, they shouldn’t be subject to any of the restrictions.  Likewise, a 55-lb aircraft flying 100 mph in an urban neighborhood has a far higher potential for causing injury or property damage.

All in all, this NPRM is a step in the right direction, though smells like too little, too late.