VR Physics And Collision Detection In Hardware?

Alea asks: "Currently, a big chunk of the graphics pipeline, transform and lighting (T&L), is beginning to show up in graphics hardware. It seems likely that some other capabilities, such as collision detection, will follow. This means the main processor can be used to compute more sophisticated physics models for games and VR systems. However, it seems to me that many physical model computations could also be performed in hardware, freeing the processor for more sophisticated AI and conceptual modeling. Does anyone know if there is any work being done on implementing collision detection and simple physical models (e.g. momentum, gravity, friction) in hardware?"

What's the point?

[moderation]

The "hardware implementation" of those is a general-purpose processor. It would take a general purpose processor to compute those ideas, so what's the point? Why not just ask everybody to buy an SMP system and fork() off a seperate process to handle collision dection and physics? Your suggestion is stupid.

Don't know, but here is another idea

[Pilchie]

Why not do some of the Collision detection or physics models in an FPGA to offload it from the main processor? (Assuming you have control over the VR controller of course), then when (if) they do become available in hardware, you just have to modify your driver. This also lets you model some more interesting things that might not ever be in hardware (like aerodynamics, etc).
>~~~~~~~~~~~~~~~~

Flexability vs Efficiency

[rips]

It seems to me that it comes down to that age old tradeoff between efficiency and flexability. You could implement a 'polygon soup' collision detection/response system in hardware but:
a. It would require hardware to hold geometric details for the entire level (ie. lots more memory)
b. It would require a lot of data to be sent back and forth across the bus to correctly pass relevant physics and in-game object collision information.
c. Certain objects that are rendered shouldn't be colided with (for example some particles like smoke, semi-transparent polygon's like vines, etc..)
d. Can't be used in all scenarios such as massive worlds as in these cases certain 'quick outs' are used to quickly discard the possiblity of colliding with areas of the scenery that can't possibly be colliding.

Physics lend themselves a little more to hardware acceleration (particularly with mathematical intergration and other cpu intensive operations) but still require close interaction with the collision detection system.

Consider a ball bouncing off the floor. This requires physics to drop the ball, collision detection to detect the collision of the ball with the floor and response by the physics code to handle the resulting bounce back up again. Moving this all to hardware would help a great deal in simple cases as above but due to the independant nature of collision detection/physics and graphics, something like this would likely involve some tradeoff in flexability when moving to more complicated scenarios.

Re:What's the point?

[Pilchie]

I disagree, although I don't think that the equations involved in simple physics models are complex enough to be a major factor, collision detection is. Since most graphics systems already calculate a bounding volume for each object, why not have them also detect if those bounding volumes intersect, and do something if they do? This could be done in hardware and fits in nicely with what most graphics pipelines do anyway.
>~~~~~~~~~~~~~~~~

Collision Detection is a Hard Problem (TM)

[dnxthx]

Regardless of hardware or software, collision detection is a difficult problem. It would be nice if it was just a matter of detecting intersecting bounding boxes, but it's not. For instance, suppose two objects are moving towards each other with non-constant velocity (and perhaps non-constant acceleration). In one frame, they might not "collide", but by the next frame, perhaps their bounding boxes will be intersecting. At what point in time should you consider the "collision" to occur? Additionally, if both objects are going fast enough, then in one frame two objects could be about to collide, and in the next frame perhaps they have already "passed through" each other! So, in every frame you have to keep track of trajectories as well as bounding boxes (and I'm sure lots of other things I'm forgetting right now).

Just wanted to shed some light on a problem that seems a lot easier than it really is. Perhaps that's why specialized hardware is in order.

Sparta is doing just that...

[affegott]

Have a look at Sparta. http://www.cse.psu.edu/~mdl/sparta/

They seem to be doing just what you are talking about. I have used the demo program, and I must say it is VERY impressive. I haven't seen such realistic physics in a while...

Just a thought...

Ryan

Amiga Forever!

[gibson_81]

well, maybe not really, but the Amigas back in 1985 had hardware collision detection. They did it by having the graphics chip checking for overlaps between the "background (odd bitplanes)", the "foreground(even bitplanes)" and the 4 sprite-pairs. If a collision was detected, an interrupt was generated.

Dedicated game engine cards

