Any shape
 slembcke
 Site Admin
 Posts: 4164
 Joined: Tue Aug 14, 2007 7:13 pm
 Contact:
Re: Any shape
Unfortunately no, collisions between concave polygons is fairly difficult problem. You can always split concave polygons into convex ones, but then you have to deal with the "cracks" that other shapes can get caught on. It's not a perfect solution, but it's a free library that I work on mostly in my spare time.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! > http://howlingmoonsoftware.com/wordpress/
Check out our latest projects! > http://howlingmoonsoftware.com/wordpress/

 Posts: 41
 Joined: Mon Feb 14, 2011 7:10 am
 Contact:
Re: Any shape
It is not impossible, so surely it will be included at some point.
Last edited by Mixel on Fri Feb 18, 2011 4:44 am, edited 1 time in total.

 Posts: 41
 Joined: Mon Feb 14, 2011 7:10 am
 Contact:
Re: Any shape
Any polygon can be created using segments, so why is it difficult to implement?
 slembcke
 Site Admin
 Posts: 4164
 Joined: Tue Aug 14, 2007 7:13 pm
 Contact:
Re: Any shape
For one, segment shapes don't collide with other segment shapes. Secondly, even if they did the segments would collide individually with other segments. The shape would be hollow and there would be a high chance that you would get shapes stuck inside of each other.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! > http://howlingmoonsoftware.com/wordpress/
Check out our latest projects! > http://howlingmoonsoftware.com/wordpress/

 Posts: 41
 Joined: Mon Feb 14, 2011 7:10 am
 Contact:
Re: Any shape
Could you explain why concave shapes are not possible.
 slembcke
 Site Admin
 Posts: 4164
 Joined: Tue Aug 14, 2007 7:13 pm
 Contact:
Re: Any shape
They are possible, but they require you to break them down into convex polygons.
The reason why they are difficult is because they don't have any of the properties that make convex polygons simple to work with like the separating axis theorem. Not only is collision detection with concave polygons, but generating contact data (collision points and normals) is also very difficult.
The reason why they are difficult is because they don't have any of the properties that make convex polygons simple to work with like the separating axis theorem. Not only is collision detection with concave polygons, but generating contact data (collision points and normals) is also very difficult.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! > http://howlingmoonsoftware.com/wordpress/
Check out our latest projects! > http://howlingmoonsoftware.com/wordpress/

 Posts: 4
 Joined: Sat Mar 26, 2011 10:44 am
 Contact:
