3D intersection detection

From: Ilkka Tapio Ikonen (itikon01@starbase.spd.louisville.edu)
Date: Wed Sep 11 1996 - 21:04:28 EEST


Howdy!

I am working with a problem where we pack three dimensional objects of
all kind of shapes (not only blocks or convex bodies). We planned to use
Minkowski Sum to check part interference after the packing is done.
 
I have seen applications where Minkowski Sum is used to check
intersection of 2D non-convex shapes.(work of Dr. Victor Milenkovic and his students)
By the thoery "point sets A and B intersect only
iff A+(-B) (Minkowski Sum of A and reflection of B) includes the
origin."

However, (at least :-) one question remains and I wished somebody might
be able to help.

Is the Minkowski Sum theory valid for objects (3D) with cavities
and holes?
I use it to check if parts A and B interfere after a packing pattern is
done.
Is it also valid in the following case: part A is a cup and part B is
inside it. Does Minkowski Sum still tell if the parts interfere??

Parts can be any shape and smaller parts can be inside cavities of
larger ones.
Parts are represented by their extreme points in 3D. So, for a solid
block we have 8 points, one in each corner. We would like to use only
these extreme points instead of wire frame or surface representation. This to
keep the algorihm as simple (fast) as possible. We also have the .stl file
available for each part. if this is taken as accurate as needed for RP purposes,
it is too large for a complex shape. (will make the algorithm slow)

For a block with a cavity (cup) we have 16 points
(8 in outside corners, 8 in inside corners).

Minkowski Sum is valid in 3D and for discrete point sets, that's ok.
But, how does it know if part B is inside the cavity of part A and does
not intersect with its boundaries?

Order and orientation of parts is searched by genetic algorithms,
so we need to check how much parts in created pattern intersect each
other.

I haven't been able to find out, if we can utilize Minkowski Sum to
check part intersection??

I wish we can, because it seems such a nice tool for this.
But, at the same time I am afraid that it is not proven to be true in a
case like this (with holes and cavities in 3D)

Any comments on how to check intersection using some other method would
also help.
 
The method should be as fast (simple) as possible.

Any comments and advice will be helpful

--------------------------------
Ilkka Ikonen
itikon01@starbase.spd.louisville.edu

-- 



This archive was generated by hypermail 2.1.2 : Tue Jun 05 2001 - 22:37:34 EEST