Kenton's Programming Blog

Building a Collision Engine Part 3: 3D GJK Collision Detection

Now that I've conquered 2D collision detection and intersection calculation, it's time to move onto 3D. Thankfully, GJK is relatively easy to extend into 3D once we have the base framework that we developed before.

Building a Collision Engine Part 2: 2D Penetration Vectors

In my last post, I discussed how to determine if any two convex shapes in two dimensions overlap. The result of this calculation is a boolean state—either the two are colliding or they aren't. This is great for things such as triggers, but if you want to use the collision engine for any type of physics calculations, you'll need at least one more crucial piece of information: the penetration vector. This post discusses how to calculate the penetration vector using the EPA algorithm.

Building a Collision Engine Part 1: 2D GJK Collision Detection

I've previously written about using the Minkowski Difference to detect collisions of 2D AABBs, but I now want to expand this into creating a fully fleshed out and flexible collision engine for my own purposes. The engine will detect collisions using the GJK method, and calculate intersections using the EPA method. This post details how 2D GJK works, which will serve as a basis for getting the rest of the engine up and running.

VR UX Case Study: Tilt Brush

My day job consists of creating virtual and augmented reality applications for teaching and learning at my local University. In doing this, we run into far more inexperienced users than traditional VR games do. Most of the people using our tools and applications have never experienced virtual reality first hand. Ultimately, this means that a significant amount of our target audience has based their entire digital experience expectations on the interactions they've grown accustomed to on their phones, tablets, and workstations—namely 2D interactions on a 2D screen with 2D objects. Overcoming the tendency to think of and interact with digital spaces as two-dimensional rather than three-dimensional is VR's great power, however it comes with a cost—upending 30 years of 2D zeitgeist is no easy task.

Getting Started With Haxe Macros

