# SuperColliders in Unity

I was fooling around with collision a few weeks ago so I thought I'd write about it.

## SAT

The Separating Axes Theorem is a simple theorem concerning the collision of convex polyhedra. Basically, you take two polyhedra and create an axis perpendicular to every face of both polyhedra. For two cubes you would have 12 axes, one perpendicular to each face of both cubes. However in the case of a single cube, you can see that there are really only 3 unique axes, as the other 3 are duplicate. That is a very useful optimization...

Once you have all the axes, iterate over each axis and project both polyhedra onto the axis. The two polyhedra intersect if and only if the projections overlap for each axis. What's great about this is that if you have been summing the vector overlaps, you end up with a resolution vector, i.e. a vector that will push the objects apart!

The algorithm is fairly straightforward and it's also fairly cheap, as the full number of axis projections only need to be computed for intersecting polyhedra. For every other polyhedra, the theorem will let us exit as soon as there is an axis found with no overlapping projections.

## Why?

Unity comes bundled with a powerful physics engine-- so why would you ever use this technique? PhysX is great, but it's also overkill for many applications. If you just need collisions, not resolutions, then SAT may be cheaper. This is the case much of the time, like when you fire a weapon and when it hits something you want it to explode. There's no collision resolution needed, just the point of impact.

For my particular application, I had thousands of cubes and projectiles firing through them. If I had a Collider running on every cube, I would drain the planet of all natural resources. Instead, I partitioned the space into a hash, then did narrow phase collision detection with SAT. I was able to scale up to 50k cubes at a solid 60 fps with dozens of projectiles flying through them.

## Where?

I have extracted a simple demo and stuck it on GitHub.

Hit play, then move the objects around in the scene view. Turn on gizmos to see the axis projections.

It may be difficult to tell without playing around with it but each axis is drawn from the same origin. The light green axes are orthogonal to the faces of the small cube and the light red axes are those of the large cube. The solid green line segments are the projections of the small cube onto each of the axes.

When the two objects intersect, they both turn red, and as you can see from the screenshots, scale and rotation are both easily accounted for.

## Further Thoughts

There is obviously a lot of room for improvement. While I created an interface that will work for any convex polygon, the more useful strategy is tooling that allows you to create convex collision shapes. For instance, creating a set of collision shapes from any mesh, or more wrappers for other primitives.

The interface also has a few shortcomings of its own. I would like to be able to use this same technique for "roundy" shapes, like a circle. SAT can be used for these, but the axes need to be created dynamically to point at the center of the circle. You will see what I'm talking about if you take a look at the article I linked to at the beginning.

Maybe my next iteration will include some of these generalizations.

# Ninject and Unity

## The Background

I have searched high and low for a good dependency injection solution that works well with Unity, even when AOT'd. Unfortunately, even my most brilliantly worded Google queries have rendered fruitless results. I'm a little bit ashamed to admit this, but I even tried 'Binging' it.

A host of full blown, .NET DI frameworks won't compile against .NET 2.0 and the remaining libraries usually JIT, meaning they won't work when compiled to crummy old, JITless iOS. What's more, it seems that no one in Unity land has figured out how to use MonoBehaviours in conjunction with dependency injection.

## NinjectSettings

When configuring Ninject, there's a simple flag that controls how the injection mechanism works. Simply tell Ninject to use reflection based injection, rather than JIT.

_kernel = new StandardKernel( new NinjectSettings { UseReflectionBasedInjection = true, LoadExtensions = false }, new CoreModule());

The LoadExtensions setting is also crucial, as it seems that the way Ninject loads in extensions is also illegal.

## Working With MonoBehaviours

I'm not going to go over how to use Ninject, but I will go over my solution for using injection in tandem with GameObjects and Monobehaviours. There are two real possibilities: either you want to inject into a MonoBehaviour, or you want to inject a MonoBehaviour into something else. As a solution to the first, I created a simple class called InjectableMonoBehaviour and call inject from Awake: the earliest possible time I have control after MonoBehaviour construction.

protected virtual void Awake() { Main.InjectScript(this); }

In Main.cs, I'm doing something equally non-fancy:

public static void InjectScript(MonoBehaviour script) { if (null == _main) { GameObject main = GameObject.FindGameObjectWithTag("MainCamera"); _main = main.GetComponent(); }   _main._kernel.Inject(script); }

With InjectableMonoBehavior, I can do incredible things. Check out this MonoBehaviour:

public class Touchable : InjectableMonoBehaviour { [SerializeField] private Bounds _bounds;   [Inject] public InputController InputController { get; set; }   // elided }

Now my instance of Touchable magically has a reference to an InputController. Brilliant.

## HierarchyResolver

I've covered injecting into MonoBehaviours, so now I'll cover the more tricksy, injecting MonoBehaviours into other objects.

HierarchyResolver<T> is a subclass of Provider<T>, which is essentially a factory class provided by Ninject. Overriding Provider<T> allows you to specify a specific implementation for the injection of a particular type. This allows me to do a few cool things.

With HierarchyResolver, you can place a MonoBehaviour in the scene, and inject that specific instance through Ninject's usual injection mechanisms. For instance, say I place a CameraController on the scene's main camera. If I want to inject that via Ninject, I just have to configure a HierarchyResolver<CameraController> in whatever module you wish:

Bind().ToProvider(new HierarchyResolver("MainCamera"));

This is binding a Provider<CameraController> to the Ninject module. Additionally, HierarchyResolver can take a tag as a constructor argument. The tag is where a recursive search for the dependency is started. I can leave off the tag if I want to, but using tags will always be more straightforward and performant. In this case, I've tagged the scene's camera with the "MainCamera" tag, so the resolver finds the dependency immediately.

## InjectFromHierarchy

I've done one more really cool thing, I think.

The above method of injecting MonoBehaviours into other objects is very useful, but has some shortcomings. Most notably, this method can only resolve a single instance of an object. What if you want to get a little fancier?

I've created the attribute InjectFromHierarchy to remedy this.

InjectFromHierarchy extends Ninject's InjectAttribute, but provides a tag and a query string.

[InjectFromHierarchy("HUD", "Readout.Star1")] public Star LeftStar { get; set; }   [InjectFromHierarchy("HUD", "Readout.Star2")] public Star RightStar { get; set; }

In this example, I have a GameObject tagged "HUD". Somewhere down in the children (at any level), there is a GameObject named "Readout" with two Stars on it: "Star1" and "Star2". This will grab references to both of those objects and inject them into this class.

COOL.

What's really cool is that the query string you use is not limited by the conventions of Unity's Transform::Find. In Unity's method, you specify direct children with a period. So "HUD.Readout.Star" represents a direct parent-child relationship, HUD->Readout->Star. With this query string, the periods are recursive. So the same query means HUD->...->Readout->...->Star.

I would like to update this in the future to be more similar to boX's scene graph query language, but haven't had the time as of yet. Also I need to blog about boX sometime...

Get it on GitHub!

# Interview Question: Which Side of a Square?

Q: Given a square and a point outside of the square, how do I quickly determine which "quadrant", (top, bottom, left, or right) the point is in?

It's helpful to draw a picture:

Most people probably jump to trig, which is alright-- but then press them that trig functions are not cheap. How might you get at the information more efficiently? Everyone always jumps to trig lookup tables. Boo. Those are boring. There's a much simpler way!

Draw a line from the point in question to the center of the square.

See it yet? You don't need trig, you just need arithmetic!

Remember what slope is? It's a measure of how slanted a line is. You can find it easily with arithmetic: $m=\frac{y_2-y_1}{x_2-x_1}$. If you look closely at my picture, you can see exactly how this can give us the answer. We know that if $-1, the point is either on the right or the left of the square. If $P$ has a greater $x$, then $P$ is on the right. Using this method we can very quickly determine which side of the square the point is.

Another great thing about this question, is that you can easily extend it. Once you get here, ask how the method can be extended to any rectangle!

# Of Wisdom Teeth and Acceleration

There comes a time in every man's life when he remembers he has a job and goes and buys an RC car. That time for me came a couple of weeks ago and man is this thing fun. I've been tearing up the local middle school dirt track. This past weekend, however, whilst lying around doped up from wisdom teeth removal, I decided to do my first mod.

I was walking through a RadioShack looking for cool stuff (they used to sell cool stuff), and I came across a Mesmic 2125 Dual Axis Accelerometer (you should read how this thing works, it's actually pretty fascinating). I thought, why not slap this puppy on my RC car so I can track acceleration?

First I wired it up to my Netduino (which rocks by the way). Turns out I actually understood the diagram.

My workbench may also be our kitchen table...

Anyway, I've also got a switch on there for controlling the 9v power supply. This was surprisingly easy. The surprisingly tricky part, was actually the software (surprising because I write software for a living).

I don't know how much Arduino-ing you've done, but my Netduino has a bunch of analog inputs that are easy enough to read from and you get a value from 0 to 1023. The tricky part; however, is that the output of the accelerometer is not a single value of the current acceleration, it's a waveform. I guess this is basic stuff for people that actually know more about electricity than V=IR, but the accelerometer uses something called pulse width modulation.

Essentially, the output from the accelerometer is a square wave, and the length of the high end of the square wave is the value I can derive the acceleration from. A regular Arduino has a method called pulseIn that measures the high or low end of the PWM wave, but my Netduino, for some reason, does not. After a few minutes of googling, I found a clever solution using interrupts. That, combined with my weak understanding of the accelerometer documentation yielded the following AccelerometerPulseInput class:

using System; using Microsoft.SPOT; using Microsoft.SPOT.Hardware;   namespace TheGoldenMule.Arduino.Telemetry { public class AccelerometerPulseInput { private readonly InterruptPort _port; private DateTime _time;   public float PulseWidth { get; private set; }   public AccelerometerPulseInput(Cpu.Pin pin) { _port = new InterruptPort(pin, false, Port.ResistorMode.Disabled, Port.InterruptMode.InterruptEdgeBoth); _port.OnInterrupt += new NativeEventHandler(OnInterrupt); }   private void OnInterrupt(uint data1, uint state, DateTime time) { if (0 == state) { // end of pulse PulseWidth = (float)((((TimeSpan)(time - _time)).Ticks / 10000.0) - 5); } else { // start of pulse _time = time; } } } }

What's going on?

Well using an InterruptPort, I actually get a C# event when a pin switches from high to low or from low to high. No, I don't properly grasp what incredible things allow C# to receive hardware interrupts. Anyway, since I'm looking for the high end, I start a timer when the wave goes high, and end it when it goes low. Then I have to divide and subtract as per the accelerometer documentation. That's my daggum pulse width (actually, it's the gs of acceleration after I divide and subtract).

## The Less Interesting Parts

Once I have the accelerometer values, I write them to an SD card. I wrote a class that just buffers up a few and writes them when the buffer is at some predefined maximum length. That's fairly uninteresting, but is included in the source on GitHub.

I also wrote a quick AIR app (seriously, with AIR it took 10 minutes) that would plot the data from the SD card. This is also on GitHub, but I'm not going to discuss it here...

## The Super Interesting Part

I rubber banded my creation to the battery cover and took it for a test run.

Then brought over the logs from the SD card. Behold!

COOL HUH!?!!???!!!!

I'm actually really surprised that it all worked. But here are real data points. The y-axis measures acceleration in gs. The x-axis is time. It's not seconds or milliseconds, it's kinda arbitrary at the moment, but it's time nonetheless. The blue is acceleration along the x-axis, and the red is acceleration along the y-axis.

Take a look on GitHub.

# Python on the Bus: Particles

On my way to work today, I wrote a "particle engine" in Python on my iPhone. Particle engine is a fairly generous term (it's 90 lines) but hey it's plugged in to the accelerometer!

I used the Pythonista particle demo as an example but I didn't borrow its implementation as you'll see. I use a simple ring buffer for particles and emit using a simple physics model where the accelerometer value is the force of gravity (F=ma anyone?). Take a peek-- a full xcode project is here:

https://github.com/thegoldenmule/PythonOnTheBus/tree/master/Particles

AWESOME screenshot:

# Just a Thought: Virtual and Final as Contracts

Virtual. It's a language feature that I've decided I have understood incorrectly for awhile-- but it's not completely my fault...

See, a large part of my professional career has been in Java Land where the virtual mechanism is a quiet little assumption sitting off by itself in the corner. All methods are virtual by default and so you don't have an opportunity to question the why or the how of it, you just use it: on purpose or, more likely, completely by accident. In reality, Java has switched its way of thinking on you, so where once you had virtual in C++, you now have an "antivirtual" keyword, final.

In C#, language designers took the "original" approach. C#, like C++, assumes final unless the virtual keyword is used explicitly. It's actually a bit puzzling to me now, that Java takes the approach it does, because not only is this potentially a performance concern (there's extra indirection with virtual method calls), I think there's also a contractual one.

If you write any system in these languages, that system's contract with the outside world is given in terms of members on implementations and interfaces (the capital 'I' Interfaces of Java + C#). There are other constructs here and there, like Java's checked exceptions, or C#'s event delegates-- and all of these form a compiler enforced, or visible, contract. But there are also less visible portions of the contract. In AS3, for instance, the platform designers chose poorly in that AS3 events are not well supported by the language or the compiler, but they are used heavily in the core API. Thus, a large part of the API is actually invisible to compilation (but that's a rant for another day).

What I haven't given much thought to, however, is that the virtual keyword is actually part of that contract too, somewhere between visible and invisible.

There is a huge difference here in terms of what contract will naturally surface for a system of any size, where multiple engineers use their best judgement on how to engineer software that is "open for extension but closed to modification". So which way should it be?

Well for whatever my opinion is worth, I think that virtual is the more powerful of the two, particularly when thinking about that visible contract.

Virtual makes you provide precise points of contact with code that isn't yours, i.e. it makes you think about where your class should be extended. Final, on the other hand, encourages you to restrict access to code that is yours, i.e. it makes you think about how to restrict modification.

Just a thought.

# Quick Post: Repeat

public static void Repeat(this int value, Action callback) { for (int i = 0; i < value; i++) { callback(); } }   ...   10.Repeat(DoStuff);   ...   Random.Range(10, 20).Repeat(CreateDoodad);

Only the finest material makes it to thegoldenmule's Reading Roundup series. This time, I even included a video for you folks that can't read!

Predicting the Future, by Alan Kay

http://www.ecotopia.com/webpress/futures.htm

This is the one where Kay famously says, "the best way to predict the future is to invent it." And it's brilliant. I wish I had read it ten years ago. He talks about the nature of idea and design and how it's all rolled up into programming-- just writing this short blurb is making me want to go back and read it again...

Everybody Thinks About Garbage Collection the Wrong Way, by Raymond Chen

http://blogs.msdn.com/b/oldnewthing/archive/2010/08/09/10047586.aspx

You may know all about multi-phase, multi-generational garbage collectors-- but chances are you haven't thought about GC in quite this way. I've posted an article from this guy before, and if you read it you probably discovered you had an incorrect understanding of the stack and the heap, value types and reference types. Well this article will challenge your GC knowledge as well.

Why Mobile Web Apps Are Slow, by Drew Crawford

http://sealedabstract.com/rants/why-mobile-web-apps-are-slow/

Yes, we all know JavaScript is slower than native, so why am I posting another article about it? For two reasons: firstly, this guy empirically proves that JS is too slow for real apps and will always be too slow. There's really no hope here. JavaScript will not get faster, sorry friends. Secondly, much of the article is about the nature of compilers and technology, not specifically JavaScript or C++ or anything in between. It's a long, long article, but it's golden.

The Future of Programming, by Bret Victor

http://worrydream.com/dbx/

I've saved the best for last. Yes, my friends: pull up a chair, dim the lights, give thirty minutes to one of the best lectures I've ever seen. Bret will tear your world down and leave you with only a faint hope that it's not quite too late to rethink everything you've ever known about programming. Brilliant, brilliant, brilliant.

# More Memoization

I had to cache the results a couple methods recently, and only after I had done it a few times, I realized I should just write a memoization extension for System.Func.

public static Func<T, TResult> Memoize<T, TResult>(this Func<T, TResult> func) { Dictionary<T, TResult> dict = new Dictionary<T, TResult>();   return input => { if (!dict.ContainsKey(input)) { dict[input] = func(input); }   return dict[input]; }; }

With this handy extension, I'm free to have fun with memoizing arbitrary Funcs.

Func<int, int> fib = n => { int a = 0; int b = 1;   for (int i = 0; i < n; i++) { int temp = a; a = b; b = temp + b; } return a; };   Func<int, int> memoizedFib = fib.Memoize();`

Loyal followers! I'm not dead! In fact I've been working away on a few cool projects, but I'm not quite ready to divulge. Anyway, I thought I would post about a few different resources I've been reading through lately:

A Conversation with Anders Hejlsberg

You have to read every word. Seriously, stop reading this stupid blog and click that link. This is an incredible eight part interview with the creator of C# (and now, TypeScript). In this interview, Anders gives his vision of C#: what it is, why it exists, and why certain design choices were made.

# The Effective Engineer's Handbook

This article is another incredible read. I'm not sure how, but Akhamechet distills down years of engineering experience into a short article on what makes a good engineer. This is actually a pretty challenging read-- you might discover you're not so hot.

# The Nature of Lisp

Another great article by Akhamechet. It's old, but I rather enjoyed it. He attempts to explain Lisp by starting with XML and the popular Java build tool, Ant. From there, Akhamechet describes with clarity the problems that Lisp attempts to solve. It's a fascinating read, but I admit, I haven't yet written any Lisp.

# How to Write Portable WebGL

I'm not sure who Florian Boesch is (or how to pronounce his name), but he's got an excellent write-up on many of the obscurities of WebGL. Give it a read!

# JavaScript Patterns

I know, I know, more JS, right? As much as I want to hate it, it's pretty dang fun. This website describes in detail many of the more useful JavaScript patterns. I guarantee you wouldn't have thought of half of them.