Compose 3D Transformations

3D transformations in computer vision are usually represented as 4×4 homogeneous matrices so that translation, rotation, and scaling can all be expressed as a single matrix multiplication on a 4D vector $[x, y, z, 1]^T$. Using homogeneous coordinates lets you chain multiple operations (like rotate then translate) as matrix products instead of applying each transformation separately. In this representation, the upper-left 3×3 block typically encodes rotation and scale, and the last column encodes translation.

A key subtlety is order of composition: matrix multiplication is not commutative, so $A @ B \neq B @ A$ in general. In transformations, when you say “apply $T_1$, then apply $T_2$”, the combined matrix is T_{\text{combined}} = T_2 @ T_1. In other words, the matrix closest to the vector is applied first. This is crucial in 3D graphics and vision for placing cameras, moving objects, and traversing scene graphs: changing the order of multiplication can completely change the resulting pose.

---

1. Background Knowledge

• Homogeneous coordinates: A 3D point $(x, y, z)$ is represented as a 4D vector $(x, y, z, 1)$. A 4×4 transformation matrix $T$ acts on this vector by matrix multiplication:

$$p' = T \, p$$

This form allows translation to be included in the same linear operation as rotation/scale.

• Basic 3D transforms as 4×4 matrices:
• Translation by $(t_x, t_y, t_z)$:

$$T = \begin{bmatrix} 1 & 0 & 0 & t_x \\ 0 & 1 & 0 & t_y \\ 0 & 0 & 1 & t_z \\ 0 & 0 & 0 & 1 \end{bmatrix}$$

• Rotation around X/Y/Z axes (using sin/cos in the top-left 3×3 block).
• Scale by $(s_x, s_y, s_z)$:

$$S = \begin{bmatrix} s_x & 0 & 0 & 0 \\ 0 & s_y & 0 & 0 \\ 0 & 0 & s_z & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$$

• Composition rule: If you have transforms $T_1, T_2, T_3$ and you want to apply them to a point in this order:

$$p' = T_3(T_2(T_1(p)))$$

then the combined matrix is:

$$T_{\text{combined}} = T_3 @ T_2 @ T_1$$

That is: the first applied transform appears rightmost in the product.

---

2. Algorithm / Approach

Given a list of 4×4 transformation matrices and a specified order of application:

1. Decide the application order (e.g., “apply T1, then T2, then T3”).
2. Compose by right-multiplying in that order:

• Start from the identity matrix.
• For each transform in application order, multiply it on the left of the current result.

3. Use the final composed matrix to transform points: result @ point_homogeneous.

Pattern in NumPy:

import numpy as np

M = np.eye(4)
for T in transforms_in_application_order:
 M = T @ M

---

3. Step-by-Step Strategy

1. Represent each basic transform as a 4×4 NumPy array:

• Implement helper functions:
• translation_matrix(tx, ty, tz) -> (4,4)
• rotation_x(angle), rotation_y(angle), rotation_z(angle)
• scale_matrix(sx, sy, sz)
• Each returns a np.array of shape (4, 4) with dtype float.

2. Understand the required order from the problem statement:

• If the statement says: “Apply T1, then T2, then T3”, you must compute:

M = T3 @ T2 @ T1

• If they give you a Python list like [T1, T2, T3] in application order, use a loop as above.

3. Initialize the composition:

• Start with identity:

M = np.eye(4)

4. Iteratively apply transforms:

• For a list Ts in application order:

for T in Ts:
M = T @ M # left-multiply

5. Use the composed matrix:

• Convert points to homogeneous coordinates:

p = np.array([x, y, z, 1.0])
p_transformed = M @ p

• Optionally convert back to 3D by dividing by p_transformed (usually 1).

---

4. Common Pitfalls

• Reversing the order incorrectly: Doing M = M @ T instead of M = T @ M will invert the order of application. Always remember: matrix closest to the vector is applied first.

• Confusing “listed order” with “multiplication order”: If the problem lists transforms in the order they should be applied, your multiplication must go from right to left in that list.

• Mixing row-major / column-major mental models: In NumPy, vectors are typically column-like and you use M @ v. Stick consistently to this convention to avoid transposed logic.

• Shape errors: Ensure all matrices are (4, 4) and points (4,) or (4, 1). Even one (3, 3) rotation sneaking in will break multiplication.

• Angle units: If building rotation matrices, ensure you use radians for NumPy trig functions, not degrees.

---

5. Time & Space Complexity

• Let there be $k$ transformations, each a 4×4 matrix.
• Matrix–matrix multiplication of 4×4 matrices is $O(1)$ with a small constant (since 4 is fixed).
• Time complexity:
• Composing $k$ transforms: $O(k)$ operations on constant-size matrices.
• Applying the final matrix to $n$ points: $O(n)$ (each is a 4×4 @ 4×1 multiply).
• Space complexity:
• Storing the composed matrix: $O(1)$.
• Storing all $k$ matrices: $O(k)$.
• Per point transform: $O(1)$ extra space.