A physics demonstration of a ball bouncing on a implicit surface. My friend and fellow game developer Terry Cohen was commenting of wanting to write a small openGL app of a ball bouncing on a implicit surface. After a few minutes of discussion I got a bit hooked on the problem, and proceeded to kill quite a number of nights trying to get a decent simulation running.

Unlike some of my other demos there isn't that much that is new here.  But on the whole a toy like this exposes quite a number of fundamental computer graphics/physics problems. I'd like to touch on a couple of them. The first problem is generating the surface,  in this case:
Z = X^2/10.0f  + X/5.0 + .25*cos(Y). I tessellated a grid and plugged (x,y) into equation to get the Z value at each point.
Deciding that I was too lazy to average the vertex normals I took the partial derivate with respect to x and y.
dx =  X/5.0 + 1.0/5.0) and dy = -.25*sin(Y) used them as the gradient vectors in the X direction and Y, i.e .

`Vec3 px = Vec3(1, 0, dx );Vec3 py = Vec3(0, 1, dy );Vec3 Normal = cross(py,px);Normal.normalize(); `

In retrospect I would have probably been faster to just average the per triangle normals than it was to go through the math.

The next challenge was to find the polygon that the ball could potentially hit. Assuming that the ball is a point you can create a ray in the direction of the ball's velocity and ray trace into the surface. There are lots of web references for intercepting a ray and a triangle.

I quickly discovered that I had massive variations in performance. The surface consisted of 5000 polygons and the ray test was doing a linear search through them. (For you real CS people O(n) ). Now for certain N like the left side I was getting 70 fps (70 fps is about as fast as GLUT will go under any circumstances). However on the right side of the grid, where the triangles in question were closer to the 5000th element in the array, fps started hanging out at the 5-10 fps rate. :-(

Implementing an oct tree scheme seemed like the best way to speed up the intersection test, and turned out to be a fairly straightforward piece of code.. Except for: degenerate bounding boxes with zero volume, deciding what to do with polygons that intersected the bounding box edges, I just put any triangle that intersected the box in the leaf of the tree, alternatively I could have sliced them...... the usual.

Eventually ray tracing  against the oct tree, i.e. intersecting the rays with the bounding boxes and eventually using the triangles in the leaf nodes, gave a solidly high frame rate.

The actual physics is a bit ad-hoc.  Involving a check on the velocity impact vector and using the surface normal to calculate the bounce. If no directional collision is occurring a ray cast down is performed. The ball is then pushed out onto the top of the surface and the downward velocity is projected into the plane of the surface below. This allows the ball to roll down the surface.

The two tests I do just approximate the real situation. I think it would actually make more sense to ray test the moving sphere against the surface, that would allow me to only do one ray cast, but it would probably be a more computationally expensive one.

I've modeled the angular velocity by relating it directly to the motion of the ball, which implies no slipping, between the ball and the surface.

I also allow basic user control which can steer the ball on the surface and act against gravity to a degree..
If the user is steering I have a natural frictional force so I discount friction on the ball. However, If user control is off implemented friction based on angular velocity, that should eventually bring the ball to a stop..

Gedalia Pasternak | Gedalia has been playing with computer graphics and computer animation long enough to say "I remember when." He's just finished working on the Asheron's Call 2 engine, and is currently freelancing.