Ghost vertices Implementation in dyn4j?

Posts regarding potential bugs, enhancement requests, and general feedback on use of dyn4j
maheshkurmi
Posts: 60
Joined: Tue Mar 27, 2012 7:20 am
Location: India
Contact:

Ghost vertices Implementation in dyn4j?

Postby maheshkurmi » Fri Jan 01, 2016 11:38 am

Hi William,
Have you planned to implement 'ghost Vertices' in dyn4j?
If not, would you please let me know, i will make a try.
By the way have you ever used 'Algodoo' , Its collision response is very smooth and is free from jerkiness due to "internal corners" of two closely placed fixtures. I have no idea how does it do (even which physics engine it is using).

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

Re: Ghost vertices Implementation in dyn4j?

Postby William » Sat Jan 02, 2016 6:27 pm

maheshkurmi wrote:Have you planned to implement 'ghost Vertices' in dyn4j?
If not, would you please let me know, i will make a try.

I have it planned but haven't made any progress on it at this time. I'm not a fan of having a separate structure for this one case, but I haven't come up with anything better either. I'd like it to be more general in that it would be something that could be executed on every multi-fixture body rather than just on a special shape.

It shouldn't be too difficult to add in. Create a new shape that implements the Convex interface. Create a new NarrowphaseDetector that does collision detection for this new shape. Add in the new detector using the FallbackNarrowphaseDetector class. This would allow you to add this feature your self until I can incorporate it into the engine.

maheshkurmi wrote:By the way have you ever used 'Algodoo' , Its collision response is very smooth and is free from jerkiness due to "internal corners" of two closely placed fixtures. I have no idea how does it do (even which physics engine it is using).

I have not. I couldn't find details of their engine are either. From what I read it sounds like their own engine.

William

maheshkurmi
Posts: 60
Joined: Tue Mar 27, 2012 7:20 am
Location: India
Contact:

Re: Ghost vertices Implementation in dyn4j?

Postby maheshkurmi » Sun Jan 03, 2016 3:57 am

I'd like it to be more general in that it would be something that could be executed on every multi-fixture body rather than just on a special shape.

This is exactly what i would like to be implemented.
If you are planning to implement it then its a great news, as this would be lot better than what I will do.
Thanks

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

Re: Ghost vertices Implementation in dyn4j?

Postby William » Mon Jan 04, 2016 8:51 am

I'm not sure what the timing would be, but I wouldn't wait on me if you need this soon.

My thought is to add a new flag to the body class that would effectively compute the 'border' of all the fixtures. Bear in mind that it's possible that this process could create multiple 'borders' if the fixtures are not connected. Either way, this would be computed when the setMass methods are called after fixture modification. Then, during collision detection, we would do a post processing step with these specially flagged bodies and apply the 'internal edge fix' before creating the contact constraints. I think this would fit in well, but there some details here that could get cumbersome and/or slow.

I'll add this as an enhancement on the github page so that it stays visible.

William

maheshkurmi
Posts: 60
Joined: Tue Mar 27, 2012 7:20 am
Location: India
Contact:

Re: Ghost vertices Implementation in dyn4j?

Postby maheshkurmi » Mon Jan 04, 2016 1:16 pm

effectively compute the 'border' of all the fixtures

Is there any efficient algorithm to create border for multi-fixture body, and to check if it has multiple borders (non connected fixtures)?

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

Re: Ghost vertices Implementation in dyn4j?

Postby William » Mon Jan 04, 2016 3:14 pm

I'm not sure, I need to do some research to see if there are any existing algorithms out there.

Just thinking out loud, lets assume all the fixtures are polygonal (I totally forgot about curved shapes when I wrote my idea above) and that they are all attached in some way. Since the fixtures are all convex, i think we could just use all the vertices of the shapes and create a tight fitting boundary.

After a cursory look I found this: http://www.geosensor.net/papers/duckham08.PR.pdf.

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

