The first thing I did was write a pseudo 5x5 matrix class. Rotations, scales, skews, etc. can all be handled by the built in 4x4 matrix provided by XNA, but to be able to combine translation in there with a matrix multiply, you need one more dimension than the space you're working in. As it turns out though, I only actually needed the fifth row, not the fifth column. XNA uses row vectors, so the translation portion of the matrix is in the fifth row, but since I'm not doing any kind of 4D projection, the fifth column is always [0, 0, 0, 0, 1]. I implemented the class to always assume that, and substantially cut down on the number of floating point operations required. This means that it's not actually a "true" matrix though, so I called it AffTrans4D, since its sole purpose is to represent affine transformations. For similar reasons, I didn't implement a Vector5, since the last element would always be 1, so I just kept using XNA's Vector4.
With that out of the way (complete with vigorous unit testing to make sure it actually worked right), It was time to actually make some geometry. This is where it starts to get weird. In 3D, the basic unit of geometry is the triangle. Some combination of these can form 2D faces, which in turn make up a 3D object. In 4D, the situation is similar. The basic unit of 4D geometry is the tetrahedron, some combination of which makes up a 3D "Cell," which are the basic facets of a 4D shape (also called a polychoron). As an example, the tesseract (or hypercube), is composed of 8 cubic cells, two capping the extremes of each axis. This is surprising at first, to realize that the 4D analog of the cube contains a full 8 of its 3D counterparts, but it gets worse...
In 3D, perhaps the most common arrangement of triangles into a face is the quad, which is a mere 2 triangles. A 3D cube therefore is built from 12 trianlges, 2 for each face. Unfortunately, the situation isn't so simple for the tesseract. Subdividing a cube into tetrahedrons yields more primitives than subdividing a square into triangles:
We have not 2, but 5 primitives within. A tesseract is consequently an arrangement of 40 tetrahedrons, each of which itself has 4 triangles. So going strictly by triangle composition, a tesseract is roughtly 13 times as much geometry. Many of those triangles are shared by cells, just as edges are shared by faces, but this is just an illustration of the kind of complexity explosion that can happen even with simple geometry. Curved and sphere-like shapes are even worse, but that's another discussion.
Anyway, we have all this geometry, but what do we do with it? To render it, we need a 3D slice that we can add to the scene. This part was intimidating at first, but the algorithm actually isn't too bad. Getting a slice of an object is the same as the sum of the slices of its component tetrahedra. To slice a tetrahedron, we must examine each of its 6 edges to find if they cross the camera realm, and use those intersections to construct 3D geometry. This can be made much easier by first doing a sort of "view" transform on all the 4D geometry such that the camera realm aligns with W = 0. Once this is done, we can easily check for intersections if the two endpoints of an edge have opposing signs for their W component. If they do, a nice quick linear interpolation can give us the actual intersectioin point.
That's all fine and good, but what do we do once we have all the intersection points? It helps to first think about what kinds of cross-section a tetrahedron yields. If there are 0, 1, or 2 intersection points, we can discard it completely, as that means it's barely touching the camera realm and would yield at most a line segment. If there are 3 intersections, that means the slice is a triangle, which is useful to us and can be shipped off to the rendering system. If there are a full 6 intersections, then the entire tetrahedron is parallel with the camera realm, and we could choose to either draw the whole thing, or discard the whole thing. I chose to discard it, since a fully parallel tetrahedron means the 4D shape is lying cell-wise on the camera realm, barely intersecting it. The most interesting case is if there are 4 intersections, because this forms a quad. So what? just draw a quad! Well, the rub is that if you just have a set of 4 points, how exactly do you arrange them into the proper quad? In other words, which edge is the common edge?
My first take on this was to just draw all 4 possible quads, since one of them will be correct, and that one will contain all the incorrect ones, so you wouldn't actually see the overdraw. This felt sloppy though, so I was considering all kinds of cross product/normal comparison trickery to figure it out. Then I realized though, that the reason I didn't know which quad was correct was because I was doing the intersections in an arbitrary order, but that if I did the checks in a very specific order, I could be sure which was the right one:
As can be seen here, if we number the edges thusly and do the checks in that order, any quad slice we get will come out in triangle-strip order, so we can be sure which way we need to construct the triangles, at no addition performance cost at all!
This is lucky, because computing a 4D normal is about 4 times as costly as a 3D one. In 3D, if we have 2 vectors, we can take their cross-product and get a 3rd which is a normal to the surface containing those 2 vectors. But what to do in 4D? As it turns out, Cross4 requires 3 input vectors, yielding one result. It took some rather desparate googling to find the answer, but in the end the solution is to take the determinant of a 4x4 matrix with the top row as the components of the answer, and the lower 3 rows as your argument vectors. This is a rather heavy op though, so I try to avoid it as much as possible. The one place where I couldn't avoid it though was when trying to do proper face-culling on the gpu. The 3D slices were working, but I couldn't for the life of me think of an efficient way to figure out which side of the slice is the "front" without taking the 4D normal of the tetrahedron, projecting that into 3D, and using that to determine the front face. This makes the slicing algorithm about twice as complicated though, so for now I've simply decided to disable face culling and live with the overdraw. I'm so massively CPU bound though that it's not a huge issue yet. Still though, if anyone has any ideas about this I'd love to hear them.
I think that about covers the main algorithms. If anyone has any questions or I forgot to explain something, feel free to ask. The next entry will be more about what I did to improve performance on the 360.
