Discuss manifoldness, co-incident faces edges etc
On 11/14/2019 11:39 AM, Carsten Arnholm wrote:
On 14.11.2019 19:42, Jordan Brown wrote:
Consider the 2D case. I'm drawing with a paintbrush, and so I'm
drawing areas, not lines. I draw a figure-8. It's
self-intersecting, but it's clearly not impossible. The two parts of
the stroke are unioned.
So if you changed paintbrush colour along the way, what would the
colour of the intersecting area be?
Good question, but you don't need self-intersection to have to answer
that question. What color do you get if you have two independent
strokes of different color that overlap?
What I was thinking of was the case in 3D where the topology is well
defined and closed, but where the geometry (i.e. the coordinates) are
such that some vertices fall within the volume of another part of the
body.
Yes. (It need not be vertices. Strictly, I think it's that one or more
edges penetrate one or more faces.)
What I meant it by physically impossible was if you took a steel rod
and bent it such that it would overlap itself. You cannot have two
instances of material occupying the same volume even though you can
formulate it with a polyhedron.
Indeed, two material objects cannot occupy the same space. But again
you don't have to get self-intersection to have that problem; you can't
have two independent steel rods overlap either. We do allow two
cylinders to overlap, via union, so our cylinders are not steel rods.
Two independent cylinders are allowed to occupy the same space, so why
isn't a bent cylinder allowed to have two parts that occupy the same space?
(Klein bottles are an obvious problem case, though I think they can be
looked at as either a winding problem or a self-intersection problem.
They don't have well-defined interiors and exteriors, and they
self-intersect.)
On 2019-11-15 01:25, Jordan Brown wrote:
Good question, but you don't need self-intersection to have to answer
that question. What color do you get if you have two independent
strokes of different color that overlap?
Since this is an analogy of booleans the answer is that you will have to
apply the proper colour model (additive or subtractive or something
else) to find the answer. This is possible in a union of two bodies,
see below.
Yes. (It need not be vertices. Strictly, I think it's that one or
more edges penetrate one or more faces.)
Agreed, I just simplified it.
Indeed, two material objects cannot occupy the same space. But again
you don't have to get self-intersection to have that problem; you
can't have two independent steel rods overlap either. We do allow
two cylinders to overlap, via union, so our cylinders are not steel
rods. Two independent cylinders are allowed to occupy the same space,
so why isn't a bent cylinder allowed to have two parts that occupy the
same space?
The answer is that when you union two different cylinders we have a well
understood process (boolean union) to resolve overlaps that typically
also offer a way to handle a way to handle properties, at least I
believe that is the case in Carve even if I have not used those
features. I don't know if CGAL has something in that area.
However, there is no union operator that I know of that is able to
handle "self-unions", and thus no way to handle the properties that may
not necessarily be constant throughout the solid.
Since this is about manifoldness, it is worth mentioning that solids
with different subvolumes consisting of different materials (e.g.
different plastic colour) is a good example where something else than
2-manifold solids is both useful and even required. The internal
boundary between the materials causes the body to have N-manifold edges,
and faces with no "outside". This is is perfectly meaningful both
topologically and physically, such solids are all around us.
Returning to the bent cylinder case, if it was all one material you
could argue that selecting the material in the resulting overlap would
not matter since it would be the same either way (assuming the property
was constant that is, but you still have to figure out how to do self
union). If the bar was N-manifold with different materials you would
have to resolve the property issue.
So I think the answer to your question about the difference between two
overlapping cylinders vs. one self-overlapping bent cylinder is that
union is defined for the first case, but I am not so sure about the
other. Perhaps a self-union can be defined that resolves self overlaps,
I have not studied that.
Carsten Arnholm
If you can partition the self-overlapping object into separate sections
that don't self overlap but do overlap each other than they can be unioned
back together. So perhaps the solution lies that way.
On Fri, 15 Nov 2019 at 07:19, arnholm@arnholm.org wrote:
On 2019-11-15 01:25, Jordan Brown wrote:
Good question, but you don't need self-intersection to have to answer
that question. What color do you get if you have two independent
strokes of different color that overlap?
Since this is an analogy of booleans the answer is that you will have to
apply the proper colour model (additive or subtractive or something
else) to find the answer. This is possible in a union of two bodies,
see below.
Yes. (It need not be vertices. Strictly, I think it's that one or
more edges penetrate one or more faces.)
Agreed, I just simplified it.
Indeed, two material objects cannot occupy the same space. But again
you don't have to get self-intersection to have that problem; you
can't have two independent steel rods overlap either. We do allow
two cylinders to overlap, via union, so our cylinders are not steel
rods. Two independent cylinders are allowed to occupy the same space,
so why isn't a bent cylinder allowed to have two parts that occupy the
same space?
The answer is that when you union two different cylinders we have a well
understood process (boolean union) to resolve overlaps that typically
also offer a way to handle a way to handle properties, at least I
believe that is the case in Carve even if I have not used those
features. I don't know if CGAL has something in that area.
However, there is no union operator that I know of that is able to
handle "self-unions", and thus no way to handle the properties that may
not necessarily be constant throughout the solid.
Since this is about manifoldness, it is worth mentioning that solids
with different subvolumes consisting of different materials (e.g.
different plastic colour) is a good example where something else than
2-manifold solids is both useful and even required. The internal
boundary between the materials causes the body to have N-manifold edges,
and faces with no "outside". This is is perfectly meaningful both
topologically and physically, such solids are all around us.
Returning to the bent cylinder case, if it was all one material you
could argue that selecting the material in the resulting overlap would
not matter since it would be the same either way (assuming the property
was constant that is, but you still have to figure out how to do self
union). If the bar was N-manifold with different materials you would
have to resolve the property issue.
So I think the answer to your question about the difference between two
overlapping cylinders vs. one self-overlapping bent cylinder is that
union is defined for the first case, but I am not so sure about the
other. Perhaps a self-union can be defined that resolves self overlaps,
I have not studied that.
Carsten Arnholm
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
On 2019-11-15 09:15, nop head wrote:
If you can partition the self-overlapping object into separate
sections that don't self overlap but do overlap each other than they
can be unioned back together. So perhaps the solution lies that way.
That sounds as complicated as the original problem, maybe more so.
Partitioning is not so easy, it is the kind of thing that is done in
Minkowski.
Here is a rough sketch of I think it could be done (ignoring the issue
of property resolution):
Assume we start with a clean 2-manifold solid, potentially self
overlapping.
Stage 1 is to detect whether self overlapping has indeed happened. I
think this must be done by discovering face/face intersections between
faces of the solid.
Stage 2 is to imprint the intersection edges on those faces, i.e. split
them creating N-manifold edges. When all intersections are done, you
have some internal faces with no outside.
Stage 3 is to identify those internal faces and remove them. This is
tricky. The candidates are faces referring to N-manifold edges where
N>2, but it is not a sufficient criterion. However if you can identify
the internal faces and remove them, the result is 2-manifold.
Carsten Arnholm
I think those three steps are exactly what union does. The only
difference is the faces belong to two separate objects instead of being
from the same object. So perhaps the source code for a union operation can
be hacked to union an object with itself. A unary union!
On Fri, 15 Nov 2019 at 09:15, arnholm@arnholm.org wrote:
On 2019-11-15 09:15, nop head wrote:
If you can partition the self-overlapping object into separate
sections that don't self overlap but do overlap each other than they
can be unioned back together. So perhaps the solution lies that way.
That sounds as complicated as the original problem, maybe more so.
Partitioning is not so easy, it is the kind of thing that is done in
Minkowski.
Here is a rough sketch of I think it could be done (ignoring the issue
of property resolution):
Assume we start with a clean 2-manifold solid, potentially self
overlapping.
Stage 1 is to detect whether self overlapping has indeed happened. I
think this must be done by discovering face/face intersections between
faces of the solid.
Stage 2 is to imprint the intersection edges on those faces, i.e. split
them creating N-manifold edges. When all intersections are done, you
have some internal faces with no outside.
Stage 3 is to identify those internal faces and remove them. This is
tricky. The candidates are faces referring to N-manifold edges where
N>2, but it is not a sufficient criterion. However if you can identify
the internal faces and remove them, the result is 2-manifold.
Carsten Arnholm
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
We are now discussing how shape operators (like union) should deal with properties (like colour) that vary over space.
In Curv, which is my own 3D solid modelling language, I have a general answer to these questions.
Curv supports full colour models. Curv supports volumetric colour. A colour function assigns a colour to every point on the surface and within the interior of a 2D or 3D shape. I chose this model because it works for advanced 3D printers, like the Stratasys J750, that are capable of assigning different colour and material properties to each voxel of a 3D solid.
For the union operator, I chose the "painters algorithm" to determine the colour of the output. The order of the arguments to union matters. First we "paint" the first shape onto the "canvas", then we "paint" the second shape, which overrides the colours of the first shape wherever they overlap, and so on. It is a very intuitive model when you work in 2D, and 3D works the same way.
The intersection operator is different. I regard the first argument to be the "base" shape, and all of the colours of the output come from this base shape. Subsequent arguments are interpreted as specifying what parts of the base shape to carve away. Since Curv has volumetric colour, not surface colour, carving away parts of the base shape reveal colours under the surface that might not be visible on the surface. For example, I have a "wood grain" colour function, and a "marble" colour function, that simulate the 3D colour distribution of these natural materials. Using difference or intersection to carve away parts of an object has the same visual result as carving wood or marble.
For the case of sweeping a 2D object along a path in 3-space, with possible self-intersection, my model is based on the idea of a paint brush moving over a canvas, where the shape of the brush and the colour of the paint may change as the brush moves, and using opaque paint. You could also call this "painters algorithm", it's conceptually related to how union works. The path that we sweep along is specified by a function that maps a parameter 't' onto a point in 3-space. Let's say that 't' varies from 0 to 1. We begin the sweep at t=0, and we end the sweep at t=1. If there is a self intersection at t=i and t=j, where i < j, then the colours at j override the colours at i.
For the case of sweeping a 3D object along a path in 3-space, I have no idea how to apply the painters algorithm to this situation. My only idea is to apply a single colour function to the final result. I don't find these kinds of sweeps interesting or useful for my own work, so I haven't tried to develop this further.
The final problem is positive offsets, where you are growing the object by adding a constant offset from the surface. For a non-convex shape, different branches of the shape can self-intersect as the shape grows. There is no obvious concept of ordering here, where one branch of the shape is later than or comes after any other branch, so it's not clear how painters algorithm would apply. So I don't do that. Instead, I rely on the colour function that is attached to the shape, which assigns a different colour to each point in 3 dimensional space. As the shape grows, it occupies new points in space that it didn't previously occupy, and the colour function is consulted to determine the colour of those new points. This analogous to what happens when you carve away parts of a shape using difference or intersection, except happening in reverse.
This is probably a naive question, in that I consider all this stuff to be
magic, but...
Is there a substantial difference between detecting the internal
faces/edges/vertices of two cubes in the form of an 'X', and the 'X' formed
by a single square swept in a figure 8?
--
Sent from: http://forum.openscad.org/
Probably not but OpenSCAD uses CGAL and CGAL seems to reject self
intersecting manifolds. If you generate a figure of 8 with an S unioned
with a mirrored S then the result will be fine. The actual operation it
does where they cross is exactly what the same as if it was fixing a full
figure of 8. The only difference is the operands of union are both
non-self intersecting.
On Fri, 15 Nov 2019 at 14:41, lar3ry lar3ry@sasktel.net wrote:
This is probably a naive question, in that I consider all this stuff to be
magic, but...
Is there a substantial difference between detecting the internal
faces/edges/vertices of two cubes in the form of an 'X', and the 'X' formed
by a single square swept in a figure 8?
--
Sent from: http://forum.openscad.org/
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Not really. But the problem is that the lines are a representation of the
boundary of an object. If the line pieces end at the "x", you have two
separate close loops that could be printed or constructed. However, if the
line pieces cross each other, this is no longer possible.
This is because the boundary lines have a "material" side and an "outside"
size. 3D triangular faces have something similar: they have an outward
facing normal that follows from the order of the corner points.
In the crossing lines example, the figure may look just the same to you, but
it is impossible to know on which side of the lines you would have to put
the material. For the crossing lines, the "material" and "outside" side swap
at the crossing. But even without crossing lines or faces you could make
impossible figures like the Moebius band
https://www.escherinhetpaleis.nl/story-of-escher/perpetuum-mobile/?lang=en
or the Klein bottle https://en.wikipedia.org/wiki/Klein_bottle .
So you can invent more boundaries that do not define objects. The
manifoldness is a way to ensure that there is actually something that could
exist as an object. We might think of that as "3D printability", but even
the preview window wants to show you what your code looks like as an object.
So if that object cannot be defined, the preview window cannot show you
anything useful either.
--
Sent from: http://forum.openscad.org/
[How Curv treats properties that vary over space.]
Okay, I missed the original problem description, which was bending a rod around a cylinder through an angle > 180°, so that the ends of the rod self intersect. What happens if the rod is not uniformly coloured?
So I don't actually know a solution to this that I like.
Carsten said "You will have to apply the proper colour model (additive or subtractive)". In other words, some sort of order-independent colour mixing. That seems like the obvious solution to me as well. I don't particularly like it, because in most cases I don't like the visual results of colour mixing. The results are probably useless to me, so I just need to override the colours anyway to make the result look good. If the rods are cylindrical, then it might not matter (the colour mixing won't apply to the surface of the shape, only to the interior. But if the rod has a square cross section, and the square faces of the two rod ends are perfectly aligned in the self intersecting region after the bend, then you will also see the colour mixing on the surface.
Nophead said to partition the self overlapping object into separate sections. Now you have a basis for specifying that one section overrides the colours of the other section. The problem with this, as Carsten said, is the complexity of specifying this. It's nice to just have a generic "bend" operator that doesn't require you to specify extra parameters to specify the override priority of different regions of the shape you are about to bend, in case there is a self intersection.
Carsten said "self-intersection is a sign something has gone wrong". The fact that there isn't a really satisfying solution to the bend problem might seem to validate that stance.
But, I've defined several bend operators in Curv, and I find them very useful. As currently implemented, they aren't fully general, because they don't support self intersection. Because self intersection is hard to implement. It would be better if I could remove this limitation, it would provide a better user experience.
There are CAD programs that support a bend command, but I haven't used any of them, so I don't know if self intersection is supported or how it is handled. Eg, I found this with google: https://knowledge.autodesk.com/support/inventor-products/learn-explore/caas/CloudHelp/cloudhelp/2016/ENU/Inventor-Help/files/GUID-98FDE447-C0A7-4694-ABD3-BA19A329DDF6-htm.html