Re: Any shape
Have you thought about creating a special type of shape for envelopes?
Use Case 1: Curved boundary
I've just read this:
I imagine that it would be a composite of special line segments: infinite in length and solid on one side. I propose cpLineBoundry.
I'm thinking on my feet now but is it possible to create such an object with an infinite area triangle? I.e. A cpPolyShape with vertices {{0,INFINITY}, {0, INFINITY}, {INFINITY, INFINITY}}, thus creating a boundary that collides with any object with nonpositive x position. What would the consequences of this be? I guess it would be impossible to rotate...
I digress, the constructor would need three inputs:
Where y = a.x + b and outside would specify a y coordinate in the solid area of the object.
E.g.
Would create a horizontal wall preventing an object to pass 'below' 0.0 (assuming up is positive).
A special case would be needed for a vertical boundary:
Alternatively, (better now that I think of it) the line could be specified with two 'vertices' that lay on it or the line's axes interception points:
An envelope could be created with many cpLineBoundries. Technically an envelope should be specified with an equation and resolution (defined as either the number of lines or step interval along the x axis, assuming a cartesian equation). Better yet, use a parametric equation with values supplied via user callback function. Better yet, define some sort of cpPath (too complex? KISS). Or just leave the implementation up to the user (I mean developer).
Scott, is cpLineBoundry possible? I don't know the ins and outs of collision detection... I guess it doesn't have a bounding box and would need special consideration. If you give me a few pointers I'd have a crack at it if I can find the time.
Use Case 2: Concave Shapes
Assuming that cpLineBoundry exists would it then be possible to define cpLineBoundrySegment? Whereby a bounding box is given to a cpLineBoundry and the line is 'oneway'. Meaning that collisions only occur if the colliding shape approaches the line in the 'right' direction and if the colliding shape was in the solid region of the bounding box then it must pass through as if there were no boundary.
Imagine, building a shape with boxes where only one side of the box had any effect! This would allow a concave surface and convex polygons come to think of it.
I guess calculating moment of inertia and torque would be difficult, I dunno...
I suppose cpLineBoundry could be approximated with a cpLineBoundrySegment (if it made the math easier).
What do you think? Is the math for this hard (nontrivial, computationally expensive)? I would love to see this addition to the already excellent chipmunk library!
Use Case 1: Curved boundary
I've just read this:
samtny was using line segments. I think this use case would be the most popular.samtny wrote:when the ball is moving at high speed towards a curved "turn in the road", the ball tends to "stick" in the wall of the curve and bounce backwards, instead of proceeding smoothly around the curve at high speed.
I imagine that it would be a composite of special line segments: infinite in length and solid on one side. I propose cpLineBoundry.
I'm thinking on my feet now but is it possible to create such an object with an infinite area triangle? I.e. A cpPolyShape with vertices {{0,INFINITY}, {0, INFINITY}, {INFINITY, INFINITY}}, thus creating a boundary that collides with any object with nonpositive x position. What would the consequences of this be? I guess it would be impossible to rotate...
I digress, the constructor would need three inputs:
Code: Select all
cpLineBoundry * cpLineBoundryInit(cpLineBoundry *shape, cpBody *body, cpFloat a, cpFloat b, cpFloat outside)
E.g.
Code: Select all
cpLineBoundryInit(shape, body, 0.0f, 0.0f, INFINITY)
A special case would be needed for a vertical boundary:
Code: Select all
cpLineBoundry * cpLineBoundryVerticalInit(cpLineBoundry *shape, cpBody *body, cpFloat x, cpFloat outside)
Code: Select all
cpLineBoundry * cpLineBoundryInit(cpLineBoundry *shape, cpBody *body, cpFloat xIntercept, cpFloat yIntercept, cpFloat outside)
cpLineBoundry * cpLineBoundryInitWithVectors(cpLineBoundry *shape, cpBody *body, cpVector a, cpVector b, cpFloat outside)
Scott, is cpLineBoundry possible? I don't know the ins and outs of collision detection... I guess it doesn't have a bounding box and would need special consideration. If you give me a few pointers I'd have a crack at it if I can find the time.
Use Case 2: Concave Shapes
Assuming that cpLineBoundry exists would it then be possible to define cpLineBoundrySegment? Whereby a bounding box is given to a cpLineBoundry and the line is 'oneway'. Meaning that collisions only occur if the colliding shape approaches the line in the 'right' direction and if the colliding shape was in the solid region of the bounding box then it must pass through as if there were no boundary.
Imagine, building a shape with boxes where only one side of the box had any effect! This would allow a concave surface and convex polygons come to think of it.
I guess calculating moment of inertia and torque would be difficult, I dunno...
I suppose cpLineBoundry could be approximated with a cpLineBoundrySegment (if it made the math easier).
What do you think? Is the math for this hard (nontrivial, computationally expensive)? I would love to see this addition to the already excellent chipmunk library!
 slembcke
 Site Admin
 Posts: 4164
 Joined: Tue Aug 14, 2007 7:13 pm
 Contact:
Re: Any shape
Well, it's not impossible, but Chipmunk makes the assumption that shapes have finite sized bounding boxes. Objects with infinite sized bounding boxes are hard to deal with in most spatial indexes. They don't work with the spatial hash you'd end up in a infinite loop adding the object to and infinite number of hash cells. They don't work with the tree data structure in 6.0 either because they don't have a finite centroid or area and I have no idea how you'd group them.
BSP trees are pretty well suited to this sort of thing, but I don't really have any plans to add them to Chipmunk as they aren't very general purpose.
Also, you can trivially implement one way collisions in Chipmunk using a simple presolve callback. The demo application has a demo of this actually.
BSP trees are pretty well suited to this sort of thing, but I don't really have any plans to add them to Chipmunk as they aren't very general purpose.
Also, you can trivially implement one way collisions in Chipmunk using a simple presolve callback. The demo application has a demo of this actually.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! > http://howlingmoonsoftware.com/wordpress/
Check out our latest projects! > http://howlingmoonsoftware.com/wordpress/

 Posts: 2
 Joined: Mon Mar 28, 2011 5:21 pm
 Contact:
Re: Any shape
Hi,
I'm also haunted by this "crack" problem in my game where I need continuous terrain of linesegments used as a ground.
Could it be possible to have a special linesegment that only pushes bodies away to the direction of its normal. So that the end points of the segment didn't trigger collisions. This way you could make solid ground from linesegments lined up perfectly without the "cracks".
So the collisions would work as in the envelope case when combined as one single string of segments.
Could this work?
I'm also haunted by this "crack" problem in my game where I need continuous terrain of linesegments used as a ground.
Could it be possible to have a special linesegment that only pushes bodies away to the direction of its normal. So that the end points of the segment didn't trigger collisions. This way you could make solid ground from linesegments lined up perfectly without the "cracks".
So the collisions would work as in the envelope case when combined as one single string of segments.
Could this work?
Who is online
Users browsing this forum: No registered users and 2 guests