It is currently Thu Dec 12, 2013 9:11 am

 All times are UTC

 Page 1 of 1 [ 7 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Polygon collision testingPosted: Fri Nov 05, 2010 10:19 am
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
Hey folks, I'm fiddling with making a small game. The idea is that the game area is a 2D polygon (with arbitrary number of sides), and I want to be able to use either a circle or another polygon for objects within the game area. The points that make up the game area are vectors.

What I want to do is have things stay inside the game area, no matter how it is shaped. This way I can make a "floor plan" with whatever shape I want, and keep everything that belongs inside within that area.

If you have any suggestions (i.e. what to Google, if applicable) or better yet have some ideas on how to implement this type of collision testing, please share.

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Top

 Post subject: Posted: Fri Nov 05, 2010 10:35 am
 Corpse Bride

Joined: Tue Jul 01, 2008 11:44 pm
Posts: 2221
Location: England
The critical test is point crossing line segment, which I'll explain if you want me to.

If there are n points in the boundary polygon, and m points in the object polygon, there would be upto 2n*m such tests doing it by brute force.

There are various ways you can optimise that number.

_________________
I ain't pushing no moon buttons.

Top

 Post subject: Posted: Sat Nov 06, 2010 3:40 am
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
I give up on this. I'm too goddamn retarded to program.

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Top

 Post subject: Posted: Sat Nov 06, 2010 11:27 am
 Corpse Bride

Joined: Tue Jul 01, 2008 11:44 pm
Posts: 2221
Location: England
I've had an unhappy week too.

One method you could use is a "Point Inside/Outside polygon test", aka a scanline test.

Point Inside/Outside polygon test

INPUT: Point P=(x,y) and a polygon.
OUTPUT: True or False, and possibly a normal vector of the collision surface.

1. Consider the point P = (x,y) which we're testing for collisions.

2. Consider the infinite horizontal line through that point. (x from -inf to +inf, at the same y) This is called a scanline.

3. Determine which line segments the scanline passes through. This is simply a case of if one end vertex is >=y and the other end vertex <y.

4. Create a list of those line segments, and calculate the point (x[i], y) where the line segment [i] intersect the scanline.

5. Order the line segments by that x intersect value.

6. Travelling from from left to right along the scanline, we start off outside the polygon. After the first point (x[1],y), we are inside the polygon. After the second point (x[2],y) we are outside the polygon, and so on, alternating in/out.

7. Our point P will be in one of those sectors. Test which one.

We can use this as follows:
If PointInPolygon(x,y) = true and PointInPolygon(x+vx*dt, y+vy*dt) = false then // point tries to exit polygon in this physics step.

If you want normal vectors, those can be calculated extra.

Here's some code...
http://www.ecse.rpi.edu/Homepages/wrf/R ... npoly.html

_________________
I ain't pushing no moon buttons.

Top

 Post subject: Posted: Sat Nov 06, 2010 8:55 pm
 Corpse Bride

Joined: Tue Jul 01, 2008 11:44 pm
Posts: 2221
Location: England
theraje wrote:
I give up on this. I'm too goddamn retarded to program.

Game programming should be a fun thing, but If we over stretch ourselves it only brings us sadness.

Try something less mathematical, theraje. You've said in the past that you think of yourself as an artist, so you might enjoy programming projects that are more about art than they are about mind boggling maths/physics.

If you want a new project, try making a vertical scrolling arcade shooting game, in the style of Slap Fight. There's lots of art there

_________________
I ain't pushing no moon buttons.

Last edited by Jasmine on Sat Nov 06, 2010 11:58 pm, edited 1 time in total.

Top

 Post subject: Posted: Sat Nov 06, 2010 9:08 pm
 Ankle Nibbler

Joined: Tue Jun 29, 2010 6:41 pm
Posts: 129
Nonsense man, you're not to retarded to program. This is a new thing you are trying to achieve, you are simply broadening your understanding in the way of polygons

Collision is no simple task, so I wouldn't scold myself if I were you.

Being the person that I am, if I understand your problem correctly, I would use Rigid Body Dynamics. I suggest you try that if point crossing line segment doesn't work out for you.

As the name states, it is motion of rigid bodies. It has geometrical properties such as center of mass, moments of intertia, relationship of position, velocity and acceleration etc. It is characterized by 6 degrees of freedom. I believe that is what you need.

I would explain it to you but the truth is, it's way to much! Also, I wouldn't be that reliable I tend to forget stuff if I don't use it. So I strongly suggest you check out these tutorials:
http://chrishecker.com/Rigid_Body_Dynamics

Top

 Post subject: Posted: Sat Nov 06, 2010 11:47 pm
 Level 22 Norse Warrior-Librarian

Joined: Mon Sep 04, 2006 5:25 pm
Posts: 517
Location: U.S.
Aw....you're not retarded, theraje

If you're up for using a physics engine to do this, Chipmunk is an awesome physics engine, and I believe it could handle this quite well.

_________________
Worlds at War (Current Project) - http://www.awkward-games.com
Ganadu'r, The Eternal Sage (Other Current Project) - http://rpg.naget.com
Programming tutorials and web-design services: http://www.wyrmmage.com

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 7 posts ]

 All times are UTC

#### Who is online

Users browsing this forum: No registered users and 1 guest

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forum

Search for:
 Jump to:  Select a forum ------------------ Forums    Forum Rules and Posting Guidelines Wiki Discussion    Help    Content Issues Game Programming Discussion    C and C++ Game Programming    Java Game Programming    Language Agnostic Programming    .NET Game Programming    VB Game Programming    Mobile Game Programming    Web-Based Game Programming    Other Languages    OpenGL Development    Direct X Development Game Development Discussion    Game Design    Game Media Off-Topic Discussion    Announcements    Off-Topic    Community Projects    News