Re: Ghost vertices Implementation in dyn4j?

Postby William » Wed Jan 06, 2016 4:51 pm

Just to record my thoughts, another thing is that we may need to exclude Segment fixtures from the initial 'border' or contour build step since including them may create a solid rather than a line. We could always add these in at the end I guess...

Regarding curved shapes, we could always convert them to polygons before the contour build step. Not ideal. Another option is to modify the algorithm for determining the proper normal to account for the curvature. We'd need to add in some extra classes for this which could cause its own problems.

Another case we'd need to cover is the case where there's only Segment fixtures and the user really wants just a segmented line. Again, we wouldn't be able to build a border from a point cloud as this could create a solid instead of the line. In this case we'd need to just find where they are linked. This poses some problems too, especially from 'close' but not connected segment fixtures. I guess the 'close' problem also exists in the above cases as well.

Another option might be for the user to manually specify a contour object and then provide the automated processes as 'helpers' much like the convex decomposition stuff works today. This could enforce polygonal only contours and would allow both enclosed and open shapes that are both convex and non-convex. At that point though we might as well just make another collision shape type for it.

I'm thinking a separate collision shape (sequence of Segments basically, maybe with an api similar to Path2D) might be the best route. box2d went this route. Bullet only does this for their triangle mesh 'shape' which is the 3D analog. We could still include the point cloud non-convex contour generation process too to help out with user constructed bodies.

maheshkurmi
Posts: 60
Joined: Tue Mar 27, 2012 7:20 am
Location: India
Contact:

Re: Ghost vertices Implementation in dyn4j?

Postby maheshkurmi » Fri Jan 08, 2016 1:02 pm

Contour for multifixture bodies can easily done using Java2D Api's path iterator for GeneralPath, and I already tried it successfully. Just we need to dig the source for Java2D for its efficient implementation.

I'm thinking a separate collision shape (sequence of Segments basically, maybe with an api similar to Path2D) might be the best route


This is exactly what i am thinking about. I tried it too, in my Calculus projecthttp://www.shikharedusoft.com/simgeo/, but only restriction so far for dyn4j is that it will support only convex curves (quad2d , arc2D etc) because getFarthestPoint() can't be implemented for concave edges.

Regarding curved shapes, we could always convert them to polygons before the contour build step. Not ideal. Another option is to modify the algorithm for determining the proper normal to account for the curvature.

once again collision detection for concave curves imposes problem.

But Overall it seems quite interesting. I am sure we will get some solution sooner or later.

maheshkurmi
Posts: 60
Joined: Tue Mar 27, 2012 7:20 am
Location: India
Contact:

Re: Ghost vertices Implementation in dyn4j?

Postby maheshkurmi » Fri Jan 08, 2016 1:13 pm

Is there some built in function in dyn4j to check if two fixtures in a body are not touching each other, so that body can be treated as group of fixtures separated from each other? I just want to know how many closed contours body has.

One way is to use Brute Force DistanceDetection for each pair of fixture, but it does't seem efficient.

I did this using Java2D's Path iterator by counting number of MOVETO with some sanity checks, but would be pleased to do it in dyn4j way.

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

Re: Ghost vertices Implementation in dyn4j?

Postby William » Mon Apr 18, 2016 9:02 pm

It's been a while, but I finally have something to show.

I decided to go the Bullet/box2d route and have a special shape that records the connectivity information. Then, there's a post narrowphase process that fixes the normal after collision detection.

Click here to see an example of the problem in action
Click here to see that same example with the new feature in place
*NOTE: these videos are in slow motion for better viewing of the problem/fix

I'm going to put some tooling around it (helper methods in the Geometry class for example) to make constructing them a little easier. I also have a bit of clean up and documentation to write as well.

William


Return to “Bugs, Enhancements, Feedback”

Who is online

Users browsing this forum: No registered users and 1 guest