3d collision

Member
Posts: 567
Joined: 2004.07
Post: #1
this is a quick jump from sprites two days ago, but collisions with 3d? (i'm using .obj, but that shouldn't matter). Sad I could spend the time searching google, then proting it to my engine but I only have three weeks. Smile Any links?

It's not magic, it's Ruby.
Quote this message in a reply
DoG
Moderator
Posts: 869
Joined: 2003.01
Member
Posts: 156
Joined: 2002.11
Post: #3
Flipcode.com has not being updated in a while, but the forum is still up and there are some useful tutorials over there. Also, Gamasutra.com is full of useful articles, you might get better luck with the old ones, from 2+ years ago (registration required, but it's free).
Quote this message in a reply
Member
Posts: 304
Joined: 2002.04
Post: #4
Quote this message in a reply
Member
Posts: 567
Joined: 2004.07
Post: #5
I like codemattic's suggestion; but do i check every polygon on the object for collision?

It's not magic, it's Ruby.
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #6
Here's what you want:

http://www.ode.org

And specifically:
http://www.ode.org/ode-latest-userguide.html#sec_10_7_6

I use ODE for all my physics and collision detection, but ODE doesn't *require* you to use its physics, you can use it as just a collision detection mechanism. ODE's trimesh collision system, while not on par with commercial engines like HAVOCK, is still fast, correct, and easy to use.

That said, the learning curve is steep.
Quote this message in a reply
Member
Posts: 567
Joined: 2004.07
Post: #7
Thank you, that would be great, but I don't want an engine (of someone else). I would prefer to use all my own work. Thank you again, though!

It's not magic, it's Ruby.
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #8
Nayr Wrote:I like codemattic's suggestion; but do i check every polygon on the object for collision?

if you're going to roll it yourself you'll have to either a) Check all polys against all polys/rays every time you check, or b) Come up with a partitioning scheme so you can pre determine what potential intersections may be possible.

Most will take a sort of quadtree/octree partitioning scheme for the "world" and will use axis-aligned bounding boxes ( AABBs ) to do quick potential intersection calculations. Then, when you have sets of potential intersections you can perform the computationally intensive work on a massively pruned amount of data.

Of course, if you've only got a handful of polygons to intersect, you can probably do away with the space partitioning. Consider though that while the intersection math is simple enough, your set of polys to check against will grow exponentially as you add more polygons. It's probably worth your time to write a scene-graph of sorts early on, it'll save you time in the future.
Quote this message in a reply
Member
Posts: 184
Joined: 2004.07
Post: #9
Nayr Wrote:I like codemattic's suggestion; but do i check every polygon on the object for collision?

If you're trying to code this from scratch, I would first suggest you write code that, given two triangles, check if they intersect, and make sure it works. This is fairly easy since there's a lot of code out there you can take as an example.

Then use that simple method (check every polygon on one, vs every polygon on the other), make sure it works. Of course, this is really easy since you just have two for loops running the triangle collision.

Depending on what you want to do, this may actually be fast enough, and then you'll be done, especially if you simplify your collision models. If it's not fast enough you are going to have to spend a lot of time working on geometrical data structures such as bounding box trees or BSP trees- of these probably the axis-aligned box trees (like an octree) are easiest to implement.

There's another fast way to do mesh-mesh collision detection, which is to use the 'separating axis/plane' theorem. If two 3d convex meshes do NOT intersect, then there is a plane that lies on one of the faces of one of the meshes that separates the two meshes. So for each face on each mesh, just check if all vertices of one mesh lie on one side, and all vertices of the other mesh lie on the other side. You have to of course either always use convex meshes, or break your concave meshes into convex pieces.

Now, if you want accurate physics functionality, here's how ODE and most rigid physics simulators works- you test if the two models intersect and now you have a number of collision points and associated penetration depth for the intersection. For each of the collision points, you apply a force proportional to the penetration depth. How do you compute these things? For mesh-to-mesh it's quite difficult to compute, so most games use only convex proxy colliders to represent more complicated objects (for example, a cylinder is a concave object that represents an upright person reasonably well.)
Quote this message in a reply
Member
Posts: 23
Joined: 2002.08
Post: #10
I originally learned a lot of my intersection tests from Paul Bourke's Geometry page, so I'll always suggest that. However, once you get past testing a handful of triangles, you definitely need to partition somehow.

Honestly, my first collision detection system consisted of a bunch models and I'd do bounding sphere intersection tests between them, then do triangle-triangle intersection tests between them (if the bounding spheres collided, of course). Very rudimentary, but works to get you started. Once you get past a couple low polygon models, again, you need to do some major rethinking about how you're going about the process.
Quote this message in a reply
Post Reply