Add offset3d() or shrinkwrap() operations using CGAL 5.6.1 new alpha offset feature

[amatulic]

Problem description

One significant feature that has been missing from OpenSCAD is the ability to perform 3D offsets efficiently, as well as perform non-convex hull operations as described in issue #4743.

Proposed solution

CGAL 5.61 implements an 'alpha wrap' capability, so why not OpenSCAD? It's there, it's available, let's take advantage of it.

It can accomplish a 3D offset for beveling, and create new manifold shapes by wrapping a non-convex skin around a cloud of points. As a bonus, in doing so it creates a closed manifold from shapes that might otherwise be messed up in some way.

Alternatives considered

The minkowski() operation is one way to do a 3D offset, but negative offsets aren't straightforward (see example 2 comments down). A true 3D offset would make it easier to create chamfers and fillets, in a similar fashion to doing it in 2D.

I have worked around the issue described in #4743 using polyhedron(), stitching the vertices of the two polygons together, and while this works, it isn't as elegant as a single function as #4743 suggests.

[gsohler]

3D offset is a very delicate topic and there are many cases which could make the operation fail. This is my favorite one. Any Idea, what happens with this vertex,which is part of 4 faces on negative offset ? [image: image.png]

…

On Sun, Mar 17, 2024 at 8:22 PM Alex Matulich ***@***.***> wrote: *Problem description* One significant feature that has been missing from OpenSCAD is the ability to perform 3D offsets efficiently, as well as perform non-convex hull operations as described in issue #4743 <#4743>. *Proposed solution* CGAL 5.61 implements an 'alpha wrap' capability. https://doc.cgal.org/latest/Alpha_wrap_3/index.html It can accomplish a 3D offset for beveling, and create new manifold shapes by wrapping a non-convex skin around a cloud of points. As a bonus, in doing so it creates a closed manifold from shapes that might otherwise be messed up in some way. *Alternatives considered* The minkowski() operation is one way to do a 3D offset, but negative offsets are not possible. A true 3D offset would make it easier to create chamfered edges. I have worked around the issue described in #4743 <#4743> using polyhedron(), stitching the vertices of the two polygons together, and while this works, it isn't as elegant as a single function as #4743 <#4743> suggests. — Reply to this email directly, view it on GitHub <#5049>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACCO4MUTMWT3GA64VPX2SO3YYXUOHAVCNFSM6AAAAABE2OHW5KVHI2DSMVQWIX3LMV43ASLTON2WKOZSGE4TAOBSGQYTKMA> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[jordanbrown0]

Nit: you can get Minkowski difference (which is, I believe, equivalent to negative offset) with minkowski() by negating the original object, doing the sum, and then negating the result.

From Wikipedia:

• [Minkowski difference] is defined as the complement of the Minkowski sum of the complement of A with the reflection of B about the origin.

Something like:

// An object larger than the model.
module universe() {
    big = 100;
    cube(big, center=true);
 }

// Minkowski difference, subtracting the second child from the first.
module mdiff() {
    intersection() {
        difference() {
            universe();
            minkowski() {
                difference() {
                    universe();
                    children(0);
                }
                children(1);
            }
        }
        universe();
    }
}

mdiff() {
    union() {
        cube(20);
        cube(20, center=true);
    }
    sphere(3, $fs=0.5);
}

[jordanbrown0]

Reflection of B left as an exercise for the reader.

[jordanbrown0]

@gsohler Your image didn't come through.

Independent of algorithm, I suspect that for the "radial" definition of offset, the definition is:

• For positive r, all points within r of any point of the surface are added to the object.
• For negative r, all points within r of any point of the surface are removed from the object.

In 2D space, this is the equivalent of tracing the outline with a round pen nib, or a round eraser, of the specified radius. That notion seems to extend to 3D space without trouble.

[amatulic]

@gsohler :

Any Idea, what happens with this vertex,which is part of 4 faces on negative offset ?

I have no idea. My main point was that this feature is already implemented in CGAL, the library that OpenSCAD uses for rendering, so why not support it in OpenSCAD?

If you want to know what happens in certain situations, wouldn't the best way to find out is to try it with the native CGAL operation? Admittedly I don't know how.

[nophead]

I would love a speed efficient way to model heat shrink sleeving over an arbitrary shape, such as a crimped faston like this.

[pca006132]

I think one still needs to offset the individual faces after calling alpha wrap, as alpha wrap just closes the gaps that are smaller than alpha? Also, it seems that internal holes are closed after doing this operation?

And we probably need a benchmark for this. Not very useful if it is not faster than doing minkowski...

[thehans]

It can accomplish a 3D offset for beveling

Can it?

I see there is mention of an offset parameter in its documentation, but it does not look anything like a clean roundover one might expect. From the description, it sounds more like relaxing the constraints for a sloppier output. I don't see this being desirable in any way for purposes of modeling a general 3d offset.

Quoted CGAL docs:

Figure 61.6 Impact of the offset parameter on the output. (Left) Input mesh generated by meshing a NURBS CAD model in parameter space. (Right) The smaller the offset, the closest sample points are to the input. The offset parameter is decreasing from left to right, to respectively 1/50, 1/200 and 1/1000 of the longest diagonal of the input bounding box. The alpha parameter is equal to 1/50 of the longest diagonal of the input bounding box for all level of details. A larger offset will produce an output less complex with better triangle quality. However the sharp features (red edges) are well preserved when the offset parameter is small.

[thehans]

Closing for misinformation. Alpha shapes have nothing to do with 3d offset

[amatulic]

@thehans - I apologize for the misunderstanding. Alpha shapes are still quite useful, however, and this ticket was not all about 3D offset if you look at the title. I would think that shrink-wrapping an error-ridden STL file would allow OpenSCAD to actually perform operations with it. Should I open a new feature request to support this?

[thehans]

There is also #1986 where shrinkwrap discussion could be added to, rather than open another ticket.

As mentioned in that thread, CGAL has had 3D Alpha Shapes for ages also, but no one has added that to openscad yet. The differences or advantages of the new "shrinkwrap" module is not immediately obvious to me, but I haven't spent much time reading over and comparing the two. If you have time to compare and summarize that could be useful info to add to the discussion.