2
\$\begingroup\$

I'm familiar with quaternions... have used them in the past to model arbitrary rotations in 3D, as for a plane flying around with full pitch/yaw/roll freedom. Works great.

Now I'm working on a 3D puzzle where the rotation is "quantized": all rotations are whole multiples of 90 degrees. I could use quaternions, but it seems like complexity overkill for this situation. And more importantly, I need to be able to test different orientations according to their quantized values, aligned to the three main axes. Quaternions (usually) use floating point values rather than integers, so if we compose several rotations and then compare the resulting orientation to a known orientation, it may not be straightforward to test whether a certain face is pointing a given direction, due to rounding.

Anyway, there may be an easier way to model this.

The puzzle is like "netwalk", but in 3D. So the requirements are:

  • Be able to rotate a given piece +/-90 degrees, around a specified axis, updating its orientation state (which is modeled how?)
  • Be able to query whether a particular piece, in its current orientation, is connected in a particular direction (e.g. has a tube touching the face that is in the positive X direction)
  • For the latter we probably have an array of booleans that say whether the piece is connected in each direction in its "initial" orientation. But in order to make use of this, we need a way to rotate this initial state to the current orientation.
  • Oh, we also need to be able to display each piece graphically in its updated orientation. But that could use a separate orientation state if necessary... it's a pretty standard feature of scene graph libraries.

Maybe I just need to implement an integer version of quaternions?

Thanks for any thoughts...

\$\endgroup\$

3 Answers 3

5
\$\begingroup\$

Frankly, I would continue to use quaternions if you are already using them and comfortable with them. It doesn't seem to me like it's worthwhile to build out a whole system -- if even it's a small one -- to handle fixed sets of rotations when you can simply do that on top of a system that handles arbitrary ones.

Furthermore, you can address the floating point issue by comparing with epsilon values -- that is, test if components are equal within a small tolerance. This is the general technique for comparing floating point values.

However, all that aside, you shouldn't be conflating game logic and render state by comparing the orientation quaternions of your render objects to decide where a particular game piece is facing. It is better to divorce the states and operations of the two domains as much as possible:

You could simply have an enumeration of possible orientations of your pieces (facing +Z, -Z, +X, -X, +Y, -Y). This alleviates most of your concerns, although you'd probably want a mapping of potential target rotations from any given rotation enumeration value, since you wouldn't have "real math" to work with any longer.

It would allow you to query for connectivity relatively easily since you could simply get the set of surrounding pieces in a fixed order that corresponded to the ordering of the enumeration, and then plug the piece's current orientation in to that result array to see which piece was in that direction (if any; you'd always have to return an array of the same size so you'd want to pad with null or empty values when there was no piece around).

When it's time to display a piece, you can trivially construct the orientation quaternion for the particular orientation enumeration and send that to the render subsystem.

\$\endgroup\$
7
  • \$\begingroup\$ Thanks for looking at the question and giving feedback. I agree about divorcing the logic from the rendering, though the latter could derive from the former. A given piece can have 24 orientations, rather than just six (though usually some orientations are equivalent to each other). How would you suggest implementing a mapping from one orientation to another? \$\endgroup\$
    – LarsH
    Oct 31, 2011 at 16:13
  • \$\begingroup\$ When I say that I'm "familiar" with quaternions, I should qualify that as "I'm able to do what I need to do with them, but don't understand them deeply." They're kind of a black box to me, but the interface to the black box is documented well enough. \$\endgroup\$
    – LarsH
    Oct 31, 2011 at 16:16
  • \$\begingroup\$ Yeah, I didn't intend that list to be comprehensive, just an example. You could implement the mapping as a simple dictionary lookup (using std::map in C++, for example). Since you can only rotate 90 degrees at a time, there's only a small subset of rotations you can directly reach from any position. \$\endgroup\$
    – user1430
    Oct 31, 2011 at 16:16
  • \$\begingroup\$ OK... so you're saying the "set of surrounding pieces in a fixed order that corresponded to the ordering of the enumeration" would be an array of 24 values, in which surrounding pieces are repeated as often as necessary? \$\endgroup\$
    – LarsH
    Oct 31, 2011 at 16:26
  • \$\begingroup\$ Yes, except that I'm not sure why any surrounding piece would be need to be repeated. \$\endgroup\$
    – user1430
    Oct 31, 2011 at 16:32
3
\$\begingroup\$

There are only 24 possible orientations achievable by 90° rotations around coordinate axis, which form the rotation group of a cube, also known as the chiral octahedral symmetry group. Since there are only 24 elements, you could easily build a multiplication table for them. (In fact, you only need a 24 × 6 table, since only 6 of the elements are 90° rotations.)

The elements of the rotation group can also be naturally represented by 3×3 transformation matrices — in particular, those 3×3 matrices which:

  • contain only the values -1, 0 and 1,
  • have exactly one non-zero value in each row and each column, and
  • have their determinant equal to 1 (rather than -1).

Among these matrices, the 90° rotations are those which swap two coordinate axes while negating one of them, i.e. those that have a single 1 on the diagonal and one 1 and one -1 off the diagonal.

This matrix representation allows you to use straightforward matrix multiplication to combine rotations, and to apply those rotations to point coordinates. Since all the elements of the matrices are integers, you don't need to worry about rounding errors.

\$\endgroup\$
3
  • \$\begingroup\$ Thanks, this sounds pretty good. When you say a multiplication table, you mean a lookup table where one index is the previous orientation (24 possibilities) and the other index is the 90-degree rotation (6 possibilities), and the value in each cell is the resulting orientation (24 possibilities)? I guess the part of this that seems complicated is mapping the 24 different orientations to/from a linear value. I like the idea of 3x3 integer matrices. But I'm not sure how to use those to query whether a cell is connected in a given direction. Use the inverse matrx to map that direction backwards? \$\endgroup\$
    – LarsH
    Oct 31, 2011 at 20:07
  • \$\begingroup\$ That should work, yes. Note that, since these matrices are orthogonal, their inverse is equal to their transpose. \$\endgroup\$ Oct 31, 2011 at 20:49
  • \$\begingroup\$ Ah, my linear algebra is so rusty. \$\endgroup\$
    – LarsH
    Oct 31, 2011 at 21:33
0
\$\begingroup\$

The solution I'm leaning toward is this...

For the puzzle logic, I will have for each cell (or piece) an array of 6 directions, storing a boolean value isConnected.

When initializing a cell, this boolean array is initialized from the array for the archetype of the shape being placed in the call.

Whenever a given piece is rotated, I call a function rotateFaces(rotation) that permutes these 6 boolean face values according to whether rotation is '+x', '-x', '+y', etc. Based on the axis it selects a sequence of four directions. Then the selected sequence is used to permute four of the six values in the array. E.g. if the rotation is '+x', then the sequence of directions to permute are +y, +z, -y, -z. So the boolean value for +y is shifted to +z, and so on in a cycle.

To query whether a piece is connected in a given direction in its current orientation, we just query the boolean array for that direction.

That way I can avoid any floating point rounding issues, the math is all fairly simple, and the query (which will happen very often) is quick.

The graphic display of the pieces will most likely be handled separately via the scene graph library. I may see if I can "round" their orientation to be axis-aligned after each move is completed.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .