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 |
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:
_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
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]>:
_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
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 |
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 |
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:
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:
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 |
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 |
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 |
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 |
On 2/28/2018 12:52 AM,
[hidden email] wrote:
On 2018-02-28 00:43, 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? (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 |
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 |
On 3/1/2018 1:23 PM,
[hidden email] wrote:
Intuitively, it seems like a particular volume is "inside" if inWell, 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 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:
_______________________________________________ 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:
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 |
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 |
> ... 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 |
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 |
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 |
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 |
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 |
Free forum by Nabble | Edit this page |