1
$\begingroup$

I am trying to compute all possible intersections between a tetrahedron lying in 4D space and a non-centered 3D hyperplane. Because of my lack of visualization (obviously), and for computer rendering purposes, I am using a computational approach.

My algorithm fills an array with vertices, and builds the resulting intersection as being the convex polygon or polyhedron uniquely defined by said vertices, on the basis that the intersection of a convex set with a hyperplane is also convex.

Here is the workflow of the algorithm :

  • Determine which of the tetrahedron's points lie in opposite half-spaces
  • If all points are in the same half-space, terminate with an empty intersection
  • If at least one point is inside the hyperplane, then add to the array all the vertices that are inside the hyperplane. This could be 1, 2, 3 or 4 vertices
  • Then, for each edge that intersects the hyperplane (ie edges for which the two vertices lie in opposite half-spaces), add to the array the intersection between that edge and the hyperplane

Although I have not written a rigorous proof for this, I find empirically that you only get points, lines, triangles, quadrilaterals or tetrahedras out of this algorithm (or at least, I have never encountered a counter-example).

The problem resides in this visualisation of a unit hypercube rotating around its center on the XZ and ZW canonical planes by equal angles, in that order (WebM video) :

http://www.mirari.fr/ITg9

The principle of the visualisation is a simple application of the aforementioned algorithm. The hypercube is decomposed in 4D tetrahedras, which are subsequently intersected with a 3D hyperplane, which is defined by the position of the camera and the direction of its (3D) viewing frustum. The resulting intersections, being 3D objects, are directly displayed on the screen with no further transformation. The pixels colored with different shades of blue are forward-facing faces, and the black pixels are backward-facing faces.

As you can see, the 3D model becomes non-convex from time to time, as it looks like a face or two are "forgotten" and we can see the "inside", back-facing faces behind. This leads to my question : am I forgetting any scenario in my intersection algorithm that may lead to the omission of some of the 3D objects making up the hypercube ? Although I have not yet totally outruled a flaw in my rendering process, I believe I have done enough checking and trying to think the error is in this algorithm.

$\endgroup$
2
  • $\begingroup$ In general, you can solve this problem for a $k$-simplex in $n$-space sliced by an $n-k + 1$ plane. Aside from the kind of edge-cases (like slicing a tetrahedron in a way that gives you a single edge), you can look at $s+1$ vertices on one side of the slice plane, $k - s$ on the other side, and then figure out the number of vertices of the slice object, and their connectivity, and there's really no need for anything numerical -- it's pure combinatorics. (The "special cases" are really just the cases where there are some verts on one side, some on the other, and some ON the slice plane, BTW.) $\endgroup$ Aug 28 '17 at 20:22
  • $\begingroup$ Surely, but the point of the whole thing is the actual representation of it, so I do have to get numerical at one point, haha. $\endgroup$ Aug 28 '17 at 20:33
1
$\begingroup$

The slice of a tetrahedron $T$ in 4-space by a 3-plane $P$ can be simplified:

let $U$ be the 3-plane that contains the tetrahedron (there always is one!).

Then $$slice(T, P) = slice (T \cap U, P \cap U) $$ so any such slice is the slice of a tetrahdron by some plane in 3-space. So you're done, and no visualization is needed.

$\endgroup$
4
  • $\begingroup$ Just to be sure, what you wrote as $slice(A, B)$ is really just $A \cap B$ right ? $\endgroup$ Aug 28 '17 at 20:16
  • $\begingroup$ Yes, but I wanted to emphasize that it was the slicing operation; I should have mentioned that. $\endgroup$ Aug 28 '17 at 20:18
  • $\begingroup$ Okay, I guess it helps a little, although I won't be using that approach. The point of the algorithm is to not have to calculate $P \cap U$, which would require calculating a base for $U$ and the intersection between both hyperplanes, in addition to actually intersecting the tetrahedron with the result. Instead, it directly computes the intersection with very few and fast (from an algorithmic point of view) conditionals. One thing that bugs me is that there are infinitely many 3-planes that contain the tetrahedron, so can't I always choose one that is parallel to P ? $\endgroup$ Aug 28 '17 at 20:31
  • $\begingroup$ Answer to self : no you can't, because 4 non-coplanar points define a single 3-plane. Nevermind ! $\endgroup$ Aug 28 '17 at 20:34
0
$\begingroup$

You mentioned your second step as: If all points are in the same half-space, terminate with an empty intersection. Just checking (as I will be needing to do this myself soon) if you wouldn't also need to do a test if three or four points lie completely in the intersection instead of in opposite halves? If that tests as true then wouldn't that single face (3 points) or the whole tetrahedron (4 points) need to be drawn instead of an intersection through the tesseract? Could that possibly be why yours had missing faces?

$\endgroup$
3
  • 1
    $\begingroup$ Welcome to MSE. This should be a comment, not a answer. $\endgroup$ Apr 9 '18 at 12:51
  • $\begingroup$ Thanks José I'll try to move it to the right place. Just realised I can't so I better remove it... $\endgroup$ Apr 9 '18 at 13:04
  • $\begingroup$ By "in the same half-space", I meant that all the points returned the same non-zero value when fed to the hyperplane's cartesian equation. $\endgroup$ Apr 9 '18 at 21:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.