Sign in to follow this  
illadel4life

Avg number of polygons

Recommended Posts

My Collision Detection system can refresh a hierachical tree consisting of 6k nodes representing 3k polygons, in 11.14 micro-seconds. Is that good? Do games usally have more polygons per model? and if the polygons count is super high would it be feasible to have special collision detection models? Thanks in advance

Share this post


Link to post
Share on other sites
Quote:
Original post by illadel4life
My Collision Detection system can refresh a hierachical tree consisting of 6k nodes representing 3k polygons, in 11.14 micro-seconds.

Is that good?
Do games usally have more polygons per model? and if the polygons count is super high would it be feasible to have special collision detection models?

Thanks in advance


Honestly, I don't know if that's good or not, but it's likely good enough. How does it work? Does it use some sort of bounding volumes to "easy out" on collisions (e.g. a box around a character and an enemy, and if the boxes don't colide, the program doesn't even check each triangle)? Because those are the kinds of things that will make a system fast enough for real application with many different models with many polygons. 3000 polygons is a bit on the low side for most games now, but that's not a problem. It's not at all bad to use a lower-poly model for collision purposes (in fact, many times only bounding boxes are tested, and the program doesn't compare any triangles, much less fewer).

Share this post


Link to post
Share on other sites
It works by making a 14-dop bounding box hierarchy tree structure. Where each bouding box has two sub bounding box, and so on and so on. Also I found a higher polygon model, so now 6k triangles, and it refreshes 17 micro-seconds. now that refresh also can handle if the model was deformed, rotated, translated, and scaled. Now I have a "quick refresh" that only takes 7 micro-secs for a 6k polygon model that can only handle translation. Now for that 6k model it creates 10k bouding boxes for intersections. Now you said games don't check triangle-triangle intersection?

Share this post


Link to post
Share on other sites
6k nodes, 3k polygons...

Did you put every polygon in its own node? If so, that's a terrible idea. In fact, 3k polygons isn't very many polygons at all. The entire model should represent a single node in the hierarchy of your world, most likely.

Share this post


Link to post
Share on other sites
Well it all depends on how deep the tree should be constructed. My professor who is using this for robotics, so he wants exact coordinates of collisions and ray collisions. Now for a video game maybe the develpers want to go down to a bounding box for every 2 triangles, or 3. Then of course there wouldn't be so many. But yes in a hierarchy tree the entire model does have its own bounding box, then the next level that box is split into 2, and then those boxes are split, and so on and so on. The tree is a "full" tree but it may be unbalanced. Meaning Every node has 2 children creating what is called a binary search tree, which makes intersection tests much faster. Also lucky for me I created a "system" class which contains certain number of theese hierachies, the developer can have multiple of these systems maybe organized by scene location to further speed up the testing process. I recently included a ray intersection as well. w00t my system is almost complete.

Share this post


Link to post
Share on other sites
Promit has a good point. 6k node for 3k objects would be okay, but 3k polygons is going to mean that you have quite a small poly-budget for your art assets.

A given object (a player, say, using a 500 polygon model) should have one node in your collision detection tree; you don't need to reduce the collision detection to a per-poly level because

a) you (probably) don't need to test the player for collision against himself, and
b) you (probably) don't need polygon-accurate collision of other objects (bullets) with the player. Bounding volumes should suffice.

EDIT: The OP got a post in after Promit's while I was writing mine.

Quote:

Now for a video game maybe the develpers want to go down to a bounding box for every 2 triangles, or 3.


Even that is likely to be FAR to fine-grained of a resolution.

However, your statement about doing this for some robotics thing and needing exactly collision location absolves you from my statements about not needing polygon accurate collision, it sounds.

Share this post


Link to post
Share on other sites
People plz read my replies. My professor wants a triangle-triangle intersection. THe tree could stop building if

a) the number of nodes suffice for accurate collision detection, i.e. if you
want 5 nodes per model, then hierarchy can do that.
b) The developer maybe wants to have the nodes do not go further down than 4
triangles per volume. Again this can be setup.

Lol the timing on forums is tricky somtimes. Hey if the less nodes then refreshing a tree could be reduce dramatically. I'm not even worried about intersection test cause a 14-dop tests are fast. THe tests are maybe slower than AABB trees becuase of the more planes to test, but beacuse k-dops represent volumes more accuratly tests that would normally traverse any other tree could be stopped early when seeing that the objects do not intersect.

Share this post


Link to post
Share on other sites
Just FYI, if your meshes happen to be convex, you can use convex hulls for collision instead of generic kDOP, which will be considerably faster and still provide accurate results.

In fact, you might want to generally look into how the OPCODE library does things.
Quote:
Hybrid trees (OPCODE 1.3) keep a maximum of 16 triangles per leaf and reorganize client triangle lists, to eventually need roughly 16 times less ram than OPCODE’s standard trees. In the best case, this goes down to 1.25 byte / triangle, which is 115 times smaller than RAPID’s OBB trees (using floats ! else it’s 168 times). Speed hit is often negligible, and volume queries can actually run faster than OPCODE 1.2 due to less cache misses (reorganizing clients arrays also helps in this regard). They’re also faster for deformable meshes.

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