# Why are manifolds important?

28 messages
12
Open this post in threaded view
|

## Why are manifolds important?

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

## Re: Why are manifolds important?

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

## Re: Why are manifolds important?

 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 : 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
Open this post in threaded view
|

## Re: Why are manifolds important?

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

## Re: Why are manifolds important?

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

## Re: Why are manifolds important?

Open this post in threaded view
|

## Re: Why are manifolds important?

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

## Re: Why are manifolds important?

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

## Re: Why are manifolds important?

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

## Re: Why are manifolds important?

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

## Re: 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 _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Why are manifolds important?

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

## Re: Why are manifolds important?

Open this post in threaded view
|

## Re: Why are manifolds important?

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

## Re: Why are manifolds important?

Open this post in threaded view
|

## Re: Why are manifolds important?

 > ... 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   -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Why are manifolds important?

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

## Re: Why are manifolds important?

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