How does the Simple Stupid Funnel Algorithm work?

Question

Working with the funneling algorithm shown on Digesting Duck I'm not sure how the detection of the funnel works.

Can someone explain the method clearly to me or suggest an alternative way of detecting the funnel and if the funnels sides overlap?

Answer 1

The algorithm start with a path you found earlier, in this case a list of triangles:

The code at the bottom of Mikko's blog post constructs the portals array, which is a list of line segments representing the line segments between the path's polygons. These are the "portals" the smoothed path has to go through (or the polygon edges from "let's trace the polygon edge midpoints"). Note that the portals list starts and ends with degenerate line segments at the start and goal points.

This portals list is shown as the yellow dotted line segments in his pictures.

The algorithm starts with a wide funnel and proceeds by iteratively moving the funnel sides forward along the portal side points (the end points of the line segments) as long as this tightens the funnel (A-D).

This means each move forward should move the funnel edges inward, this can be checked with the cross product of the vectors representing the old side and the potential new side (P × Q in the image below; also see triarea2 in Mikko's code). If a move forward for a side would not tighten the funnel, we don't update that side for the current iteration of the portals (E).

The other case that needs to be handled is when the funnel degenerates to a line segment. To account for this the algorithm checks if one of the sides is on the "wrong" side by using the cross product again, this time of the vectors made by the funnel apex and the right and left side end points respectively (R × S in the image below).

If this is the case, the vector from the funnel apex and the correct side end point is added to the smoothed path (R in the image above) and the algorithm is restarted with its end point as the new apex (F-G), unless, of course, if it is the goal point.