A Fast Sudoku Solver

Everyone has to write a Sudoku solver! A few months back I was in an hotel room at 4 am in the morning when the thermostat inexplicably decided to heat my room to 90 degrees Fahrenheit. That woke me up, and since I had nothing to do for a few hours I decided to write a Sudoku solver (because everyone has to write one). I hadn’t thought about it since then, until I ran across this post on reddit and decided to run the same puzzles through my solver and see how it did.

Thoughts on light culling for clustered shading

A while back I came across the presentation Improved Culling for Tiled and Clustered Shading by Michal Drobot and it’s really clever. It inspired a bunch of thoughts that I’ve been meaning to try out but since it’s now several months later and I still haven’t got around to it, I figured I’d just jot down some notes here instead (in other words: Caution, untested braindumps ahead!). Review First, let’s review the basic idea.

Naming Convention for Matrix Math

There’s a fairly common naming convention for matrix math which makes most of the matrix math used in games as simple as slotting together Legos. This is by far the biggest bang-for-buck coding convention I know of. Ever randomly inverted a matrix or swapped the order of a matrix multiply until things look right? Yeah no, you never have to do that again. This really should be taught in graphics programming 101 because it pretty much eliminates all matrix transform headaches.

Efficient Weighted Sampling

Here’s a really simple and cheap way to do importance sampling that I came across a few months ago (while learning about particle filters, incicentally). It’s simple enough that I have no idea how I went so long without ever knowing about it! In case anyone else is in the same boat - let me walk you through it.

Robust estimation

Least squares optimization is a super useful technique, and indeed I’ve used it twice on this blog before. However, it has a major down side - it’s very susceptible to pollution by outliers. In one of my previous posts using least squares optimization I used a technique called RANSAC to deal with outliers, today I want to talk about a different approach. The issue with least squares First, let’s recap the issue with least squares by working through a simple example.

Doing Garbage Collection Without Requiring Uniform Representation

After some discussion on reddit recently the issue of uniform representation came up, and how it’s seemingly necessary to do GC, and what problems it causes. While I’m 99% sure I didn’t invent any of this, I can’t seem to find it while searching so I’ll just write down a quite note about how to do GC without enfocing uniform representation of objects. Uniform representation So what is uniform representation?

Tracking spheres in images (aka Let's Build a Half-Assed Playstation Move tracker!)

For fun, I decided to write basically a Playstation Move tracker. The idea is that you have some kind of glowing sphere with a known radius, take a picture of it with a camera, and infer where it is in 3D space. I bought these glowy balls since I don’t actually own a Playstation Move controller. I ended up having some issues with my camera (possibly caused by running an internal windows build!

On using 'auto' and 'var'

Programmers love to argue about coding standards, and one of the most contentious points is whether or not it should be allowed to use the equivalen to the “auto” keyword in C++ (in C# it’s called “var”, other language shave similar things). This is a keyword that does simple type propagation and lets you name a value without explicitly giving its type. I don’t actually care all that much about coding standards, but this one bugs me because it seems to me that the main argument against allowing “auto” is a very transparent post-hoc justifications for “It’s unfamiliar to me, therefore bad”.

Using SSE intrinsics to optimize scalar code

Just a quick note on optimizing scalar code using approximate SSE instructions. Now, first off let me just say that it’s rarely useful to micro-optimize scalar code (e.g. implementing Vector3 addition using SSE is probably a net loss, or at least wasted effort). If you really want to go fast, what you need to do is find hotspots which operates on a lot of data in a loop and turning that whole thing into SSE code.

Fixing Texture Seams With Linear Least-Squares

This post is about how use least squares optimization to slightly adjust the texel values in a texture in order to minimize seams across edges in UV-space.