Any shape

Discuss new features and future development.
Mixel
Posts: 41
Joined: Mon Feb 14, 2011 7:10 am
Contact:

Any shape

Post by Mixel »

Is the improvement of being able to create shapes that are polygons of any shape under consideration? If it is, how long will it take to release this feature?
User avatar
slembcke
Site Admin
Posts: 4166
Joined: Tue Aug 14, 2007 7:13 pm
Contact:

Re: Any shape

Post by slembcke »

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/
Mixel
Posts: 41
Joined: Mon Feb 14, 2011 7:10 am
Contact:

Re: Any shape

Post by Mixel »

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.
Mixel
Posts: 41
Joined: Mon Feb 14, 2011 7:10 am
Contact:

Re: Any shape

Post by Mixel »

Any polygon can be created using segments, so why is it difficult to implement?
User avatar
slembcke
Site Admin
Posts: 4166
Joined: Tue Aug 14, 2007 7:13 pm
Contact:

Re: Any shape

Post by slembcke »

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/
Mixel
Posts: 41
Joined: Mon Feb 14, 2011 7:10 am
Contact:

Re: Any shape

Post by Mixel »

Could you explain why concave shapes are not possible.
User avatar
slembcke
Site Admin
Posts: 4166
Joined: Tue Aug 14, 2007 7:13 pm
Contact:

Re: Any shape

Post by slembcke »

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.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
corin
Posts: 4
Joined: Sat Mar 26, 2011 10:44 am
Contact:

Re: Any shape

Post by corin »

Have you thought about creating a special type of shape for envelopes?

Use Case 1: Curved boundary

I've just read this:
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.
samtny was using line segments. I think this use case would be the most popular.

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)
Where y = a.x + b and outside would specify a y coordinate in the solid area of the object.
E.g.

Code: Select all

cpLineBoundryInit(shape, body, 0.0f, 0.0f, -INFINITY)
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:

Code: Select all

cpLineBoundry * cpLineBoundryVerticalInit(cpLineBoundry *shape, cpBody *body, cpFloat x, cpFloat outside)
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:

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)
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 'one-way'. 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!
User avatar
slembcke
Site Admin
Posts: 4166
Joined: Tue Aug 14, 2007 7:13 pm
Contact:

Re: Any shape

Post by slembcke »

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 pre-solve 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/
bc80
Posts: 2
Joined: Mon Mar 28, 2011 5:21 pm
Contact:

Re: Any shape

Post by bc80 »

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?
Post Reply

Who is online

Users browsing this forum: No registered users and 9 guests