Concave Shapes "impossible"?

Posts that don't fit into other categories.
TMNCorp
Posts: 2
Joined: Thu Aug 04, 2016 1:31 pm

Concave Shapes "impossible"?

Postby TMNCorp » Thu Aug 04, 2016 1:49 pm

Hello,

I have used several physics engines before (LiquidFun, JBox2D, Chipmunk2D and Nape) and I know that none of them support concave shapes.

The actual question is: Can I write my own concave shape by implementing the Convex interface?
I have a solely mathematical based complex concave shape (including holes), however testing against a point in this shape is a one liner and just needs comparison with two numbers.

Before I implement this shape into dyn4j (which is really tedious and complicated because dyn4j has a different and more complicated interface for shapes then the others) I wanted to know if this engine can actually handle a concave shape class?

Thank you very much
with best Regards

William
Site Admin
Posts: 345
Joined: Sat Feb 06, 2010 10:23 pm

Re: Concave Shapes "impossible"?

Postby William » Thu Aug 04, 2016 9:04 pm

Put simply, no.

Presumably, you'd like to use some features of an existing physics engine with your new shape. The problem is that many of their sub systems rely on the simple fact that the shapes are convex. To circumvent this constraint would mean that you lose some of their most appealing features. In the context of dyn4j, if a shape isn't convex, then you cannot use any of the narrow-phase collision detection, continuous collision detection, or contact point generation components because they all rely on it.

Now, that's not to say that you can't create non-convex bodies. dyn4j, and I'm sure the others you've listed, will allow you to compose multiple convex shapes into one "body." This allows you to have non-convex "shapes" within the framework of a convex only system. This may not be what you are looking for exactly, but its likely it will be more efficient and stable.

TMNCorp wrote:which is really tedious and complicated because dyn4j has a different and more complicated interface for shapes then the others

I would like to know why you think that its so much harder than other libraries? You extend from AbstractShape and implement 10 or so, in my opinion, well defined methods and you are done.

William

TMNCorp
Posts: 2
Joined: Thu Aug 04, 2016 1:31 pm

Re: Concave Shapes "impossible"?

Postby TMNCorp » Fri Aug 05, 2016 11:35 am

Thank you very much for your answer. This explains it very well.

I am aware of the method to split a non-convex shape into multiple convex ones. It is not an option with this shape as it would create (in worst case) exactly 524.288 single convex shapes. I tried that before with LiquidFun but the system crashed every time because of memory overflow - creating up to 500.000 fixture- and shape-objects plus included data is not very memory efficient.

I guess I have to find another way to implement this shape.

William wrote:
TMNCorp wrote:which is really tedious and complicated because dyn4j has a different and more complicated interface for shapes then the others

I would like to know why you think that its so much harder than other libraries? You extend from AbstractShape and implement 10 or so, in my opinion, well defined methods and you are done.

William

In regards to my complex shape, dyn4j's shape interface (AbstractShape&Convex) is more difficult as it is different from shape interfaces of the other 2d engines I have used and mentioned above, which are all very similar to each other. So I can't just port my code to dyn4j, instead I have to rewrite my mathematical functions describing the shape to meet dyn4j's requirements - and those mathematical functions are pretty complex.
However, the advantage of my shape is fast collision detection against every other convex shape and raycasting (speaking in nanoseconds).

And to not let it go unmentioned: In general in contrary. The reason I am migrating this project to dyn4j is because it has a better and well planned architecture then the others and seems to be easier to maintain and develop. While the same can be said about LiquidFun/Box2D which has very beautiful written C++ code but only in the context of it being written in C++.


Thank you very much for your support
With best Regards
Tim

William
Site Admin
Posts: 345
Joined: Sat Feb 06, 2010 10:23 pm

Re: Concave Shapes "impossible"?

Postby William » Fri Aug 05, 2016 7:49 pm

TMNCorp wrote:creating up to 500.000 fixture- and shape-objects

That is well beyond an acceptable number. Do you need to have all of them in the system at the same time?

William wrote:In regards to my complex shape, dyn4j's shape interface (AbstractShape&Convex) is more difficult as it is different from shape interfaces of the other 2d engines I have used and mentioned above, which are all very similar to each other. So I can't just port my code to dyn4j, instead I have to rewrite my mathematical functions describing the shape to meet dyn4j's requirements - and those mathematical functions are pretty complex.

This is true, the interface is certainly different, but shouldn't be any more or less complex. Now, if we are talking about your concave shape, that's may be a different story entirely (trying to fit a square peg into a round hole sort of thing). What method do find particularly complex? I'd like to know more specifics so I can potentially make it better.

William wrote:And to not let it go unmentioned: In general in contrary. The reason I am migrating this project to dyn4j is because it has a better and well planned architecture then the others and seems to be easier to maintain and develop. While the same can be said about LiquidFun/Box2D which has very beautiful written C++ code but only in the context of it being written in C++.

Thank you for you kind words!

William

