# trvrmrtn Blog/Hello-4D-Raytracing

Posted: June 24th, 2024

If you don't already have a strong understanding of vectors (or want a refresher), see the previous post. I highly recommend it.

In the last post, we went over how we can expand geometry into four spacial dimensions. In this post, we're actually going to use it to draw some (hopefully) interesting things. But first, we're going to need a brief intro to raytracing.

Introduction to raytracing

In the real world, light is emitted from sources like a desk lamp, your phone, or the sun. It then travels in rays until it hits something. When it collides with an object, some wavelengths get absorbed and some get reflected. Light keeps doing this until it is completely absorbed, gets scattered senselessly, or is captured by a camera or human eye. While this process seems simple (especially as I write it out), it is extremely complex and gives rise to several interesting phenomina that we will attempt to replicate later.

So let's get started.

The ray function

If you remember from geometry, a ray originates at a point and goes off infinitely in one direction. We want to define a function to map a distance along the ray with a point on the ray. Let's define two variables: O and D. O is the ray's origin (or starting point). D is a vector in the ray's direction (we'll say for now that |D| = 1). Going back the the examples in the previous post, O can be thought of as the position of the cat and D is a vector of the relative position of the dog but of length 1. D isn't the relative position of the dog, but it points in the same direction. If we add O and D, we will get a vector 1 unit along the ray toward the dog.

