
12

One of the things that has puzzled me is the requirement that
objects for 3D printing be manifold.
First, I should note that I'm not strong on the math involved and
so I'm not *absolutely* sure what "manifold" means.
I understand that it's bad for objects to be selfintersecting.
A selfintersecting object ... isn't exactly an object at all, and
has no translation to physical reality. Well, except maybe
through implicitly unioning. And, absent "polyhedra" and
"polygons" that aren't polyhedra or polygons, is there any way to
get selfintersecting objects in OpenSCAD?
But I don't understand the requirement to avoid shared edges.
cube(1);
translate([1,1,0]) cube(1);
Why is this a problem? Yeah, it's got a piece that's zero
thickness right along where the two cubes touch, but that doesn't
seem any harder than having it be infinitesimal. It's more or
less obvious what I mean, so why should I have to worry about it?
Why should I have to keep nudging objects around so that they
don't touch, when in the physical reality that I'm trying to model
they *do* touch?
(And if you ask "should the slicer put a filament between the two
cubes", my answer is "I don't care". If I wanted them to be
separate objects I would have kept them separate, and if I wanted
them to be solidly joined I would have made them solidly joined.
Again, this seems like an extreme case of a piece of an object
that is much smaller than the extrusion width or thickness, or two
objects that mathematically don't touch but are separated by less
than the printer resolution.)
Is it all about making unambiguous sense out of polygon soup?
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


Jordan,
The manifold condition is demanded mainly for technical reasons. Fortunately, it agrees with the common sense for 3D printing as nophead likes to say. But many algorithms would be more complex if the manifold condition is not met. For instance, imagine a slicer algorithm computing the outer hotend path of a layer. When it arrives to the edge of the mesh, it should decide where to go from there. If the edge is common to two cubes there are three possible ways to go on and the algorithm should keep a record of the decision it makes there in order to avoid retracing a path already taken. With a manifold condition there is only one way to go on from an edge and you don't need to keep any record.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


On Tue, Feb 27, 2018 at 04:28:45PM +0000, nop head wrote:
> Two objects can't share an edge in reality, so there is no reason to
> send such models to a 3D printer. If you want them joined then have
> some overlap, if not leave a gap.
My printer makes the outsides of objects quite accurately. But when I
command a 3mm hole in openscad, I get something quite a lot smaller.
I can then command a 3.5mm hole and get something that fits a 3mm
bolt. Great.
The problem with this approach is that I can design perfect objects
for my printer, but they will work "not well" for others.
The objects STL/openscad that we publish should be as close as
possible to "what works". People should preferably tell the slicer to
increase the hole sizes etc.etc.
Suppose I have
union () {
cube ([20,20,1]);
translate ([10,0,0]) cube (10);
translate ([0,10,0]) cube (10);
}
In theory two of these can mate. In practice, to make it work
you would have to do something like this.
tol=0.2;
union () {
cube ([20,20,1]);
translate ([10+tol,0,0]) cube ([10tol,10,10]);
translate ([0,10+tol,0]) cube ([10,10tol,10]);
}
So... I would think that "edges in common" are something that happen
commonly "theoretically ideal" files. And it would be preferable to be
able to load such theoretical files into slicers because that
eliminates the tolerances that individual printers have from the
objectdescriptionfiles.
Roger.

** [hidden email] ** http://www.BitWizard.nl/ ** +31152600998 **
** Delftechpark 26 2628 XH Delft, The Netherlands. KVK: 27239233 **
* BitWizard writes Linux device drivers for any device you may have! *
The plan was simple, like my brotherinlaw Phil. But unlike
Phil, this plan just might work.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


Very "explain like I'm 5" explanation:
The manifold is the surface that determines what's the inside and what's the
outside of the object, which is, of course extremely important when
3Dprinting. So, if a polygon is facing the wrong way, or two sides or edges
line up perfectly, we get an ambiguous situation, where we can't always
figure out what's inside and what's outside, which of course messes things
up.

Sent from: http://forum.openscad.org/_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


