Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Solve the "get-stuck" problem via manifold instead of extra vertices #456

Open
louis-langholtz opened this issue Jun 1, 2017 · 6 comments

Comments

Projects
None yet
3 participants
@louis-langholtz
Copy link

commented Jun 1, 2017

This is an idea for a potential enhancement for the library.

Box2D (at least version 2.3.2) adds extra vertices to edge shapes "for smooth collision". While this smooths sliding for a polygon sliding over edges (edge shapes or chain shapes), it doesn't smooth the sliding of say a box over a flat ground made up of other boxes which seems often the scenario encountered by new users to the library.

I've been playing with an alternative solution that doesn't need nor use extra vertices and seems to work exactly as desired and for all shapes. This solution is a change in the way the contact manifold is generated. Simply stated, resisting impulses are not part of the generated manifold for less-than-skin-deep penetrating shapes.

I read that Erin doesn't want pull requests for source code so I'm only describing the technique here. I've made a more detailed writeup of the conceptual change that I've put online in case anyone is interested.

Implementation wise, what I've written and/or changed works in all of my testing of it so I'm fairly confident that the idea is at least usable. I'd feel more confident though if others also considered the idea and independently determined it was usable. As for trade-offs, any implementation of this idea may well introduce overhead however. Whether the overhead is more than the overhead of handling extra vertices in the chain and edge shapes is unclear to me. Note that the manifold calculating related code in my fork does more than implementing this idea making apples-to-apples comparison harder.

Ultimately whether this idea is preferable, may come down to a matter of opinion. I'd feel honored if Erin uses it but I'd understand if he decided against it. I'd love to discuss it anyway if anyone is so inclined.

@louis-langholtz louis-langholtz changed the title Solve the "get-stuck" problem via manifold instead of ghost vertices Solve the "get-stuck" problem via manifold instead of extra vertices Jun 1, 2017

@MelvynMay

This comment has been minimized.

Copy link

commented Jun 1, 2017

I think this more than warrants a discussion! I'm pretty sure most users would welcome any overhead in solving this problem or at least, minimising it.

@erincatto

This comment has been minimized.

Copy link
Owner

commented Jun 5, 2017

Hi Louis,
This is a hard problem. I'm glad to see people work on solutions. I read your document. It gets a bit fuzzy at the end. How does the algorithm work?
Thanks,
Erin

@louis-langholtz

This comment has been minimized.

Copy link
Author

commented Jun 5, 2017

@erincatto Sorry about the fuzziness. I've updated the writeup with the addition of a Details section. It's part description of what your code does for manifold calculation, and part description of what I changed.

If anyone can share insight into stuff they'd like me to clarify (or change) more, I'd love that. I can already imagine ways it could be improved but I don't want to change it more based only on my own criticism. So feedback is appreciated.

@erincatto

This comment has been minimized.

Copy link
Owner

commented Jun 6, 2017

Thanks for the update. How does your algorithm when colliding on the side of a static box? If a dynamic box presses into the side of a static box, does the algorithm still choose an upward normal?

BTW, if the goal is to truly support tile based maps, I would explicitly make such a structure. This is the 2D analog of voxel map, like Minecraft. In that structure you would define the grid size and width. Then you could fill in the grid cells with a single bit instead of a polygonal box. This would be a huge memory savings. Next I would identify internal and border edges. I would disable collision with internal edges. Of course then I would to support circle vs tile grid and polygon vs tile grid.

@louis-langholtz

This comment has been minimized.

Copy link
Author

commented Jun 6, 2017

@erincatto The normal chosen is the normal of the edge whose normal-oriented distance is the lesser of the two to the other shape's corner. It's not hard coded to the upward normal if that's what you're asking.

Under the circumstance of skin penetration, it turns out that the edge that's most parallel to the edge of penetration gets chosen because it's then closest to the corner in terms of its normal-oriented distance. This gives us the desired result though I won't say I'm positive it never has a possibly undesirable result and I think that's what you're wanting to ascertain.

So for say a zero-friction dynamic box sliding vertically under the force of gravity between two vertically aligned stacks of boxes that only have space enough for the dynamic box, the dynamic box indeed slips down between the two columns. Here's an image of this scenario that I setup to demonstrate this where I had dropped the dynamic box from the top of its column and it'd slid smoothly to the bottom.

screen shot 2017-06-06 at 8 57 46 am

For those who aren't familiar with the Testbed colors and what we're seeing:

  • The dynamic box is shown in a brownish color at the bottom between two tiled columns of static boxes.
  • Static shapes are shown in green.
  • The contact points are indicated as blue dots.
  • The contact normals are shown as white lines in the direction of those normals.
@louis-langholtz

This comment has been minimized.

Copy link
Author

commented Jun 6, 2017

Here's a greatly zoomed in image of the skin interaction between the dynamic box and just the right side column of static boxes (where only the bottom left corner of the lowest right side box is shown):

screen shot 2017-06-06 at 9 16 12 am

The skin interaction is similar on the other side except everything's the mirror image.

@erincatto erincatto added the bug label Jun 23, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.