Why are manifolds important?

classic Classic list List threaded Threaded
28 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Why are manifolds important?

JordanBrown

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 self-intersecting.  A self-intersecting 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 self-intersecting 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
Reply | Threaded
Open this post in threaded view
|

Re: Why are manifolds important?

nophead
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.

On 27 February 2018 at 14:45, Jordan Brown <[hidden email]> wrote:

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 self-intersecting.  A self-intersecting 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 self-intersecting 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



_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Why are manifolds important?

Ronaldo
In reply to this post by JordanBrown
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.

2018-02-27 11:45 GMT-03:00 Jordan Brown <[hidden email]>:

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 self-intersecting.  A self-intersecting 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 self-intersecting 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



_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
rew
Reply | Threaded
Open this post in threaded view
|

Re: Why are manifolds important?

rew
In reply to this post by nophead
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 ([10-tol,10,10]);
  translate ([0,10+tol,0]) cube ([10,10-tol,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
object-description-files.

        Roger.

--
** [hidden email] ** http://www.BitWizard.nl/ ** +31-15-2600998 **
**    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 brother-in-law Phil. But unlike
Phil, this plan just might work.

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Why are manifolds important?

Troberg
In reply to this post by JordanBrown
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
3D-printing. 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
Reply | Threaded
Open this post in threaded view
|

Re: Why are manifolds important?

JordanBrown
In reply to this post by nophead
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 corner-to-corner, 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 three-way 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
Reply | Threaded
Open this post in threaded view
|

Re: Why are manifolds important?

JordanBrown
In reply to this post by Troberg
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
3D-printing. 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
Reply | Threaded
Open this post in threaded view
|

Re: Why are manifolds important?

NateTG
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
Reply | Threaded
Open this post in threaded view
|

Re: Why are manifolds important?

cacb
In reply to this post by JordanBrown
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.

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([+size-delta,0,0])cube(size,center=true);
     translate([0,+size-delta,0])cube(size,center=true);
     translate([0,0,-size+delta])cube(size,center=true);
     translate([0,0,+size-delta])cube(size,center=true);
}

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.

Carsten Arnholm

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Why are manifolds important?

JordanBrown
On 2/28/2018 12:52 AM, [hidden email] 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
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Why are manifolds important?

cacb
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

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Why are manifolds important?

JordanBrown
On 3/1/2018 1:23 PM, [hidden email] 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.


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Why are manifolds important?

doug.moen
In reply to this post by JordanBrown
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 <[hidden email]> wrote:
On 2/28/2018 12:52 AM, [hidden email] 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
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org



_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Why are manifolds important?

JordanBrown
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?)


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Why are manifolds important?

cacb
In reply to this post by JordanBrown
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
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

polyhedron.scad (2K) Download Attachment
polyhedron.scad (2K) Download Attachment
polyhedron.scad (2K) Download Attachment
polyhedron_flipped.scad (2K) Download Attachment
polyhedron.zip (1K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Why are manifolds important?

NateTG
> ... 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/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Why are manifolds important?

cacb
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



_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Why are manifolds important?

JordanBrown
In reply to this post by cacb
On 3/2/2018 2:16 AM, [hidden email] 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.

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Why are manifolds important?

cacb
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
Reply | Threaded
Open this post in threaded view
|

Re: Why are manifolds important?

NateTG
In reply to this post by JordanBrown
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/

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