I can, by the way, readily believe that
in a polygon soup it may be difficult or perhaps even impossible
to decide what parts are inside and what parts are outside. If
you have six cubes laid out touching around a central cubic void,
I could easily believe that it would be hard to tell whether that
central cube should or should not be filled. That seems like a
key problem with a "polygon soup" structure.
On 2/27/2018 8:28 AM, nop head wrote:
Two objects can't share an edge in reality, so
there is no reason to send such models to a 3D printer. If you
want them joined then have some overlap, if not leave a gap.
Can't they?
For all macroscopic purposes, they can  if I take two cubes and
shove them cornertocorner, they sure *look* like they are sharing
an edge.
Yes, I understand that at some microscopic / mathematical level they
aren't, but why do I have to care about that?
On 2/27/2018 9:02 AM, Ronaldo Persiano
wrote:
The manifold condition is demanded mainly for
technical reasons. Fortunately, it agrees with the common sense
for 3D printing as nophead likes to say. But many algorithms
would be more complex if the manifold condition is not met. For
instance, imagine a slicer algorithm computing the outer hotend
path of a layer. When it arrives to the edge of the mesh, it
should decide where to go from there. If the edge is common to
two cubes there are three possible ways to go on and the
algorithm should keep a record of the decision it makes there in
order to avoid retracing a path already taken. With a manifold
condition there is only one way to go on from an edge and you
don't need to keep any record.
If my two cubes were separated by a tiny distance  say, a
micrometer  then the slicer would know what to do. It would
probably try (and probably fail) to separate the two paths by a
micrometer, and the result would probably be either a tiny gap or a
tiny overlap.
If my two cubes were joined by a similarly tiny distance, the slicer
would again know what to do. It would probably consider putting
plastic across the joint, realize that the plastic would have to be
much smaller than the extrusion width, and either leave a gap or lay
down plastic far larger than that called for by the model.
So if the slicer can handle a gap of epsilon, and it can handle a
joint of epsilon, and it produces pretty much the same result in
both cases, why does a gap of zero cause its brain to explode? Or
perhaps I should say: why SHOULD a gap of zero cause its brain to
explode?
In 3D printing, the resolution is around 100um (depending on printer
and axis blah blah blah). Anything below that is too small to care
about... so why should we have to care about it?
I can get that the algorithms might be a little simpler, but how
many slicer developers are there and how many model designers are
there? Which does it make sense to optimize for?
Also: it seems like your slicer algorithm will inevitably be faced
with issues like this, because it's dealing with physical reality,
not math. If the two cubes have a joint that is only one extrusion
width wide, the slicer is faced with the same threeway choice.
Similarly if it's three extrusion widths wide, when making the
second loop. In fact, the "zero" case seems easier  there (if
you've defined that the edge of the mathematical object should be
the edge of the physical object) it's clear that it must stay on the
"same" cube, because the centerline of the extrusion must be 0.5EW
inside the mathematical boundary... and transitioning onto that
other cube would necessarily take the plastic outside of the bounds
of the mathematical object.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


Sorry, I thought I read ahead before
responding, but it seems not.
On 2/27/2018 11:50 AM, Troberg wrote:
Very "explain like I'm 5" explanation:
Exactly! :)
The manifold is the surface that determines what's the inside and what's the
outside of the object, which is, of course extremely important when
3Dprinting. So, if a polygon is facing the wrong way, or two sides or edges
line up perfectly, we get an ambiguous situation, where we can't always
figure out what's inside and what's outside, which of course messes things
up.
As you will have seen, that was my guess.
This is a "polygon soup" problem, that would be solved using a data
structure that directly represents polyhedra, right?
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


JordanBrown wrote
> ...
>
> As you will have seen, that was my guess.
>
> This is a "polygon soup" problem, that would be solved using a data
> structure that directly represents polyhedra, right?
>
> ...
I'm not sure that "directly represents polyhedra" means anything.
Something like a voxel model would not have these issues, but has its own
drawbacks.

Sent from: http://forum.openscad.org/_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


