Reversed faces
From the Admesh library, referenced by
https://github.com/openscad/openscad/issues/1042:
A common problem with STL files is that some or all of facets are oriented
backwards; i.e. the vertices are listed in a clockwise direction when
viewed from outside the part. Admesh repairs the orientation of facets
according to the following algorithm:
- Generate the neighbors list for all facets.
- Inspect the first neighbor of the first facet to determine the
orientation of its vertices. - If the neighboring facet is oriented in the same direction as the first
facet, mark the neighbor as checked. If the neighboring facet is oriented
opposite to the first facet, reverse the neighbor, and mark it as checked. - Repeat steps 2 and 3 until all facets have been checked.
The above algorithm ensures that all connected facets are oriented in the
same direction. However, if the first facet is backwards, then all facets
will be backwards. The correct orientation for the entire part is
determined after the volume has been calculated. If the volume is
negative, then all of the facets must be backwards. Admesh then reverses
all facets to set the correct orientation.
Nop Head's original suggestion is to report if two neighbouring facets have
opposite orientations, which matches what Admesh does. And that probably
takes care of the most common case where people screw up the arguments to
polyhedron and ask for help on the forum. It wouldn't be perfect, but it
would be progress.
Detecting whether all faces are backwards looks more complicated and
expensive. There's no "local" property you can test, as in the neighbouring
facet test. It's a global property of the entire shape.
- Admesh does this by computing the volume, and testing if it is
negative. Computing the volume might be expensive? There's another thread,
a pull request for a "probe" function, which adds the ability to compute
the volume of a shape, but this computation is said to be very expensive.
It requires a convex decomposition, which in itself is expensive. - I'm not sure how Admesh deals with a complex object containing an
interior void. Then you have an interior mesh, and an exterior mesh, which
aren't connected. The interior mesh is expected to have a negative volume,
while the exterior mesh is expected to have a positive volume.
On 11 January 2016 at 08:59, Marius Kintel marius@kintel.net wrote:
Some related issues:
https://github.com/openscad/openscad/issues/348
https://github.com/openscad/openscad/issues/1042
https://github.com/openscad/openscad/issues/590
Two things:
o We should rewrite our mesh class to support tests and operators like
this. This would also be a good step towards repairing imported STLs which
CGAL struggles with. We could also look at external libraries with good
mesh classes.
o Highlights of reversed faces in preview mode: It should be possible to
simply turn this on.
-Marius
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Does polyhedron currently work if you have an interior hole with a negative
volume?
On 11 January 2016 at 16:42, doug moen doug@moens.org wrote:
From the Admesh library, referenced by
https://github.com/openscad/openscad/issues/1042:
A common problem with STL files is that some or all of facets are oriented
backwards; i.e. the vertices are listed in a clockwise direction when
viewed from outside the part. Admesh repairs the orientation of facets
according to the following algorithm:
- Generate the neighbors list for all facets.
- Inspect the first neighbor of the first facet to determine the
orientation of its vertices. - If the neighboring facet is oriented in the same direction as the first
facet, mark the neighbor as checked. If the neighboring facet is oriented
opposite to the first facet, reverse the neighbor, and mark it as checked. - Repeat steps 2 and 3 until all facets have been checked.
The above algorithm ensures that all connected facets are oriented in the
same direction. However, if the first facet is backwards, then all facets
will be backwards. The correct orientation for the entire part is
determined after the volume has been calculated. If the volume is
negative, then all of the facets must be backwards. Admesh then reverses
all facets to set the correct orientation.
Nop Head's original suggestion is to report if two neighbouring facets
have opposite orientations, which matches what Admesh does. And that
probably takes care of the most common case where people screw up the
arguments to polyhedron and ask for help on the forum. It wouldn't be
perfect, but it would be progress.
Detecting whether all faces are backwards looks more complicated and
expensive. There's no "local" property you can test, as in the neighbouring
facet test. It's a global property of the entire shape.
- Admesh does this by computing the volume, and testing if it is
negative. Computing the volume might be expensive? There's another thread,
a pull request for a "probe" function, which adds the ability to compute
the volume of a shape, but this computation is said to be very expensive.
It requires a convex decomposition, which in itself is expensive.
- I'm not sure how Admesh deals with a complex object containing an
interior void. Then you have an interior mesh, and an exterior mesh, which
aren't connected. The interior mesh is expected to have a negative volume,
while the exterior mesh is expected to have a positive volume.
On 11 January 2016 at 08:59, Marius Kintel marius@kintel.net wrote:
Some related issues:
https://github.com/openscad/openscad/issues/348
https://github.com/openscad/openscad/issues/1042
https://github.com/openscad/openscad/issues/590
Two things:
o We should rewrite our mesh class to support tests and operators like
this. This would also be a good step towards repairing imported STLs which
CGAL struggles with. We could also look at external libraries with good
mesh classes.
o Highlights of reversed faces in preview mode: It should be possible to
simply turn this on.
-Marius
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
I tried and got a CGAL error.
If it doesn't work, then that may be bad news for users of STL -> SCAD file
converters. This trick is used for posting OpenSCAD files to Thingiverse,
since the thingiverse customizer won't work if your scad file imports an
STL file: the imported polyhedron must instead be written as inline code. I
haven't used one of these converters: you could write one smart enough to
detect interior voids and generate difference() statements.
On 11 January 2016 at 11:55, nop head nop.head@gmail.com wrote:
Does polyhedron currently work if you have an interior hole with a
negative volume?
On 11 January 2016 at 16:42, doug moen doug@moens.org wrote:
From the Admesh library, referenced by
https://github.com/openscad/openscad/issues/1042:
A common problem with STL files is that some or all of facets are
oriented backwards; i.e. the vertices are listed in a clockwise direction
when viewed from outside the part. Admesh repairs the orientation of
facets according to the following algorithm:
- Generate the neighbors list for all facets.
- Inspect the first neighbor of the first facet to determine the
orientation of its vertices. - If the neighboring facet is oriented in the same direction as the
first facet, mark the neighbor as checked. If the neighboring facet is
oriented opposite to the first facet, reverse the neighbor, and mark it as
checked. - Repeat steps 2 and 3 until all facets have been checked.
The above algorithm ensures that all connected facets are oriented in the
same direction. However, if the first facet is backwards, then all facets
will be backwards. The correct orientation for the entire part is
determined after the volume has been calculated. If the volume is
negative, then all of the facets must be backwards. Admesh then reverses
all facets to set the correct orientation.
Nop Head's original suggestion is to report if two neighbouring facets
have opposite orientations, which matches what Admesh does. And that
probably takes care of the most common case where people screw up the
arguments to polyhedron and ask for help on the forum. It wouldn't be
perfect, but it would be progress.
Detecting whether all faces are backwards looks more complicated and
expensive. There's no "local" property you can test, as in the neighbouring
facet test. It's a global property of the entire shape.
- Admesh does this by computing the volume, and testing if it is
negative. Computing the volume might be expensive? There's another thread,
a pull request for a "probe" function, which adds the ability to compute
the volume of a shape, but this computation is said to be very expensive.
It requires a convex decomposition, which in itself is expensive.
- I'm not sure how Admesh deals with a complex object containing an
interior void. Then you have an interior mesh, and an exterior mesh, which
aren't connected. The interior mesh is expected to have a negative volume,
while the exterior mesh is expected to have a positive volume.
On 11 January 2016 at 08:59, Marius Kintel marius@kintel.net wrote:
Some related issues:
https://github.com/openscad/openscad/issues/348
https://github.com/openscad/openscad/issues/1042
https://github.com/openscad/openscad/issues/590
Two things:
o We should rewrite our mesh class to support tests and operators like
this. This would also be a good step towards repairing imported STLs which
CGAL struggles with. We could also look at external libraries with good
mesh classes.
o Highlights of reversed faces in preview mode: It should be possible to
simply turn this on.
-Marius
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Hm, that should work - we fixed some bugs related to that a while ago.
I’ll give it a spin..
-Marius
On Jan 11, 2016, at 12:21 PM, doug moen doug@moens.org wrote:
I tried and got a CGAL error.
If it doesn't work, then that may be bad news for users of STL -> SCAD file converters. This trick is used for posting OpenSCAD files to Thingiverse, since the thingiverse customizer won't work if your scad file imports an STL file: the imported polyhedron must instead be written as inline code. I haven't used one of these converters: you could write one smart enough to detect interior voids and generate difference() statements.
On 11 January 2016 at 11:55, nop head nop.head@gmail.com wrote:
Does polyhedron currently work if you have an interior hole with a negative volume?
On 11. jan. 2016 17:05, nop head wrote:
Pointing away from the material is a bit ambiguous for concave polyhedra
as a normal pointing outwards could hit another part of the object.
No it isn't ambiguous. It refers only to the immediate direction of the
non-material wrt. the face as compared to the immediate direction of the
solid material wrt. the same face.
Carsten Arnholm
You can determine the correct orientation at the outset by randomly
sampling faces until you find one whose normal does not collide with any
other faces on the object. I.e. if there is a face whose normal, when
raycast, does not hit any other faces, then that face has the correct
orientation.
In practise sampling some % of faces in the object looking for a single
fail to set the orientation.
Then start the growing/winding procedure with that face.
No it isn't ambiguous. It refers only to the immediate direction of the
non-material wrt. the face as compared to the immediate direction of the
solid material wrt. the same face.
Not ambiguous as a definition but in practice there is no solid material,
just faces representing its boundary. So as the previous post says you need
to see if the normal intersects another face. I.e. you need to find an
outwards normal that doesn't intersect. One that does intersect is
ambiguous on a concave object.
On 11 January 2016 at 21:47, Mark Schafer mschafer@wireframe.biz wrote:
You can determine the correct orientation at the outset by randomly
sampling faces until you find one whose normal does not collide with any
other faces on the object. I.e. if there is a face whose normal, when
raycast, does not hit any other faces, then that face has the correct
orientation.
In practise sampling some % of faces in the object looking for a single
fail to set the orientation.
Then start the growing/winding procedure with that face.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
On 12 Jan 2016, at 8:49 am, nop head nop.head@gmail.com wrote:
No it isn't ambiguous. It refers only to the immediate direction of the non-material wrt. the face as compared to the immediate direction of the solid material wrt. the same face.
Not ambiguous as a definition but in practice there is no solid material, just faces representing its boundary. So as the previous post says you need to see if the normal intersects another face. I.e. you need to find an outwards normal that doesn't intersect. One that does intersect is ambiguous on a concave object.
On 11 January 2016 at 21:47, Mark Schafer mschafer@wireframe.biz wrote:
You can determine the correct orientation at the outset by randomly sampling faces until you find one whose normal does not collide with any other faces on the object. I.e. if there is a face whose normal, when raycast, does not hit any other faces, then that face has the correct orientation.
In practise sampling some % of faces in the object looking for a single fail to set the orientation.
Then start the growing/winding procedure with that face
If it intersects an even number of times, you started on the outside. If it intersects an odd number, you are on the inside.
Yes if you are careful about intersecting another face at an edge or a
vertex or along its plane.
On 12 January 2016 at 09:44, Greg Frost gregorybartonfrost@gmail.com
wrote:
On 12 Jan 2016, at 8:49 am, nop head nop.head@gmail.com wrote:
No it isn't ambiguous. It refers only to the immediate direction of the
non-material wrt. the face as compared to the immediate direction of the
solid material wrt. the same face.
Not ambiguous as a definition but in practice there is no solid material,
just faces representing its boundary. So as the previous post says you need
to see if the normal intersects another face. I.e. you need to find an
outwards normal that doesn't intersect. One that does intersect is
ambiguous on a concave object.
On 11 January 2016 at 21:47, Mark Schafer mschafer@wireframe.biz wrote:
You can determine the correct orientation at the outset by randomly
sampling faces until you find one whose normal does not collide with any
other faces on the object. I.e. if there is a face whose normal, when
raycast, does not hit any other faces, then that face has the correct
orientation.
In practise sampling some % of faces in the object looking for a single
fail to set the orientation.
Then start the growing/winding procedure with that face
If it intersects an even number of times, you started on the outside. If
it intersects an odd number, you are on the inside.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Many of my issues occur with lines/planes and faces of circles/cylinders with
varying $fn values, particularly intersection/difference, how does this
approach consider the tangential inconsistency of the curve approximation.
He says naively... ;) or provocatively...if I have 1/2 an understanding...
Newly minted Admin - PM me if you need anything, or if I've done something stupid...
Unless specifically shown otherwise above, my contribution is in the Public Domain; to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work. Obviously inclusion of works of previous authors is not included in the above.
The TPP is no simple “trade agreement.” Fight it! http://www.ourfairdeal.org/ time is running out!
View this message in context: http://forum.openscad.org/Reversed-faces-tp15649p15673.html
Sent from the OpenSCAD mailing list archive at Nabble.com.