Sign in to follow this  
LancerSolurus

Convex Hull Creation and Usage Question

Recommended Posts

Just a quick question, how many use convex hulls for collision detection? And how do you go about making them? This is so I can determine the viablility of supporting other file formats for my program, which would be moot if there is a much better program available for creating convex hulls already... [Edited by - LancerSolurus on March 6, 2010 10:56:12 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by LancerSolurus
Just a quick question, how many use convex hulls for collision detection? And how do you go about making them?


Quickhull is conceptually simple, easy to implement and has reasonable big-O complexity for the general case.

Share this post


Link to post
Share on other sites
What about something that is GUI based, reads a standard model format such as OBJ and creates the hull in a standard model format.

Quickhull may do the job but it uses a non-standard input and output format. Its also CLI based and IIRC it can't handle multiple meshes in a single model. As in create a hull for each sub-mesh...

I am currently in the process of building just such a program but it's currently only for the game Freelancer. This post was mainly to see if it would be useful for those making games here. It loads up the game model (CMP or 3DB)and spits out a collision model (SUR) that can be dropped into the game and used without any modifications.

Share this post


Link to post
Share on other sites
Quote:
Original post by LancerSolurus
What about something that is GUI based, reads a standard model format such as OBJ and creates the hull in a standard model format.

That's not very useful if my app doesn't know what models it's going to load in advance (which is the case for the project I'm involved in at work, currently).

Quote:

Quickhull may do the job but it uses a non-standard input and output format.

There's no input or output format. It takes some points and returns a bunch of simplexes.

Quote:

Its also CLI based and IIRC it can't handle multiple meshes in a single model. As in create a hull for each sub-mesh...

I meant quickhull the algorithm, not a particular program/implementation.

Share this post


Link to post
Share on other sites
1 - actually that doesn't matter, most projects use at most 1 to 2 object formats, the collision file can be stored with the model since it is pregenerated as a static asset. Unless your assets are dynamically generated this method works good.

2 - yes...there are several different varieties of the code available, all have been source code or cli apps. The program I'm making is not based off of any of those apps (they did give the right direction to start). It uses a combination of mesh reduction and determinant based culling. Plus as the hull is being built it is being drawn in 3d within the dialog box.

3 - true but I was speaking of the programs, not the code. All of those I messed with were cli based and required their own special format for in/out. I talking about taking a model in 3ds/obj/lwo etc. and building a hull in those formats or a custom format...

Share this post


Link to post
Share on other sites
For those who don't know what convex hulls are used for, they are used for much higher speed collision detection. If your modding some older games you may need them. For those writing their own 3D games, convex collision models can come in quite useful. Consider the following example, a space station contains over 40k faces, you need to test for collision with every last face. That many faces could cause a huge perfomance hit when a user is firing multiple shots per second. Now take the same model converted to a convex mesh, this model is less than 800 faces. Which one do you think will perform better for collision detection?

Here is an example of a compound collision mesh (multiple meshes in one)

Share this post


Link to post
Share on other sites
Quote:
Original post by LancerSolurus
1 - actually that doesn't matter, most projects use at most 1 to 2 object formats, the collision file can be stored with the model since it is pregenerated as a static asset. Unless your assets are dynamically generated this method works good.

The object formats our app supports don't support the storage of a convex hull. But calculating the hull is near instantaneous so it's not a problem to do it once upfront.

And writing the code to do this isn't really all that hard. I'd suggest that's probably the reason that this thread hasn't seen much action thus far.

So why add another tool to your pipeline to do something that you can do quite simply yourself? In fact, writing code to import whatever your tool generates is probably more work than writing the hull code oneself.

Share this post


Link to post
Share on other sites
Well this tool isn't mainly for my use, it's for the Freelancer's community use atm. That game does require a convex hull for collision since it is a fairly old game. And MS dind't provide any type of editing tools for it at all. Many of us have made our own tools which we do for free. This was one of those that hadn't been made before and I have written many others just for that reason.

You're probably right, most of the advanced programmers on this site can do convex hull creation. In that case something like this would be useless to them. I will start looking around for modding communities to see which games use convex hulls and they don't have a tool to make them. Any suggestions?

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