Jump to content
  • Advertisement
Sign in to follow this  

Broadphase collision detection

This topic is 2789 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

My apologies for a long post, i've tried to keep it as short as possible.

a) My game is in 3D.
b) Any dynamic actor (player, enemy, npc) is represented by a sphere.
c) Any static or dynamic environment object is represented by a polyhedra constructed using triangular faces. By dynamic im refering to an object capable of changing origin or size, not shape.

For my narrow phase collision detection between actors and the environment I use a 'swept sphere vs triangle' test for each individual triangle of each individual environment object. This works perfectly and I have no issues. Now I need to implement a broadphase collision detection.

I figure it will run in two phases:

phase 1) determine which environment objects have a potential for collision.
phase 2) determine which triangles have a potential for collision

My questions are as follows:

a) I figure I can use spheres to generalize the information for each of these two phases. Therefore within each collidable object, along with its vertices and triangle indexes i would:

phase 1) store the sphere radius that would contain all vertices of the polyhedra collidable.
phase 2) store an array, each element corresponding to a radius that would contain an entire triangular face.

For static environment objects these values would never change. For dynamic they would have to be scaled/translated based upon size changed or movement. Any forseeable issues with this? Any opinions on a more efficient method?

b) Should I used sweep and prune or octrees (or maybe a different method)? I figure using octrees to partition the triangular faces of static environment objects would be most efficient, as they only need to be generated once. This could also be used to partition the entire static objects as they never move around the scene. Im not sure what to do about the dynamic environment objects though. Any suggestions?

c) Im not exactly sure how you determine whether a potential collision will take place. Since the actors are represented as spheres, would i simply create a 'capsule' swept sphere shape and any objects/faces that intersect must be passed to the narrow phase detection?

Thanks for the help!

Share this post

Link to post
Share on other sites
[font=georgia, serif]I found that sweep and prune is the best technique, especially if you take advantage of available efficiencies. I found that performing the sort on only one axis is best. Sometimes this axis never changes, and I've found the x-axis is almost always the best to sort on (the z-axis being "toward the zenith"). When you find two objects overlap on that axis, just check for overlap of the AABBs on the other axis. Or if one or both objects are spheres, that test is slightly better and faster.[/font]

[font=georgia, serif]Other efficiencies to note. Keep a bit in every object that is set when the object is "modified" (moved, rotated or deformed), and cleared before the next frame (perhaps in collision detection when tests on it are finished). If that bit is not set in two objects, those objects did not collide, and you need not perform any more tests on them. You can test those bits before you check for overlap, or you can check for overlap on the first axis, then check those bits and then exit further testing immediately unless one or both of them have their "modified" bit set.[/font]

[font=georgia, serif]The sort of objects on your master objects do not change very often, since most objects do not move, or do not move very far since last frame. Therefore keep that sorted array around (the array with begin and end markers for each object) and perform an insertion sort (or even better, a merge sort) of that array next frame with new object positions.[/font]

[font=georgia, serif]If you implement the above efficiencies on top of the minimalist (one-axis) "sweep and prune" technique, you'll be amazed how fast and efficient that is.[/font]

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!