🔒 Locked

Collision Detection in hi-poly scenes

Started by Assassin Apr 9, 2003 at 8:44 PM 9 replies 6.9k views

Original Post

Apr 9, 2003 at 8:44 PM

With all the recent discussion of BSP versus octree, and the introduction of newer methods for speeding up rendering on modern video hardware, it seems that collision detection is just an afterthought that should be worried about after your bazillion-vertex level renders as fast as possible. I'm yet another person trying to make a 3D engine because I can't afford to license the big-name engines around and would rather sell my own game rather than make a mod and encourage sales of a game that I don't have any interest in promoting. As such, I'd like to have support for levels with relatively high polygon counts, which can be either indoors or outdoors. It seems that rendering the level is fairly easy in comparison to doing collision detection with it - for rendering you have a dual-CPU system, but for collisions you only have 1 CPU to make use of. So how can you do accurate collision detection in hi-poly scenes that manage to make use of modern video hardware's incredible speed? There's a variety of spatial subdivision methods available, with many of them offering variations on the KD-tree (quake-style BSP, ABT, quadtree, octree) and others making use of constrained visibility to slice up the level into arbitrary chunks (portalized sectors). These are all great for rendering, and I've seen it said several times that "you should keep a separate structure for rendering and collision detection," but I haven't seen much elaboration past that statement as to which methods are good for doing that. There also is the trouble of keeping the structures synchronized when dealing with dynamic environments, and whether or not they even deal with the same geometry - some methods don't even worry about the actual geometry and just create AABB's and OBB's around the geometry to collide with. So, what is good and what is bad when dealing with collisions in hi-poly environments? Let's say that we want to deal directly with the level geometry to avoid any issues with inconsistencies between collision and visual geometry; here are some tidbits that I've gathered: BSP: (Binary Space Partition) very expensive to compile for hi-poly scenes due to the complexity of the splitting plane selector and the polygon splitting incurred when resolving the multiple-reference issue. Once compiled, points can be tested for being inside/outside the mesh, rays can be cast through the splitting planes to find intersections with a simple check, and the splitting plane orientation provides the best solution for doing CSG. Quadtree/Octree: Less expensive than BSP to compile due to the simplistic splitting plane selection. Still no better in terms of data bloat due to splitting - the simplistic subdivision plane selection incurs a lot of splitting or multiple references (depending on how you implement it). Casting rays through an octree can be fairly fast, although all leaves that are intersected have all their contained polygons checked for intersection. Cannot indicate inside/outside unless you start from a point that is known to be inside or outside and do a ray-cast to determine the number of intersections (assuming the mesh is closed and has a definite "inside"). The splitting penalty can be reduced and spatial locality and expense increased by using an adaptive splitting plane method. You can also make an octree/BSP hybrid and compile a BSP for each leaf, which may give you faster ray-casts through a leaf. ABT: (Adaptive Binary Tree) Expense for compilation is somewhere in the middle, because the splitting plane selection is adaptive (it picks the best place it can for the splitting plane based on various criteria) but not as complex as a quake-style BSP because the splitting planes are all axis-aligned. Has the interesting feature that the volumes of the 2 children of a node don't necessarily sum to the same volume as the parent node, because each node uses a bounding box to get a more accurate representation of the volume taken up by the geometry it contains - the volume can be less when objects are separated by empty space, or more when objects butt up against each other and interpenetrate, in which case the volumes can also interpenetrate. As such, ray-casts can be done more quickly because more geometry can be rejected than with an octree, and the planes are axis-aligned which can result in quicker comparisons and less data bloat. Also has a better multiple-reference resolution system than BSP or octree because the splitting plane's selection function takes the amount of split geometry into account and tries to minimize it. I'm still not completely sure how the whole system works, because I've only seen discussion of it in relation to rendering hi-poly scenes and because I've seen figures of 2000 or more polygons in a leaf, which may be optimal for rendering when compared to the 1-poly leaves of BSP and 50-poly leaves of the average octree. Doing a brute-force collision test on 2000 polygons isn't the best idea though, so I'm interested in seeing a way to adapt this system to efficient collision detection - perhaps compile a BSP for each leaf and use that? The issue with inter-penetrating volumes might also be a problem because it's non-deterministic in choosing which child node to recurse into for checking for the first intersection of a ray. Portals: more of a scenegraph thing than a spatial subdivision thing, since it relies on spatial subdivision or a human being to place portals appropriately. Don't really help with collision detection except to form a cutoff point for the amount of geometry in the local sector. Hmm, I've rambled on for quite a while on all that now, and I hope I've got most of the important things noted. I don't really see an obvious choice when choosing a collision detection method, but it seems that the ABT is a good choice for getting high rendering speeds on shader-class hardware. I would like to use the same structure for both rendering speedup and collision detection, but that's not always possible. I just feel a little lost and not sure where to start when deciding how to go about computing collisions, and since I'd like to have both indoor and outdoor scenes, the issue is clouded even more. So please, I'd like any comments or discussion you have on this topic. -- Andy Campbell www.andyc.org [edited by - Assassin on April 9, 2003 9:45:19 PM]

