Jump to content
  • Advertisement
Sign in to follow this  
PrestoChung

Using minkowski difference to check for containment

This topic is 2677 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm working on an implementation of a GJK algorithm and as a preliminary I'm looking for a test that will determine if one shape completely contains another. I know that it will contain the origin for sure, but I don't know if there is a general test that will tell me whether one shape completely contains another or not.

From what I can tell, for two objects A and B, if B contains A, then the difference B-A will intersect with B if B contains A completely. But sometimes the difference will intersect B even when A is not completely contained, as when they are intersecting and B also happens to contain the origin.

Any insights? Thanks.

Share this post


Link to post
Share on other sites
Advertisement

There is a nice discussion on the MollyRocket forum about a boolean GJK with a video You can also look at Gino v.d. Bergens book.


Thanks this is what I was looking at initially. I think the answer is that if you check every point in the object as an isolated case and they all are contained, then by induction the whole thing is contained. I was just wondering if there was another property of the minkowski difference or sum that allowed you avoid the brute force approach.

Share this post


Link to post
Share on other sites
From what I can tell, for two objects A and B, if B contains A, then the difference B-A will intersect with B if B contains A completely. But sometimes the difference will intersect B even when A is not completely contained, as when they are intersecting and B also happens to contain the origin.[/quote]

Minkowski difference A - B means you subratct all points in B from all points in A. If A and B overlap they must share equal points. Therefore A - B must contain the origin. This is actual trivial and no rocket science.

Share this post


Link to post
Share on other sites

From what I can tell, for two objects A and B, if B contains A, then the difference B-A will intersect with B if B contains A completely. But sometimes the difference will intersect B even when A is not completely contained, as when they are intersecting and B also happens to contain the origin.


Minkowski difference A - B means you subratct all points in B from all points in A. If A and B overlap they must share equal points. Therefore A - B must contain the origin. This is actual trivial and no rocket science.
[/quote]

I think the OP is asking about containment, not overlap/penetration -- does the minksum have any properties which would make it easy to detect/infer containment using only a few tests rather than testing all vertices of each object against the other.

Share this post


Link to post
Share on other sites

[quote name='DonDickieD' timestamp='1298036669' post='4775852']
From what I can tell, for two objects A and B, if B contains A, then the difference B-A will intersect with B if B contains A completely. But sometimes the difference will intersect B even when A is not completely contained, as when they are intersecting and B also happens to contain the origin.


Minkowski difference A - B means you subratct all points in B from all points in A. If A and B overlap they must share equal points. Therefore A - B must contain the origin. This is actual trivial and no rocket science.
[/quote]

I think the OP is asking about containment, not overlap/penetration -- does the minksum have any properties which would make it easy to detect/infer containment using only a few tests rather than testing all vertices of each object against the other.
[/quote]

Yes, this is what I am asking: not overlap, but rather containment. Thanks.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!