# How to rotate a 3d grid?

I have a spatial hashing grid that's mapped out like

keyX = Math.floor(position.x/cellsize) + 1;
keyY = Math.floor(position.y/cellsize) + 1;
keyZ = Math.floor(position.z/cellsize) + 1;

keyFinal = (keyX, keyY, keyZ);


I need this grid to be able to point in a given direction, or just match a given rotation.

How can I make this able to account for rotation of the object it would be attached to?

The best solution I can come up with is "unrotating" the position before passing it into the key. Although I am curious as to any solutions that bake this step into the hash key.

Your "unrotate" step before hashing is the way I'd do it.

I'd multiply my position by a matrix before flooring the x/y/z. You can bake the rotation, division by cell size, and the +1 into the same matrix, to reduce the total cost.

For instance, if you want the x direction of your new grid to point along the unit vector $$\(x_x, x_y, x_z)\$$, in the parent coordinate system, the y direction to point along $$\(y_x, y_y, y_z)\$$, and z along $$\(z_x, z_y, z_z)\$$, you can express this as the matrix:

$$M = \begin{bmatrix} \frac {x_x} {\text{cell size}} & \frac {x_y} {\text{cell size}} & \frac {x_z} {\text{cell size}} & 1\\ \frac {y_x} {\text{cell size}} & \frac {y_y} {\text{cell size}} & \frac {y_z} {\text{cell size}} & 1\\ \frac {z_x} {\text{cell size}} & \frac {z_y} {\text{cell size}} & \frac {z_z} {\text{cell size}} & 1\\ 0 & 0 & 0 & 1 \end{bmatrix}$$

Then if your input position is $$\(p_x, p_y, p_z)\$$ then you can multiply to get your output position $$\(o_x, o_y, o_z)\$$ like so:

$$\begin{bmatrix} o_x \\ o_y \\ o_z \\ 1 \end{bmatrix} = M \begin{bmatrix}p_x \\ p_y \\ p_z \\ 1\end{bmatrix}$$

So we've incorporated the rotation, scaling, and shifting by one in a single matrix multiplication (which many vector libraries will have efficient SIMD implementations for). There's a bit more up-front work to construct the matrix, but presumably you'll re-use the same transformation for hashing many points, so that cost gets amortized. If the points themselves come from an object with its own local transformation matrix, you can compose the two matrices together so you only need to do one matrix multiplication per point in the object.

• ah, so if I understand it, you mean to multiply the position by these matrices? wikimedia.org/api/rest_v1/media/math/render/svg/…
– Pen
Commented Jul 24 at 23:25
• Myself, I'd skip the trig and construct the matrix from basis vectors, as shown above. Commented Jul 26 at 14:52
• I hadn't heard of basis vectors until today, but these can forgo euler rotations in this scenario? I haven't seen anything to suggest otherwise
– Pen
Commented Jul 27 at 1:32
• I like to avoid Euler whenever I can. 😉 If you need to use Euler/Tait-Bryan angles as an input though, you can use them to generate the basis vectors something like this. Commented Jul 27 at 1:43
• honestly I'd prefer not to use them in this case as well. But say i decided not to have this baked into the key, and instead unrotated before passing into the key. Would I invert the rotation, then get the dot product of each position axis to its corresponding axis (forward, up, right), then make a new vector based off the results?
– Pen
Commented Jul 27 at 2:16