realtimecollisiondetection.net - the blog

It is very easy for programmers to be seduced by pretty tech. Case in point: graph-based shader systems. Unless you’ve been sleeping under a rock, you must have noticed that these systems have become haute couture in the rendering world. Just so we’re clear, what I’m talking about are systems where you can construct shaders in a graphical UI, stringing together Lego-like building blocks of shader code snippets, with connecting lines. Read the rest of this entry »

Anyone who has ever experimented with Conway’s Game of Life or any other cellular automata (CA) know they can be very fun to play with. You can easily lose several hours in e.g. George Maydwell’s awesome Modern CA site; his CA evolution lab is particularly cool. If you like to write your own CA code, there are some good efficiency hints on Tim Tyler’s CA page. (As a side note, Tim also has a good — but NSFW, due to boobie pic — rant on why the entertainment industry should be destroyed.) Read the rest of this entry »

The A* algorithm is perhaps the most ubiquitous algorithm in games but also seemingly one of the more misunderstood algorithms. Not in the sense that people don’t know how to implement it (they do) but in failing to use it properly. Read the rest of this entry »

The “Design Patterns” book is one of the worst programming books ever. Yes, really. I’m 100% dead serious when I say that I think it has set (and will continue to set) the progress of software development back by decades. Why?! Let me offer up a parable; I will call it “The Plank.” Read the rest of this entry »

With the signal-to-noise ratio of the internet at an all-time low, here are some fairly recent graphics-related blog posts from across the world that I think contributed positively to the SNR. Just in case you missed them the first time around. Read the rest of this entry »

That min() and max() are highly related to each other probably doesn’t come as a surprise to many people. After all, we have some pretty obvious identities such as:

min(a,b) = -max(-a,-b)
max(a,b) = -min(-a,-b)

What may not be as immediately apparent is Read the rest of this entry »

We ran into an interesting problem at work the other day, where we had some geometry partitioning code that gave vastly different results on the same tessellated plane, depending on the scale factor that was applied to the plane. That would be fine, of course, if the code was taking size into consideration when partitioning, but this code wasn’t! Read the rest of this entry »

There are many possible collision geometry representations. One representation is the triangle soup: an unordered collection of triangles. The triangle soup is great in the sense it is easy for artists and designers to create, edit, and apply collsion materials to the triangles. A not-so-great property is that the triangle soup does not define a volume, so there is no way to dinstinguish between being inside or outside of the objects it represents — we can only detect collisions with the boundary. It therefore becomes very important to detect tunneling to avoid objects falling through the world. Read the rest of this entry »

Hacker’s Delight (in homage to the excellent book of the same name) is a pretty cool, sporadically-run coding challenge organized by Jim Hejl (previously of EA Tiburon, now Director of Rendering Technology out of EA in Vancouver). Each new HD challenge provides an interesting optimization problem to solve, where you have to consider both choice of algorithm, cache effects, and operation counts. Oh yeah, if it wasn’t clear: fastest implementation wins! Read the rest of this entry »

I sort of implied this in passing in my triangle-triangle tests post, but let’s state it officially: coplanarity (or collinearity) in your inputs will almost always screw you over in one way or another! Here’s another example of what can go wrong: this time performing continuous collision detection between a moving point and a moving triangle. (In case this looks familiar it’s probably because you’ve seen me mention it before in other forums, but hey, self-plagiarization is OK as long as you’re not trying to publish!) Read the rest of this entry »