Like has been said many times before, Haxe macros are incredibly powerful. They don't always have the best documentation however, and I find a lot of people forgo their use entirely (instead doing things such as creating nodejs scripts to copy files around for building). Hopefully I can help shed some light on how to build your own macros for those who are new to the language, or macros in general. I'll cover three macros I use on a regular basis, one each of the three types listed in the manual: an initialization macro for copying files to the build folder; a build macro for providing easy auto-completion of asset filenames (a la HaxeFlixel's AssetPaths); and an expression macro for grabbing the build date as a Date object.

Dynamic Blender Properties

As part of my most recent adventures in game engine programming, I came across a small problem—I needed a way to edit levels (both their geometry, and the entities within the level and their associated components). Writing an editor to do this is a rather daunting task. Thankfully, Blender is a free, open-source 3D application that is 'easily' extended (well, easy-ish). So, instead of writing my own editor, I can write a Blender addon to make it do what I need it to. First up in that, was presenting an interface for editing which components an object has, and setting the values of each components' attributes. I found this to be more difficult that I expected, thanks to the way Blender handles and presents data. I will show you here how I got things working, as there doesn't seem to be documentation on this and I had to wade through a lot of half-expired forum posts to get things working.

Quaternions as Four-Dimensional Complex Numbers

Although I have a pretty solid background in math (especially vectors, matrices, and even tensors), I've always somewhat struggled with quaternions. Most sources focus on quaternions as some tool for performing rotations in three-dimensions while avoiding gimbal lock. Which is true, they are/ that, but they're also more. After reading several articles about quaternions over the past several days, quaternions finally clicked and made sense! I'll try to share that insight with you here, though be warned that my description may be just as confusing (if not more so) than anywhere else.

Creating a Code Profiler in Haxe Using Macros

Haxe macros are said by many to be “black magic”, and in some ways they are—macros in Haxe are actual Haxe code (rather than macros in C/C++ for example, which are just fancy pre-processor directives). Macros are undoubtedly the most advanced feature of Haxe and probably the hardest to grasp, however I think a major reason for that is a lack of really solid documentation on the subject. To me, the Haxe docs regarding macros are somewhat obfuscated and leave something to be desired, and unfortunately there’s not a lot of other resources online. This is what led me to embark on my own journey of learning Haxe macros, and hopefully starting to shed a little more light on their mystery.

A Unity 4.6 UI Shader to Ignore Depth Testing

I’ve started using Unity again for some 3D development with Google Cardboard and have been using the new Unity 4.6 UI (which I think is great by the way). Specifically, in order to get UIs rendered for the user in the 3D environment, I needed to place text on a canvas set to World Space (parenting the canvas to the camera, so that it tracks with the user’s head motion). This places the UI in a physical space, which works well for the 3D view but doesn’t work well for a HUD where you need it to always be displayed over everything.

A Platform Agnostic Thread Pool for Haxe / OpenFL

With modern hardware utilizing multiple cores, it can be highly advantageous to do as much parallel processing as possible. I think the most elegant way of doing this is to use thread pools which allocate tasks to a limited number of threads. Unfortunately, multi-threading support isn’t fully implemented in Haxe—but it is on the neko and cpp targets, so I wrote a simple thread pool to take advantage of multi-threading on those platforms!

AutoTileGen Rearranger

I somewhat recently came across AutoTileGen by Pixelatto—a tool for rapidly creating “blob pattern” tilesets from just three input images. It seems like a pretty good tool, at least for a quick rough-in of tiles. It just has one major flaw—the tilesheet that it outputs is all mangled.

Swept AABB Collision Detection Using the Minkowski Difference

Continuing on from yesterday’s post where I explored detecting discrete collisions using Minkowski differences, today I’m going to talk about detecting continuous collisions using Minkowski differences (again, focusing solely on axis-aligned bounding boxes). Continuous collision detection is essential in any game where you have fast-moving objects and/or low frame rates. It adds slightly more complexity to the discrete collision detection algorithm, but the advantages far outweigh the costs in this case!

Simple AABB Collision Detection Using the Minkowski Difference

Since I’ve started on an adventure to start creating my games with Haxe and OpenFL, I found myself in need of some collision detection. I don’t really need anything as fancy or extensive as Nape, and although the HxCollision library is a pretty solid Separating Axis Theorem implementation, it doesn’t deal with swept-collisions, which is a bit of an issue for games (without swept collisions, any lag spikes can easily cause objects to pass right through objects!).

Better Beamer Themes

I love LaTeX for typesetting all my documents. A lot of people don’t understand why, but that’s a discussion for another time. One thing I’ve always been hesitant to use LaTeX for is presentations - the main LaTeX package for making presentations is Beamer, and although it is extremely functional, I am firmly of the opinion that all the default themes are butt ugly and there are barely any other themes out there. Thankfully, Beamer themes are very easy to create from scratch!

Writing an Editor Extension to Customize Mesh Colours in Unity

I'm an engineer and a programmer, not an artist. This sometimes becomes an issue for me when I work on games as while I can make the game technically sound, the art is often downright horrible, or I spend way more time on it than I have any right to. I'm currently working on a long-term, back-burner type game project to keep me busy and distracted when I occasionally need a break from real life. Programming-wise, I'm fine, but what's a game without art? Well, aside from Dwarf Fortress and most Roguelikes out there, it's not much. Fortunately, I recently stumbled across (what I think) is a great art style - geometric assets, as shown below

Simple Bézier Curves in Matlab

I've always been curious about how [Bézier] cubic splines are generated and I how I can use them in various projects (game development probably being the most immediately obvious). If you don't know what I'm talking about, Wikipedia has a decent if somewhat tedious description. After digging through the math, I came up with these results which I'll share for the simplicity of it all (they really are simpler than I ever though). I found most sources started at the beginning and gave huge mathematical backgrounds, which although are nice, are typically just not what I was looking for. What I was looking for (and what is presented here) is just the end result - given a set of input weights, how do I calculate the actual spline?

Making A Custom Teensy3 HID Joystick

I recently got married and for our wedding we decided we wanted to include some arcade games for a more unique, personal, and fun wedding experience. Me being the overly-ambitious type that I am decided it would be even more spectacular to create our own wedding arcade ("Wedcade" for short)! These actually turned out pretty decently in the end, and I'll try to write up a post or two about them (as well as the arcade cabinets!) later, but for now I want to talk about using the Teensy3 as a joystick (namely using Teensyduino).

Super Mario World Physics

Arguably one of the greatest video game series of all time, I spent countless hours playing these games as a kid. One thing I always particularly loved about the games is that the kinematics / physics of Mario's motion were just so.. fun! Not necessarily that they felt real, but when you ran, you ran fast. When you jumped, you jumped high, etc. I think this is a problem that I have with numerous other platforming games.. yea, sure, the gameplay can be fun, but moving around just seems so... boring in comparison to Mario.

Auto-Detecting Certain Methods in Java

Although I still have reservations about using Java for publishing large projects (I find these inevitably become slow and clunky due to the JVM), Java is great from a programming standpoint. One thing I especially love about Java is the ability to do run-time "reflections" which allow you to hook into all the loaded classes at run time and do all kinds of crazy things. Combine this with custom Java annotations, and you get a very easy way to write a scriptable interface for a program for example.

Solving Equations Using the Newton-Raphson Method

Computers are great, but as it turns out - they're not always the smartest of folks. However, they are great at doing simple math! Today, I'll show you how to exploit these silicon monsters to do something that sometimes humans even fail at: solving a simple non-linear equation.

Solving Systems of Partial Differential Equations

Systems of partial differential equations crop up all the time in engineering, especially when examining real-world complicated problems that vary in time (such as a ballistic trajectory with drag forces non-negligable), or in various process control systems (ex: relating flow conditions in systems of tanks with the height in those tanks).