• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
sqwerty

OBB-OBB Collision data

7 posts in this topic

Note: 3D not 2D

OBB-OBB (oriented bounding box) intersection tests are fairly well covered (separating axis) but I can't find much information about generating intersection data (contact point, normal, penetration depth) for collision response.

I'm using a separating axis test to determine whether or not they are in contact. If they ARE I need to generate collision data. This is what I have/know currently.

for vertex-face collisions:
Test each vertex of each box against the other box to see if it lies within its boundaries. If it lies within the box's boundaries use the closest face's normal as the contact normal, and the distance to that face as penetration depth. This seems fine although it seems like a lot of tests? (16, one for each vertex on each box)

for edge-edge collisions:
Test each edge from each box against each other. This is what I'm not too sure about. The only method I can find is to do a test on each edge line to find the closest points on each. Then determine if these points lie on the segments of the lines that make up the edge. If so test whether point a is closer to the center of body b than point b, and vice versa. This seems massively inefficient. 12*12 = 144 tests, and it's a pretty expensive test.

Can anyone shed any light (or links) on this?



Cheers

edit: numbers
0

Share this post


Link to post
Share on other sites
One approximate way to generate contact points between two convex polyhedra A and B, is the following recipe:

1) find a separating axis between A and B using your favorite method (SAT, GJK etc)
2) find reference face on A and a incident face on B with a normal that is closest to this separating axis
3) perform Sutherland-Hodgman clipping on the vertices of this face on A against the polyhedron B
This clipping can be performed either in worldspace or in the local space of B, using the faces connected to face B

I recently implemented this method in the open source Bullet physics library, part of the Bullet 2.78 release, so you can test the implementation and read the code here:
[url="http://code.google.com/p/bullet/source/browse/trunk/src/BulletCollision/NarrowPhaseCollision/btPolyhedralContactClipping.cpp"]http://code.google.c...actClipping.cpp[/url] in particular [font="Monaco,"][color="#000000"]btPolyhedralContactClipping[/color][color="#666600"]::[/color][color="#000000"]clipHullAgainstHull and [/color][/font][font="Monaco,"]clipFace.[/font]
[font="Monaco,"] [/font]
[font="Monaco,"][color="#000000"]For general convex polyhedra you need to compute the connectivity and connected faces ([font=Monaco,]m_connectedFaces in above code), Bullet uses the btConvexHullComputer for this. For the special case of OBB-OBB this information can be hard-coded, you can see the OBB-OBB clipping code in ODE/Bullet here: [/font][/color][/font][font=Monaco,][url="http://code.google.com/p/bullet/source/browse/trunk/src/BulletCollision/CollisionDispatch/btBoxBoxDetector.cpp#574"]http://code.google.com/p/bullet/source/browse/trunk/src/BulletCollision/CollisionDispatch/btBoxBoxDetector.cpp#574[/url][/font]
[font="Monaco,"]
[/font]Thanks,
Erwin
1

Share this post


Link to post
Share on other sites
Just to echo what Erwin said, you shouldn't need to do any sort of search to find the intersecting features. Since you know the 'intersection axis' (that is, the axis corresponding to the minimum penetration depth for the discrete test, or the 'axis of last intersection' for the continuous test), you can find the features that will intersect (they'll be the supporting features of the boxes with respect to the axis and its negative).

Once you have the supporting features, you can then clip them together to yield the contact manifold.

Also, if all you need is the penetration depth, you can skip all that (the penetration depth and direction can be derived directly from the results of the discrete test).
0

Share this post


Link to post
Share on other sites
Thanks for the replies.

For SAT, by separating axis do you mean the axis on which the projections show the least penetration/overlap.
For GJK how would you go about finding such an axis? My understanding of GJK was that it is just a true/false intersection test.

Also I've seen posts of people describing modifications to the GJK algorithm to find actual collision data. Is that an acceptable approach or is it simpler/better to just use clipping. Only because I haven't looked into clipping and it seems like it may just be simpler to just look into the GJK modification if it's a reasonable alternative.


cheers
0

Share this post


Link to post
Share on other sites
Gjk gives you a separating axis, distance and closest points if objects don't overlap. It requires an additional algorithm for the penetrating case, such as SAT or expanding polythope algorithm (EPA). Still, this only gives you an axis (normal) and a single point.

To gather multiple points for polyhedra, you better simply combine SAT and clipping.

An alternative to clipping is contact caching, where you add a contacts to a small cache, and update this cache (in Bullet this is called a persistent contact manifold). You can use any method to add contacts to this cache, including GJK/EPA. GJK/EPA/contact caching is more complicated but also more generic, it can deal with a wider range of shape types. For example implicit (not tesselated) cylinders, cones etc. Bullet implements all those methods, so you can compare.

Is the SAT/clipping idea clear?
0

Share this post


Link to post
Share on other sites
I guess the GJK implementation I looked at must have been a refined one. I'll probably take the SAT/clipping approach anyway as it seems simpler at this point. Computing the connected faces seems like it may be painful to implement, but I'll just hardcode it like you mentioned for the OBB-OBB case for the time being.

Just to clarify:
1) Use SAT to find the axis showing least penetration (which is also the contact normal and penetration depth)
2) Find the faces from A and B with normals closest to the separating axis and its negative.
3) Perform clipping on A face using B face + connected faces as the clip geometry

From here the contact points are the new vertices created in the clipping process?

Is this right?

One more question. jyk mentioned doing continuous intersection testing. Do you have the name of a good algorithm for this?


cheers
0

Share this post


Link to post
Share on other sites
[quote name='sqwerty' timestamp='1302791762' post='4798408']
Just to clarify:
1) Use SAT to find the axis showing least penetration (which is also the contact normal and penetration depth)
2) Find the faces from A and B with normals closest to the separating axis and its negative.
3) Perform clipping on A face using B face + connected faces as the clip geometry[/quote]
That sounds right, except that the features can be faces, edges, or vertices, rather than just faces. Also, I'm not sure there's any need to concern yourself with connected faces.

You'll generally have some [i]a priori[/i] knowledge about the axis and supporting features that can be leveraged. For example, if the axis is a coordinate frame axis from one of the boxes (as is often the case), you know that the supporting feature for that box will be one of the two faces for which the normal is parallel to the axis. Also, I'm pretty sure that if the axis is an edge cross-product axis, the supporting features will be the two edges in question (it's been a while since I've implemented such a system though, so I might be forgetting something or other).

I remember that when I implemented this (for OBBs), the supporting features other than those known [i]a priori[/i] were found by analyzing the components of the axis transformed into the local space of the box. Generally speaking, if two of the components of the transformed axis are near-zero, the supporting feature is a face; if one of the components of the transformed axis is near-zero, the feature is an edge; and if no components are near-zero the feature is a vertex. Furthermore, the signs and values of the components tell you which feature should be selected.

[quote]One more question. jyk mentioned doing continuous intersection testing. Do you have the name of a good algorithm for this?[/quote]
'Continuous' is probably as good a term as any, although 'swept' and 'dynamic' are sometimes used as well. (A search for 'obb continuous sat' or 'obb swept sat' would probably turn up some relevant info.)
0

Share this post


Link to post
Share on other sites
I decided to go ahead and code connected faces and clipping in properly. I figured this way it's more robust and if I extend my SAT implementation to handle arbitrary convex polyhedra I can use it for more than just box-box collisions. I don't think it was really much more work anyway.

Thanks for all the help.
0

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  
Followers 0