   Choosing the right Bounding Volume type.
  Hello everyone,I'm writing a little project, of a top-down shooter game (think alien breed). I'm somewhat stuck on theoretical disputes about the BV system I should use.What I want to focus on here are several things :- Speed/Ease of implementation- Constraints to gameplay imposed by the CD system.Of course you can just toss BSP at anything and it will work, but I'd rather make a working project and finalize it, rather than dig through BSP/kd-Tree documentation.In my previous project (  nGine  ) I've used AABB volumes for simple collision detection against the camera. Precision was not a big thing, and spheres bound boxes like on the below picture weren't a problem : AABB Sphere However, since now the character, which will be a quad BV basically needs to move through more or less rectangular world, or more oval world depending on the level, the accuracy of CD is needed.This is aspecially imporant as I want to implement 'sliding' against the walls, and the jaggy bounding boxes might create a problem here. Tips on implementation of this technique would be welcome too.Let's get to the problem at hand : http://nestor.vg/dump/volumes.gifThe black objects are walls covered in AABB, as long as everything is aligned with the axes, it's fine and dandy.However, below we see the character (red box) approaching a trianglish structure, here AABB would prevent the character going anywhere near it.So far, from brief search it seems that OBB (oriented bounding boxes) would be the choice for me. I am still fresh in the 3d coding, and some techniques might've slipped my eye.Thus I'm writing here with a humble request for advice which (out of all known) bounding volume/CD techniques I should use to allow the character to enter concave areas, and slide against their walls.A followup discussion I would like to have is the culling technique to remove invisible objects from the drawing queue, provided that each segment of the wall would be a separate object, just like the in the picture above. The easiest thing that sprung to my mind is to divide the array of objects loaded from the map file into n sectors, and encase each sector (the first being the whole scene) into a bounding volume and then just test the frustum agains the collections of bounding volumes and draw only those intersecting. A simple binary tree should suffice for this.This is however a secondary matter, and hopefully we'll manage to get some sort of consensus on the BV technique first.Thank you for reading, and thanks in advance for any advice given.   
