Oriented Fish and Hairy Balls
I have to admit, I have a tendency to write about abstract nonsense here. But I do so for entirely practical reasons - I don't want to run afoul of my employer by mentioning anything that could be construed as a trade secret. But today I thought I'd mention a small application of topology to computer graphics. The reason I can safely mention it is that I won't be revealing a technique or algorithm. Instead, I want to point out the opposite: a proof that a certain algorithm cannot possibly exist.
From time to time, anyone who works in computer graphics is likely to want to implement a function with this specification:
This kind of function is ubiquitous in graphics and most math libraries geared towards graphics that I have seen have some kind of implementation of this. A typical application is as follows: suppose you're animating shoals of fish. Using a variety of methods its easy to generate nice paths that guide the motion of thousands of fish. For example you could assume that the motion of the fish is approximately described by a divergence-free vector field (so that the fish don't 'pile up' anywhere) and then integrate these fields to give streamlines that the fish can follow. Unfortunately there is a slight catch with this. If you have some 3D geometry representing the fish's shape, knowing the position of the fish isn't enough to specify how it looks. You also need to give its orientation. An obvious choice is to orient the fish so that the line from tail to nose points along the flow. But you still need to be able to describe its orientation around this axis. To do this, we need to complete this orientation vector along the fish to an orthogonal basis ie. find a set of mutually orthogonal unit vectors, e1, e2, and e3 such that e1 points from tail to nose. We can easily define e3 to be e1×e2, so if we had the function f above we could write e2=f(e1).
The function f appears in a multitude of other contexts too. It's useful when orienting 'virtual' cameras. For example the user might want to specify that the camera points at a target and have the graphics system select an orientation with this property.
However, anyone who's met these problems immediately hits an issue. Try writing code to do this for yourself if you haven't already. Chances are you'll end up with a conditional branch in your code, and when you flip from one branch to another you'll see it clearly causing ugly flips in the animation. So the above spec needs to be revised to:
And here's the rub: the Hairy Ball Theorem says there is no such function. So if you're having trouble writing one, it's not because you're not being ingenious enough. It just can't be done! (Though there are lots of other solutions to the animation problems I mention above.) See, topology is useful after all, it can save you wasting your time on impossible tasks.
(Funnily enough though, the best way to see that this is true is using a suitable functor...)
Actually, I think anyone who works in graphics ought to read up on the Hairy Ball Theorem, the Ham Sandwich Theorem and the Borsuk-Ulam theorem as well as learning about the double cover of SO(3) (which I'll write about here in the near future).
That was a public service announcement.
From time to time, anyone who works in computer graphics is likely to want to implement a function with this specification:
Implement a function f:R3→R3 such that for all non-zero x, f(x) is also non-zero and is perpendicular to x.
This kind of function is ubiquitous in graphics and most math libraries geared towards graphics that I have seen have some kind of implementation of this. A typical application is as follows: suppose you're animating shoals of fish. Using a variety of methods its easy to generate nice paths that guide the motion of thousands of fish. For example you could assume that the motion of the fish is approximately described by a divergence-free vector field (so that the fish don't 'pile up' anywhere) and then integrate these fields to give streamlines that the fish can follow. Unfortunately there is a slight catch with this. If you have some 3D geometry representing the fish's shape, knowing the position of the fish isn't enough to specify how it looks. You also need to give its orientation. An obvious choice is to orient the fish so that the line from tail to nose points along the flow. But you still need to be able to describe its orientation around this axis. To do this, we need to complete this orientation vector along the fish to an orthogonal basis ie. find a set of mutually orthogonal unit vectors, e1, e2, and e3 such that e1 points from tail to nose. We can easily define e3 to be e1×e2, so if we had the function f above we could write e2=f(e1).
The function f appears in a multitude of other contexts too. It's useful when orienting 'virtual' cameras. For example the user might want to specify that the camera points at a target and have the graphics system select an orientation with this property.
However, anyone who's met these problems immediately hits an issue. Try writing code to do this for yourself if you haven't already. Chances are you'll end up with a conditional branch in your code, and when you flip from one branch to another you'll see it clearly causing ugly flips in the animation. So the above spec needs to be revised to:
Implement a continuous function f:R3→R3 such that for all non-zero x, f(x) is also non-zero and is perpendicular to x.
And here's the rub: the Hairy Ball Theorem says there is no such function. So if you're having trouble writing one, it's not because you're not being ingenious enough. It just can't be done! (Though there are lots of other solutions to the animation problems I mention above.) See, topology is useful after all, it can save you wasting your time on impossible tasks.
(Funnily enough though, the best way to see that this is true is using a suitable functor...)
Actually, I think anyone who works in graphics ought to read up on the Hairy Ball Theorem, the Ham Sandwich Theorem and the Borsuk-Ulam theorem as well as learning about the double cover of SO(3) (which I'll write about here in the near future).
That was a public service announcement.
Labels: mathematics
posted by sigfpe at Saturday, January 06, 2007
6 Comments:
You have a cool job ! I'd like to be able to use some cool math for my job.
The hairy ball theorem that I know is : every vector field on S^2 has a singularity and it is related to the Euler characteristic of the sphere.
I had not made the connection with the example you give. Interesting ... as always on this blog :-)
Interesting. I thought quaternions could handle this. At least, that's what I always use for interpolation of 3d rotations.
bot builder,
quaternions don't give a solution to this problem, and have some fascinating topological no-go theorems of their own. For example, if you've written a slerp routine you'll know that there are two unit quaternions for each rotation and you have to make a decision about which one to use. This causes discontinuities of its own. But the fact that you have two of these things per rotation relates to the double cover of SO(3) that I briefly mentioned...
bot builder,
It just dawned on me - quaternions provide a solution in 4D. but not 3D. If you identify 4-vectors with quaternions in the obvious way then f(x)=i*x will do. You can adapt this to any even dimension.
Could you solve the oriented fish problem by giving "time" as an argument to the normal generator, making it a function R^4 -> R^3?
panic,
Simply adding time won't solve the problem, but time might come into one possible approach to the animation problems I mention. The idea is to make the function f a function not just of some vector, but the history of the vector. But I've no space for details here...
Post a Comment
<< Home