Concave polygons

[kach]

Is there any way to make concave polygons with matter.js?

[liabru]

Currently only convex polygons are supported, although I may implement convex decomposition in the future.

[shakiba]

+1

[ponychicken]

Is there an easy way to "glue" multiple convex shapes together?

[liabru]

@ponychicken you could try using really small and stiff constraints between edges (e.g. the wheels on the cars demo) but it may not be good enough in practice.

I'm considering implementing pin constraints when I get time, which would allow this.

[ponychicken]

Ok, thanks. I had tried stiff constraints, but they were still too flexible for my use case.

[eweitnauer]

I implemented a convex decomposition algorithm in geom.js, maybe you can reuse (parts of) it. It is a little more complex than a simple ear-clipping algorithm, but produces less convex parts and less vertices on the edge of the polygon.

It's used in svg2physics to allow you to turn SVG images into Box2D physics scenes.

[liabru]

Concave and compound bodies are now supported in the compound-concave branch.

You can also try them out in this demo.

Hopefully these should be merged into master soon!

[karolsluszniak]

@liabru Demos look very promising, do you have any estimates about when will it land in master and/or tagged release? Also, do you think it's mature enough to use for actual game (which I'm considering right now)?

[liabru]

Yea from my testing it's now stable enough in most use cases, so it should be in landing in master within the next week (unless I find new issues but I think I've solved most).

The API for this is also now unlikely to change very much, so I'd say it's ready to start using. It's obviously not mature and battle tested yet, but this obviously will take time and I'll be fixing issues as they come in.

[liabru]

This feature has been merged into master. Please open new threads for new issues found, thanks!

[donaldpipowitch]

Can I create holes that way? So I could place a ball inside a ball?

[liabru]

@donaldpipowitch holes are possible if you have a good enough convex decomposition algorithm, or you just define all the convex parts by hand.

Check out the SVG demo and the source code. Also see the compound demo.

Note that if you use Matter.Svg to do convex decomposition, holes aren't guaranteed to work but they often do after some fiddling with your SVG path.

[donaldpipowitch]

Thank you.

[donaldpipowitch]

Just to be sure: This isn't tagged in 0.8.0, right? Only master.

And I get this warning Matter.js: Bodies.fromVertices: poly-decomp.js required. Could not decompose vertices. Fallback to convex hull. Is this https://www.npmjs.com/package/poly-decomp? Is this a peer-dependency now?

I require poly-decomp now before matter-js, but I get the same error.

[liabru]

Just to be sure: This isn't tagged in 0.8.0, right? Only master.

Correct, only master right now.

Is this https://www.npmjs.com/package/poly-decomp? Is this a peer-dependency now?

That's the right package, but it probably won't work if you're using node rather than browser.

Currently it just expects window.decomp to be available, but I guess now since I recently set browserify up I should probably change this to use require.

Do you need support for this? I've added an issue you can track.

[donaldpipowitch]