On 20180228 00:43, Jordan Brown wrote:
> I can, by the way, readily believe that in a polygon soup it may be
> difficult or perhaps even impossible to decide what parts are inside
> and what parts are outside. If you have six cubes laid out touching
> around a central cubic void, I could easily believe that it would be
> hard to tell whether that central cube should or should not be filled.
> That seems like a key problem with a "polygon soup" structure.
No, the issue of where the material is and where the void is, is
unrelated to the question of "polygon soup" vs. an explicitly connected
polyhedron, assuming the "polygon soup" is reasonable enough that
connectivity can be inferred from it.
What is is "inside" is entirely determined by the triangle face normal
vectors. The normal vector is computed from the 3 triangle vertex
coordinates, i.e. cross product of 2 vectors. It is the local order of
the triangle vertices that determines which way the face normal points
and therefore also where "inside" and "outside" is. This can be either
way in both a polyhedron and a polygon soup representation.
To make a meaningful solid you need to have faces that are properly
connected to a single neighbour at each edge (2 manifold) and the
normals must be consistently pointing the same way ("outwards") from one
face to its neighbour. The face normal requirement is valid also when
you have a polygon soup like STL.
Your six cube example is ok wrt. defining inside/outside as long as the
face normals all point out of the cubes. You will however have 12 edges
that are not 2 manifold (they are each referenced by 4 faces rather than
2).
size = 10;
delta = 0;
union() {
translate([size+delta,0,0])cube(size,center=true);
translate([0,size+delta,0])cube(size,center=true);
translate([+sizedelta,0,0])cube(size,center=true);
translate([0,+sizedelta,0])cube(size,center=true);
translate([0,0,size+delta])cube(size,center=true);
translate([0,0,+sizedelta])cube(size,center=true);
}
The material volume of this is well defined (6000) even if it is not
2manifold. You could print it, but it would fall apart. For a reallife
print you would set delta to some reasonable small value, and the model
becomes 2manifold and would hold together.
Carsten Arnholm
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


On
20180228 00:43, Jordan Brown wrote:
I can, by the way, readily believe that in
a polygon soup it may be
difficult or perhaps even impossible to decide what parts are
inside
and what parts are outside. If you have six cubes laid out
touching
around a central cubic void, I could easily believe that it
would be
hard to tell whether that central cube should or should not be
filled.
That seems like a key problem with a "polygon soup" structure.
No, the issue of where the material is and where the void is, is
unrelated to the question of "polygon soup" vs. an explicitly
connected polyhedron, assuming the "polygon soup" is reasonable
enough that connectivity can be inferred from it.
What is is "inside" is entirely determined by the triangle face
normal vectors. The normal vector is computed from the 3 triangle
vertex coordinates, i.e. cross product of 2 vectors. It is the
local order of the triangle vertices that determines which way the
face normal points and therefore also where "inside" and "outside"
is. This can be either way in both a polyhedron and a polygon soup
representation.
If you have a real polyhedron definition, where you know which
triangles belong together and how they are connected, do you still
need to care about normal vectors?
(Assuming that you define the rest of the universe to be "outside".)
Intuitively, it seems like a particular volume is "inside" if in
getting there from the outside you have to cross an odd number of
faces.
Your six cube example is ok wrt. defining inside/outside as long
as the face normals all point out of the cubes. You will however
have 12 edges that are not 2 manifold (they are each referenced by
4 faces rather than 2).
Yes.
The material volume of this is well defined (6000) even if it is
not 2manifold. You could print it, but it would fall apart. For a
reallife print you would set delta to some reasonable small
value, and the model becomes 2manifold and would hold together.
Right. It was intended as a geometry discussion point, not
something really printable. (But two cubes with touching edges, on
top of another object, would be not2manifold, but would be
reasonably sensible to print.)
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


On 20180301 21:55, Jordan Brown wrote:
> If you have a real polyhedron definition, where you know which
> triangles belong together and how they are connected, do you still
> need to care about normal vectors?
Yes, you still need to care about normal vectors. If you flip them all,
the rest of the universe becomes "inside". If you flip a few, the
inside/outside is not defined. Calculating the volume depends on the
normal vector directions, if you flip a few, you will not be able to
calculate a meaningful volume.
> Intuitively, it seems like a particular volume is "inside" if in
> getting there from the outside you have to cross an odd number of
> faces.
Well, you need a definition of "outside" to perform that test...
otherwise you don't know if the starting position is inside or outside.
;)
The F12 test in OpenSCAD is there to show if some normals are flipped.
If you see a red face it is the back side of the polygon (opposite of
face normal). It should never be visible for a correctly defined
polyhedron when the viewpoint is outside.
Carsten Arnholm
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


Intuitively, it seems like a particular
volume is "inside" if in
getting there from the outside you have to cross an odd number
of
faces.
Well, you need a definition of "outside" to perform that test...
otherwise you don't know if the starting position is inside or
outside. ;)
I *did* define the rest of the universe to be "outside".
And finding a point that is "outside" by that definition is easy:
any point that's outside the bounding box.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


