## Optimizing a sphere-triangle intersection test

It’s been quite a while since I posted on the blog (a) at all, and (b) about a topic remotely related to the name of my domain and subsequently my book. Thanks to a gentle nudge from my friend and colleague Pål-Kristian Engstad I’ll try to rectify the situation with this post about how one could go about optimizing a sphere-triangle intersection test, suitable for a SIMD-implementation (such as on the PS3 SPUs). Read the rest of this entry »

## Floating-point tolerances revisited

For several years now I’ve participated in the physics tutorial session at GDC (along with Jim Van Verth, Gino van den Bergen, Erin Catto, Brian ‘Squirrel’ Eiserloh, and Marq Singer). One section I’ve covered in some detail is robustness and within this area I’ve stressed (amongst other things) the importance of distinguishing between absolute and relative tolerances when performing comparisons of floating-point numbers.

I won’t go into details about why you would want to care about how your floating-point numbers are compared. (Detailed information can be found in part in my GDC presentation slides and in much more depth in my book.) Here I will assume you already know why you care, and I will just note that absolute and relative tolerances are tested as Read the rest of this entry »

## Secrets of a scalar triple product identity

In my post about the evilness that is coplanarity I asked to be reminded to blog about the scalar triple product. Read the rest of this entry »

## Crunching your abs

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 »

## Robustly computing the centroid for a point set

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 »

## And an old-school division trick

This is just a short note to give a division trick to go with the multiplication tricks of my previous blog post. Two divisions, r = a / b and s = c / d, can be turned into one division and five multiplies by computing the terms as Read the rest of this entry »

## Old-school multiplication tricks

In a land far far away (meaning some 10-20 years ago) it used to be very important to do all kinds of extreme optimizations to get games and other performance-sensitive code to run at a decent speed. Often, one important optimization was to remove expensive arithmetic operations like multiplications and — heaven forfend — divisions. Anyone who was around then tends to have amassed a lot of “tricks” for this, which these days are really just meaningless trivia occupying valuable brain real-estate. I’m hoping that writing “my” tricks down might help me purge them from memory. Hey, it’s worth a try! Read the rest of this entry »

## Minimum bounding circle (sphere) for a triangle (tetrahedron)

In Chapter 4 of RTCD I talked about, amongst other things, how to compute the minimum bounding sphere for a set of points. The algorithm I described (Welzl’s algorithm, in Section 4.3.5) requires a pair of functions to return the bounding sphere for three as well as four points. As I didn’t cover these primitive functions in the book, I thought I’d here explain how to compute both. Read the rest of this entry »

## Vector expressions as matrices, using outer products

Reading through Peter Shirley’s graphics blog I found an old post asking about what the outer product means operationally and what value it may have in graphics. This is actually a pretty interesting topic, and I thought I’d try to explain what the outer product means to me and the value I see it having. Read the rest of this entry »

## Plücker coordinates considered harmful!

I admit, I have lots of pet peeves; although I like to think of it not as much as having pet peeves but having a heightened sense of what’s right and what’s wrong! Something that gets my spider sense of wrongness tingling is seeing research papers use Plücker coordinates. (Computer graphics and computational geometry papers predominantly, because those are the fields I follow.) Why the sense of wrongness? Because these days, increasingly more people in these fields are grasping for Plücker coordinates to solve problems that would have been both more elegantly and more efficiently solved with simpler, more traditional tools. Let me explain myself. Read the rest of this entry »