[LWJGL] 3D Collision

Game Mechanics
#1

I’m writing a 3D Gaming library in conjunction with LWJGL for future use. I find myself spending more time on programming the same thing over and over again for each project I decide to start, so a library seems like a good idea. I actually used the incomplete library for Ludum Dare 35 and it worked great!

I’ve got models, shaders, etc etc support in my library. Tons of rendering tools. However, I’ve yet to set up any sort of physics portion of the library and had to resort to AABB collision detection for LD35, and I’d really like to get started on that before I go deeper into rendering with animation/lighting and stuff. Any ideas on how I would start on collision-detection for 3D models?

Here are some thoughts but I truly have no idea. I’ve always shied away from physics anytime I do something in 3D because I have no experience with it.

So my thoughts:
My library makes use of entities. Each “Entity” has a number of rendering components. My thoughts are I should add two more components to a class extending an Entity that allows for physic calculations. I say two because I’m thinking a simple collision model with far fewer vertices than the model being rendered, and then a more complex collision model that more closely resembles the model being rendered. This seems like a good idea (I think? No clue :)), but even with this basic concept I still have no idea how I’d go about detecting collision between two 3D models that aren’t mathematical shapes (pyramid, cube, etc). Then that begs the question should I handle collision differently for models generated from heightmaps? The heightmap model is stored temporarily in the same format as a Blender OBJ model for rendering, but image-data is stored as well in case I ever need it for collision. There are so many things I don’t know that I don’t know where to start either.

Could someone please advise or point me in the right direction? Thanks, any and all help is appreciated! :slight_smile:

Oh! And here’s a screenshot of a game I made in 48 hours using what I’ve written with the library so far! Library is extremely early in development but it was still great seeing it work and be able to produce something. :stuck_out_tongue:

#2

This is where reinventing the wheel doesn’t really make much sense. Trust me i know. I would just use the jMonkey engine. If you really don’t want to use the whole thing. Then just use its collision code. I mean like 2 lines of code and i am done.

#3

That’s not the point, though. The reason I start whatever project I’m working on at the time isn’t just for fun, it’s to learn. I want to learn how all this stuff works so that I can implement it in my own way rather than straight-up use another library or someone’s code.

#4

Everyone goes through that phase once in life. :slight_smile:
But when time becomes the limiting factor (or generally “opportunity costs” becomes high enough) then you end up with: Just use someone else’s code. :wink:
But when you want to learn how everything works then my advice would be: Still use someone else’s code and learn from that.

#5

I suggest this paper: http://www.peroxide.dk/papers/collision/collision.pdf. Correctly implemented, it gives you proper ellipsoid->polygon collision detection which should work fine in your case.

#6

If you want to go the hard way. Which i did once, as well as write a ray tracer for shits n giggles. You have a huge set of different algorithms that are designed to be efficient in particular cases.

However all (almost) share one feature. You prune the number of pairwise checks you need to do. Typically with some spacial data structure, say a quad tree for “2.5D” cases like an RTS or even FPS. Or a full oct tree for true full 3d. jME uses the scene graph for this (I think).

Now your down to a reduced set of pairwise checks you still do some fast pruning. For example use a bounding spheres and check if they overlap. If not discard.

Now you do the real checks. This can use full math based collision if the geometry is mathematically defined (ie constructive geometry). Or polygon methods for polygon data. Polygon data may be further required to be subsets of strictly convex geometry as well. Or just use the convex hull. Typically the polygon data needs to be a specific “collision” structure so different again from what you would send to the GPU.

A good example of this is the “closest triangle” method. I have convex polygon sets A and B. In A i find the polygon closest to B, and in B the same. I keep track of those polygons from frame to frame, updating the closest polygon if needed. Then i just check to see if they “intersect”. Now this is a hard check. There are many edge cases you must consider. But you get the idea. It is easy to see that i want some data structure where each polygon has a list of adjacent polygons. this is not anything like the structure you use for drawing.

There are a lot of papers out there. From the often fairly poorly written game/graphics gems to different well written siggraph papers.

#7

I know of trees/scene graphs for optimization when it comes to collision, but since I’m writing a library and not a game I don’t need any of that. That will be up to the user to determine how/when to check for collisions. Right now I’m looking only for how to actually detect collision between two models (I say model, but that really just means a large set of non-mathematically generated vertices/normals).

#8

I’m just going to reply to my own answer here for other people who may come across this thread in the future, but http://www.euclideanspace.com/threed/animation/collisiondetect is a good resource to get you going in the right direction.

#9

This is a great resource if you want to learn more