How do I get a 3D cross section of a 4D mesh?

Question

I have a polychoron represented as a four-dimensional mesh, stored with the face-vertex method. All the faces are triangles. How can I get a three-dimensional cross-section of the figure?

The closest thing I've found is this question, but it's one dimension short.

Banshee

see how should i handle (morphing) 4D objects in opengl? – Mcnelly

Answer 1

Working with 4 dimensions are a bit difficult.

The only way to solve the problem is finding dimensional analogies.

Let's start from 2D

A convex 2D polygon has convex 1D sides: line segments.

The cross-section of a filled convex polygon is a line segment.

Calculate the intersection points of your poligons edges with the intersecting line, you'll get two intersections for a convex polygon, and the cross section will be a line segment.

To do this easily transform the coordinates so you do the cross section on the Y axis of the coordinate system. The two points of the edge is A and B. Their coordinates are a1, a2 and b1, b2.

If the signs of a1 and b1 is the same, (aka a1*b1 > 0) the edge won't intersect the Y axis.

Otherwise calculate k = a1/(a1-b1).

Then the coordinate of the intersection point will be: (0; (1-k)*a2+k*b2)

As I said for convex polygons you'll get two intersection points, connect the two point to get the 1D cross section.

Now let's generalize to 3D

A convex 3D mesh has convex 2D sides: triangles.

Again, transform the coordinates to make the operation easier. Let's get the cross section of the mesh on the Y-Z plane, so the X coordinates will be zero again.

Get the cross sections of the triangles. Using the algorithm above for each edge of them. Since we have 3 dimensions the endpoints of the edge will have the coordinates a1, a2, a3 and b1, b2, b3. If a1*b1<0 we have an intersection point. So

Let k = a1 / (a1 - b1)

The coordinate of the intersection point is (0; (1-k)*a2+k*b2; (1-k)*a3+k*b3). Store this coordinate, but also store the index of A and B points of the mesh (the edge index). It'll be useful later.

For each triangle this will yield a line segment.

Now you'll need to connect these cross section line segments to a polygon. That's why we stored the edge indexes along with the intersection points. You have a set of lines and you can match their endpoints by the stored edge index, so you can connect them into a polygon.

Now let's generalize to 4D

A convex 4D mesh has convex 3D "sides": tetrahedrons. (note probably your face-vertex representation is incorrect)

Again, transform the coordinates to make the operation easier. Let's get the cross section of the mesh on the Y-Z-W hyperplane, so the X coordinates will be zero again.

Get the cross sections of the tetrahedrons. Using the algorithm above for each face of them. Since we have 4 dimensions the endpoints of the edge will have the coordinates a1, a2, a3, a4 and b1, b2, b3, b4. If a1*b1<0 we have an intersection point. So

Let k = a1 / (a1 - b1)

The coordinate of the intersection point is (0; (1-k)*a2+k*b2; (1-k)*a3+k*b3; (1-k)*a4+k*b4).

For each triangle of a tetrahedron this will yield a line segment. For each tetrahedron this will yield a triangle. For each edge of these triangles also store the index of A, B and C points of the triangle of the 3D mesh (the face index) the line segment originates from. It'll be useful later.

Now you'll need to connect these cross section triangles to a 3D mesh. That's why we stored the face indexes along with the intersection edges. You have a set of triangles and you can match their edges by the stored face index, so you can connect them into a triangle mesh.

For concave 4D meshes you may have get multiple 3D meshes.

---

Hope you see the analogy.

The concrete implementation will be a bit diffcult, you'll need to take care of all corner cases (division by zero cases, floating point errors, etc).

Crasis

Many concave polyhedra can't be divided into tetrahedra, e.g. the Schönhardt polyhedron. The face/vertex method is clearly not what I want here, but I haven't found a decent substitute. This is probably the most help I can get given the obscurity of the subject, so I'll accept your answer. – Banshee

@ColdFusion 4D meshes have cells, faces, edges and vertices. In 4D the basic 3D building block of a 4D mesh is a cell, a tetrahedron. Just like the 2D triangles are the building blocks of 3D meshes, or 1D line segments for the 2D polygon. Schönhardt polyhedron is 3D, tetrahedron 3D. Of course you cannot divide it, but you can always define that shape by triangles. – Crasis

@ColdFusion If you can somehow find a copy of Paul L. Isaacson's master's thesis entitled "Computer Graphic Presentation of Hypothesized Four-Dimensional Phenomena" (1984), he includes a few useful 4D geometry-related algorithms, one of which is an n-dimensional intersection algorithm. If you're having trouble finding it, let me know; I currently work for the professor who was the adviser of this thesis. – Weil