Renus

Apr 9, 2003 at 9:30 PM

I''m sure you get a lot of posts on this topic as there is no perfect solution.

I also was unsure on what to use, and finally decided for a compressed balanced AABB tree as collision database for static geometry:
http://www.dawntec.com/docu/conOWCollDetect.htm

After implementing the stuff and profiling, I''d say that the choice of the collision detection algorithm has no major impact on the overall performance, as long as you have any medium clever, non-brutal search (O(log n) or the like). Just keep an eye on the memory consumption of your solution, and when designing keep in mind that returning some material description of the colliding face is necessary.

In this regard, I would also consider what kind of implementation you already have. Reusing this will save you weeks.

Regarding the dynamic stuff, I handle them as any other dynamic object separately, I am not sure if it''s a good idea to pack it into your static geometry data as you might lose things like compression and precomputation.

- thomas

MindCode

Apr 9, 2003 at 9:38 PM

I think your on the right track with this. I am also concerned with people using commercial engine features (not necessarily moding). 99% of the game engines out there use the Q3 map format. What ever happened to originality? What happened to experimentation? The community used to be really into this, now everyone chases the "standard". It''s really hurt the community as a whole.

Collision detection is a lot harder than simply rendering. Many people have given up on their engines under the pressure of coming up with an efficient collision system. This is because they usually wait too long to develop it. You should be thinking about it from the get go. Don''t worry about how you will code it, but keep it in mind. You don''t want to have to go back and re-write a lot of code just to accomadate collisions. Collisions will slow things down enough on their own.

To elaborate on the "you should keep a separate structure for rendering and collision detection" thing. They should be separated primarily because the geometry efficient for rendering will not necessarily be efficient for collision detection. When I compile my geometry, I create two structures at the leaves of my tree. One is compiled for OpenGL/D3D (which may be comprised of triangle strips or fans), and another structure that is compiled for collisions (which may be an aabb tree or heirarchal bone tree etc...). Each is optimal for performing their own task but do not look alike at all.

Obviously the best choice will depend on what you are doing, but usually people are talking about "first person" when they mention vsd, so I will assume that. And I''ll avoid starting another arguement by not going too deep into what''s best for terrain, but I will say one thing. When you are in a first person camera mode, you are not likely to see most of the terrain anyway. In fact if you look at some of the best outdoor maps from commercial games (Halo is a good example) much of the terrain is not seen all at once. Usually it is occluded by more terrain.

You also have to keep in mind that your artists are going to want to use higher level tools like 3dsmax anyway. If your map compiler takes in one of these commercial formats and compile it for your maps, then wether the file is of an outdoor or indoor environment will have little to do with it anyway. You will have to handle both situations with the same method (unless you want to double your work load by writting 2 compilers and 2 engines).

duhroach

Apr 10, 2003 at 12:32 AM

Well, I know this topic is probally out of my league, but what about using Collision Meshes?
Someone once said Best way to reduce a high polygon count scene, is to just use less polies.
Even making an app that would create lower level LOD versions of the same object that takes up (roughly) the same geometric area space of an object / scene and simply using that mesh to check against collision would greatly increase scene speed. I saw an article somewhere that divided each object itself into an octree, then used that for collision.

And of course optomizations can come based upon what kind of engine you''re designing, and how much interaction you want to allow with your enviroment. That would seem the first step, then move onto designing an efficient system.

I do believe that you should keep a seperate structure for collision than you do rendering, however some aspects are just good to keep all around. You want to reduce the number of checks to get down to what data is actually intersecting, and then as least amount of checks in that respect too.

If your goal is to just reduce the amount of hot "Poly of poly" collision action going on, I''d really reccomend the LOD collision meshes.

~Main

==
Colt "MainRoach" McAnlis
Programmer
www.badheat.com/sinewave

Dirge

Apr 10, 2003 at 3:14 PM

Great topic, I had just started wondering about this as well. As Yann mentioned and I completely agree with, an Octree is an extremelly efficient SPS (Spatial Partitioning System) to use for both Collision Detection and Rendering, especially with dynamic objects. I''ve used both (in seperate instances for Collision and Rendering) in seperate structures (it wasn''t combined).

You could use a single combined SPS (lets say an octree) to keep both static and dynamic entities, with I would guess minimal extra overhead. The trick is you would still need different traversal functions (for inserting/querying dynamic ents or ent to world collision). Also the node would contain both sets of data; some kind of list of the number of ents in this node (as AABB''s maybe), and if it''s a leaf, the actual geometric data. This combined tree would save you quite a bit of data versus creating two tree''s for the same purpose, plus would promote code reuse.

