This is What I Do Instead of Having Normal Person Fun

I've decided to dedicate a blog post to some of the math/programming work I'm doing for MLPOnline. This should also help me remember why I'm still single on Valentine's Day so I can rant about the correct things when I drink myself into a gutter later.  Warning- this post has math. But its in the form of badly drawn Microsoft Paint pictures.  So, lets dig in!

Lets say that you have two objects- a box and a triangle.  You want to make sure the triangle can't stab into the box, especially if the box is made of concrete. The triangle should stay outside our box of concrete, unless our game is set in Alice's Wonderland.

This part comes right after the Caterpillar gets baked

Now, the question is: how do you keep that from happening?  Well, look at anything vaguely box-like in your room right now (books are good for this example).  Look at the corners- the only way for a book to be "inside" of our proverbial box is if one of the corners was inside the box.  There is no way to put the book inside the box without putting at least one corner in.

So, really, we just want to test if any of the corners of the book are inside our box.  In math, we call the corners of things vertices.  With a little imagination- perhaps with the help of Figment if you're a character on a Disney ride- you can see that each object is actually a collection of faces (the front of the book, the back of the book, the spine of the book, etc), and each of these faces each have a set of vertices.

Example: For the front of a book, the vertices would be the front bottom left corner, front bottom right corner, front top right corner and front top left corner.

So, really, the problem is: how do we check to see if one of these vertices is inside a bunch of other vertices?  Your answer is probably something along the lines of, "Um, by looking at it, numbskull".  You're also perfectly right- but computers are very retarded and can't look at objects.  All they see is a bunch of points in space that make up the objects we're talking about.  So, to a computer, our problem looks something like this:

Green dot- inside or outside the box?

Yeah.  The computer has no idea what inside or outside even mean.  If I gave you a sheet of random dots and told you to tell me if one dot was inside the others you'd tell me to lay off the drugs.  Remember how I said before that our objects are actually a collection of faces?  Well, time to use that to our advantage.  Sorta.

You see, there is another way to look at faces- as planes.  Planes are flat surfaces that extend out forever.  They're handy because they divide space in to two parts- the part on the left of the plane and the part on the right of the plane.

These two horribly drawn stick people can't see each other because there is a theoretical mathematic construct in the way.  This happens all the time in real life.

There are a few ways to describe planes, but the easiest to calculate (when we already have a bunch of points in the plane- the vertices that I rambled about before) is to have have a perpendicular arrow that points away from the plane and another point on the plane.  Or more simply- we can describe one of these great space dividers with nothing more than a point and an arrow we can get from a bunch of points.  Perfect!

Now, we finally have enough information to start to figure out our starting problem.  Some other very smart person figured out that a point is inside of a 2 dimensional shape if you could draw an arrow from somewhere outside the shape to the point and the number of intersections it made with the shape's sides was odd.

Thanks, dead smart person!

I need to generalize this to 3 dimensions, because apparently 2D graphics are lame.  Whatever.  So, I drafted up a test cube, picked a point I knew was going to be inside of the box, and picked a point that I knew was going to be outside of the box and made a line.  Then came the very unfortunate task of checking to see if the point intersected with any of the planes of my box.  There is a lot of linear algebra I'm going to ignore.  Unless, there is some demand to hear about it and or need for a sleep aid.

In a nutshell I got this:

I fail art forever. 

Which seems like a great success.  Until you start to look at more complicated shapes.  If one of those box sides was angled- like a ramp- then I would have had two plane intersections, and my algorithm would have mistakenly divided that the point was outside the box.  (Remember, planes extend infinitely out in two dimensions so they can divide 3-D space in two.  They don't have edges like the sides of a box would)

So, I also need to check each plane intersection point to make sure its in the face.  If it isn't, I need to throw it out.  To do that requires even dryer math (woo-hoo trigonometry!), but I have a solution that I think works.  Almost.  There are two problems that I still need to tackle.

1) My point in face check requires some order be imposed on the vertices.  They need to either be in clockwise or counter clockwise order.  I can either ask the developer working on generating our level geometry to impose this order on his stuff, or I can order them myself at the start of all this math mess.  Ordering them shouldn't be hard (which means I should be able to find out how someone else did it on the Internet), but there is a lot of computations happening already.  I'm beginning to get worried that it'll take too long to check this stuff, and that results in lag.  No one likes lag.

2)I've used some meta-knowledge here.  I know that my second point is outside the figure because I drew the figure up.  In our actual game, I my code won't be able to know any of that and will need to pick a secondary point all by itself.  And remember, all the computer knows about is a bunch of points- all this plane crap is done by my code in the middle of it.  The solution to this sucker is to use what smart people call a bounding sphere, which is the smallest sphere that encloses a set of points.

I just have to grab a point on that sphere (actually, I'll grab a point a little ways outside of the sphere, so I can avoid accidentally using a vertex) and I should be set.  The issue is that getting a sphere from the way the data is saved is going to be a pain.  I need to actually get a unique list of points that make up the object (which, when looking at how the data is saved right now is looking to take a lot of computational time) and then generate the sphere

In conclusion: video games are complicated.  Even ones about ponies.