Super Mario Galaxy problem Suppose Mario is walking on the surface of a planet.  If he starts walking from a known location, in a fixed direction, for a predetermined distance, how quickly can we determine where he will stop?



More formally, suppose we are given a convex polytope $P$ in 3-space, a starting point $s$ on the surface of $P$, a direction vector $v$ (in the plane of some facet containing $p$), and a distance $\ell$.  How quickly can we determine which facet of $P$ Mario will stop inside?  (As a technical point, assume that if Mario walks into a vertex of $P$, he immediately explodes; fortunately, this almost never happens.)

Or if you prefer: suppose we are given the polytope $P$, the source point $s$, and the direction vector $v$ in advance.  After preprocessing, how quickly can we answer the question for a given distance $\ell$?

It's easy to simply trace Mario's footsteps, especially if $P$ has only triangular facets.  Whenever Mario enters a facet through one of its edges, we can determine in $O(1)$ time which of the other two edges he must leave through.  Although the running time of this algorithm is only linear in the number of edge-crossings, it's unbounded as a function of the input size, because the distance $\ell$ could be arbitrarily larger than the diameter of $P$.  Can we do better? 

(In practice, the path length isn't actually unbounded; there is a global upper bound in terms of the number of bits needed to represent the input.  But insisting on integer inputs raises some rather nasty numerical issues — How do we compute exactly where to stop? — so let's stick to real inputs and exact real arithmetic.)

Is anything nontrivial known about the complexity of this problem?

Update: In light of julkiewicz's comment, it seems clear that a real-RAM running time bounded purely in terms of $n$ (the complexity of the polytope) is impossible.  Consider the special case of a two-sided unit square $[0,1]^2$, with Mario starting at $(0,1/2)$ and walking in direction $(1,0)$.  Mario will stop on the front or the back of the square depending on the parity of the integer $\lfloor \ell \rfloor$.  We can't compute the floor function in constant time on the real RAM, unless we're happy equating PSPACE and P.  But we can compute $\lfloor \ell \rfloor$ in $O(\log \ell)$ time by exponential search, which is an exponential improvement over the naive algorithm.  Is time polynomial in $n$ and $\log \ell$ always achievable?
This problem is very very difficult.  We could simplify it to make it easier, as follows.


We can add the assumption that the angle sum about every vertex of the polytope $P$ is a rational multiple of $\pi$.  This gets rid of most "polytopes" but there are still many interesting possibilities: for example, the platonic solids. 
We can assume that the polytope is not truly three-dimensional, but instead is the "double" of a polygon; this looks a bit like a pillowcase. We can simplify even further and suppose that the polygon has equal and parallel sides; for example a square, as in the game Astroids.


If we make both of these assumptions then there is a large theory.  (Finding an $O(\log(\ell))$ algorithm for the square is a difficult exercise involving the continued fraction expansion of the angle of Mario's path.  To achieve a similar result for the regular octagon is possible but harder.  The solutions for the square and the octagon involve thinking about how to efficiently encode a "cutting sequences for a geodesic on a translation surface".  Most other rational polygons will quickly lead to open problems.)  An initial reference, which includes a further reference to Caroline Series's discussion of the square torus, are these talk slides by Diana Davis.

If we do not assume rationality, but do assume that the polytope is the double of a polygon, then we are discussing the theory of "cutting sequences in irrational billiards".  It seems that essentially nothing is known here; for example see the final sentence of this talk by Corinna Ulcigrai.

If we make neither assumption, well, I can't think of anything in the literature. 

Finally - I'll guess that there is an $O(\log(\ell))$ solution to the Super Mario Galaxy problem for the platonic solids.  This is a good problem for a graduate student getting started in rational billiards.  For example, the case of the dodecahedron "should" follow from Diana Davis's thesis.  (But start with the tetrahedron - that will follow from an analysis of cutting sequences for the hexagonal torus.)