In a more general context than OpenSCAD, it is meaningful to have infinite polyhedra. If you perform a set complement operation on a cube, you get an infinite polyhedron that fills all of 3D space, except for a cubeshaped hole. This can be represented by flipping the triangles, so that everything inside is outside, and vice versa. For example, CGAL supports this with its Nef Polyhedron data structure. For another example, my Curv project supports infinite objects, and I regularly use them to construct models for 3D printing. In this case, the infinite object is intersected with a finite object to create a printable object.
Within the context of OpenSCAD, it is meaningful to construct a hollow shape, with internal voids. A common convention used by the 3D printing community is that mesh surfaces with the triangles flipped are "negative objects". Voids are represented by negative objects, and their volume is subtracted from any positive object that they intersect. By contrast, positive objects that intersect are implicitly added together or unioned together by slicers. I think you are arguing that a different convention could also be used successfully, but it's more important for everybody to agree on one convention, so that different 3D modelling and printing tools are compatible. A possible downside of your convention is that two mesh volumes that slightly intersect, perhaps by accident, create a void where they overlap, which might lead to accidental occurrences of voids.
The "negative object" convention of the 2nd paragraph is different from the "infinite object" convention of the first paragraph. They illustrate two different use cases where the direction in which the face of a polyhedron is pointing matters.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


On 3/1/2018 1:54 PM, doug moen wrote:
In a more general context than OpenSCAD, it is
meaningful to have infinite polyhedra. If you perform a set
complement operation on a cube, you get an infinite polyhedron
that fills all of 3D space, except for a cubeshaped hole. This
can be represented by flipping the triangles, so that everything
inside is outside, and vice versa. For example, CGAL supports
this with its Nef Polyhedron data structure. For another
example, my Curv project supports infinite objects, and I
regularly use them to construct models for 3D printing. In this
case, the infinite object is intersected with a finite object to
create a printable object.
Within the context of OpenSCAD, it is meaningful to
construct a hollow shape, with internal voids. A common
convention used by the 3D printing community is that mesh
surfaces with the triangles flipped are "negative objects".
Voids are represented by negative objects, and their volume is
subtracted from any positive object that they intersect. By
contrast, positive objects that intersect are implicitly added
together or unioned together by slicers. I think you are
arguing that a different convention could also be used
successfully, but it's more important for everybody to agree
on one convention, so that different 3D modelling and printing
tools are compatible. A possible downside of your convention
is that two mesh volumes that slightly intersect, perhaps by
accident, create a void where they overlap, which might lead
to accidental occurrences of voids.
The "negative object" convention of the 2nd paragraph is
different from the "infinite object" convention of the first
paragraph. They illustrate two different use cases where the
direction in which the face of a polyhedron is pointing
matters.
Thanks. (Come to think of it, I've occasionally wanted infinite
objects  e.g., to clip off everything below Z=0. I've faked it
with objects that are merely really big.)
I'm not really pushing hard for any particular answer, just trying
to understand whether a less soupy representation would get rid of a
number of these nuisances where somebody who isn't deeply familiar
with the math and geometry will say "what's your problem, it's
obvious what I mean!".
While I don't think it's necessary to have only one convention, I
agree that the number needs to be small. I'd actually say that it's
best if there's more than one, so that the tools are designed to
support more than one rather than having the One True Format burned
into them. That way, when somebody comes up with a new scheme that
is demonstrably better, it's less hard to plug it into the existing
applications. (E.g., how do you do multiextruder models with STL?)
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


On 20180301 22:35, Jordan Brown wrote:
> I *did* define the rest of the universe to be "outside".
>
> And finding a point that is "outside" by that definition is easy: any
> point that's outside the bounding box.
Well, you can use such a definition, but counting the number of faces
crossed and coming up with a reliable even/odd answer is really not
trivial if at all possible. Sometimes you hit exactly an edge and will
have to decide whether it is 1 or 2 intersections. If you happen to hit
exactly a vertex there will be more than 2 alternatives.
Let us for the sake of argument assume your premise that the face normal
orientation of a polyhedron is irrelevant and can be either way. My
question is then: How do you compute the volume of a general polyhedron
without assuming anything about face normals? I have attached a zip file
with 2 OpenSCAD scripts
polyhedron.scad : all face normals away from object (standard, correct
definition)
polyhedron_flipped.scad : Some faces are flipped (inverted normals),
otherwise identical.
Can you compute the volume of these two, and what are the answers? Are
the answers meaningful?
Carsten Arnholm _______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


