FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Unified Polygon Collision System

 
Post new topic   Reply to topic     Forum Index -> ArcLib
View previous topic :: View next topic  
Author Message
clayasaurus



Joined: 21 May 2004
Posts: 857

PostPosted: Fri Jun 30, 2006 10:24 pm    Post subject: Unified Polygon Collision System Reply with quote

I just found some really nice tutorials on how to model and respond to the collision of polygons, and it even includes a rigid body dynamics system. http://uk.geocities.com/olivier_rebellion/Polycolly.zip . It includes binaries as well.

What I'm thinking is that I do not need 3 different types of collision systems (Circle, Box, and PerPixel/Polygonal) but all three can rather be replaced by plain old polygon collisions. Using only polygons I can do some cool physics stuff. Of course I can check using Box collision before I check using polygon collision, and I'll keep all my old CircleBox collision functions around just in case.

The question would become... how would the polygons be defined?

1) Create an algorithm to automatically create a polygon for each frame of the sprite.

2) User defined polygons, the user defines a polygon for each frame in the sprite.

3) Use 1 general polygon outline no matter what the animation of the sprite is

4) Instead of animations through different frames, mimic 3D models which have the vertecies move. This could also be useful to 'explode' the polygon into a bunch of seperate pieces, and would allow for 'Gish' like effects.

[edit]
I think what I should do is a combination of all of the above. I could use an algorithm _or_ allow the user to define an outline for each frame of the polygon. I'll also give the user access to the verticies of the polygon for 'deformation' effects and allow the user the split the polygon into a subset of smaller polygons for 'explosion' or 'ice cracking' effects. I'll limit it so the user can only use 1 polygon to represent 1 image.

~ Clay


Last edited by clayasaurus on Sun Aug 13, 2006 5:16 pm; edited 1 time in total
Back to top
View user's profile Send private message AIM Address
Lutger



Joined: 25 May 2006
Posts: 91

PostPosted: Tue Jul 04, 2006 4:57 pm    Post subject: Reply with quote

Good find, I like it. It seems you have quite some good stuff planned for arc, seems like a lot of work I hope you will get it done Wink
Beyond aabb and alpha pixel testing I have never done anything with collision detection, so this may be a good tutorial for me to study if I can wrap my head around it - and find some time...

Did you ever take a look at the clanlib library? There's a lot of fancy collision detection (2D) in there, i think it covers all of what you propose and some more.
Back to top
View user's profile Send private message
clayasaurus



Joined: 21 May 2004
Posts: 857

PostPosted: Tue Jul 04, 2006 11:28 pm    Post subject: Reply with quote

Lutger -

These collisions are absolutely amazing, I'm guessing that clanlib only provides 'static' 2d collision, but this 2D collision is not only rock solid (it doesn't matter how fast your objects are moving), but it comes with its own top-notch physics system. You'll be able to do ragdolls and have objects interact in 2D just like they do in those new 3D games. You'll be able to create 2D Halflife 2 games Razz

As for the work, it is cut out for me but I'm getting there at a decent pace.

As for the rest of ClanLib, it is 'somewhat' similar to what I'm doing with Arc but with my library I'm going to try to go the extra mile while being D native.
Back to top
View user's profile Send private message AIM Address
clayasaurus



Joined: 21 May 2004
Posts: 857

PostPosted: Sun Jul 09, 2006 11:23 pm    Post subject: Reply with quote

So far I have perfect polygon collision for rotating and fast moving objects, now I just need to get the physics to work correctly as I am having a little bit of trouble with it.
Back to top
View user's profile Send private message AIM Address
clayasaurus



Joined: 21 May 2004
Posts: 857

PostPosted: Mon Jul 10, 2006 5:57 pm    Post subject: Reply with quote

Arc users, get ready for ...

2D Polygon Swept Ridig Body Dynamics!

I got it ported to D with success after hours of bug hunting!

/me crawls back into cave Wink
Back to top
View user's profile Send private message AIM Address
Lutger



Joined: 25 May 2006
Posts: 91

PostPosted: Tue Jul 11, 2006 8:32 am    Post subject: Reply with quote

You finished it already!! Very Happy
Cool stuff, I'm going to play with it, it's in trunk/polycoly/rigidbodycollision right?

EDIT: yay I could build the demo, it is awesome! Thanks for this.
Back to top
View user's profile Send private message
clayasaurus