I haven''t used ABT''s, I suppose I need to investigate those next. I''m a little biased though in that I would reccomend an Octree/Quadtree for shear simplicity and speed. Also, no one mentions it but you can precompile Octree''s and save it out just like Quake style .bsp files, making them even faster to load.

If you want flexibility in your algorithms though you should probably use two different SPS''s, but remember, flexibility always comes at the price of speed (carmack knows this, so should you) and memory.

Just to mention it, you could accomplish the same thing through a BSP but your poly density would probably be bigger because of the cutting inefficiency. Remember, you ALWAYS want LESS polys in geometric collision tests and MORE in rendering dumps. (Adaptive) Octree''s even splitting can help with both, but BSP and ABT''s attempt to group your cells more within polygon dense area''s (making them not as good for collision detection???).

"Love all, trust a few. Do wrong to none." - Shakespeare

Dirge - Aurelio Reis
www.CodeFortress.com
Current Causes:
Nissan sues Nissan

ArnoAtWork

Apr 11, 2003 at 2:46 AM

I am novice in the space partition technique, so don''t be surprised(or scared by this question).

When you talk about dynamics, it''s BOTS, physical elements,...? They have to be stored in the leaves with the geometry?

I understood that geometry to be render must be stored in the leaves in the SPS. Then you could still subdivide and add new nodes to store geometry for CD, that is ok.

thanks.

Dirge

Apr 11, 2003 at 11:57 AM

Kind of. By dynamic we mean it''s able to move thus it''s position is unpredicted (well kind of) and can''t be pre-calculated. So, basically every time this object (or the common term, entity) moves, we have to invalidate it''s previous position and re-insert it into the tree hierarchy. You wouldn''t keep them exactly with the geometry (in other words, you don''t put their geometry into the node), but just a pointer/reference/whatever to them in there.

"Love all, trust a few. Do wrong to none." - Shakespeare

Dirge - Aurelio Reis
www.CodeFortress.com
Current Causes:
Nissan sues Nissan

Assassin

Apr 11, 2003 at 3:40 PM

Another thing that I''d like to take into account for the collision detection method is the ability to handle CSG (constructive solid geometry) effectively, because I will likely be using the same collision methods in the editor and in the game, although the editor doesn''t have to return results so quickly. I''ve seen many an article on CSG that recommends using a BSP to do the dirty work, which seems like a fairly effective solution, but storing all the level geometry into a BSP isn''t effective.

Perhaps something like the Unreal methodology would be good - their levels are carved out of "the infinite solid" using BSP methods at first, and then you can place many many StaticMeshes inside the level to add detail. The BSP is collided with on a per-poly level, and all the StaticMeshes get simplified collision volumes. That would effectively reduce the number of polygons stored into the raw geometry structure, because the BSP faces are kept large and coarse, and then covered up by more complex meshes that do less complex collisions. Quake3 did something like this with their curved surfaces too I think. So it seems that using a low-detail collision mesh paired with some detail meshes that have associated collision meshes might be a good approach.

Shmiznac

Apr 12, 2003 at 6:03 PM

I've heard that the Sweep and Prune (SAP) method is highly effective and fast for dynamic object-to-object collision detection. Google for "Sweep and Prune" to find more info. For static geometry though, you're probably better off with some kind of BSP and portals for inside environments and a looser spatial partitioning method like an octree for outdoor environments.

[edited by - Shmiznac on April 12, 2003 7:16:20 PM]

Assassin

Jun 3, 2003 at 4:33 PM

How about collisions in environments that were created in a modelling app like Maya or 3DS Max, how can you effectively create a collision system for handling these arbitrary geometry scenes, where creating a low-res mesh might not be feasible in all cases. Would it be effective to just create an AABB tree, such as in an ABT, and then once you get down to a leaf AABB just test against each of the polygons inside that leaf?

Also, on this note - would you prefer an Unreal-style level editor where you create a basic shell of a level that has a precise collision system, and then import a bunch of detail objects with simple, imprecise collision systems to cover up the shell? For example, you make an arched hallway by putting in a simple rectangular prism, then use some bezier patches to make a curved ceiling. Then you can add some pipes running along one wall with either some more bezier patches, or perhaps import a pipe model and stretch or copy it down the length of the hallway. Alternatively, you could just model the whole hallway with the arched ceiling and pipes all built in, with no extraneous polygons or low-res collision meshes.

This basically comes down to "make a level editor, or try to use 3DS Max for making levels", and I''m trying to take into account not just the rendering quality, but the collision detection systems also. And if I can get this cake to bake up properly, I''d like to get some CSG in as icing, for carving holes in the levels at runtime...

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.