CGAL users discussion list

["J.L.M." <>]

There are actually two slightly different definitions of Minkowski 
difference. Since you mention opening and closing, I am assuming you are 
talking about mathematical morphology. Wikipedia has some useful 
information here: http://en.wikipedia.org/wiki/Mathematical_morphology

Minkowski difference is also called erosion in this context, and is 
represented as a circle with a minus sign inside it. Looking at the 
Wikipedia article, you can see that Minkowski sum and Minkowski 
difference (dilation and erosion) are duals of each other. One way to 
implement Minkowski difference is like so: A ominus B = (A^c oplus -B)^c
where ^c means complement, and -B means reflection about each axis. The 
code to do this would be something like this (though this doesn't work):

#Nef_polyhedron_3 A and B are already created.
static Aff_transformation inversion(-1, 0, 0, 0, -1, 0, 0, 0, -1, 1);
Nef_polyhedron_3 A_comp(A.complement());
Nef_polyhedron_3 B_invert(B);
B_invert.transform(inversion);

Nef_polyhedron_3 partial_result=CGAL::minkowski_sum_3(A_comp, B_invert);
Nef_polyhedron_3 result(partial_result.complement());

The problem is that although infimaximal frames are implemented in CGAL 
to handle infinite point sets as A.complement() would be, the 
minkowski_sum_3 doesn't allow such shapes.

As part of my research, I have devised an alternative algorithm to 
obtain an identical result that does not require infinite point sets. 
The algorithm is A ominus B = A - (A.boundary() oplus -(B.interior()).

This code works partially:

static Aff_transformation inversion(-1, 0, 0, 0, -1, 0, 0, 0, -1, 1);
Nef_polyhedron_3 A_boundary(A.boundary());
Nef_polyhedron_3 inverted_B_interior(B.interior());
inverted_B_interior.transform(inversion);
Nef_polyhedron_3 result(A - CGAL::minkowski_sum_3(A_boundary,
                        inverted_B_interior));

The problem that I have with the above is that I keep running into 
various assertions that crash the program on the minkowski_sum_3 
function. For example I found that this code did not work with the 
necessary inversion transformation, but would work if I converted my 
Nef_polyhedron_3 into a Polyhedron and then back. There are other 
assertions, see my previous posts.

So what can we do? Well, we can put in a feature request to allow the 
use of infinite point set Nef polyhedra in the minkowski_sum_3 function. 
This would be useful to me also. Otherwise, you can use my second bit of 
code and we can either try to work around the assertions, or report them 
here in the hopes that a developer can fix them. I have looked at the 
code myself, and guessed that it would take me several months to learn 
the code and determine a fix. There are thousands of lines of code there.

If you need more information just let me know. I can provide my 
incomplete thesis and other documents/code if you wish.

On 12/20/2010 04:28 AM, johnzjq wrote:
> Hi everyone,
>
> I am working on the feature elimination for CAD components and it would be
> nice to try "Opening" and "Closing" on a 3D model. However, I found it is
> not trival to implement "Minkowski difference" which is the oppsite of the
> "Minkowski sum".
>
> Any ideas or suggestions would be appreciated?
>
> John