Archive for the ‘Mathematics’ Category

SIGGRAPH 2020 talk for my technical paper: N-Dimensional Rigid Body Dynamics

Tuesday, January 5th, 2021

It’s very exciting for work from a game (and a first for an indie game) to be presented in the SIGGRAPH Technical Papers program! Thank you all for your patience during development of the game, as you can see it can get pretty involved, ahah!

Link to the paper

SIGGRAPH 2020 Technical Paper: N-Dimensional Rigid Body Dynamics

Thursday, May 7th, 2020

Excited to announce that my technical paper “N-Dimensional Rigid Body Dynamics” was accepted to SIGGRAPH 2020! Very proud to present research developed for 4D Toys & Miegakure at such a prestigious conference.

Here is the link to the paper and the abstract:

I present a formulation for Rigid Body Dynamics that is independent of the dimension of the space. I describe the state and equations of motion of rigid bodies using geometric algebra. Using collision detection algorithms extended to nD I resolve collisions and contact between bodies. My implementation is 4D, but the techniques described here apply to any number of dimensions. I display these four-dimensional rigid bodies by taking a three-dimensional slice through them. I allow the user to manipulate these bodies in real-time.

Btw I believe it is basically unheard of to have work from an indie game presented in the SIGGRAPH technical papers track?

The paper is full of really fun and beautiful math (obviously Geometric Algebra based, see my recent article) that makes me happy. One reviewer called the work “whimsical,” and they’re not wrong, ahah.

Most of this work (including writing the paper) is from ~2012, but I added a section on the (4D) Dzhanibekov effect at the suggestion of the reviewers. Many thanks to them for helping me greatly improve the paper.

Interactive Article/Video: Let’s remove Quaternions from every 3D Engine (An Interactive Introduction to Rotors from Geometric Algebra)

Monday, February 3rd, 2020

I have not yet posted on this blog that last year I released an article/video with interactive diagrams on Geometric Algebra, specifically Rotors. (I also recently updated it). Here is the introduction:

To represent 3D rotations graphics programmers use Quaternions. However, Quaternions are taught at face value. We just accept their odd multiplication tables and other arcane definitions and use them as black boxes that rotate vectors in the ways we want. Why does $\mathbf{i}^2=\mathbf{j}^2=\mathbf{k}^2=-1$ and $\mathbf{i} \mathbf{j} = \mathbf{k}$? Why do we take a vector and upgrade it to an “imaginary” vector in order to transform it, like $\mathbf{q} (x\mathbf{i} + y\mathbf{j} + z \mathbf{k}) \mathbf{q}^{*}$? Who cares as long as it rotates vectors the right way, right?

Personally, I have always found it important to actually understand the things I am using. I remember learning about Cross Products and Quaternions and being confused about why they worked this way, but nobody talked about it. Later on I learned about Geometric Algebra and suddenly I could see that the questions I had were legitimate, and everything became so much clearer.

In Geometric Algebra there is a way to represent rotations called a Rotor that generalizes Quaternions (in 3D) and Complex Numbers (in 2D) and even works in any number of dimensions.

3D Rotors are in a sense the true form of quaternions, or in other words Quaternions are an obfuscated version of Rotors. They are equivalent in that they have the same number of components, their API is the same, they are as efficient, they are good for interpolation and avoiding gimbal lock, etc… in fact, they are isomorphic, so it is possible to do some math to turn a rotor into a quaternion, but doing so makes them less general and less intuitive (and loses extra capabilites).

But instead of defining Quaternions out of nowhere and trying to explain how they work retroactively, it is possible to explain Rotors almost entirely from scratch. This obviously takes more time, but I find it is very much worth it because it makes them much easier to understand!

Earth-Centric planetary motion

For example, Quaternions are introduced as this mysterious four-dimensional object, but why introduce a fourth dimension of space to visualize a 3D concept? By contrast 3D Rotors do not require the use of a fourth dimension of space in order to be visualized.

Trying to visualize quaternions as operating in 4D just to explain 3D rotations is a bit like trying to understand planetary motion from an earth-centric perspective i.e. overly complex because you are looking at it from the wrong viewpoint.

It would be great if we could start phasing out the use and teaching of Quaternions and replace them with Rotors. The change is simple and the code remains almost the same, but the understanding grows a lot.

As a side note, Geometric Algebra contains more than just Rotors, and is a very useful tool to have in one’s toolbox. This article also serves as an introduction to it.

And here are some quotes about it:

The clearest explanation of 3D geometric algebra within 15 minutes that I’ve seen so far —BrokenSymmetry
I am sold. While I can understand quaternions to an extent, this way of thinking is a much more intuitive and elegant approach. —Jack Rasksilver
This sets a high standard for educational material, and is a shining example of how we can improve education with today’s technologies. —Sebastien Pierre
When I was in college, I asked one of my math professors why the cross product of two vectors results in a perpendicular vector whose magnitude is equal to the area of the parallelogram formed by the two vectors. Like..what? Why? And what about 2D? They blew me off, and that was a big part of why I stopped taking math in college. […] Anyway, I had pretty much given up on ever truly understanding the whole jumble of seemingly unrelated types that are cross products. But then I saw this: And…wow. Just 15 minutes and a lot more than just cross products suddenly make a lot more sense. —Mason Remaley
I’m a pure math dude at heart, even if I don’t get to do it much any more. Two years ago, my wife asked me, “If you had to get a math equation tattooed on your body, what would it be?” I answered, “i^2 = j^2 = k^2 = ijk = -1”. I felt a brief flush of anger when I saw this headline. This is an extraordinarily good article that should be read by pretty much anyone doing graphics programming. —pflats

I wrote most of in 2011/2012, but didn’t release it because I was not satisfied with part of it. But I thought it was time to let go and release it anyway. I actually think it is hurting the advancement of science that people are still mainly using quaternions instead of Geometric Algebra, so holding on to it was not good.

So last fall/summer I cleaned up some of the diagrams and made a 15 minute long video that follows the article exactly. I never made a video this long, and it was quite exhausting. But I thought it would be really cool to make an article that is perfectly synced to a video, so you can either read it or watch it, and the article serves as an exact table of contents for the video.

I think I came across Geometric Algebra from attending SIGGRAPH a long time ago? Specifically this book: Geometric Algebra for Computer Science by Dorst et al. Later on I found this great book: Linear and Geometric Algebra by Macdonald

Geometric Algebra soon came in handy for Miegakure, specifically to define the 4D equivalent to Quaternions, which I posted about on this blog. Later on it became the backbone of 4D Toys.

Learning about Geometric Algebra was also great because it answered so many questions I had when learning linear algebra, the cross product, quaternions, etc… I basically wrote this article for my past self as a college student.

I recently rewrote the introduction to add more detail about the properties of Rotors and how they relate to quaternions. Even though the content went into detail, it should now be clear what Rotors are from only reading the introduction. I can already see from reading recent comments that it was worth it.

I deliberately picked a cheeky click-bait title…

Something else that might be of interest is the history of Geometric Algebra, so I recently added a heavily summarized version to the end of the article. I think looking at the history makes it clearer how the quaternion viewpoint stayed in people’s minds for longer than necessary…

4D Toys: a box of four-dimensional toys

Friday, June 2nd, 2017

So I have been working on Miegakure for a long time now, and I have created and accumulated many cool 4D things of all sorts. I think it’s about time that I share some of them, so…

Surprise! Today I am releasing something!

The History of 4D Toys

Near the very beginning of Miegakure’s development, someone joked I should do a “4D physics engine.” Then a year or so later I had gathered enough knowledge (especially in geometric algebra) that it was a possibility. So I made one for fun, and kept working on it on the side. It evolved into a 4D physics-based toy box that you can get right now, for iOS (Multitouch & Accelerometer) and Steam (both VR (Vive) and Mouse/Keyboard).

Basically it turns out the rules of how objects bounce, slide, fall, spin and roll around can be generalized to any number of dimensions, and this toy lets you experience what that would look like.

My initial goal in making this was to have a ton of fun inventing the math for it. At first I was skeptical it was going to be possible at all, but in the end the mathematics fit together so well.

I was only planning to use 4D physics a little bit for Miegakure as a purely aesthetic component, since dynamic physics is a bit too unpredictable to make good puzzles with. But then I started thinking about making a stand-alone iOS toy to play with 4D objects, to take full advantage of the physics. At first it was very simple and based around the idea that in 4D you can have interesting new dice shapes like a perfectly symmetrical 600-sided die, or a 4D hypercube die with 8 faces (each of them a cube). But I kept adding new shapes like hyperspheres, etc… and it got out of hand, so the dice theme didn’t fit anymore, and I named it simply “4D Toys.”

The website (4dtoys.com) has more info on it!

More details about the design of 4D Toys

Undirected 4D Play

4D Toys doesn’t take you through carefully-constructed successively harder challenges the way Miegakure does. It’s just 4D shapes, as if you were a very young kid again and given a box of wooden toys. Since the toys are 4D, that’s sort of true: you have no experience playing with 4D shapes.