On 20180302 15:01, NateTG wrote:
>> ... How do you compute the volume of a general polyhedron without
>> assuming
> anything about face normals?
>
> You need a closed orientable surface in order for there to be an
> interior
> volume. So you really only have to assume that there's some consistent
> way
> to assign face normals.
That was my assertion. The alternative implication by Jordan Brown (at
least as I understood it) was that the normal orientation didn't matter
and could be arbitrary from one triangle to the next, but this is not
so. As you say, all normals must be oriented consistently. The common
convention is that when the normals are pointing away from the object it
corresponds to a positive volume and if all normals are flipped it
corresponds to a negative volume. When only some are flipped the volume
is not really defined.
Carsten Arnholm
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


Well, you
can use such a definition, but counting the number of faces
crossed and coming up with a reliable even/odd answer is really
not trivial if at all possible.
"It's hard" is very different from "it's impossible".
And maybe it is too hard.
Can you
compute the volume of these two, and what are the answers? Are the
answers meaningful?
*I* certainly can't, for either of them.
The first important question is whether it's theoretically
possible. Then there's the question of whether it's practically
possible.
The reason that I'm pushing on these question is that it seems like
there are a number of "gotchas" where somebody who doesn't deeply
understand the underlying math will do something subtly wrong
(letting two objects touch, or describing a polyhedron wrong) and
will get error messages or, worse, strange results. Eliminating
cases like that seems highly desirable, when it's possible.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


Btw. sorry for repeated attachments in the previous message, my webmail
played a trick on me.
On 03. mars 2018 05:38, Jordan Brown wrote:
>> Can you compute the volume of these two, and what are the answers? Are
>> the answers meaningful?
>
> *I* certainly can't, for either of them.
>
> The first important question is whether it's theoretically possible.
> Then there's the question of whether it's practically possible.
It is certainly both theoretically and practically possible *if* the
face normals are consistently oriented. It is almost trivial when that
condition is met. The answer to the volume question for polyhedron.scad is
volume1=1171573.2378
To compute the volume, select an arbitrary point P, such as e.g the
origin (0,0,0). Then, for each triangle in the polyhedron compute the
*signed* volume of the tetrahedron defined by the triangle vertices and
point P. Add the signed volumes computed this way for all the faces of
the polyhedron, and you get the polyhedron volume. This also works for
polyhedra with one or more internal voids *if* the faces are oriented
consistently "away from the material".
If you apply the above procedure to the other model
polyhedron_flipped.scad where some of the faces were flipped (not all)
you will get a different and meaningless result:
volume2=571489.003806
By flipping more and more faces, the value becomes less and less. Once
all the faces are flipped and thus again become consistent, the volume
becomes 1171573.2378, i.e. the same absolute value as for volume1, but
negative sign. This illustrates how the volume computation with internal
voids work.
Most people are not concerned with computing the volumes like this, but
the point I am trying to make through this is that it is essential to
orient the face normals consistently. If you are sloppy about it there
will be bad effects, and it isn't limited to computing the volume.
> The reason that I'm pushing on these question is that it seems like
> there are a number of "gotchas" where somebody who doesn't deeply
> understand the underlying math will do something subtly wrong (letting
> two objects touch, or describing a polyhedron wrong) and will get error
> messages or, worse, strange results. Eliminating cases like that seems
> highly desirable, when it's possible.
It is certainly a good idea to spend some time understanding these
"gotchas", I agree 100%. I guess the most common mistake is letting two
objects touch without some overlap.
Carsten Arnholm
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


Since you guys are still on this:
JordanBrown wrote
> On 3/2/2018 2:16 AM,
> arnholm@
> wrote:
>> Well, you can use such a definition, but counting the number of faces
>> crossed and coming up with a reliable even/odd answer is really not
>> trivial if at all possible.
>
> "It's hard" is very different from "it's impossible".
>
> And maybe it is too hard.
Provided the space is defined in terms of orientable
nonintersecting/nontouching triangle meshes "shell counting" isn't
appreciably harder than calculating the volume.
>> ... was that the normal orientation didn't matter and could be arbitrary
>> from one triangle to the next, ...
It doesn't. What matters is that a consistent assignment of normals is
possible and the surface doesn't selfintersect. If that is the case, it's
not that challenging to work out a proper winding direction of each face
automatically. (Zero volume surfaces can have multiple valid windings.)

Sent from: http://forum.openscad.org/_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

12
