I had a great time this week, having been given the opportunity to present a talk at IGDA – Ann Arbor in Ypsilanti, Michigan this month. I’ve been attending their meetups for over a year, and they consistently get a great turnout and great discussions. This time, group was a good size, the audience seemed interested, and I didn’t mumble as much as I tend to. Of course, the talk was about “3D Cel Animation.”

But with many developers and programmers in the room, they brought up some suggestions to optimize how I check which ‘perspective’ of a character should be shown at a given frame. A common suggestion was to use “dot product” at a low-level instead of relying on “Physics.Raycast.” Even years ago, this had been suggested to me. I had fears about its’ efficiency, but after a few one-on-one discussions, I agreed it might turn out to be more efficient, and it wouldn’t be hard to implement.

I felt like such a fool. For 5 years, I’ve preached the brilliance and simplicity of my design! Was an alternate solution so obvious, and really better?

So I gave it a try. And the results surprised me.

While not well organized or well written, there are a few blog articles (and videos) on this website that already explain how I USED to implement “3D Cel Animation,” using “Physics.RaycastAll” in Unity3D. I like simple solutions, and I tend to stop when I find something that works. I like solutions that seem so easy, it’s strange we hadn’t been using it this whole time. That’s what “RaycastAll” was for me. If child objects were always in the correct orientation relative to the character, one could cast a straight line from the camera, and the plane closest to the character hit would be the right plane to render. Easy, intuitive, and scalable.

Well, not quite scalable. I discovered 2 years ago that having over 100 objects like this in the world, requiring “RaycastAll” to be called over 100 times per frame, would cause serious performance problems. The solution? I didn’t need to pass through EVERY object. Instead, draw a line in the opposite direction, and I could use the first object hit. “Raycast” is much more optimal than “RaycastAll.” There were some issues due to my character designs using overlapping elements, but otherwise, this solved my problem.

But why use “Physics.Raycast” at all? Unity3D themselves say to avoid that where possible, as it’s an expensive operation. So what would I do if I were to directly use “dot product” instead?