Quote:Original post by NestorPLOf course you can just toss BSP at anything and it will work, but I'd rather make a working project and finalize it, rather than dig through BSP/kd-Tree documentation.In the context of collision detection generally (emphasize this because it's not always the case) bounding volume hierarchies (BVH) are preferred because they don't deal with spatial ordering like spatial partitioning structures such as BSP/kd-tree and therefore no issues of having to split primitives which intersect the partition plane. BSP trees are more useful with doing intersection tests with concave n-sided polygons.Quote:Original post by NestorPLLet's get to the problem at hand : http://nestor.vg/dump/volumes.gifThe black objects are walls covered in AABB, as long as everything is aligned with the axes, it's fine and dandy.However, below we see the character (red box) approaching a trianglish structure, here AABB would prevent the character going anywhere near it.So far, from brief search it seems that OBB (oriented bounding boxes) would be the choice for me. I am still fresh in the 3d coding, and some techniques might've slipped my eye.Thus I'm writing here with a humble request for advice which (out of all known) bounding volume/CD techniques I should use to allow the character to enter concave areas, and slide against their walls.Yes OBBs generally give you better fitting volumes/areas but they can be much harder to construct (at least in 3D anyways). However You can still do this with AABBs and in most cases not no matter which bounding volume/area type you use if the BV only contains a whole object and you want more accurate CD you will have to do further intersection tests, use BV for quick rejection and then and in-depth intersection test. In this case the accurate test would be pixel collision detection (it's a 2D game right?) and you can accelerate this by using BVHs again for pixel areas (typically done with 2D fighting games).You could have 2/3 level CD system where the first level quickly culls out non colliding entities and get a list of potential colliders, then do in-depth intersection tests using BVHs if the in-depth test are to expensive.Try to use dynamic intersection tests for BV of movable objects.Quote:Original post by NestorPLA followup discussion I would like to have is the culling technique to remove invisible objects from the drawing queue, provided that each segment of the wall would be a separate object, just like the in the picture above. The easiest thing that sprung to my mind is to divide the array of objects loaded from the map file into n sectors, and encase each sector (the first being the whole scene) into a bounding volume and then just test the frustum agains the collections of bounding volumes and draw only those intersecting. A simple binary tree should suffice for this.This is however a secondary matter, and hopefully we'll manage to get some sort of consensus on the BV technique first.Thank you for reading, and thanks in advance for any advice given.You meant using BVH? if so that sounds fine to me, you don't have to stop at just at levels go down the object level (and even pixel if you need it for some objects). You could use this for both visibility & CD culling.[Edited by - snk_kid on September 6, 2007 4:58:05 AM];Quote:Original post by snk_kidYes OBBs generally give you better fitting volumes/areas but they can be much harder to construct (at least in 3D anyways). However You can still do this with AABBs and in most cases not no matter which bounding volume/area type you use if the BV only contains a whole object and you want more accurate CD you will have to do further intersection tests, use BV for quick rejection and then and in-depth intersection test. In this case the accurate test would be pixel collision detection (it's a 2D game right?) and you can accelerate this by using BVHs again for pixel areas (typically done with 2D fighting games).You could have 2/3 level CD system where the first level quickly culls out non colliding entities and get a list of potential colliders, then do in-depth intersection tests using BVHs if the in-depth test are to expensive.Try to use dynamic intersection tests for BV of movable objects.The game's principle is 2d-ish, and indeed most calculations will be done in 2d, but the game is made from solid 3d objects, so per-pixel collision is not something I will do.My concern was mainly the fact that AABB will give a very inaccurate BV, even at face-level, creating spacious cubes of doom which will prevent the character from moving smoothly against the wall.I think creating a binary tree from the set of all non-dynamic objects in the scene and then dividing it by half each time will be enough for a BVH supporting CD and culling.If anyone has a good idea how to implement wall sliding (reaction to collision with a wall) it would be very appreciated indeed.;Quote:Original post by NestorPLThe game's principle is 2d-ish, and indeed most calculations will be done in 2d, but the game is made from solid 3d objects, so per-pixel collision is not something I will do.Well it doesn't matter if it's pixels or polygons at the end of the day either still apply.Quote:Original post by NestorPLMy concern was mainly the fact that AABB will give a very inaccurate BV, even at face-level, creating spacious cubes of doom which will prevent the character from moving smoothly against the wall.Yes some BV types will fit better than others but as i was saying before unless the object being contained is the same shape as the BV type or your BVs are convex hulls you will always have some slack but it doesn't matter as i've said BVs are used for cheap rejection tests and CD/visibility culling. If there still is an intersection with BV then drill down further to find the exact collision either doing primitive (poly/triangle)-ray/plane/BV/primitive intersection tests or if the set of primitives is large and the tests are expensive accelerate this by using a BVH again.The BVH leaves could have a BV therefore you may end up with two intersection tests, BV first and then primitive or just the primitive itself and only one intersection test occurs at the leaf. Which way you choose depends on how expansive the primitive intersection test is.   ;  Hello,implementing wall sliding with AABB is not a problem. Just check if the bounding box collides with the polygons of the wall and move it back along the surface normal. That way, when a player wants to slide along a wall, the forward moving power and the offset power from the collision algorithm will add together to get a slide-effect. Ofcourse if you want to apply this technique to large levels, you'll have to perform some collision culling to make it fast. The way I did this is to use a separate octree structure for collisions. It worked surprisingly well and collision detection had almost no effect on framerate.Jeroen   ;Quote:Original post by godmodderThe way I did this is to use a separate octree structure for collisions. It worked surprisingly well and collision detection had almost no effect on framerate.The way I did it previously, was just an AABB binary tree and I would test an object against the nodes until I hit the leaf.I think I might go with tile-based levels in this project, which would mean that I could easily predict which tiles on the map are visible and then check against those.I might also make a big binary tree for the whole level and then test against the tree structure, I need to sit down and think which of those would be faster for CD.Thanks for that sliding idea, I'll test it out when i finally sit to digging through my old code ;-)   ;  As snk_kid suggests you really want to use a multi-phase collision detection scheme. The most popular sort is to use a BVH to do a "broad phase" collision detection pass which generates pairs of potentially colliding objects. Then the "narrow phase" actually performs intersection tests with the base meshes (may be simplified collision meshes... forcing them to be convex is not uncommon).You don't want to try to do *everything* with just BVH as it will be both inaccurate and inefficient. Once you get down to just a few pairs of objects/polygons in the leaves it's much more accurate and efficient to compute proper mesh intersections.The key of such things is always to think of your data structure as an accelerator for the otherwise unreasonably expensive work of testing collisions between every pair of objects in the scene -> O(N^2). Think of the "broad phase" as conservatively culling that list of potential intersections.The same concept is true for view frustum, ray-tracing, and other accelerators.   ;Quote:Original post by AndyTXAs snk_kid suggests you really want to use a multi-phase collision detection scheme. The most popular sort is to use a BVH to do a "broad phase" collision detection pass which generates pairs of potentially colliding objects. Then the "narrow phase" actually performs intersection tests with the base meshes (may be simplified collision meshes... forcing them to be convex is not uncommon).That's what I intend to do, actually.Collide the "Actor" BV with Binary Tree containing world Bounding Volumes (that's BVH if i understand correctly), and do fine CD once the tree returns a leaf. The leaf will contain only one triangle and I can do fine testing there.The problem I'm anticipating here is of a different nature, however.Let's say that i have 1000 objects in a scene. I build a BV of this dataset and subdivide it into halves until each single objects (not primitives). Only a part of those is ever visible on the scene.The question is would i be faster to check collisions from around the object (the game is tile based, i can easily tell which tiles/objects would collide with the player), or go through the tree.With some simple drawings I've established that for a 7x7 room I'd have to do 6 node checks + 1 leaf using BVH. Determining the collision would basically take only one check, two if the player is on the border between two tiles. Nine checks if we want to check all adjacent tiles for some reason.Tile-based checks are a bit faster because they check if there's actually any tile at the given x/y, as opposed to doing BV-BV checks. This would mean that for the most of the time, collision checking would not be done, as this is not a wall-crawling game ;-)With tiles it will be also easier to perform collision checks on the objects. Since the type of the tile we're colliding with is known, there is no need to store a BVH for each single object on the scene, and they can be computed on-the-fly, by just adding the tile offset to each vertex. So once BHV are built they can be easily re-computed. As long as the tiles don't contain 20k faces, re-computing the vertices upon collision should not have a major impact on the performance. Theoretically.Do you see any flaws and major limitations of such approach? Of course bullets and AI opponents will also use CD for movement. Bullets will perform very many checks, but then, the collision of bullets can be easily just cut at the root BV  level of each tile. Possibly AI movement too, as they will be slaughtered anyway, and don't need to try to squeeze in between texels like players do.I know this post is somewhat chaotic, but I've had a healthy break from programming and procedure-thinking and I'm trying to pick very many paths and ideas at the same time.Any input is as always greatly appreciated.   ;Quote:Original post by NestorPLDo you see any flaws and major limitations of such approach?The biggest limitations are that it will become inefficient in the case where a tile contains lots of objects (it effective assumes a uniform distribution of objects to remain efficient), and that an object shouldn't be so big as to span many tiles, or else you lost the entire benefit of the system (the latter is a bit of a problem for any system, but can be more easily handled with a BVH).If you don't anticipate having huge objects or large clumps of objects though, I think it's quite a reasonable approach. What you're describing is called a "uniform grid" accelerator and is comparatively simple to implement, but you waste a lot of space/time/efficiency if your scene isn't at least somewhat uniformly distributed.