@liabru I had no luck using poly-decomp with an SVG containing a hole. (It seems to treat the hole as a solid shape and ignores the outer shape.) I tried other libraries (https://github.com/mattdesl/svg-mesh-3d which returns a "simplicial complex"), but had no luck either. Could you create an example with an SVG containing a hole, if this is possible with poly-decomp? If not, I think there are other libraries which could help with triangulation like https://github.com/mapbox/earcut, which are maybe better as poly-decomp?

Purpose: I want to have a body with a hole which contains other bodies. The body is parsed from the path of an SVG.

[liabru]

Strange, I've usually had success with holes using poly-decomp (but it's not a guarantee). As for an example, just look at the SVG demo (ok those arn't exactly holes, but trust me I do have projects that have them).

It probably depends on how the hole is constructed. You often need to experiment with your SVG a bit until it works.

Have you tried playing with the sampleLength argument of Svg.pathToVertices? It's trial and error but it can often help.

Be aware though that the SVG to absolute conversion is limited and may have some bugs, so even with a good decomposer you may still get bad results with certain SVGs.

You should certainly try https://github.com/mapbox/earcut as I expect it's more robust, but the downside is that it creates triangle parts rather than convex parts which is more optimal, but performance should still be reasonable. I wonder if there's some easy heuristic for joining triangles...

If you do try it, tell me how you get on, I'd be interested in adding support for earcut. There's also libtess which may even be better.

[donaldpipowitch]

@liabru Thank you for your fast response. Playing with sampleLength doesn't seem to help. I couldn't generate a Body from earcuts results. Maybe I need to change my SVG. This is my path value I used:

d="M540,88.317C791.695,88.317 996.039,292.661 996.039,544.356C996.039,796.051 791.695,1000.39 540,1000.39C288.305,1000.39 83.961,796.051 83.961,544.356C83.961,292.661 288.305,88.317 540,88.317ZM547.838,189.504C551.324,189.523 554.81,189.592 558.294,189.726C565.573,190.007 572.841,190.552 580.081,191.36C599.633,193.543 618.966,197.653 637.714,203.619C650.214,207.596 662.451,212.396 674.323,217.975C685.458,223.208 696.271,229.126 706.683,235.679C724.066,246.619 740.324,259.33 755.181,273.51C766.839,284.636 777.634,296.662 787.487,309.413C795.627,319.947 803.125,330.975 809.963,342.397C821.861,362.269 831.751,383.32 839.706,405.067C847.003,425.017 852.674,445.549 856.869,466.369C861.352,488.615 864.154,511.188 865.502,533.837C865.936,541.117 866.22,548.407 866.361,555.699C866.442,559.88 866.474,564.062 866.465,568.244L865.984,573.609C865.516,575.343 865.197,577.123 864.579,578.809C863.962,580.495 863.193,582.133 862.292,583.687C860.483,586.805 858.143,589.582 855.376,591.893C852.61,594.205 849.461,596.014 846.071,597.24C842.681,598.466 839.102,599.089 835.497,599.081C831.892,599.074 828.317,598.436 824.932,597.195C821.547,595.955 818.405,594.133 815.649,591.81C812.892,589.487 810.563,586.699 808.767,583.574C806.972,580.448 805.736,577.032 805.118,573.481C804.81,571.712 804.796,569.904 804.66,568.114C804.643,567.899 804.661,567.683 804.661,567.468C804.661,567.259 804.662,567.05 804.662,566.842C804.662,566.216 804.66,565.59 804.659,564.964C804.655,563.925 804.648,562.887 804.639,561.848C804.569,554.927 804.365,548.007 804.006,541.094C803.77,536.553 803.469,532.015 803.1,527.483C800.615,496.969 795.041,466.636 785.537,437.507C783.657,431.744 781.623,426.03 779.431,420.378C776.966,414.021 774.301,407.742 771.43,401.558C768.145,394.481 764.591,387.529 760.761,380.732C756.142,372.533 751.124,364.557 745.706,356.862C739.218,347.647 732.158,338.833 724.549,330.518C715.079,320.169 704.758,310.597 693.692,301.974C679.571,290.971 664.239,281.526 648.036,273.912C638.383,269.375 628.425,265.488 618.251,262.286C607.434,258.882 596.373,256.254 585.181,254.427C572.016,252.277 558.671,251.236 545.332,251.312C532.415,251.384 519.505,252.503 506.766,254.644C491.021,257.289 475.543,261.496 460.614,267.154C446.981,272.32 433.811,278.694 421.278,286.14C407.734,294.189 394.94,303.488 383.049,313.821C373.615,322.019 364.75,330.865 356.489,340.243C349.535,348.137 343.01,356.408 336.918,364.985C332.409,371.336 328.137,377.856 324.1,384.517C321.295,389.147 318.603,393.846 316.023,398.606C314.022,402.297 312.089,406.025 310.222,409.786C296.978,436.459 287.097,464.734 280.017,493.64C278.832,498.48 277.725,503.34 276.693,508.215C275.334,514.635 274.106,521.081 273.002,527.549C271.716,535.079 270.599,542.637 269.64,550.215C268.786,556.967 268.057,563.735 267.446,570.513C267.143,573.877 266.872,577.244 266.625,580.612L265.764,585.93C265.173,587.626 264.728,589.379 263.992,591.017C262.515,594.305 260.473,597.309 257.96,599.894C255.447,602.478 252.501,604.603 249.256,606.172C246.01,607.741 242.515,608.731 238.929,609.095C235.343,609.459 231.72,609.194 228.225,608.31C224.731,607.425 221.418,605.937 218.436,603.911C215.454,601.884 212.85,599.352 210.741,596.429C208.633,593.505 207.052,590.235 206.07,586.766C205.581,585.039 205.242,583.261 205.06,581.475C204.879,579.689 204.991,577.884 204.985,576.089C204.984,575.845 205.02,575.602 205.038,575.359C205.075,574.861 205.113,574.364 205.15,573.867C205.301,571.885 205.462,569.905 205.631,567.925C206.52,557.508 207.662,547.113 209.073,536.753C214.2,499.108 222.899,461.88 236.014,426.195C237.807,421.317 239.682,416.468 241.641,411.654C251.687,386.967 263.953,363.162 278.569,340.863C287.205,327.687 296.656,315.043 306.906,303.078C317.656,290.531 329.283,278.733 341.721,267.856C351.804,259.038 362.419,250.826 373.504,243.306C387.321,233.932 401.868,225.634 416.987,218.55C435.25,209.994 454.343,203.213 473.923,198.377C489.444,194.543 505.265,191.929 521.195,190.58C526.577,190.124 531.972,189.813 537.371,189.646C539.908,189.568 542.446,189.525 544.984,189.507C545.935,189.503 546.886,189.502 547.838,189.504Z"

[liabru]

I've experimented with both earcut and libtess. Both gave similar results, neither of them very good for my test cases (lots of missing pieces). I suspect they require explicit information about holes, which would require another tricky algorithm to identify them.

Either way, polydecomp gave better results that were more optimal since it outputs polygons rather than just triangles. So I'm going to stick with it for now as it appears earcut and libtess would require even more effort from users to get working.

[JeffWeim]

@liabru I'm curious if you would be willing to consider the PathToPoints project as an alternative to poly-demp?

[melanieimfeld]

Is there an example with polydecomp and SVG's with holes somewhere? I am also facing problems with my SVG's

[ggorlen]

Is there an example with polydecomp and SVG's with holes somewhere? I am also facing problems with my SVG's

You can try this SO answer but whether it works for you may depend on the nature of your SVG, so you might want to post it. That said, I'm mostly replying for the sake of future visitors since your post was 3 years ago and you've probably moved on by now.

[dreerr]

For those who want to make @mapbox/earcut to work with matter.js: you will have to apply this Pull Request, because the position of a convex VertexSet is messed up. Would be great to use whatever algorithm you want though…