Thoughts on 4D Rendering: Slicing Method

Design

Let's say you want to render an \(n\)-dimensional scene, one 3D slice at a time.

In 3D rendering, we typically represent the world as a mesh of triangles. So the obvious thing to do is replace this with a mesh of \((n-1)\)-simplices. But I think this is a mistake.

Why? Polygon count. To make a square, you need two triangles, which isn't bad. But for a cube, you need five tetrahedra. For a hypercube, you need sixteen simplices. Et cetera.

Instead, let's represent it as a mesh of arbitrary convex faces, with data about which faces connect to which. Each face simply stores the equation of the hyperplane it lies in.

Math

Before starting on the math, recall the idea of an affine transformation. Basically a linear transformation, plus a translation. A map \(\mathbb{R}^m \xrightarrow{\text{affine}} \mathbb{R}^n\) is represented as an \(n \times (m+1)\) matrix; we apply it to a vector in \(v \in R^m\) by computing \(M\begin{bmatrix}v\\1\end{bmatrix}\).

High-level Algorithm

Our mesh will consist of the following data:

• A collection of facets. Each stores its containing hyperplane, as an affine transformation \(h_f : \mathbb{R}^n \to \mathbb{R}\). We take the convention that \(h_f \lt 0\) is the inside, and \(h_f \gt 0\) is the outside.
• A collection of ridges (places where the facets meet), each associated with an unordered pair of facets.
• The above should describe the surfaces of a collection of convex polytopes.

We want to cut this down to a 3D subspace, given by an affine transformation \(i : \mathbb{R}^3 \to \mathbb{R}^n\).

By composing with \(i\), each facet's hyperplane restricts to a map \(p_f : \mathbb{R}^3 \to \mathbb{R}\), whose kernel describes a plane in \(\mathbb{R}^3\).

Focusing on one facet, \(f\), find an affine map \(j : \mathbb{R}^2 \to \mathbb{R}^3\) whose image is this plane. (Sadly, there's no particularly nice way to do this, so just pick something that works.)

For each neighboring facet, \(f'\), we have an affine map \(p_{f'} \circ j : \mathbb{R}^2 \to \mathbb{R}\), which describes a line in the plane. And the intersection of all the half-spaces \(p_{f'} \circ j \lt 0\) describes the facet itself.

There's a classic algorithm to triangulate the intersection of half-spaces in a plane. Do that. Then apply \(j\) to the resulting vertices, to place the result back into 3D space.

Combining the results from all facets, you now have a triangle mesh, which you can hand to the standard graphics pipeline.

Data Layout

This algorithm ought to be relatively GPU-friendly.

Lay the data out as follows:

• Array of facets. Each facet contains \(n+1\) floats, describing the hyperplane, and an index into the array of ridges.
• Array of ridges. Each ridge appears twice, one for each ordering of its facets. The array is sorted so that all the ridges with common first facet are together. Each ridge stores its second facet.

When you run the algorithm:

• The \(p_f\)s form an array of vec4s.
• The \(j\)s form an array of mat3s.
• The half-space intersection algorithm is a bit less friendly, but you can still handle the facets in parallel. Execution of the algorithm essentially proceeds by detecting and throwing away redundant faces, so memory use is easily bounded.
• The resulting triangle array will have holes in it. But these are easily removed with a scan operation, which has a relatively fast parallel algorithm.
• Then it's just a matter of making sure the vertex array has the right format for OpenGL to accept it.