Now, say that we know that the dog is 1.7 units away from the cat in the direction described by D. We can get the position of the dog relative to the cat by multiplying the vector D by 1.7 (because we know that the length of D is 1; |D| = 1). This would mathematically be expressed by 1.7D (I'm avoiding using * because it looks like dot product). We can then get the actual position of the dog (relative to origin) by adding O and out new direction vector: O + 1.7D.

But what if we don't know the dog's length along the ray? We define a function.

R(t) = O + Dt, where t ≥ 0

This function may look a little scary, but we're expressing the exact same thing as above. We have a relative direction (D) that we're scaling by an amount (t) and adding to O to find the actual position. Going back to the example, we can calculate the position of the dog by evaluating R(1.7).

dog position = R(1.7) = O + 1.7D = what we did above

This is a rather contrived example of the use of a ray as we'll be primary be modeling light with it (as opposed to pets). The logic still stands, however, a ray of light has an origin source and an initial direction which it will follow until it hits something.

Now, to find when (or if) the ray hits something. To do so, we just need to solve for t!

Introducing the hypersphere

How would you explain a sphere to a square on a piece of paper? For one, you shouldn't; you should be on medication. But if you wanted to, one may go through a plethora of definitions like a circle rotated about the x axis or an object whose slices are circles of varying radius. We would likely, however, be met with unwavering confusion as we try to explain something utterly outside the square's experience. Instead, we'll go with the definition of all three dimensional points of distance r from its center C.

Note: This definition can also apply to defining circles.

True, our definition does little to help our square friend visualize a sphere, but we'll assume that truly envisioning it is impossible for our dear friend. Instead, by providing a mathematical definition, our square can still reason about it. Now, our four dimensional friend (who setup the fourth ruler in the last post) is going to attempt something similar for us.

Our friend begins by telling us about this new shape called a hypersphere (creative, I know). The hypersphere is to a sphere what a sphere is to a circle, and like a sphere (or circle) can be defined by the points a set distance from its center. Whether a point makes us a hypersphere can be checked with the inequality:

|P - C| = r

Important: Take a second to read over this formula. Understand exactly what it is discribing will make your life easier, and you have the tools to do so. If necessary, look back at the previous blog post to review vector algebra.

Using this formula, we can check if a point P is on our hypersphere. We can also check if a point of distance t along the ray R(t) is on the hypersphere:

|R(t) - C| = r

Now, an attentive reader may notice that the above equation has one unknown: t. All other variables (C and r) are defined by the object. Therefore, if we can solve for t it means that the ray hits the hypersphere! Time for some algebra.

First we substitute R(t) for O + Dt and move the variables around a bit:

|R(t) - C| = r
|O + Dt - C| = r
|Dt + O - C| = r

Now, we'll use our definition of magnitude (|A| = sqrt(A * A)) from the previous post:

|Dt + O - C| = r
sqrt((Dt + O - C) * (Dt + O - C)) = r
(Dt + O - C) * (Dt + O - C) = r2

At this point, I'm going to be a little hand-wavey. Like scalar addition and multiplication, vector addition and dot product are also distributive. I could prove the following step, but I don't want to; it could be an interesting exercise for the reader. I'll just group the equation and distribute it:

(Dt + O - C) * (Dt + O - C) = r2
(Dt + (O - C)) * (Dt + (O - C)) = r2
(Dt * Dt) + (Dt * (O - C)) + (Dt * (O - C)) + ((O - C) * (O - C)) = r2
(Dt * Dt) + 2(Dt * (O - C)) + ((O - C) * (O - C)) = r2

Vector scaling can be moved outside the dot product (because the variable will be in each of the components summed up, and we can use the distributive property). So, As * B = (A * B)s. Once again, if you feel so inclined, prove it. Based on that property, we can move the ts outside their dot products:

(Dt * Dt) + 2(Dt * (O - C)) + ((O - C) * (O - C)) = r2
(D * D)t2 + 2(D * (O - C))t + (O - C) * (O - C) = r2

We'll just move r2 to the other side of the equation:

(D * D)t2 + 2(D * (O - C))t + (O - C) * (O - C) = r2
(D * D)t2 + 2(D * (O - C))t + (O - C) * (O - C) - r2 = 0

Now, squint really hard at the equation. It should look like something. I'll give you a hint:

a = D * D
b = 2(D * (O - C))
c = (O - C) * (O - C) - r
x = t

Gives us:

ax2 + bx + c = 0

Now, let's go back and remember what we're actually doing this for. We are trying to find the value t such that the resulting point from R(t) is on our hypersphere. Now, how do you solve a quadratic equation? The quadratic formula.

x = (-b ± sqrt(b2 - 4ac)) / 2a [Sorry, I can't do fractions easily]

Now, I won't write out the full equation. An implementation should probably just evaluate a, b, and c and store them in variables. But, when evaluating the quadratic formula, there are two things you need to keep in mind: the denominator not being zero and the number of solutions.

First, the denominator will never be 0. That would mean that our D vector would be a zero vector, which we will just pinky promise to never do. This is because each component is squared with itself, so they're all positive. For the sum to be zero, all squares must be zero. Secondly, the expression b2 - 4ac can be three things: positive, zero, or negative.

If b2 - 4ac (aka. the discriminant) is positive, that means we have two solutions (the square root will be added to and subtracted from -b and divided. A positive discriminant means that the ray hits the hypersphere at two points. Great!

If the discriminant is zero, that means we only have one solution (because a number plus or minus zero will just be that number). If the discriminant is zero, our result will be -b divided by 2a, and that will be the end of it. Still good; we at least hit it.

If the discriminant is negative, that means we have two imaginary solutions on our hands. For practical purposes, that means we have no solutions. In this case, the ray goes off into infinity, never being seen again. Further Research: I would love to know if there are actual meanings behind the complex numbers from a miss.

In summary:

    Two Hits (Positive)  |       One Hit (Zero)    |    No Hits (Negative)
                         |                         |
                         |            /            |  ^
          _____          |          X____          |  |       _____
         /     \         |        //     \         |  |      /     \
        /       \        |      / /       \        |  |     /       \
       |         |       |    /  |         |       |  |    |         |
  O----X---------X-->    |  O    |         |       |  O    |         |
       |         |       |       |         |       |       |         |
        \       /        |        \       /        |        \       /
         \_____/         |         \_____/         |         \_____/
			

Important: For a hypersphere, use the minus solution to the equation (that's the closest hit). Also, make sure you always check to that your t value is positive, or you're linetracing--not raytracing.

So, if we define a hypersphere located at C = <0, 0, 0, 0> with radius r = 1, and have rays originate at O = <0, 0, -3, 0> in the direction of D = <x, y, 1, 0> where x and y vary from -1 to 1 and render it, we get:

Initial Hypersphere Render

Riveting...

Because this image is kind of boring, I'll spice it up by having the color correspond to the direction the surface is facing at that point (the sphere's normal at that point). Don't worry if you don't understand any of what I just said. I'll go over that in the next post on shading.

Normal Shaded Hypersphere Render

At first this appears disappointing, but it's exactly what we expect. Going back to our square friend, he would see something almost identical if we introduced a sphere. Say we placed him on a table looking over the ledge. The square's field of view will be exclusively limited to the flat surface of the table, but he will be able to see straight out over the edge. If we hold a red sphere just off the ledge, the square will only be able to see part of the sphere: the part contained by the plane that makes up the table surface. To the square, our sphere will only look like a circle that will shrink and grow as we move the sphere up and down. The same is true as our four dimensional friend moved a hypersphere up and down; our three dimensional eyes will only be able to percieve a sphere growing and shrinking in size. It's kinda lame, but what happens if we show the square a mirror facing outside of their planar view? That's next post.

Before you head out, however, I feel like we need a 'floor' to put our hypersphere on.

Introducing the hyperplane

As you can tell, mathematicians' creativity knows no bounds.

Ok, first: what is a hyperplane? I'm going to skip over our arguments with our square and four dimensional friends, and go right out of the gate with this definition: all points P which are (relative to the plane center C) perpendicular to the normal vector N.

What does that mean? Well, we may need our square friend after all...

These are some lines (our square's closest thing to planes). Labeled in the drawing is the point C and our normal vector N. For now, you just need to know that a normal vector is perpendicular to the line.

                        \        N           \
       N                 \     /              \
       ^                  \  /                 \
       |                   C                    C
       |                    \                 /  \
-------C-------              \              /     \
                              \            N       \
			

You can see that (at least in the first example), every point along the unmarked section (the actual line) is perpendicular to the vector N. This is the same in three dimensions; if you put a piece of paper on a table and place a pencil facing straight up, all points on the paper are at 90° angles to the pencil. The same is true in four dimensions.

So how do we define a hyperplane?

You know when I said in the last post that there was "a different formula" that "we'll deal with it in shading"?

Turns out I lied. Sorry.

The other formula for a dot product is:

A * B = |A||B|cos(theta) [Where theta is the angle between the vectors A and B]

Note: Now you can find another reason why A * A = |A|2.

Because all points must be at a right angle to the normal vector relative to the center, that means that theta = 90° and cos(theta) = 0. And because the position of P relative to the center C is P - C, the final equation is (P - C) * N = |P - C||N|cos(90°) = |P - C||N|(0) = 0

To reiterate, our hyperplane equation is:

(P - C) * N = 0

Now, like above, we can substitute in R(t) and solve. I'll be a bit quicker this time.

(P - C) * N = 0                [Given]
(R(t) - C) * N = 0             [Substitute P for R(t)]
(O + Dt - C) * N = 0           [Expand R(t)]
(Dt + O - C) * N = 0           [Shuffle around some stuff]
(Dt + (O - C)) * N = 0         [Group O - C together (just for looks)]
(Dt * N) + ((O - C) * N) = 0   [Distribute N]
(D * N)t + ((O - C) * N) = 0   [Move t out of the dot product]
(D * N)t = -((O - C) * N)      [Move (O - C) * N to the right side]
t = -((O - C) * N) / (D * N)   [Move t all the way to the left side, solving for t]
			

That's it. You do need to check if D * N is 0 (the ray is parallel to the hyperplane) and make sure t is positive, but other than that, you just created a hyperplane!

Here is a normal-shaded hypersphere (from above) on a hyperplane (C = <0, -1, 0, 0>, N = <0, 1, 0, 0>):

Normal Shaded Hypersphere Render

If you're bored, please feel free to mess around with the parameters. What happens if you change the w value of the hyperplane's normal? What happens when you move the hypersphere through w? Does a ray's direction (D) need to have a magnitude of 1? What about the hyperplane normal? Can you make an approximation of the Cornell box? Play around with this; have fun.

In the next post, we'll probably do shading so the real fun stuff can begin.

Til next time,

Cheers.

Trevor Martin