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

Allow Non-Convex, Arbitrary-Sized Polygon Shapes in RigidBodies #446

Closed
ilexp opened this Issue Dec 8, 2016 · 11 comments

Comments

2 participants
@ilexp
Member

ilexp commented Dec 8, 2016

Summary

RigidBody polygons are currently limited to a maximum of eight vertices and convex polygons only. Remove this limitation.

Analysis

  • The implementation of PolyShapeInfo accepts a Vector2[] and is otherwise opaque to the outside. It could very well transform this polygon into an internal representation.
  • The polygon shape could internally generate multiple fixtures to represent a single non-convex polygon. (Make sure to serialize it and only re-generate on changed source shapes!)
  • On the Farseer side, each generated Fixture could be tagged with the same shape, making the distinction invisible.
  • Provide API to retrieve the internal set of convex polygons that represents the shape when needed. This will be useful for the RigidBodyRenderer.
  • As far as size limitations go, investigate whether the eight-vertex limit is really an issue for Farseer and remove it without replacement if it isn't.
  • Test RigidBody behavior thoroughly after these changes.
  • Update the RigidBody Editor to reflect the above changes.

Attachments

  • Related: issue #54
@YMRYMR

This comment has been minimized.

Contributor

YMRYMR commented Feb 17, 2017

I've made this possible solution using the ear cutting algorithm: https://github.com/YMRYMR/YMR.ComplexBody
The plugin is a WIP, but something like that might work.

@ilexp

This comment has been minimized.

Member

ilexp commented Feb 17, 2017

Thanks, much appreciated! Will take a look when approaching this issue to do more fine-grained planning and implementation preparations.

@ilexp

This comment has been minimized.

Member

ilexp commented Apr 7, 2017

Progress

  • Looked into decomposition algorithms and found that Farseer already provides five of them. To be evaluated.
  • Adjusted internal PolyShapeInfo implementation to use Farseer API rather than re-invent it. Also may or may not be more efficient now.

Immediate ToDo

  • Refactor ShapeInfo in general to allow more than only one fixture per shape.
    • While at it, consider reworking the entire shape update code to be more structured.
    • Use only a single "SyncFixture" method and get rid of as many extra code paths as possible.
  • Investigate whether that refactoring requires moving this issue to the v3.0 milestone.
  • Use Farseer decomposition in shape preprocessing to allow arbitrary polygons.
    • Check whether MaxVertices is respected and re-route even already convex polygons through decomposition if it is.
    • Investigate where in Farseer MaxVertices is required and why.
  • See how well that works and address issues that may arise.
  • Store and serialize decomposed polygons, only re-process when not already available so there will be no load or runtime overhead.
@ilexp

This comment has been minimized.

Member

ilexp commented Apr 8, 2017

Progress

  • Refactored physics shape handling to allow ShapeInfo to create and handle any number of fixtures without a hardwired 1:1 mapping. Also did some general cleanup in the internal APIs and implementations.
  • Only internal API was affected. Changes have been done on the master branch.

Immediate ToDo

  • Use Farseer decomposition in shape preprocessing to allow arbitrary polygons.
    • Check whether MaxVertices is respected and re-route even already convex polygons through decomposition if it is.
    • Investigate where in Farseer MaxVertices is required and why.
  • See how well that works and address issues that may arise.
  • Store and serialize decomposed polygons, only re-process when not already available so there will be no load or runtime overhead.
@ilexp

This comment has been minimized.

Member

ilexp commented Apr 9, 2017

Progress

  • Created the complex-rigidbody-shapes-wip branch for further work on this.
  • Removed redundant shape updates from ShapeInfo implementations.
  • PolyShapeInfo now performs an internal decomposition of non-convex polygons as described previously.
  • Improved overall RigidBody editor shape rendering and updated it to support non-convex shapes.
  • Updated RigidBodyRenderer to support non-convex shapes.

Immediate ToDo

  • Investigate why BayazitDecomposer runs into an exception for some polygons.
    • Consider merging Farseer 3.5 changes of decomposition into the custom Farseer port and see if that helps.
    • Consider using a different decomposition algorithm.
  • Merge back to master.
  • Trigger a binary release.
@ilexp

This comment has been minimized.

Member

ilexp commented Apr 10, 2017

Progress

  • Merged Farseer 3.5 decomposition code into the AdamsLair.FarseerDuality port.
  • Released a new nuget package (4.1.2) for it.
  • Updated the farseer dependency accordingly.
  • This seems to fix the previous decomposition issue. Potentially due to the fact that polygons are expected to be counterclockwise and there previously was no code in place to ensure this.

Immediate ToDo

  • Enforce polygons to be simple polygons only (no overlapping edges), reject non-simple polygons before decomposition.
  • Fix the stack overflow exception that sometimes occurs when defining a polygon shape: devenv_2017-04-10_18-44-22
    • Investigate ValidatePolygon. Consider discarding non-convex polygons in the decomposition results, as this shouldn't happen for valid inputs anyway and patching up things doesn't seem like a good practice and appears to cause a stack overflow when the convex hull is still considered non-convex (?)
  • Do some additional testing with grid snapping enabled to trigger corner cases of colinearity and identical vertices.
  • Consider going back to thin-line rendering for the RigidBody Shape layer. Otherwise:
    • Fix polygon outline rendering vertex caps for shapes with sharp angles.
    • Profile and optimize Shape layer drawing in DualStickSpaceShooter sample when viewing the full level.
    • Update RigidBody Joint layer to match thick-line drawing of Shape layer. Consider removing its text in the process, as it doesn't really provide useful information and feels mostly ornamental.
    • Consider drawing mass and geometric center points in the RigidBody shape layer as thick lines as well.
  • Highlight the shapes of RigidBodies that are parts of selected objects in the RigidBody Shape layer.
  • Draw individual convex polygons in RigidBody Shape layer.
  • Merge back to master.
  • Trigger a binary release.