[lythander]

Isn't one of the logical ends of this the Quake (or Unreal or whatever) card, where the whole engine is in silicon and for $100 you get the card and several levels on a CD? Once you have the card, it will work with any game using the engine?

Re:Amiga Forever!

[DavidOgg]

well shit, even the c=64 and atari4/800 had that (not as sophisticated as Amiga thought)

Re:Amiga Forever!

[joetee]

Amiga 1000: The OH-MY-GOD COMPUTER of game machines...
Here's a cool Hard-wired-gate idea that uses very little real estate to detect Sprite collisions (used in the C-64 and C-128?)Patent # 4572506 [ibm.com]
Commodore GOT to buy what the genius inventors of the 3 origional custom chips from Hi-Toro(Amiga) Patent # 5103499 [ibm.com]
and The Amiga 1000 Patent # 4874164 [ibm.com] (Sorry if the IBM links are kinda quirky)

Heh, now its fashionable to be "only a game machine", to have stereo sound, NTSC/TV out, 3D shutter glasses, boot fast'er, and have NO user interface slop or latentcy,
as long as you dont pose a threat to the man...

Re:What's the point?

[Raptor CK]

The problem is that the bounding volumes are currently done as boxes to simplify computation. There's simply no need to speed up the current bounding box implementation. However, such "physics acceleration" might eliminate the need for bounding boxes altogether. Then we'd have more realistic games, in which a rocket that whizzes by your head really does whiz by your head, instead of detonating about 3 inches above your shoulder, and so on. Passageways may also be smaller as a result, and other aspects of VR modeling can also be handled, such as friction of the non-boxed models against their terrain.
The problem is, 3d graphics engines lend themselves to hardware optimization by virtue of the OpenGL implementation (as of 1.2, at least) focusing more on the use of "popular" hardware acceleration. Unless we see a widely accepted physics modeling API for games, (OpenPL?), most of this will be somewhat pointless.


Raptor

See Robot Motion Planning Literature

[nellardo]

A fair amount of work has been done on using graphics accelerators for collision detection in the field of robot motion planning. SIGGRAPH 90, Lengyel et al. describes one such approach. One striking demo of this being used showed motion-planning for moving a piano through a ridiculously complicated maze, with low obstacles and narrow halls. It involves twisting the piano, backing up, etc.

The approach calculates the "Minkowski sum" for a given robot and a given set of obstacles - the Minkowski sum being a stretched-out version of the obstacles that accounts for the closest possible approach of the robot to the obstacle. Then, you repeatedly render the robot into this Minkowski sum rendering (the M. sums are polyhedra) and basically "stumble" around by looking for overlaps between the robot polyhedra and the environment. Dynamic programming is used to prevent repeat checks.

Try searching SIGGRAPH [siggraph.org] articles for more.

How do you handle collisions in software?

[Greg_Girty]

Graphics hardware currently is not required to have much dialogue with the software. Software just says, "draw this", and assumes it to be done. (Perhaps polling for refresh times.)

Once you introduce physics models, the interface between the software and hardware becomes a lot more complicated--how do you report a collision? Polling or interupt? How do you describe the objects involved?

I really don't know, but I'm quite curious: by the time you introduce all the overhead of extra communication, and drivers, will you save enough clock cycles to make it worth the trouble?

Collision detection = ability to solve many tasks

[SIGFPE]

If you have hardware that can do collision detection the chances are you could use it to speed up many other graphics related problems too - dynamics, visibility testing and a whole lot more. It would probably end up being more efficient to simply make the device general purpose and speed up those operations common to all of these tasks. These tasks include vector and matrix mathematics.

At least one games console currently available has a 4-way vector processor (everyone probably knows which machine but I'm under NDA...). This can be used for collision detection or anything else you fancy. This is more useful, it seems to me, than a collision detector. The downside is that they can be tricky beasts to program and writing an optimising compiler is hard.

--

Re:Amiga Forever!

[Maggot75]

Did you know that the Atari ST had hardware rendering capabilities? An area in memory described the scene, and 50 (or, in America, 60!) times per second, the Atari ST's hardware output every pixel of the scene onto a display device, such as a monitor. Imagine the speeds achieved! 50 fps is still quite impressive.