How to do polygon collision detection?!?!

Coding Python Support
1

Hiya guys.
I was pretty bored last night, and as per normal, my mind started wandering towards Blender. I started thinking about how to do polygon collision detection in Blender.

Up until this point (unless I’m wrong - please correct me if I am), we’ve only been able to detect collisions through ‘bounding spheres’ - that is, we assume that an object is roughly spherical, and calculate to see if any object lies within the bounding sphere that we’ve defined for this object. It’s not particularly elegant, though, since the majority of objects that we make in Blender aren’t spherical. Most aren’t even close. Sure, you can model collisions using a collection of spheres for sub-parts of the object, but it’s messy, and you end up with the same results anyway - unrealistic collision detection and sloppy looking animations.

The script I was thinking about would probably be far too large/slow for GameBlender, but I think it might just be possible for animations…

Right, it works like this. First you need to define what objects you want to monitor for collision (eg. an if statement seeing if any of the objects are within an arbitrary distance of each other, say 5 units).

Now this is the part I thought up last night. What if you checked for collisions by comparing the position of each vertex in the ‘collidor’ object against the face position and normal angle of each face in the ‘collidee’ object? I know the math would be quite complex, but by knowing the face centre (eg average the positions of the vertices that make up that face) and using the face normal, you would be able to calculate if the vertex falls in front of or behind the face in question - ie see if a collision has taken place.

Obviously, you’d only be able to count it as a collision if the vertex was within a fairly small distance of the face (otherwise you’d get faces on the opposite side of the object registering collisions!). Either that, or you only measure faces which are on the same side of the object centre as the vertex in question is. Both would achieve the same effect.

Now this obviously wouldn’t be very good in GameBlender because of the sheer size of the script - you’re checking the position of each vertex in one object against the position and normal of each face in another object - for dense objects this would be far too slow for decent frame-rates. It would only work on one side of 2 dimensional objects eg. planes/triangles. But for scripts that simply need to know when a collision is happening on complex objects (eg. physics scripts) and need realistic results, then this script would be ideal.

I think that this idea could really go somewhere. What do you people think? Is the idea feasible, or is there some sort of basic principle I’ve just completely missed (it wouldn’t be the first time!! :wink: )

So, comments?

LethalSideParting

2

you should bring this to the dynamica crew. Supposedly they wanted to make real collision detection at some point, but I’m not up to date on all that stuff so don’t take my word for it. Anyway, I would love to see this in blender as it would be a fairly excellent animation tool. Anyway, it should be done at some point. Good idea man, but it’s probably not a new idea, just new to blender…

3

Eeshlo already did some C code for collision detection. However, it’s based on face/face collision, which is more accurate. He was also working on a sphere/face collision detection code. To be included in Dynamica.

Martin

4

Hmmm…Being written in C, it will be a lot faster than the python interpreter…but that also means that people won’t be able to put collisions into their scripts (unless I’m mistaken…?). I was thinking that maybe someone could develop this as something other people could put in their scripts. I can handle maths for working out this sort of stuff, but I’ve never really studied physics in any great detail. This is my reasoning behind it - all sorts of interesting stuff could open up in the simulation world for Blender if people were given the collision stuff pre-made for them in python.

If someone wants to develop this idea further - a collision detector using this idea - then feel free. If I have a lot of spare time this summer (very unlikely!!!) I may give it a hack, coz I can handle the maths involved in it…If anyone else needs some help with the math here, I’ll be only too glad to help. Well, hopefully this won’t be the last you’ll hear of this…

LethalSideParting

5

it is a Python/C extension, so yes, it works with scripts.

Martin

6

man, eeshlo is a genius… just thought I would restate the obvious.

7

lethalsideP’s idea is not new.i thought of it sometime ago.it has a problem though.when a collision is taking place you would probably want the colliding vertex to be moved far from the other object.to which direction would you move it?how would you know which direction was it coming from?i thought of recording all the locations of the vertex before the collision via array but it could not solve the problem.can you solve it?

8

Yo Kos. That’s an interesting way to try and get a collision vector you mentioned, but it does rather strike me as like using a sledgehammer to crack a walnut. There’s a much easier way - just compare the location of the colliding vertex in the frame the collision takes place and the frame before. Compare the difference, and viola, you have a vector. As for the maths of knowing where to reflect the object, that’s a bit harder. I do know the math to do it, but I don’t really have time to write it now (I’d need to sit down with a piece of paper for an hour or so anyway just to be sure). If you WOULD like to see the maths here post a reply saying so - I’m not gonna work on a problem like that for an hour if no one wants to see it!!!

And regarding the C script…Hmmm, this raises several possibilities. I didn’t know C scripts could be run inside a Blender python script. How d’you do it?

Thanx y’all.
LethalSideparting[/quote]

9

I didn’t know C scripts could be run inside a Blender python script. How d’you do it?
It doesn’t have anything to do with Blender, it’s an ability of Python. That’s why they are called Python/C Extension. they are exactly like Python modules, but written in C (with a special structure).

Martin

10

ya lethal i knew it almost half a decade ago…but how do you record a vertex’s LocX etc in each frame?

11

no need. the collision code is just telling you “YES a collision has occurred”. you just need the object’s changing Loc & Rot values, and maybe the Loc values of the object it collides with, to figure out the reaction event.

BEAT

12

thinking cloth script, what about vertex keys?

13

ya lethal i knew it almost half a decade ago…but how do you record a vertex’s LocX etc in each frame?

Well, first you have to gain access to the mesh and the vertex you want to measure using the NMesh module. Then, once you’ve got your vertex, do the following:

 Locationx=myvertex.co[1]

The .co function returns a list with three floats in it - location x, y and z. Use this to get the location of the vertex. It may need a square or curly bracket, I can’t remember. I’m not sure if the coordinate it gives you is local or global, so if you’re after a global coordinate once you’ve done that bit of code you may need to do this:

 Globallocx=myobject.locx + Locationx

Hope this helped, Kos. And by the way, Beatabix is right - don’t go trying to do physics for each individual vertex, or you’ll end up in a world of pain!!! Just use the physics on each object, and use this vertex idea to do collision detection.

And regarding the cloth script idea, yes, i think this idea could be used for that eventually (though I’m not sure whether you can set vertex keys and the like in Blender 2.23 - ask theeth, he knows everything python related!). I think we’d have to start out with basic physics scripts first, but cloth could be done eventually.

Wow, quite a response here. Maybe this’ll go places…???

LethalSideParting

14

And regarding the cloth script idea, yes, i think this idea could be used for that eventually (though I’m not sure whether you can set vertex keys and the like in Blender 2.23 - ask theeth, he knows everything python related!). I think we’d have to start out with basic physics scripts first, but cloth could be done eventually.

there’s no access to RVKs, but you can still modify the mesh data in real time

pssst: http://www.centralsource.com/blender/dynamica/

Martin

15

Yo, Theeth - now that we’ve seen all that great news about Blender going opnesource (see News forum for those of you who’ve been living in a cave) - is there any chance you could let the Blender community include that C collision module in Blender itself? In fact, scrub that - any chance you could just put Dynamica into Blender full stop? I know it would have to be recoded into C++, but still…any word from the Dynamica team about this?

Thanx,
LethalSideParting

16

In fact, scrub that - any chance you could just put Dynamica into Blender full stop? I know it would have to be recoded into C++, but still…any word from the Dynamica team about this?

that’s on our to do list :slight_smile:

Martin