Search code examples
geometrysimulationcomputational-geometry

Laser bouncing inside arbitrary shape

I've been mulling this problem over in my head for a while. Given an arbitrary closed 2d polygon, which is well defined, consisting of lines and curves (perhaps Bezier curves for consistency). Given a starting point and direction within the polygon. How would you go about efficiently calculating how a laser, starting at that start point, and pointing in that direction, would bounce around inside the shape?

To put this in concrete terms say you had an array which defined the shape.

  • The elements of the array are either lines (start and end point), or Bezier curves (list of n points defining the curve).
  • You can assume that the end of one segment will connect to the start of the next segment of the array, and that the end of the last segment will connect to the start of the first one.
  • You can also assume that none of the segments intersect with one another or themself.

Here's an example array:

[
Line from (0, 0) to (1, 2),
Line from (1, 2) to (3, 2),
Bezier curve from (3, 2) to (3, 0) passing through (4, 1),
Line from (3, 0) to (0,0)
]

And we can say the laser originates at (1, 0.5) and travels directly NE.

Here is an image: The shape in question

The challenge is to build an algorithm which would follow the path of the line, calculating a list of intersections and normal values for reflection as the laser bounces around. I'd like to find a general algorithm for solving this given any input array. If you have a solution or just a helpful tip/place to start looking it would be much appreciated.

Solution

  • This is a 2D ray-casting problem.

    Given a starting point and a direction, you compute the implicit equation of the ray s(x, y):= ax + by + c = 0, which is a straight line, and you want to find the first intersection with the shape outline.

    In the case of a polygonal shape, an edge can only intersect the line if its endpoints are on either side of the ray, which is characterized by a change of sign of s. When there is an intersection, you can compute the parameter t of the parametric equation of the the ray, P = P0 + t.D. Then the first intersection is given by the smallest positive t (as long as you are inside a closed shape, there will be one).

    In case of a cubic Bezier arc, the above sign rule must be modified, because a Bezier arc can cross a line twice and its endpoints have the same signs. A possible cure is to decompose the Bezier in monotonic arcs, as follows:

    • rotate the line and the control points so that the line becomes horizontal;

    • compute the cubic polynomial Y(u) for the ordinates only (u is the parameter of the Bezier);

    • find the extrema of Y by solving the quadratic Y'(u)=0. This gives you from 0 to 2 values of u in the range [0,1];

    • use the corresponding points to split the Bezier, and you will get arcs guaranteed to cross the line at most once and restore the sign rule.

    [This procedure finds the tangent to the Bezier that are parallel to the ray.]

    Now for every cubic arc with a change of sign, you can't avoid solving the cubic, for instance using the Cardano formulas. Then again, keep the intersection with the smallest positive t.

    When you have found the first intersection, compute the direction of the normal to the outline at the intersection point. Then you have new starting point and direction, to continue the trajectory.

    enter image description here

    Update: I messed a little with the parameters. The convention is: t along the ray, u along the Bezier.

    It is important to realize that the sign rule brings a safety in the procedure. For correctness, every time you detect a change of sign, you must report exactly one intersection. In case of exact equality to zero, you can assume positive (provided you always assume positive).