Identifiying the next point on the surface of a cube

Question

I have a cube of unit length. Each face of the cube is divided into 10 x 10 segments. Consider an object of size equal to that of a segment moving through the surface of the cube.

I need to compute a way to find the next segment in the cube given the direction of the object.

Answer 1

I would say to simply use flatten representation. Navigation within a face is simple. Navigation between faces can easily coded using a map of "relations":

BTW, you can use any suitable net:

Answer 2

Depending on exactly what you're trying to do, you could express/convert position and direction vectors into spherical coordinates on the unit sphere (ie radius = 1), and then project onto the cube. The projection may cause an inconstant perceived velocity however, but it may or may not be objectionable in your case.

For example, convert the spherical position coordinates back to carthesian, then figure out the associated cube sides and face coordinates as shown here: http://www.nvidia.com/object/cube_map_ogl_tutorial.html (see section Mapping Texture Coordinates to Cube Map Faces), which you can then snap to your 10x10 segments.

Answer 3

All the steps "inside" on of the cube sides are trivial, there are 8 directions the object can take and the object likely have some inertia or other algorithm saying where it's heading.

One way to make the "jumping" over cube edges relatively painless is to model all the sides of the cube as 12x12 squares big (just put "an extra row" of squares outside the cube side edge) and have some logic moving the object to the right cube edge whenever it's on the outer rim of one square (this way you can keep the moving-the-object-logic uncoupled from the over-edge detection). The "jump to the right square" should be very symmetric, and best discovered with some squared paper.

There are "singularities" in the problem, when your object want to move NW in a corner, it will either be between two other squares OR bounce back. Or chose one of the adjacent squares (at random or by some rule).

Fun problem!

Answer 4

It is possible that what you are looking for is a Space filling curve. In their discrete form, they approximate a N-dimensions in (N-1)-dimensions, so if you take N = 2 we have a way to map a plane (or the 6 planes that form the net of a cube) in 1D (in a line) which can be modeled as a function that takes a point on the line, and returns the (x,y) position in the plane.

You could use the Hilbert Curve or the Peano Curve as they both approximate unit squares but the former's approximation goes up in powers of 2 and the latter's in powers of 3, so neither will approximate the unit square in 10 segments (you can approximate in 8 or 16 with a Hilbert curve, or 9 with a Peano curve).

Obviously the net of a cube is not a perfect unit square, but that doesn't matter, because you can treat each face as a unit square, and then once you reach the end of one approximation, move to the next face of the cube.

As an implementation detail, you would do this in the following manner:

• Calculate the total distance the curve has to go, for the particular approximation you choose, to approximate the entire unit square: D
• Store the (x,y) offsets of each face (labeled 0 through to 5) in an array: offsets (i.e. offsets[0] is the offset of the first face).

• Loop through the interval i <- [0..6*D).

  • The face you are currently mapping can be found as f = floor(i/D).
  • The distance through that face is d = i % D.

  • Get the (x,y) location of the next point in the cube is calculated as

    (x,y) = offset[f] + space_filling_curve(d)
    

    where space_filling_curve() is the discrete approximation of whichever curve you choose, to whichever degree of approximation you choose (as long as it matches up with your calculation of D).

I haven't added the implementation space_filling_curve() itself, because the article on Hilbert Curves, that I cited earlier has a nice, straight forward one written in C.