Play is undirected and we don’t expect a child to come up with verbal realizations of what they are doing. They can learn about making stacks, and gravity, and fitting shapes into holes, and that could form the foundation for future, verbal, learning. Alternatively, one can just look at how pretty it is, like the waves rolling down the ocean, or the intricate swirling patterns in a fire.

It’s so exciting to me to see a pile of hypercubes or a rolling 120-cell. Most representations of a fourth dimension are so abstract (a spinning bundle of lines) and my work has been to get away from that. It’s the first time anyone has seen these objects as physical objects that bounce and roll and can be grabbed!

Side project

4D Toys was a very fun side project. It uses the same engine as Miegakure, and many improvements I made to it have hugely benefited Miegakure. For example, I built a lot of the complex 4D collision detection code used in Miegakure for 4D Toys. I also came up with many ideas for Miegakure levels and scenes while playing with 4D Toys.

Designing how to present 4D Toys

After I made it, I had to come up with a metaphor for what it was. Miegakure players know it is a puzzle-platforming game, so if they’ve played one before it sets a frame for the interaction, and the game can spend less time explaining everything and focus on the new stuff. They know how the game teaches things.

But 4D toys cannot rely on this well-known format. My goal was to strongly imply that it is not supposed to teach you in the way a puzzle-platformer like Miegakure does, but instead that it may only teach in an intuitive way. I came up with the idea of a box of toys, so the “menu” could be toys laid out on the floor, and you pick one and play with it, then come back to the menu.

However unlike a real toy box I have to first teach players how to manipulate the shapes a little bit. So I made a short tutorial that you have to play initially. The only thing that players really need to know besides the basic interactions is how to get back to the 4D shapes if they loose them into the fourth dimension. It’s fascinating to me that the tutorial teaches exactly that, even if a player has no idea what they are doing. Once the tutorial is complete almost all the shapes are available to play with.

I also wanted to explain, non-verbally, this idea of a 4D toy box, so we also put a small comic strip that shows how someone might end up with such a toy box. I like how subtly this idea is communicated. By the way, Kellan Jett (who is doing concept art for Miegakure) did the amazing art for it.

(By the way, for the VR version it is recommended to be on floor when playing!)

Adding an optional verbal explanation

I wanted to stop there and just give out a mysterious box of toys with barely any instructions, but playtesting revealed that some people really wanted to know more about how the shapes and how the fourth dimension worked and what they were seeing.

I think that while kids are fine playing with toys without fully understanding them, as we get old enough we start to ask “why?” when we discover something new… and as much as I like non-verbal learning, I didn’t want to leave these “why?” questions hanging in the air. If I manage to make you interested, why wouldn’t I try to answer these questions if I can? So I decided to add an optional interactive “Interactive Explanation” that takes you step by step through what the fourth dimension is, how a 2D being would experience the third dimension, and by analogy how a 3D being would experience the fourth dimension. This provides the beginning of an answer, and the toys become even more beautiful if you understand just a tiny bit more. There are also optional questions marks in certain scenes you can click on to get more info.

The interactive explanation could stand and be interesting on its own. It is very verbal, as opposed to the toy itself, which is totally non-verbal and freeform. While I wanted to get away from verbal learning because it is so often done poorly and takes you away from the experience, it is interesting to think about when verbal communication is appropriate and when it isn’t. In this case I think it is good that the explanation stands next to the experience itself and can be ignored. Interestingly, Miegakure sits sort of in-between these two extremes: it is goal-oriented and directed and has words, but it very intentionally never verbally teaches you about the fourth dimension or how to solve its puzzles.

Interaction method

Like I mentioned before, a problem that comes up when you are a 3D being playing with 4D toys is that they tend to disappear into the fourth dimension. A friend intuitively suggested a scrollbar to move along the 4D, and that seemed like the simplest way to solve the problem. Also this way we can display the extent of each shape in the fourth dimension and that allows players to very quickly find shapes when they lose them. Note that this is different from Miegakure’s mechanic of rotating the player’s slice. Miegakure’s rotation mechanic is necessary since the avatar would hit invisible walls if they could move in a direction they can’t see: 4D Toys does not have this problem since there is no physical avatar. Aside from the fact that both Miegakure and 4D Toys are 4D, the experience of playing each is completely different and complementary!

Final words

Anyway! It’s a thing. You can get more info about it at 4dtoys.com.

It is out now for iOS and Steam (both VR (Vive) and Mouse/Keyboard).

I am excited to release something, anything (!) and see how it goes and learn from the process. While I plan to add things to it when I feel like it, my focus is on Miegakure’s development. Please enjoy!