Re: [Algorithms] Broadphase collision

[Darren G. <dg...@ke...>]

By way of anecdote, here is my experience: I am 
inserting bounding boxes into an implementation 
of the hierarchical hash table described in mirtich96a (2.4.2):

         <http://cg.cs.uni-bonn.de/docs/teaching/2004/SS/seminar_anim/documents/Mirtich96a.pdf>http://cg.cs.uni-bonn.de/docs/teaching/2004/SS/seminar_anim/documents/Mirtich96a.pdf 


This approach has proven effective for a 
relatively even distribution of many dynamic 
objects of reasonably varying size and velocity. 
The memory requirements can be quite large, which 
makes it more suitable for PC. I have thousands 
of objects running roughly 1-m to 1000-m in 
diameter and capped at 200-m/s, for instance, but 
very few are moving noticeably at any given time.

You may want to explore a hybrid partitioning 
approach to get the most out of your static world 
geometry. If you have a scenario with only a 
moderate number of small objects moving around 
there are better options. A tighter space 
partitioning and quad tree may be a better option.


Cheres,
Darren Grant.



At 10:22 AM 3/24/2010, Priyank Jain wrote:
>Hi,
>I am trying to implement broadphase collision for my game (3D FPS
>genre). I have been reading about the commonly used techniques and I
>have tailored the grid approach to my game. I want to know if this is
>the right direction to go in or not.
>The involved actors are :-
>Players
>Bullets(Fired)
>Weapons (placed at points located throughout the level, which other
>players can pick up, aka static objects)
>World
>As of now, I am just trying to get the Players and bullet collision pairs.
>Players: Players are represented by a bounding sphere, located at a
>position and moving with a velocity. Each player would have
>approximately the bounding sphere of same size.
>Players - weapons
>Players - World
>Bullets: Bullets are represented by a segment with a start point and an
>end point (using posn, posn + vel) (each frame). Bullet can hit :-
>Fired Bullet    Player
>(Other) Bullet
>World
>
>Approach:
>- As each player and bullet is created, associate a reference to each
>entity within CollisionMgr as a list<Player*> and list<Bullet*>.
>- On each update frame, do the following:
>- For each player, find Cell(s); it is associated with :=> list< Cell* >
>PlayerCells
>- For each Bullet (segment), find Cell(s); it is associated with :=>
>list< Cell* > BulletCells
>- For each entity, the cell(s) can be found out based on the entity.
>- Player: Bounding sphere :The grid size are uniformly sized cell (size,
>M) such that the M = 2R (R = radius of the bounding sphere). Thus, at
>any given time, at most the bounding sphere can be in contact with 4
>cells. To determine the cells associated, find the 8 points for a given
>sphere (each at 45 degrees to the X,Y,Z axis along the 8 octants). (And
>then find out, in which grid cell does each of the point lie. This could
>at max return 4 cells).
>- Bullet: Segmented Ray with endpoints at : Posn and (Posn + vel). Thus,
>all the cells that the line passes through would yield the cells.
>- Cell can be a structure like
>Cell {
>List < Player*>
>List < Bullet* >
>Value (x,y,z) => unique value based on these three coordinates
>}
>- As a cell is found by either of the entities, given its coordinates
>and grid position, a cell can be put on the hash-map. As the players and
>bullets yield cells, they can be referenced using this map and in-turn
>populate the list of player and bullet residing within that cell structure.
>- After all the player and bullet ­affected cells have been found, if we
>iterate through the hash-map, then it would yield all the possible pair
>of colliding players and bullets in a given cell. This can then be
>further handled using narrow-phase collision.
>
>Does this sound feasible ? I'd really like to get some feedback on this.
>
>Thank you
>/Priyank Jain
>
>------------------------------------------------------------------------------
>Download Intel&#174; Parallel Studio Eval
>Try the new software tools for yourself. Speed compiling, find bugs
>proactively, and fine-tune applications for parallel performance.
>See why Intel Parallel Studio got high marks during beta.
>http://p.sf.net/sfu/intel-sw-dev
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>Archives:
>http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list