Geometries for N-Dimensional Ray Tracing

Background

Geometries explained in this blog serve the ray_tracing_4d project.

Ray

Consider a ray in N-Dimensional space, a parametric equation of ray can be described as:

\[ r(t) = c + d t \] \[ c \in \mathbb{R}^{n}, d \in \mathbb{R}^{n}, \| d \| = 1, t \in \mathbb{R} \]

Where \(c\) is the origin point of the ray with N-Dimension and \(d\) is the direction of the ray.

C++ implementation: [geometry_ray.h]

Simplex

In geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions ^[1].

Intersect N-1-Simplex with N-Ray

An N-1-Simplex in N-Dimensional Space is composed of \(n\) vertices \(u_1, \cdots , u_{n} \in \mathbb{R}^{n}\).

Approach 1. Basis from edges

A vector space \(B \in \mathbb{R}^{n \times (n-1)} \)can be generated from \(u_2 - u_1, u_3 - u_1, \cdots , u_n - u_1 \). One can find the intersection of the ray and the vector space by solve the equation:

\[ c + d t = u_1 + B k \] \[ \left[ \begin{matrix} B & -d \end{matrix} \right] \left[ \begin{matrix} k \\ t \end{matrix} \right] = c - u_1 \] \[ \left[ \begin{matrix} k \\ t \end{matrix} \right] = \left[ \begin{matrix} B & -d \end{matrix} \right]^{-1} (c - u_1) \]

Whether the intersection point is within the simplex can be determined by:

\[ \sum_{i=1}^{n-1} k_i < 1 \ \text{and } 0 \leq k_i \text{ for } i = 1, \cdots , n-1 \]

Approach 2. Barycentric Coordinate System

Directly use \(u_1, \cdots, u_n \) as a basis \(U\) . \(\theta\) is the weighted vector of all vertices.

\[ \begin{cases} c + dt = U \theta \\ \| \theta \| = 1 \\ \end{cases} \]

In matrix form:

\[ \left[ \begin{matrix} U & -d \\ \mathbf{1} & 0 \\ \end{matrix} \right] \left[ \begin{matrix} \theta \\ t \\ \end{matrix} \right] = \left[ \begin{matrix} c \\ 1 \\ \end{matrix} \right] \] \[ \left[ \begin{matrix} \theta \\ t \\ \end{matrix} \right] = \left[ \begin{matrix} U & -d \\ \mathbf{1} & 0 \\ \end{matrix} \right] ^{-1} \left[ \begin{matrix} c \\ 1 \\ \end{matrix} \right] \]

Whether the intersection point is within the simplex can be determined by:

\[ 0 \leq \theta_i \leq 1 \text{ for } i = 1, \cdots , n \]

Connection Between Two Approaches

\[ \begin{cases} \theta_1 &= 1 - \|k\| \\ \theta_{i+1} &= k_i, \text{ for } i = 1, \cdots , n-1\\ \end{cases} \]

Current solution uses approach 1. C++ implementation: [geometry_primitive.h]

Rotation

This blog uses Special Orthogonal Group to deal with N-Dimensional rigidbody rotation problem.

\[ SO(n) = \left\{ R \in \mathbb{R}^{n \times n} \middle| \det R = 1, R^\top R = I \right\} \]

A single rotation in high dimensional space is defined by a rotation plane and a rotation angle. A general rotation can be composed by multiplying several single rotations. Details are explained in a later blog ^[2].

C++ implementation: [full_dimensional_rotation.h]

Pinhole Camera Model

In N-Dimensional Space, a Pinhole Camera projects N-Dimensional points to (N-1) dimensional points. The camera matrix \(K\) is 3D space is:

\[ K = \left[ \begin{matrix} f_x & 0 & c_x \\ 0 & f_y & c_y \\ 0 & 0 & 1 \end{matrix} \right] \]

Where \(f_x, f_y\) are the focal lengths and \(c_x, c_y\) are offsets of principle point.

By extending the matrix to N-Dimension, the model can be described as:

\[ K = \left[ \begin{matrix} \text{diag}(f) & c \\ 0 & 1 \\ \end{matrix} \right] \]

Likely, \(f\) is the focal length vector, \(f \in \mathbb{R}^{n-1}\). \(c\) is the principle offset vector, \(c \in \mathbb{R}^{n-1}\).

Screen Ray Cast

In ray tracing pipeline, pixel color calculation were started by casting rays to the scene. The transform from a pixel coordinate point \(v \in \mathbb{R}^{n-1}\) to ray expression \(r(t)\) is described as follow:

\[ r(t) = p_c + R_c \frac{d_v}{\|d_v\|} t \] \[ d_v = K ^{-1} \left[ \begin{matrix} v \\ 1 \\ \end{matrix} \right] \]

Where \(p_c, R_c\) is the position and orientation of the camera. \(d_v\) is the direction vector of pixel point, which is not normalized. \(K\) is the intrinsic matrix of the N-Dimensional pinhole camera model.

C++ implementation: [model_camera.h]

Axis Aligned Bounding Box(AABB)

An AABB in N-Dimensional Space can be described by either a center point and a half extent or a minimum point \(p\) and a maximum point \(q\) . This blog uses the later description.

\[ p \in \mathbb{R}^n; q \in \mathbb{R}^n; p_i < q_i \text{ for}\ i = 1, \cdots, n \]

The open region \(B\) described by the bounding box is

\[ B = \left\{x \in \mathbb{R}^{n} \middle| p_i <x_i < q_i \text{ for}\ i = 1, \cdots, n \right\} \]

Intersect with N-Ray

For a specific axis \(i\), the inequality equation of the intersection problem is:

\[ p_i < c_i + d_i t < q_i \]

The solution in axis \(i\) is:

\[ T = \left\{ t \in \mathbb{R} \middle| t \in \left(\frac{p_i - c_i}{d_i}, \frac{q_i - c_i}{d_i} \right) \right\} \]

Specifically, when \(d_i = 0\), there are three cases:

1. \(c_i \leqslant p_i < q_i \Leftrightarrow t \in (+\infty , +\infty ) \Leftrightarrow T = \emptyset \)
2. \(p_i < c_i < q_i \Leftrightarrow t \in (-\infty , +\infty ) \Leftrightarrow T = \mathbb{U} \)
3. \( p_i < q_i \leqslant c_i \Leftrightarrow t \in (-\infty , -\infty ) \Leftrightarrow T = \emptyset \)

Consider all axis, the solution is:

\[ T = \left\{ t \in \mathbb{R} \middle| t \in \bigcap_{i=1}^{n} \left(\frac{p_i - c_i}{d_i}, \frac{q_i - c_i}{d_i} \right) \right\} \]

C++ implementation: [spatial_aabb.h]

Bounding Volume Hierarchy(BVH) Tree

N-Dimensional BVH Tree preserves the logic in low dimensional space. Details will not be explained here.

C++ implementation: [spatial_bvh.h, spatial_bvh_inl.h ]

References

1. en.wikipedia.org, Simplex
2. Xiaoxing Chen, Two Reflections Form A Single Rotation