DavidIsAlreadyTaken
Posts: 2
Joined: Sat Oct 22, 2016 6:09 pm

Re: Concave Shapes "impossible"?

Postby DavidIsAlreadyTaken » Sat Oct 22, 2016 6:32 pm

Hi Tim and William,

I would like to join the discussion and ask for advise.
First of all I want to say that Dyn4j is really nice and the examples really helped to get started.
This is my first attempt here and I also discovered that concave shapes are not possible.

So I drew my shapes and convert them from png to polygons, which I then decompose into convex shapes.
These convex shapes are then joined in a GameObject and I add them to my World.
This works fine. I added a screenshot so you can figure what I am doing, it's obviously going to be a pinball game.
So I have 3 moving GameObjects at the moment, the ball and the two flippers, which can be moved with the help of RevoluteJoint.

My doubts:

1. How can I provoke the decomposing algorithm to detect that a circle is actually a real circle, so it doesn't split into hundreds of convex pieces if 1 is enough? I tried the 3 decomposing algorithms.

2. The collision detection with the flipper and the ball doesn't seem to work out. The ball passes half through the moving flipper and bounces into different directions. I tried to use setBullet on the ball, but it seems to make it worse.
I also tried to draw lines instead of filled polygons, but the performance (fps) was just horrible.
Should I search all GameObjects that can never hit the ball and remove them or make them sensors?

3. Obviously what I am doing is not very smart, what would be a better approach to create the playfield?
I thought it would be comfortable to be able to design the playfield with a drawing program and to simply pass it on.

Any suggestions are welcome, I thank you in advance!

Best,
David
Attachments
dyn4j_1.png
dyn4j_1.png (68.46 KiB) Viewed 1924 times

zoom
Posts: 141
Joined: Sun Mar 17, 2013 3:57 pm
Location: Stockholm, Sweden
Contact:

Re: Concave Shapes "impossible"?

Postby zoom » Sun Oct 23, 2016 2:55 am

Just throwing some random ideas here but personally I would reconsider using raster images to model the table. I would probably look into creating/finding an editor that can draw simpler shapes like circles and boxes to keep the number of triangles down. Especially triangles that are very thin. Then I'd experiement with CAG to create more complex shapes, maybe start here: viewtopic.php?f=1&t=46

If you want to use raster images as a model I'd look into finding some mesh simplification algorithms or alternatively look into finding somer path-tracer algorithm to go from raster image to vector graphics, create polygons from that and then decompose into triangles. Anything to keep the number of triangles down.

DavidIsAlreadyTaken
Posts: 2
Joined: Sat Oct 22, 2016 6:09 pm

Re: Concave Shapes "impossible"?

Postby DavidIsAlreadyTaken » Sun Oct 23, 2016 7:25 pm

Hi Zoom,

Thank you so much for your reply, I will look into that.

After testing a bit more I noticed that my flipper movement by applying impulses on key press and the returning impulse when the key is released, was faulty. I think this caused caused problems in combination with the collision detecting of the ball.
The setBullet option now also seems to have a positive effect.

I will now try to reduce the number of polygons (currently 1500).

Cheers,
David

zoom
Posts: 141
Joined: Sun Mar 17, 2013 3:57 pm
Location: Stockholm, Sweden
Contact:

Re: Concave Shapes "impossible"?

Postby zoom » Mon Oct 24, 2016 10:29 am

If you get 130 fps with that many polygons then it isn't a performance problem (I guess). I've had problems with other physics simulations when the triangles becomes to thin (or degenerate) but if you don't see that then congratulations. Dyn4J really is an excellent piece of code :-)

Angelli
Posts: 1
Joined: Fri Jul 07, 2017 9:01 am

Re: Concave Shapes "impossible"?

Postby Angelli » Sat Jul 15, 2017 2:25 am

Hey David, did you figure out the correct number of Polygons to use?

William
Site Admin
Posts: 345
Joined: Sat Feb 06, 2010 10:23 pm

Re: Concave Shapes "impossible"?

Postby William » Tue Jul 25, 2017 6:27 pm

@Angelli

I don't think the number of polygons was the issue, but rather the shape of the polygons. Thin shapes can cause problems with physics engines - I can explain more if anyone is interested.

I think the take away from this thread should be:
  • Concave shapes *are* possible in dyn4j by using a combination of convex shapes.
  • I believe this thread started before the Link shape (a list of line segments) was introduced which can be "concave."
  • I believe David's problem was that some of the shapes generated in the decomposition process were too thin and were causing problems as mentioned above.
  • If a conversion from a bitmap is required, try doing a post processing step before decomposition to reduce the number of vertices in the simple polygon. This should help reduce the number of polygons generated and reduce the number of "bad" polygons.
  • If the bitmap conversion is a tooling step, instead of user driven, then I'd recommend that you just create the shapes manually or use the decomposition as a starting point.

William


Return to “General Discussion”

Who is online

Users browsing this forum: No registered users and 1 guest