@ilexp

This comment has been minimized.

Member

ilexp commented Apr 11, 2017

Progress

  • Added various polygon validation steps to PolyShapeInfo before decomposition to make sure no exceptions or invalid polygons are generated in the decomposition process.
  • Added a vertex placement validation in the polygon tool of the RigidBody editor.
  • Fixed the stack overflow exception that was mentioned in the previous comment.

Immediate ToDo

  • Adjust the .nuspec of the Duality core to refer the updated Farseer dependency.
  • Consider going back to thin-line rendering for the RigidBody Shape layer. Otherwise:
    • Fix polygon outline rendering vertex caps for shapes with vertices on exactly the same line / with colinear vertices.
    • Fix polygon outline rendering vertex caps for shapes with sharp angles.
    • Profile and optimize Shape layer drawing in DualStickSpaceShooter sample when viewing the full level.
    • Update RigidBody Joint layer to match thick-line drawing of Shape layer. Consider removing its text in the process, as it doesn't really provide useful information and feels mostly ornamental.
    • Consider drawing mass and geometric center points in the RigidBody shape layer as thick lines as well.
  • Highlight the shapes of RigidBodies that are parts of selected objects in the RigidBody Shape layer.
  • Draw connection lines between individual convex polygon edges in RigidBody Shape layer.
  • Merge back to master.
  • Trigger a binary release.
@ilexp

This comment has been minimized.

Member

ilexp commented Apr 12, 2017

Progress

  • Updated the .nuspec file of the Duality core with the updated Farseer dependency.
  • Fixed polygon outline joint rendering for shapes with vertices on exactly the same line / with colinear vertices.
  • Fixed polygon outline joint rendering for shapes with sharp angles by switching to bevel joints for sharp angles.

Immediate ToDo

  • Fix Canvas thick outline rendering to account for and respect changes in winding order.
  • Fix polygon shapes to be valid again for DualStickSpaceShooter enemy sensors spikes.
  • Finishing polygon shapes should still work even when the current (unplaced) vertex makes the shape invalid.
  • Allow to abort collision shape tools via right-click even before starting to define the shape. Check all four tools.
  • Consider going back to thin-line rendering for the RigidBody Shape layer. Otherwise:
    • Profile and optimize Shape layer drawing in DualStickSpaceShooter sample when viewing the full level.
    • Update RigidBody Joint layer to match thick-line drawing of Shape layer. Consider removing its text in the process, as it doesn't really provide useful information and feels mostly ornamental.
    • Consider drawing mass and geometric center points in the RigidBody shape layer as thick lines as well.
  • Highlight the shapes of RigidBodies that are parts of selected objects in the RigidBody Shape layer.
  • Draw connection lines between individual convex polygon edges in RigidBody Shape layer.
  • Merge back to master.
  • Trigger a binary release.
@ilexp

This comment has been minimized.

Member

ilexp commented Apr 13, 2017

Progress

  • Fixed Canvas thick outline rendering to account for and respect changes in winding order.
  • Fixed polygon shapes to be valid again for DualStickSpaceShooter enemy sensors spikes.
  • Finishing polygon shapes now works even when the current (unplaced) vertex makes the shape invalid.
  • Allowing to abort collision shape tools via right-click even before starting to define the shape.
  • Highlighting the shapes of RigidBodies that are parts of selected objects in the RigidBody Shape layer.

Immediate ToDo

  • Consider going back to thin-line rendering for the RigidBody Shape layer. Otherwise:
    • Update RigidBody Joint layer to match thick-line drawing of Shape layer. Consider removing its text in the process, as it doesn't really provide useful information and feels mostly ornamental.
    • Profile and optimize Shape layer drawing in DualStickSpaceShooter sample when viewing the full level.
  • Draw connection lines between individual convex polygon edges in RigidBody Shape layer.
  • RigidBody Editor snap-to-grid should, when moving entire shapes, offset grid snapping so that it is actually the shapes edges that are snapped, not the shapes calculated center.
  • Merge back to master.
  • Trigger a binary release.
  • Merge to develop-v3.0
@ilexp

This comment has been minimized.

Member

ilexp commented Apr 14, 2017

Progress

  • More bugfixes and tweaks.
  • RigidBody Joint layer now renders in scree-space-constant scale and uses color tint rather than multiple materials for different drawcalls.
  • Adjusted the RigidBody Joint layer to use thick-line rendering similar to the Shape layer.
  • All RigidBody-related layer rendering is now fixed to the Z-0 plane, because that's where physics happens.
  • Removed all RigidBody Joint layer texts, since they were of little use.

Immediate ToDo

  • Merge back to master.
  • Trigger a binary release.
  • Merge to develop-v3.0
@ilexp

This comment has been minimized.

Member

ilexp commented Apr 14, 2017

Done.

@ilexp ilexp closed this Apr 14, 2017

@ilexp ilexp self-assigned this May 1, 2017

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment