Sign in to follow this  
illadel4life

Collision Detection Systems

Recommended Posts

I am currently building a collision detection system for my independent study over here at TU. My goal is to make a system so good that I could post it for open source and be a true competitor to other open source engines out there. Its still a work in progress, but its a 14-dop system that takes .05 milliseconds to generate two kdops over a sample model I use. Of course when its all done I would get more quality benchmark figures than this! I googled some systems and I get results like RAPID or OPCODE. V-Collide, and others. I suppose the system results depend on the system they're running on, but is there a factory standerd of features or speed of a CD system? My ultimate ultimate goal is to make an open source system, and be able to list developer groups or people who have DLed and are using, or atleast looked at my system and of course put that on my resume. Future goals is to make an alternate system multi threaded, and I would profile all functions and get nitty gritty with asm language optimiztaions. For example in M.Abrashes he increases the Dot product by 60%. I would take advantages like that. I was also looking into having the system done on the graphic cards. I could go on on about ideas I want to do to the system. Before people suggest a book, I am reading the best book on the market right now, lol I just forgot the name. the "know how" is no problem I can get the information from my prof, the internet, or a book, I have no questions on the "how to make a system" I'm just asking on the business side of things. Any thoughts? Also do game developers use open source systems, or do they use in-house systems, or self made ones? Thanks for reading, and inadvance.

Share this post


Link to post
Share on other sites
It's difficult to compare the raw speed of CDs. some are better in some configurations, others ideal for other situations... And the fact that RAPID and other were created years ago on old hardware don't make it easier.

anyway, a good CD should return stable contact informations (prune duplicate contacts, and provide for example, 3 or 4 contact points in the case of a box sitting on a plane). And if you noticed, RAPID and other dont'actually bother about the contact info and it's up to you to do it, which is a pain in the backside.

Those contact info usually are made of a contact point, and a normal at the contact point, and possibly a time of contact in case of a test done through time. In case of an intersection, it's a bit more blurred, but to cut it short it returns two points on the two intersecting objects.

It should also work in a variety of complex environments. Again, a lot of CDs have restrictions, like use convex objects only, ect... This can also be quite a problem.

The micro optimisations you are talking about should not be a priority, optimising the dot product on a platform might not provide any benefits on another, and usually, compilers do a good job at that stuff. Abrash (I guess you are talking about his legendary black book about Quake) had no choice, he was trying to fit a complete software renderer + BSP collision system onto a pentium, with a archaic compiler (by today's standards anyway), so every last single bit of performance had to be squeeze out. Those were the days, no quiche-eating coders back then!

Multithreaded CD however, sounds usefull, on the light of the new console architecture, people would expect that. But myself, I have no experience in that department.

Also supporting multiplatforms is probably the most important feature, besides the raw performance of the algo and that it will perform in complex and borderline cases (artists don't really have time to hand-generate collision maps for 1,000,000 polys environments).

Gino Van Den Bergen is a good example for the business side of things. He is the guy that does the SOLID collision detection library, which now has a commercial license, a book, and a website. He did it all :)

For game developers, there are a variety of plans. Some design their own engine, and that means, write a CD and physics from scratch. That can involve leaching code from the open source community, but usually, they dont return the favour (they don't share their code and algos). There are exceptions, of course (Stan Melax, ID software, ...). Some license a fully-featured physics engine (Havok, novodex), which have built in CD, very complex and with lots of features. The thing with CD, is that it's intricately bound with phyics engines. So studios with their own physics engines usually design their own CD engines. I haven't heard of RAPID or OPCODE being used for games 'as-is'. Maybe there is a hole in the market for that, or maybe no market at all. :)

Share this post


Link to post
Share on other sites
Ok, your rating went up. Thanks for the thoughtful reply. I feel humbled, and informed.

You see your information is helpful to me because if developers are looking for those features than I would go out of my way to provide them. I know I alone could not compete with havok (altho I will try) but maybe my engine could help out a person just starting, or save time and money for a development group.

My next step is to look into havok,novodex and a generate a list of features, and options. Maybe they'll list some performence benchmarks as well.

Thanks again. You set me on my path.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
There are really at least two levels to collision detection. One problem is to take 2 objects and determine if they collide, and perhaps more information about the collision like collision points, normals, penetration depth, etc. The other problem is to take N objects and quickly find pairs that may potentially be colliding, so the more fine grained collision detection doesn't need to be run between all the N*(N-1)/2 pairs of objects. Or actually the more general problem of having two sets of objects and finding all the potentially colliding pairs consisting of one object from each set.

Share this post


Link to post
Share on other sites
Quote:
Original post by illadel4life
Ok, your rating went up. Thanks for the thoughtful reply. I feel humbled, and informed.

You see your information is helpful to me because if developers are looking for those features than I would go out of my way to provide them. I know I alone could not compete with havok (altho I will try) but maybe my engine could help out a person just starting, or save time and money for a development group.

My next step is to look into havok,novodex and a generate a list of features, and options. Maybe they'll list some performence benchmarks as well.

Thanks again. You set me on my path.


Yeah, definitely check out the competition. Physics engines can also teach a lot, then you can see what they require from CD. Novodex, Tokamak, Newton, ODE, they all kinda work the same in that department.

Not just that, but also what their business plans are in term of customer support, platform support.

There are other features to collision detection apart from providing support for physics, such as basic intersection queries (ray intersections, volume intersections, distance queries, ...).

Anyway, best of luck with your work.

Share this post


Link to post
Share on other sites
A generic collision detection package is a very tricky thing to do.
As far as I can remember, we had to rewrite or "at least" heavily tweak our collision detection package for almost every new project.

My guess is that there's no perfect or generic package. Still, if you are aiming for perfection, I think that you must make sure that it's as tweakable as possible on every level. There's a reason why most developers choose to write their own collision detection system.

Here, let me give you an example. While writing a collision response code for simulating an elastic body being touched by a rigid body, we needed only the first contact between the elastic body and the rigid body.
By first contact I mean the first contact that would arise if you continuously sweep the bodies between the previous state and the current state.
Now think... The usual approach of finding all contacts and then sorting them by their contact time is very "wasteful". Since all you need is one single contact, a better approach can be devised. And this is just a little example.

GPU assisted collision detection is a very good idea. If you haven't looked into CULLIDE yet, you really should. By the way, a very good implementation and improvement of CULLIDE can be found here:
http://gamma.cs.unc.edu/CDCD/

Oh.. and of course a support for continuous collision detection is a must.

I hope that I managed to help a bit.
Good luck with your project.

Share this post


Link to post
Share on other sites
Quote:
Original post by ury
A generic collision detection package is a very tricky thing to do.
As far as I can remember, we had to rewrite or "at least" heavily tweak our collision detection package for almost every new project.

My guess is that there's no perfect or generic package. Still, if you are aiming for perfection, I think that you must make sure that it's as tweakable as possible on every level. There's a reason why most developers choose to write their own collision detection system.

Here, let me give you an example. While writing a collision response code for simulating an elastic body being touched by a rigid body, we needed only the first contact between the elastic body and the rigid body.
By first contact I mean the first contact that would arise if you continuously sweep the bodies between the previous state and the current state.
Now think... The usual approach of finding all contacts and then sorting them by their contact time is very "wasteful". Since all you need is one single contact, a better approach can be devised. And this is just a little example.

GPU assisted collision detection is a very good idea. If you haven't looked into CULLIDE yet, you really should. By the way, a very good implementation and improvement of CULLIDE can be found here:
http://gamma.cs.unc.edu/CDCD/

Oh.. and of course a support for continuous collision detection is a must.

I hope that I managed to help a bit.
Good luck with your project.


True. If the developer designs his own physics system, he would expect things done a certain way from the collision system, like what's in the collision reports, and that it should handle this kind of objects, matters of using proprietary space partitioning techniques, memory restrictions, broad phase culling, terrain collision, triangle soups, also dealing with soft meshes efficiently, ect... Which is why I don't think there is much middle ground between getting a full-featured phyiscs engine, and designing your own, with what you need and want from a complete physics engine. Either your CD will lack features, or will be too complex for the purpose of a type of game. So you need very good customer support, and be at the mercy of your clients, and hand them the code. So you need some insane logistics to make something viable.

But you are welcome to try. In any case, if I think you should start small and build up and see how far you can go.

Share this post


Link to post
Share on other sites
Thanks everyone for the thoughtful responses and I'm starting to see the flaws in what I was hoping to be the case. Also looking at havok and how they do not list any benchmarks was really annoying. Well first and foremost I need to finish this thing, lol thats step one. Step two maybe setup a demo of some sorts and see if the developers like the "framework". I suppose start from there. Since this is a one man crew, I suppose working with one developer at a time is the only way I can go. But like I said, and let me restate, this is for an indepentdent study, so my first developer in a sense is my prof. I want an A. Then, who knows, I might setup a survey on here to see features, and performences people are looking for. I can tell ya this, the model I use is about 1000 triangles, and it works purty fast. about .05 milliseconds to generate trees over two (of the same)models. And not to mention not simplified models but "in game models". Just keep a look out I might post updates as soon as I'm ready.

As for the system just need to make it so it splits into triangles ( right now I settle for 4 verts or less) , and add a fast triangle test. Then I need to "Class" everything. Definitly adding a split routine to instead of splitting the volumes along the longest axis, I split the volumes based on surface area. Also add an "area" effect to split an entire area and then find out which object is where then do collision test on objects within the same "grid". Thats where I think the multi-threading will be handy. ehh I should get this done by the end of the day. HA! Give me couple weeks. In the meantime I can find out how to package this thing, and any support of extra features I can add. Aiight peeps, thanks agian.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this