## CLANG

Neal Stephenson wants to revolutionize sword fighting video games.
Created by
9,023 backers pledged \$526,125 to help bring this project to life.

## Circumscribed Hyperspheres!

Our animation programmer, Aaron, sent the team this email yesterday and it was too good not to share!   -Subutai

So I've been experimenting with ways to best determine which guard you're in. I started simple... I added a bounding box to our character's sword, and cached off the location of the center of the sword per pose and its angle relative to the player (like the face of a clock - 3 o'clock = left, 6 o'clock = down, etc.).

This forces you to somewhat arbitrarily chose a center point, and the closer you get to that point, the more sensitive things get. This also doesn't account well for poses like Breve and Longa which extend out in front of the player. A second angle in a plane perpendicular to the first (i.e. clock face centered on the arms) can be used to account for animations that extend out in front of the player, but the origin used still gives us problems for the same reasons. Another technique is to stamp out the bounding box for each of the poses, then calculate an error metric to measure the "distance" the player controlled sword is away from each of these.

This works pretty well, and I think I'll use it at least for making sure the sword is generally pointed the correct direction. We can also use this to grade the player on their form, or keep track of their favorite guards, variations or whatever. What I really wanted, however, is to divide the space up nicely for each of the poses. I already had some triangulation code that's being used as part of our parameterized animation calculations, and figured I should be able to put that to use. A Delaunay Triangulation takes a set of points, and tessellates the space nice and evenly avoiding skinny triangles. Here's an example in 2d:

You may remember from high school that you can calculate a circle given three points that lay on its circumference. One property of a Delaunay triangulation is that no other vertex can be inside the circumcircle of a given three vertices. That's how it generates nice triangles. Here's what the Delaunay triangulation of our guard poses looks like in 3d.

Note: in 3d the space is broken up into tetrahedron instead of triangles. A tetrahedron has just four points. More generally, these are called simplexes. A simplex is the simplest container you can create for a given set of dimensions. It always has one more vertex than the number of dimensions. So in 2d, this is a shape with 3 points (or a triangle). In 3d, we require 3+1 points to form a tetrahedron.

Anyway, so far this doesn't really help us much. However, there's something called a Voronoi diagram (or tessellation) which is the dual of a Delaunay triangulation. It's made by taking all the centers of our circumcircles...

... and linking them together.

These diagrams are useful for doing stuff like calculating the closest McDonalds!

For our purposes, we'll want this in 3d for finding the closest guard pose. Unfortunately, I sometimes go a little overboard. The Delaunay triangulation implementation I wrote for calculating parameterized animations is set up to handle any number of dimensions. The technique I used involves projecting the data onto a paraboloid one dimension higher and calculating its convex hull. I only mention this, because unlike other methods, we never explicitly calculate the circumcircles of the vertices. And because my code works in any dimension, instead of just circumcircles or circumspheres, I needed a method to calculate the hypersphere that circumscribes a given simplex for a given dimension. Phew! Turns out this isn't a big deal: you just load the legs of the simplex into a matrix (along with the half squared length), invert it, and the center falls right out! And here you thought you'd never use that simultaneous equation bullshit they taught in ninth grade. Back to the pretty pictures. Here's our Voronoi tessellation in 3d.

I've highlighted the faces that contain the currently selected pose. It's kinda hard to see what's going on without moving the camera around, but hopefully you get the idea. Here's with another pose selected and from a different angle. These are all using the center point of the sword. I'll probably try experiment using the hand position instead, or maybe the tip of the sword, and see what works best.

Anyway, I hope you enjoyed!

Thus endeth today's lesson.

#### Comments

Only backers can post comments. Log In
1. ### John Cruz on December 28, 2012

So . . .

How 'bout an update? It's been about a month and a half. Any news to share?

2. ### David Thompson on November 9, 2012

I'm getting flashbacks to a realtime mocap project I worked on for a Lord of the Rings exhibit a few years ago. We had a more controlled lighting and colour environment, though, so we could afford to do things more simply. Nice work!

3. ### Cameron Usman on November 9, 2012

Looking forward to being able to try hands on the fruit of all this talented labor going into the project.

4. ### ProtonAx on November 9, 2012

Interesting post. How do you decide if the player is not in any of the proper stances, however? Do you do some arbitrary cutoff if your distance metric exceeds a certain threshold? If so, how did you decide on this threshold? Empirically?

5. ### Robert Wallis on November 9, 2012

Now that you can get a list of the closest pose simplexes, you could have an explorer mode that would show 3D arrows of the 4 neighboring poses (because the tetrahedron has 4 sides). That may help players understand the poses through comparison experimentation on their own. The arrows could be quickly drawn by making a line from the current tetrahedron center to the adjacent center, with an arrow head direction vector along the drawn line. But I don't know if that would convey rotation correctly.

6. ### retakrew7 on November 9, 2012

I thoroughly enjoyed this update, nice!

7. ### James McKendrew on November 9, 2012

I really don't need to know about their religion... Oh, circumSCRIBED. Well, that just leaves me with one question. Where IS the nearest McDonald's? (Thanks for the update!)

8. ### JS - Order of the Goat on November 9, 2012

That's really nice post. It's great to see some technical details.

9. ### Daniel Casner on November 9, 2012

Awesome. Keep up the great work and the technical updates.

10. ### John Magee on November 9, 2012

Mind = Blown

11. ### Wilson Bilkovich on November 9, 2012

Nicely explained!

12. ### Bryan Tyler Parker on November 9, 2012

Loved this update, as I come from a computer science background with a heavy focus in its application towards graphics and animation.

Aaron, if you have a blog or something I'd love to follow more posts like these. Keep up the great work!

13. ### Canis Latrans on November 9, 2012

That explanation blew my mind.

14. ### Jan Pospisil on November 9, 2012

Very cool! Nice to see something this "technical" as an update.

15. ### Apotheosis Studios on November 9, 2012

Looking good! Very excited to try it out!