I was pretty good at “Linear Algebra I,” but I took that class about 8 years ago, so I had forgotten most of the details. “Dot product” is a helpful way to calculate if 2 vectors are perpendicular to each other or not. If they are perpendicular, the dot product formula should return 0. If they are linear and facing the same direction, it returns 1. If facing opposite directions, -1. In Unity3D (and C#), there’s already a built-in “dot product” formula in the Vector3 object-type, and already “forward” vectors for every object in the scene. I could iterate through every child object of a “cel object” and choose which plane should be made visible, based on which dot product was closest to 1. Easy! And I don’t think I’ve seen other developers parenting planes to an object to help guess the orientation of a character, so even more advanced linear algebra was probably essential for early games like “Wolfenstein 3D” or “Doom.”

Years ago, I had doubts, most of which were unfounded. I used to calculate dot-product in 2 dimensions, does it still work for 3D? Of course it does. Isn’t it hard to program linear algebra? The formula isn’t that complicated, and a function already exists, so it takes even less code than what I used before! Isn’t iterating through dozens of perspective-planes per character per frame more expensive? One programmer assured me the physics engines in most games iterate through ALL objects in a scene to find collisions, so this was likely much cheaper than a Raycast.

I put it to the test. I downloaded my old GitHub template of a “3D Cel Animation” object. I replaced the “mesh colliders” on each plane with “box colliders” for efficiency. I set 200 of these in the space. And I prepared 3 different functions to switch between: to directly test “Physics.RaycastAll,” “Physics.Raycast,” and “Vector3.Dot.”

I tested them all, making it easy to switch between them. And which was more efficient? To be certain, I tested on multiple computers, too. I was surprised at what I saw. For one thing: I didn’t see as massive a boost as I saw in my original article between “Raycast” and “RaycastAll,” just a boost similar to the “total function CPU usage” from that time. And while “Vector3.Dot” was better than “Physics.RaycastAll,” it turned out “Physics.Raycast” was the best of all of them.

Maybe we take Unity’s physics engine for granted, and don’t give it enough credit. I still remember how impressed I was when I saw how smooth 3D gameplay was with a simple Unity game almost a decade ago, much faster than any other game frameworks I was trying. We assume a physics engine must be iterating through every object for every frame of gameplay, right? If you add too many colliders in a scene, their existence alone would correspond to the drop in frame rate.

But it’s likely Unity is applying other optimizations behind the scenes. What if it was keeping a sorted list (or matrix) of every object, based on their distance to each other? “Physics.Raycast” allows you to set the maximum length of the ray, and their own website mentions that its’ performance is “influenced by the ray’s length.” That would mean that even “RaycastAll” could be smart enough not to check every single object, but only those that could possibly be relevant based on how close they are. And even here on my blog, I suggested a method I hadn’t seen elsewhere to easily check if certain objects are “technically” in between two 3D positions: if “Vector3.Distance” is a quick calculation (and it should be, knowing the simple formula to find it), the physics engine could remove even more suspects from it’s “Raycast” logic. And of course, “Raycast” can quit as soon it proves it hit one object, while both “RaycastAll” and “Dot Product” have to run a loop until the end. I don’t know if any part of it is running on the GPU either, despite listing its’ hit in the CPU: it is said to be based on Nvidia’s PHYSX, after all.

The entire physics engine inside Unity is kept well hidden, and there isn’t much information out there even theorizing how it works. I’m happy we had a chance to discuss it here: Unity3D, hire me yesterday!

This doesn’t mean “Dot Product” is entirely disqualified, however. My example had the camera pretty close to its subjects, so a real game (like my upcoming “True King”) might have different real-world effects. In fact, being far away from multiple characters close to each other could explain why my tests in the past made “RaycastAll” look so inefficient. For this benchmark, I tested with the largest detail of “cel objects” I’ve ever used: 114 planes, instead of 48, like I had used in the past. I AM using more than 48 for “True King,” but maybe this test was too extreme. And if using “Dot Product,” colliders on the planes is no longer necessary. We wouldn’t need hundreds of intersecting colliders, moving as a character is animated, something that has caused some performance hits in the physics engine overall, despite my games being fairly simple as far as movement is concerned. There are definitely ways to use the low-level design of the function to find other optimizations: if I could iterate through only 1/2 the planes at each frame, it could be at least as good as “Physics.Raycast,” and that type of trick I can split across multiple game frames, something that would be really difficult with any of Unity’s Physics functions.

The most important benefit is that “Dot Product” can allow me to specify which objects to check: only the children of a specific object, for example. It’s difficult to prevent “Raycast” from hitting several overlapping objects, even when using layer masks. I had theorized ways to get around that, but “Dot Product” might be the easiest solution to understand. And I do like easy solutions…

I might try this in closer detail in my real applications, after all. But I feel a little better knowing I’m not quite the fool I thought I was, and that my current solution is (generally) the best anyway. Unless my above code is horribly optimized… if anyone has suggestions about improving performance or explaining the results of this test, let me know!

 

Update 1:

After talking again with some other developers, I’ve reconsidered how the “Dot Product” algorithm is written. This may not be the last time I modify this article either, so if anyone does have other ideas, I would love to hear them.

If reviewing the “Dot Product” solution for opportunities to optimize, the first thing that should come to mind is: “why do we need to calculate ‘Dot Product’ 114 times per character?” If just trying to figure out the current rotation… well, consider “Wolfenstein 3D” again. If we know the local “Forward” direction of a character (Unity3D can provide this easily), why not apply “Dot Product” to that single “Forward” vector, instead of with the “Forward” vector of many pre-placed planes? This would mean you need to get “Dot Product” once per character, and not more than that. From that one calculation, we can use ‘if’ statements to determine the right perspective to show.

The above graphic helps illustrate it: if the dot product is almost 1, then the “forward” sprite plane should be visible. If it was -1, then the “back” sprite. If 0… well, a single “dot product” on its own might not tell if it was left or right, but a second calculation would do. And this applies to 3 dimensions too: you would have to do 3 “dot product” calculations and compare 3 different values to understand which plane to show.

And what might the function look like for Unity3D in C#? I didn’t complete the script, but I wrote the starting pseudo-code for it:

This reminds me of the general secret many programmers rely on for fast performance: if it’s necessary to write a thousand “if” statements to avoid dynamic calculations, then do it. Compared to the previous “Dot Product” solution, this would only need to calculate it 3 times per character, potentially reducing CPU time to as low as 3% the usage from the previous “Dot Product” solution, or 6% the “Raycast” option. The drawback is that the resulting function would be REALLY long: I’d write out about 114 “if” statements to finish it.

For organizational purposes, there’s another issue: after knowing the orientation of the character, how do I update the sprite? I could have a 3D array of lists in this one class to set sprite textures in the inspector, but that sounds like a mess. I could keep the existing planes surrounding the character, just removing their colliders, and allowing them to continue maintaining sprite and animation logic for a single perspective… but then I could keep a 3D array of game objects in each character’s class? Also messy. And I shudder to think if I were to change how perspective planes were arranged, or how many there were… I could use nested “for” loops to control the “if” statement values, but what if I don’t use the same amount of planes per axis?

For that matter, if unfolding the planes away from the character, it’s really a 2D matrix, not 3D. Maybe just a 2D array would do… and maybe just 2 “Dot Product” calculations instead of 3?

I don’t think I would try to attempt this anytime soon. The current solution with “Raycast” is so much easier to understand, and for now, runs well on any Intel i-series CPU. But there are definite organizational benefits to using “Dot Product” instead, as many as there are complications. And knowing the potential performance increase… at this level, it could potentially allow “3D Cel Animation” to run on mobile at last. It’s hard to make such updates now to “True King,” another reason to finish the project quickly so I can focus on what comes next.