Joined: 21 May 2004
Posts: 857

PostPosted: Tue Jul 11, 2006 9:09 am    Post subject: Reply with quote

I finished porting it to D, now I just have it add it to Arc and get Sprite to play nicely with it. Once I get Arc to tame it, I'll get a demo out and show its API to you folks and see what you think of it.
Back to top
View user's profile Send private message AIM Address
Lutger



Joined: 25 May 2006
Posts: 91

PostPosted: Tue Jul 11, 2006 9:59 am    Post subject: Reply with quote

Well I had to check it out...
I'm already happy with this, I'm not too good on the math and physics side so to have this code and that tutorial will help me a lot.

One question, would you think it is possible to eventually have an algorithm that can 'deduct' a (number of) polygons (it has to be concave right) from a sprite, given a texture with alpha channel or color key?
Back to top
View user's profile Send private message
clayasaurus



Joined: 21 May 2004
Posts: 857

PostPosted: Tue Jul 11, 2006 10:34 am    Post subject: Reply with quote

It should be very possible to allow the game to define a polygon algorithmically and I will add such a feature, however I doubt it will be comparable to human judgement.

[edit]: the code will not work for convex polygons, but I might be able to add some code to translate convex polygons into a subseries of concave polygons.

[edit2]: turns out I have some some bugs in this new collision system.

#1) NaN's are viral, sometimes every float turns into an NaN and then objects dissapear

#2) My user defined triangle (which are always concave) is having troubles colliding :-/

I hope I can get these bugs sorted out. I also implemented a simple system to change the gravity direction and strength or to turn gravity off.

[edit] I'm learning there are some weird rules I don't understand about the position of the polygons points in order for the polygon to collide properly

[edit] I think I'm going to devise a 'work around' for now, however it will leave a limitation or two.

#1) No artistic license in manually creating polygons manually (since there is some weird formula to it that I am unable to reproduce)

#2) Only 'box' , 'triangular', or 'circular' shapes are going to work for it. However, these can not be user defined as user defined ones will not work (tried it and it was broken)

#3) Every image/s will need a special offset vector manually defined based upon the image

With these tradeoffs (that may be resolved in the future), comes a very nice physics system however.

I think I will create a Sprite editor to ease the pain a bit. Now in order to create my sprite editor, I'll start to work on my GUI system. *vicious circle*
Back to top
View user's profile Send private message AIM Address
clayasaurus



Joined: 21 May 2004
Posts: 857

PostPosted: Sun Jul 16, 2006 6:36 pm    Post subject: Reply with quote

Good news! The bugs I found in the physics system are not from me but the author of the system, and he is working on creating a new algorithm that will work fix it.

Apparently, the system should be able to work with concave polygons as well.

So hopefully the new algorithm won't take the author very long and I get it implemented before the next release, otherwise I'll provide somewhat of a workaround until it gets fixed.
Back to top
View user's profile Send private message AIM Address
clayasaurus



Joined: 21 May 2004
Posts: 857

PostPosted: Mon Aug 07, 2006 2:44 pm    Post subject: Reply with quote

The author's fix turns out to be broken as well. Here is my plan.

1) All polygons will be stored as a mesh of triangles, this allows for concave polygons. Right now I already have 'triangulation' out an outline of a polygon into a series of triangles, from code I got from flipcode. The other way would be for the user to define each triangle by themselves, this would allow for 'holes' unlike my triangulation algorithm.

2) Slowly work my way up to a full collision system using the authors sources for help. I will at _least_ have swept of multisampled collision detection, and at best have a full fledged physics system.
Back to top
View user's profile Send private message AIM Address
clayasaurus



Joined: 21 May 2004
Posts: 857

PostPosted: Sun Aug 13, 2006 5:15 pm    Post subject: Reply with quote

I am sad to announce that the 'new' code fix is slightly broken enough that I've decided to not use it in my library.

I'm sorry for all the hype around this, at first glance it seemed the code worked, but it only works under special circumstances.

Here's what I'm going to do...

Instead of PerPixel collision, I'll replace that with static polygon collision that will allow for all shapes of a polygon.

It will be a slight improvement, but not as great of a leap as I'd hoped for. This means no grand unified physics theory. Maybe in the future. *sigh*

~ Clay
Back to top
View user's profile Send private message AIM Address
Display posts from previous:   
Post new topic   Reply to topic     Forum Index -> ArcLib All times are GMT - 6 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group