Why are manifolds important?
On 2018-03-01 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
On 3/1/2018 1:23 PM, arnholm@arnholm.org wrote:
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.
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 cube-shaped
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.
On 1 March 2018 at 15:55, Jordan Brown openscad@jordan.maileater.net
wrote:
On 2/28/2018 12:52 AM, arnholm@arnholm.org wrote:
On 2018-02-28 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
2-manifold. You could print it, but it would fall apart. For a real-life
print you would set delta to some reasonable small value, and the model
becomes 2-manifold 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 not-2-manifold, but would be reasonably sensible to print.)
OpenSCAD mailing list
Discuss@lists.openscad.org
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 cube-shaped 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 multi-extruder models with STL?)
On 2018-03-01 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
... 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. Flipping faces on an otherwise consistent surface
just makes it tedious to work out.
If you really want to make it hard you can do something like a klein bottle.
kleinbottle.scad http://forum.openscad.org/file/t2140/kleinbottle.scad
--
Sent from: http://forum.openscad.org/
On 2018-03-02 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
On 3/2/2018 2:16 AM, arnholm@arnholm.org 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.
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.
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
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
non-intersecting/non-touching 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 self-intersect. 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/