What are degenerate facets anyway?
Yes, a topological hole. It does apply to STLs because CGAL won't like it
if it has topological holes. As long as all vertices that are topologically
distinct are numerically distinct and vice versa, and there are no self
interactions, a triangle soup can represent a manifold unambiguously and
CGAL will be happy if you import it as long as the OpenSCAD grid
doesn't collapse close vertices.
On Sun, 25 Feb 2024 at 08:56, Carsten Arnholm arnholm@arnholm.org wrote:
On 2024-02-25 00:35, nop head via Discuss wrote:
As long as there are no self intersections it isn't too hard to remove
degenerate triangles. It isn't trivial though because if you simply
omit them you have a hole in the mesh, so you have to fix that.
Removing a triangle with zero area does not leave a hole, because the
'hole' has zero area. If you are thinking topological hole, it doesn't
apply to STL files because they don't contain any topology in the first
place, STL files are 'triangle soups'. With other formats, such as OBJ,
it is a different matter, you could be left with a zero area topological
hole.
Carsten Arnholm
On 2024-02-25 10:55, nop head wrote:
Yes, a topological hole. It does apply to STLs because CGAL won't like
it if it has topological holes.
It should be obvious by itself, but especially from my previous post
that this is nonsensical since there is no topology in STL files. You
cannot have topological holes when there is no topology.
As long as all vertices that are
topologically distinct
This is nonsense. A triangle soup is a collection of loose triangles
where the coordinates of every triangle are stated per triangle, not per
vertex as in a proper mesh.
I have said this many times on this list, but if people prefer to ignore
it they are obviously free to do so and repeat the confusion one more
time.
Carsten Arnholm
Carsten:
Since you have written 3D object repair tools, I believe that you
understand these things more than some of us.
I am not sure what people mean by "topological hole", nor am I sure that
everyone is using the same definition for "topology". We all "know" that
slicers require that the object be "manifold", and in my mind manifold
has a topological meaning, informally in my case. I understand that an
STL file is a list of triangles which may or may not create a manifold
surface, but I feel as if the collection has topology, even if the
individual triangles do not.
Am I thinking about this incorrectly?
Jon
On 2/25/2024 6:59 AM, Carsten Arnholm via Discuss wrote:
On 2024-02-25 10:55, nop head wrote:
Yes, a topological hole. It does apply to STLs because CGAL won't like
it if it has topological holes.
It should be obvious by itself, but especially from my previous post
that this is nonsensical since there is no topology in STL files. You
cannot have topological holes when there is no topology.
As long as all vertices that are
topologically distinct
This is nonsense. A triangle soup is a collection of loose triangles
where the coordinates of every triangle are stated per triangle, not
per vertex as in a proper mesh.
I have said this many times on this list, but if people prefer to
ignore it they are obviously free to do so and repeat the confusion
one more time.
Carsten Arnholm
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
--
This email has been checked for viruses by AVG antivirus software.
www.avg.com
Topology basically refers to how vertices are connected in the mesh. STL
loses topology because it does not store the whole graph, just
individual triangles. There is no way to distinguish two distinct (with
different neighbors in the graph) vertices if they have the same
numerical coordinate. If you are working with general positions, i.e.
vertices have distinct coordinates, STL is fine, but often times we are
working with blocky stuff and they have coincident vertices.
On 25/2/2024 20:10, jon via Discuss wrote:
Carsten:
Since you have written 3D object repair tools, I believe that you
understand these things more than some of us.
I am not sure what people mean by "topological hole", nor am I sure
that everyone is using the same definition for "topology". We all
"know" that slicers require that the object be "manifold", and in my
mind manifold has a topological meaning, informally in my case. I
understand that an STL file is a list of triangles which may or may
not create a manifold surface, but I feel as if the collection has
topology, even if the individual triangles do not.
Am I thinking about this incorrectly?
Jon
On 2/25/2024 6:59 AM, Carsten Arnholm via Discuss wrote:
On 2024-02-25 10:55, nop head wrote:
Yes, a topological hole. It does apply to STLs because CGAL won't like
it if it has topological holes.It should be obvious by itself, but especially from my previous post
that this is nonsensical since there is no topology in STL files. You
cannot have topological holes when there is no topology.As long as all vertices that are
topologically distinctThis is nonsense. A triangle soup is a collection of loose triangles
where the coordinates of every triangle are stated per triangle, not
per vertex as in a proper mesh.I have said this many times on this list, but if people prefer to
ignore it they are obviously free to do so and repeat the confusion
one more time.Carsten Arnholm
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
A triangle soup is a collection of loose triangles
where the coordinates of every triangle are stated per triangle, not per
vertex as in a proper mesh.
Yes but you can re-create a proper mesh as long as those triangles obey
Euler's topology rule because you match up each pair of triangle sides that
join because they are the only two that share those two vertices.
All of the STLs I produce with OpenSCAD obey those rules and can be
imported back into OpenSCAD as I use OpenSCAD to aggregate them for
printing. CGAL would barf if they did not recreate valid manifolds. Most
STL's on Thingiverse however do not obey those rules and CGAL will not
operate on them.
On Sun, 25 Feb 2024 at 12:27, Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
Topology basically refers to how vertices are connected in the mesh. STL
loses topology because it does not store the whole graph, just
individual triangles. There is no way to distinguish two distinct (with
different neighbors in the graph) vertices if they have the same
numerical coordinate. If you are working with general positions, i.e.
vertices have distinct coordinates, STL is fine, but often times we are
working with blocky stuff and they have coincident vertices.
On 25/2/2024 20:10, jon via Discuss wrote:
Carsten:
Since you have written 3D object repair tools, I believe that you
understand these things more than some of us.
I am not sure what people mean by "topological hole", nor am I sure
that everyone is using the same definition for "topology". We all
"know" that slicers require that the object be "manifold", and in my
mind manifold has a topological meaning, informally in my case. I
understand that an STL file is a list of triangles which may or may
not create a manifold surface, but I feel as if the collection has
topology, even if the individual triangles do not.
Am I thinking about this incorrectly?
Jon
On 2/25/2024 6:59 AM, Carsten Arnholm via Discuss wrote:
On 2024-02-25 10:55, nop head wrote:
Yes, a topological hole. It does apply to STLs because CGAL won't like
it if it has topological holes.
It should be obvious by itself, but especially from my previous post
that this is nonsensical since there is no topology in STL files. You
cannot have topological holes when there is no topology.
As long as all vertices that are
topologically distinct
This is nonsense. A triangle soup is a collection of loose triangles
where the coordinates of every triangle are stated per triangle, not
per vertex as in a proper mesh.
I have said this many times on this list, but if people prefer to
ignore it they are obviously free to do so and repeat the confusion
one more time.
Carsten Arnholm
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
On Sun, 25 Feb 2024 at 08:56, Carsten Arnholm arnholm@arnholm.org wrote:
On 2024-02-25 00:35, nop head via Discuss wrote:
As long as there are no self intersections it isn't too hard to remove
degenerate triangles. It isn't trivial though because if you simply
omit them you have a hole in the mesh, so you have to fix that.
Removing a triangle with zero area does not leave a hole, because the
'hole' has zero area. If you are thinking topological hole, it doesn't
apply to STL files because they don't contain any topology in the first
place, STL files are 'triangle soups'. With other formats, such as OBJ,
it is a different matter, you could be left with a zero area topological
hole.
Suppose I have a part of a geometry and for simplicty we'll use only
2D points.
Suppose I have three triangles:
[(-1,0), (0,0), (0, 1)]
[( 1,0), (0,0), (0, 1)]
[(-1,0), (1,0), (0,-1)]
The line between (0,0) and (1,0) is traversed only once by a triangle.
You might say that it IS traversed by the line from (-1,0) to (1,0),
but it needs to be that exact same coordinate pair that counts as the
second-traverse of each edge.
To make this topologically OK, even in ascii STL, you need a fourth
(zero-area) triangle:
[(-1,0), (0,0), (1, 0)]
Now, the set-of-four triangles could be changed to:
[(-1,0), (0,0), (0, 1)]
[( 1,0), (0,0), (0, 1)]
[(-1,0), (0,0), (0,-1)]
[( 0,0), (1,0), (0,-1)]
To eliminate the zero-are triangle.
Now in this simplified case, you can join adjacent tirangles into a
bigger one, but in more complex cases there could be a reason for a
point on an edge of one triangle needing to be a vertex as well.
Binary STL by the way uses an array of vertices and indexes into the
vertex-array. So you could distinguis between different points in a
geometry that happen to have the same coordinates.
e.g. again simplifying to 2D: consider
square (10); translate ([10,10])square (10);
In binary STL you could create two points at (10,10), one belonging to
the first square and the other to the second square.
Now... An often-performed "cleanup of STL" is to de-duplicate such
points, but a program writing STL could "do this right" (whichever
way you consider right. :-) ).
Roger.
--
** R.E.Wolff@BitWizard.nl ** https://www.BitWizard.nl/ ** +31-15-2049110 **
** Delftechpark 11 2628 XJ Delft, The Netherlands. KVK: 27239233 **
f equals m times a. When your f is steady, and your m is going down
your a is going up. -- Chris Hadfield about flying up the space shuttle.
On 25.02.2024 13:10, jon wrote:
I am not sure what people mean by "topological hole", nor am I sure
that everyone is using the same definition for "topology".
This is kind of equivalent to people having different opinions for what
a "wheel" is when talking about vehicles. Much like you are supposed to
have a common understanding of what a "wheel" is, topology in the
context of a surface mesh is a very specific thing and not subject to
personal interpretation.
To try to explain this, let us use a trivial example from OpenSCAD source:
linear_extrude(1)
polygon(points=[[-10,0],[+10,0],[0,10]]);
Assume this is executed in OpenSCAD and exported as STL. What do you
get? You get 8 triangles (and supposedly 2*3=6 vertices).
- top and bottom triangles (2)
- 3 rectangular sides made up of 2 triangles each (3*2=6)
The STL format is one of many possible ways of describing a solid
object. STL does it by describing the surface of the solid in the form
of a discretized triangle mesh (this is different from traditional CAD).
Hence the term surface mesh.
In formatted STL, the model becomes like shown below (I converted it
from OpenSCADs binary STL to formatted using 'polyfix'). In STL, a
triangle is called a 'facet'. If you count the facets, you will see
there are exactly 8. Each facet (=triangle) has a surface normal vector
defining 'outside', the direction that is supposed to point away from
the solid body. There is also a 'loop' listing the 3 triangle
coordinates in counter-clockwise order as viewed from 'outside'.
solid example
facet normal 0 0 -1
outer loop
vertex -10 0 0
vertex 0 10 0
vertex 10 0 0
endloop
endfacet
facet normal 0 0 1
outer loop
vertex 10 0 1
vertex 0 10 1
vertex -10 0 1
endloop
endfacet
facet normal -0.70710678 0.70710678 0
outer loop
vertex -10 0 0
vertex 0 10 1
vertex 0 10 0
endloop
endfacet
facet normal -0.70710678 0.70710678 0
outer loop
vertex -10 0 0
vertex -10 0 1
vertex 0 10 1
endloop
endfacet
facet normal 0 -1 0
outer loop
vertex 10 0 0
vertex -10 0 1
vertex -10 0 0
endloop
endfacet
facet normal 0 -1 0
outer loop
vertex 10 0 0
vertex 10 0 1
vertex -10 0 1
endloop
endfacet
facet normal 0.70710678 0.70710678 0
outer loop
vertex 0 10 0
vertex 10 0 1
vertex 10 0 0
endloop
endfacet
facet normal 0.70710678 0.70710678 -0
outer loop
vertex 0 10 0
vertex 0 10 1
vertex 10 0 1
endloop
endfacet
endsolid
This representation is a 'triangle soup', a collection of independent
triangles without any shared information whatsoever. You can take 'no
shared information' to imply 'no topology'.
If you search the STL data for a particular coordinate set, say 'vertex
10 0 0' you will find it is repeated several times, in this case 3 times
in 3 different 'facets'. The only way to tell whether these triangles
are actually supposed to be interpreted as connected to each other or
not is to try to match coordinates against each other. Thus, it is a
question of interpretation based on some assumptions.
In this case it is supposedly easy because thecoordinates are exact, but
most of the time the coordinates are represented by finite precision
floating point numbers, there is no guarantee that neighboring triangles
will show exactly the same coordinates. This is true for both formatted
and binary STL.
Therefore, to read STL you have to introduce some scheme using
coordinate tolerances or whatever to tell whether almost identical
coordinates should be interpreted as one point or several points. This
problem happens only for STL. You have to guess what the file is
supposed to mean, and that is why different modelling software sometimes
come to different conclusions for the same STL files (and thus why STL
is not a good choice for exchanging models between applications).
To be clear, these issues are due to missing topological information in
STL files, even if such information existed at export (in the case of
OpenSCAD, in CGAL).
Let us introduce some topology.
Export the exact same model from OpenSCAD, using a different file
format, one that includes topology. Let us use the OFF format since it
is supported in OpenSCAD. The OFF representation looks like this:
OFF 6 8 0
-10 0 0
0 10 0
10 0 0
10 0 1
0 10 1
-10 0 1
3 0 1 2
3 3 4 5
3 0 4 1
3 0 5 4
3 2 5 0
3 2 3 5
3 1 3 2
3 1 4 3
As can be seen, this is a more compact format. The first line says it is
an OFF file containing 6 vertices and 8 facets. The next 6 lines contain
the x,y,z coordinates of the 6 vertices, and the vertex# = line# - 1.
The next 8 lines contain each facet definition: number of vertices in
facet (3=triangle) and the vertex# for each facet vertex.
Such a representation is not subject to interpretation problems like
STL, because each vertex is mentioned only once and triangles share the
vertices by referring to them.... this is the topology in this case.
Other formats, like OBJ are similar to this.
Unlike STL, there is no room for misinterpretation of what is connected
to what.
We all "know" that slicers require that the object be "manifold", and
in my mind manifold has a topological meaning, informally in my case.
Manifold is indeed a topological term. But saying "manifold" is too
imprecise. Since slicers expect a solid to be represented by a surface
mesh (STL, OFF, OBJ or whatever), they require the model to be exactly
2-manifold, as opposed to 1-manifold, 3-manifold, 4-manifold etc.
What does 2-manifold mean? It means every edge in the surface mesh is
referenced exactly 2 times. To explain this in more detail we have to
define the topological entities that are relevant here
vertex : a point with x,y,z coordinates and an id# that makes it referrable
edge : a line referring to 2 vertices using vertex id#
face : a flat polygon referring to vertices using vertex id#
A face referring to 3 vertices is a flat triangle. So assume triangles
only for simplicity.
A triangle has 3 sides, i.e. 3 edges. Since the triangle vertices must
be listed in CCW order, the triangle edges are well defined, using the
vertex id#s. You can establish an edge Id# by combining the 2 vertex
id#s in sorted order. This is key to determining 'manifoldness'.
Two neighbouring triangles in a well defined model will refer to the
same edge. If you go through the model and count the number each edge is
referenced (implicitly), the answer should be 2 for each edge in a
surface mesh.
This means only 2 triangles can refer to the same edge for the model to
be a valid surface mesh. If the number is 1, it is a free edge and the
edge is not 2-manifold. If the number is 3 then 3 triangles share the
same edge, and that is not allowed for a surface mesh, because one of
the triangles is not on the surface (or it may be degenerate and should
be removed).
To further illustrate manifoldness of a surface mesh take the above
example again, converting original from STL to OFF using 'polyfix'
$ polyfix topology.stl -out=.off
Parameters:
input_file = topology.stl
out = .off
polyhedron 0 ================= volume=100, dtol=0.01, atol=1e-06,
maxiter=10
iteration 0: vertices=24 faces=8
warning: nonmanifold edges: uc(1)=24
merged 18 vertices
total changes=18
no warnings
iteration 1: vertices=6 faces=8
total changes=0
no warnings
Summary:
polyhedron 0: vertices=6 faces=8 : no warnings
Writing: topology_1.off
The original STL file contains a polygon soup of 8 faces, 24 vertices
with no shared information between the faces.
The warning says that there are 8*3=24 edges with use-count=1, i.e. all
edges strictly 1-manifold. Then, the software applies some coordinate
tolerance rules and interprets some of the vertices to be the same,
while keeping track of the changing vertex references from the 8 faces.
After merging the vertices and updating the vertex references from the
faces, the edge use-count test is performed again. It results in no
warnings, which means all edges had use-count=2, i.e. all 2-manifold.
I understand that an STL file is a list of triangles which may or may
not create a manifold surface, but I feel as if the collection has
topology, even if the individual triangles do not.
In STL, the only topology you have is within the individual triangles
(CCW order of vertices + implicit definition of edges).
Am I thinking about this incorrectly?
As I tried to explain above, it is not a question of 'feeling', but
precise definition. You can get away with 'feeling' as long as the
software(s) you are using all apply the same rules, but chances are they
are not exactly the same and hence you get many threads like this.
Most (not all) such issues would go away simply by not using STL.
Carsten Arnholm
If you export an STL file from OpenSCAD then the vertices of triangles that
meet have exactly the same numerical value. You don't need to do a search
with a tolerance to match them up. They come from the same members in the
CGAL data structure, so they produce exactly the same binary or text value
in the file. This is why you can recreate the topology without ambiguity.
For each edge of each triangle there will only be one other edge of one
other triangle so you can build a vertex, edge, face data structure from
the triangle soup.
It only goes wrong when OpenSCAD snaps two vertices that should be
different to the same numerical value. To avoid that I have to make sure
all my vertices are not closer than the OpenSCAD grid.
On Sun, 25 Feb 2024 at 15:12, Carsten Arnholm via Discuss <
discuss@lists.openscad.org> wrote:
On 25.02.2024 13:10, jon wrote:
I am not sure what people mean by "topological hole", nor am I sure that
everyone is using the same definition for "topology".
This is kind of equivalent to people having different opinions for what a
"wheel" is when talking about vehicles. Much like you are supposed to have
a common understanding of what a "wheel" is, topology in the context of a
surface mesh is a very specific thing and not subject to personal
interpretation.
To try to explain this, let us use a trivial example from OpenSCAD source:
linear_extrude(1)
polygon(points=[[-10,0],[+10,0],[0,10]]);
Assume this is executed in OpenSCAD and exported as STL. What do you get?
You get 8 triangles (and supposedly 2*3=6 vertices).
- top and bottom triangles (2)
- 3 rectangular sides made up of 2 triangles each (3*2=6)
The STL format is one of many possible ways of describing a solid object.
STL does it by describing the surface of the solid in the form of a
discretized triangle mesh (this is different from traditional CAD). Hence
the term surface mesh.
In formatted STL, the model becomes like shown below (I converted it from
OpenSCADs binary STL to formatted using 'polyfix'). In STL, a triangle is
called a 'facet'. If you count the facets, you will see there are exactly
8. Each facet (=triangle) has a surface normal vector defining 'outside',
the direction that is supposed to point away from the solid body. There is
also a 'loop' listing the 3 triangle coordinates in counter-clockwise order
as viewed from 'outside'.
solid example
facet normal 0 0 -1
outer loop
vertex -10 0 0
vertex 0 10 0
vertex 10 0 0
endloop
endfacet
facet normal 0 0 1
outer loop
vertex 10 0 1
vertex 0 10 1
vertex -10 0 1
endloop
endfacet
facet normal -0.70710678 0.70710678 0
outer loop
vertex -10 0 0
vertex 0 10 1
vertex 0 10 0
endloop
endfacet
facet normal -0.70710678 0.70710678 0
outer loop
vertex -10 0 0
vertex -10 0 1
vertex 0 10 1
endloop
endfacet
facet normal 0 -1 0
outer loop
vertex 10 0 0
vertex -10 0 1
vertex -10 0 0
endloop
endfacet
facet normal 0 -1 0
outer loop
vertex 10 0 0
vertex 10 0 1
vertex -10 0 1
endloop
endfacet
facet normal 0.70710678 0.70710678 0
outer loop
vertex 0 10 0
vertex 10 0 1
vertex 10 0 0
endloop
endfacet
facet normal 0.70710678 0.70710678 -0
outer loop
vertex 0 10 0
vertex 0 10 1
vertex 10 0 1
endloop
endfacet
endsolid
This representation is a 'triangle soup', a collection of independent
triangles without any shared information whatsoever. You can take 'no
shared information' to imply 'no topology'.
If you search the STL data for a particular coordinate set, say 'vertex 10
0 0' you will find it is repeated several times, in this case 3 times in 3
different 'facets'. The only way to tell whether these triangles are
actually supposed to be interpreted as connected to each other or not is to
try to match coordinates against each other. Thus, it is a question of
interpretation based on some assumptions.
In this case it is supposedly easy because the coordinates are exact, but
most of the time the coordinates are represented by finite precision
floating point numbers, there is no guarantee that neighboring triangles
will show exactly the same coordinates. This is true for both formatted and
binary STL.
Therefore, to read STL you have to introduce some scheme using coordinate
tolerances or whatever to tell whether almost identical coordinates should
be interpreted as one point or several points. This problem happens only
for STL. You have to guess what the file is supposed to mean, and that is
why different modelling software sometimes come to different conclusions
for the same STL files (and thus why STL is not a good choice for
exchanging models between applications).
To be clear, these issues are due to missing topological information in
STL files, even if such information existed at export (in the case of
OpenSCAD, in CGAL).
Let us introduce some topology.
Export the exact same model from OpenSCAD, using a different file format,
one that includes topology. Let us use the OFF format since it is supported
in OpenSCAD. The OFF representation looks like this:
OFF 6 8 0
-10 0 0
0 10 0
10 0 0
10 0 1
0 10 1
-10 0 1
3 0 1 2
3 3 4 5
3 0 4 1
3 0 5 4
3 2 5 0
3 2 3 5
3 1 3 2
3 1 4 3
As can be seen, this is a more compact format. The first line says it is
an OFF file containing 6 vertices and 8 facets. The next 6 lines contain
the x,y,z coordinates of the 6 vertices, and the vertex# = line# - 1. The
next 8 lines contain each facet definition: number of vertices in facet
(3=triangle) and the vertex# for each facet vertex.
Such a representation is not subject to interpretation problems like STL,
because each vertex is mentioned only once and triangles share the vertices
by referring to them.... this is the topology in this case. Other
formats, like OBJ are similar to this.
Unlike STL, there is no room for misinterpretation of what is connected to
what.
We all "know" that slicers require that the object be "manifold", and in
my mind manifold has a topological meaning, informally in my case.
Manifold is indeed a topological term. But saying "manifold" is too
imprecise. Since slicers expect a solid to be represented by a surface
mesh (STL, OFF, OBJ or whatever), they require the model to be exactly
2-manifold, as opposed to 1-manifold, 3-manifold, 4-manifold etc.
What does 2-manifold mean? It means every edge in the surface mesh is
referenced exactly 2 times. To explain this in more detail we have to
define the topological entities that are relevant here
vertex : a point with x,y,z coordinates and an id# that makes it
referrable
edge : a line referring to 2 vertices using vertex id#
face : a flat polygon referring to vertices using vertex id#
A face referring to 3 vertices is a flat triangle. So assume triangles
only for simplicity.
A triangle has 3 sides, i.e. 3 edges. Since the triangle vertices must be
listed in CCW order, the triangle edges are well defined, using the vertex
id#s. You can establish an edge Id# by combining the 2 vertex id#s in
sorted order. This is key to determining 'manifoldness'.
Two neighbouring triangles in a well defined model will refer to the same
edge. If you go through the model and count the number each edge is
referenced (implicitly), the answer should be 2 for each edge in a surface
mesh.
This means only 2 triangles can refer to the same edge for the model to be
a valid surface mesh. If the number is 1, it is a free edge and the edge is
not 2-manifold. If the number is 3 then 3 triangles share the same edge,
and that is not allowed for a surface mesh, because one of the triangles is
not on the surface (or it may be degenerate and should be removed).
To further illustrate manifoldness of a surface mesh take the above
example again, converting original from STL to OFF using 'polyfix'
$ polyfix topology.stl -out=.off
Parameters:
input_file = topology.stl
out = .off
polyhedron 0 ================= volume=100, dtol=0.01, atol=1e-06,
maxiter=10
iteration 0: vertices=24 faces=8
warning: nonmanifold edges: uc(1)=24
merged 18 vertices
total changes=18
no warnings
iteration 1: vertices=6 faces=8
total changes=0
no warnings
Summary:
polyhedron 0: vertices=6 faces=8 : no warnings
Writing: topology_1.off
The original STL file contains a polygon soup of 8 faces, 24 vertices with
no shared information between the faces.
The warning says that there are 8*3=24 edges with use-count=1, i.e. all
edges strictly 1-manifold. Then, the software applies some coordinate
tolerance rules and interprets some of the vertices to be the same, while
keeping track of the changing vertex references from the 8 faces. After
merging the vertices and updating the vertex references from the faces, the
edge use-count test is performed again. It results in no warnings, which
means all edges had use-count=2, i.e. all 2-manifold.
I understand that an STL file is a list of triangles which may or may not
create a manifold surface, but I feel as if the collection has topology,
even if the individual triangles do not.
In STL, the only topology you have is within the individual triangles (CCW
order of vertices + implicit definition of edges).
Am I thinking about this incorrectly?
As I tried to explain above, it is not a question of 'feeling', but
precise definition. You can get away with 'feeling' as long as the
software(s) you are using all apply the same rules, but chances are they
are not exactly the same and hence you get many threads like this.
Most (not all) such issues would go away simply by not using STL.
Carsten Arnholm
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
The problem is that even if some vertices are distinct topologically,
they are considered the same if you look at their coordinates, e.g. when
two objects touch each other. And this can happen even if OpenSCAD
exports the exact numerical representation without any
truncation/rounding/snapping whatever. There are ways to figure out the
topological information but it is complicated and we have bugs with it.
On 25/2/2024 23:42, nop head via Discuss wrote:
If you export an STL file from OpenSCAD then the vertices of triangles
that meet have exactly the same numerical value. You don't need to do
a search with a tolerance to match them up. They come from the same
members in the CGAL data structure, so they produce exactly the same
binary or text value in the file. This is why you can recreate the
topology without ambiguity. For each edge of each triangle there will
only be one other edge of one other triangle so you can build a
vertex, edge, face data structure from the triangle soup.
It only goes wrong when OpenSCAD snaps two vertices that should be
different to the same numerical value. To avoid that I have to make
sure all my vertices are not closer than the OpenSCAD grid.
On Sun, 25 Feb 2024 at 15:12, Carsten Arnholm via Discuss
discuss@lists.openscad.org wrote:
On 25.02.2024 13:10, jon wrote:
I am not sure what people mean by "topological hole", nor am I
sure that everyone is using the same definition for "topology".
This is kind of equivalent to people having different opinions for
what a "wheel" is when talking about vehicles. Much like you are
supposed to have a common understanding of what a "wheel" is,
topology in the context of a surface mesh is a very specific thing
and not subject to personal interpretation.
To try to explain this, let us use a trivial example from OpenSCAD
source:
linear_extrude(1)
polygon(points=[[-10,0],[+10,0],[0,10]]);
Assume this is executed in OpenSCAD and exported as STL. What do
you get? You get 8 triangles (and supposedly 2*3=6 vertices).
- top and bottom triangles (2)
- 3 rectangular sides made up of 2 triangles each (3*2=6)
The STL format is one of many possible ways of describing a solid
object. STL does it by describing the surface of the solid in the
form of a discretized triangle mesh (this is different from
traditional CAD). Hence the term surface mesh.
In formatted STL, the model becomes like shown below (I converted
it from OpenSCADs binary STL to formatted using 'polyfix'). In
STL, a triangle is called a 'facet'. If you count the facets, you
will see there are exactly 8. Each facet (=triangle) has a surface
normal vector defining 'outside', the direction that is supposed
to point away from the solid body. There is also a 'loop' listing
the 3 triangle coordinates in counter-clockwise order as viewed
from 'outside'.
solid example
facet normal 0 0 -1
outer loop
vertex -10 0 0
vertex 0 10 0
vertex 10 0 0
endloop
endfacet
facet normal 0 0 1
outer loop
vertex 10 0 1
vertex 0 10 1
vertex -10 0 1
endloop
endfacet
facet normal -0.70710678 0.70710678 0
outer loop
vertex -10 0 0
vertex 0 10 1
vertex 0 10 0
endloop
endfacet
facet normal -0.70710678 0.70710678 0
outer loop
vertex -10 0 0
vertex -10 0 1
vertex 0 10 1
endloop
endfacet
facet normal 0 -1 0
outer loop
vertex 10 0 0
vertex -10 0 1
vertex -10 0 0
endloop
endfacet
facet normal 0 -1 0
outer loop
vertex 10 0 0
vertex 10 0 1
vertex -10 0 1
endloop
endfacet
facet normal 0.70710678 0.70710678 0
outer loop
vertex 0 10 0
vertex 10 0 1
vertex 10 0 0
endloop
endfacet
facet normal 0.70710678 0.70710678 -0
outer loop
vertex 0 10 0
vertex 0 10 1
vertex 10 0 1
endloop
endfacet
endsolid
This representation is a 'triangle soup', a collection of
independent triangles without any shared information whatsoever.
You can take 'no shared information' to imply 'no topology'.
If you search the STL data for a particular coordinate set, say
'vertex 10 0 0' you will find it is repeated several times, in
this case 3 times in 3 different 'facets'. The only way to tell
whether these triangles are actually supposed to be interpreted as
connected to each other or not is to try to match coordinates
against each other. Thus, it is a question of interpretation based
on some assumptions.
In this case it is supposedly easy because thecoordinates are
exact, but most of the time the coordinates are represented by
finite precision floating point numbers, there is no guarantee
that neighboring triangles will show exactly the same coordinates.
This is true for both formatted and binary STL.
Therefore, to read STL you have to introduce some scheme using
coordinate tolerances or whatever to tell whether almost identical
coordinates should be interpreted as one point or several points.
This problem happens *only* for STL. You have to guess what the
file is supposed to mean, and that is why different modelling
software sometimes come to different conclusions for the same STL
files (and thus why STL is not a good choice for exchanging models
between applications).
To be clear, these issues are due to missing topological
information in STL files, even if such information existed at
export (in the case of OpenSCAD, in CGAL).
Let us introduce some topology.
Export the exact same model from OpenSCAD, using a different file
format, one that includes topology. Let us use the OFF format
since it is supported in OpenSCAD. The OFF representation looks
like this:
OFF 6 8 0
-10 0 0
0 10 0
10 0 0
10 0 1
0 10 1
-10 0 1
3 0 1 2
3 3 4 5
3 0 4 1
3 0 5 4
3 2 5 0
3 2 3 5
3 1 3 2
3 1 4 3
As can be seen, this is a more compact format. The first line says
it is an OFF file containing 6 vertices and 8 facets. The next 6
lines contain the x,y,z coordinates of the 6 vertices, and the
vertex# = line# - 1. The next 8 lines contain each facet
definition: number of vertices in facet (3=triangle) and the
vertex# for each facet vertex.
Such a representation is not subject to interpretation problems
like STL, because each vertex is mentioned only once and triangles
share the vertices by referring to them.... this is the topology
in this case. Other formats, like OBJ are similar to this.
Unlike STL, there is no room for misinterpretation of what is
connected to what.
We all "know" that slicers require that the object be "manifold",
and in my mind manifold has a topological meaning, informally in
my case.
Manifold is indeed a topological term. But saying "manifold" is
too imprecise. Since slicers expect a solid to be represented by a
*surface* mesh (STL, OFF, OBJ or whatever), they require the model
to be exactly *2-manifold*, as opposed to 1-manifold, 3-manifold,
4-manifold etc.
What does 2-manifold mean? It means every edge in the surface mesh
is referenced exactly 2 times. To explain this in more detail we
have to define the topological entities that are relevant here
vertex : a point with x,y,z coordinates and an id# that makes it
referrable
edge : a line referring to 2 vertices using vertex id#
face : a flat polygon referring to vertices using vertex id#
A face referring to 3 vertices is a flat triangle. So assume
triangles only for simplicity.
A triangle has 3 sides, i.e. 3 edges. Since the triangle vertices
must be listed in CCW order, the triangle edges are well defined,
using the vertex id#s. You can establish an edge Id# by combining
the 2 vertex id#s in sorted order. This is key to determining
'manifoldness'.
Two neighbouring triangles in a well defined model will refer to
the same edge. If you go through the model and count the number
each edge is referenced (implicitly), the answer should be 2 for
each edge in a surface mesh.
This means only 2 triangles can refer to the same edge for the
model to be a valid surface mesh. If the number is 1, it is a free
edge and the edge is not 2-manifold. If the number is 3 then 3
triangles share the same edge, and that is not allowed for a
surface mesh, because one of the triangles is not on the surface
(or it may be degenerate and should be removed).
To further illustrate manifoldness of a surface mesh take the
above example again, converting original from STL to OFF using
'polyfix'
$ polyfix topology.stl -out=.off
Parameters:
input_file = topology.stl
out = .off
polyhedron 0 ================= volume=100, dtol=0.01, atol=1e-06,
maxiter=10
iteration 0: vertices=24 faces=8
warning: nonmanifold edges: uc(1)=24
merged 18 vertices
total changes=18
no warnings
iteration 1: vertices=6 faces=8
total changes=0
no warnings
Summary:
polyhedron 0: vertices=6 faces=8 : no warnings
Writing: topology_1.off
The original STL file contains a polygon soup of 8 faces, 24
vertices with no shared information between the faces.
The warning says that there are 8*3=24 edges with use-count=1,
i.e. all edges strictly 1-manifold. Then, the software applies
some coordinate tolerance rules and interprets some of the
vertices to be the same, while keeping track of the changing
vertex references from the 8 faces. After merging the vertices and
updating the vertex references from the faces, the edge use-count
test is performed again. It results in no warnings, which means
all edges had use-count=2, i.e. all 2-manifold.
I understand that an STL file is a list of triangles which may or
may not create a manifold surface, but I feel as if the
collection has topology, even if the individual triangles do not.
In STL, the only topology you have is within the individual
triangles (CCW order of vertices + implicit definition of edges).
Am I thinking about this incorrectly?
As I tried to explain above, it is not a question of 'feeling',
but precise definition. You can get away with 'feeling' as long as
the software(s) you are using all apply the same rules, but
chances are they are not exactly the same and hence you get many
threads like this.
Most (not all) such issues would go away simply by not using STL.
Carsten Arnholm
_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email todiscuss-leave@lists.openscad.org
On Sun, 25 Feb 2024 at 15:49, Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
The problem is that even if some vertices are distinct topologically, they
are considered the same if you look at their coordinates, e.g. when two
objects touch each other. And this can happen even if OpenSCAD exports the
exact numerical representation without any truncation/rounding/snapping
whatever. There are ways to figure out the topological information but it
is complicated and we have bugs with it.
Two objects should never touch each other if you want to export them as an
STL. For example all my printed parts will export as STLs and import again
and CGAL will be happy with them. If I try to export an assembly with
screws touching washers touching plastic parts as an STL then of course it
will fail.
On 25/2/2024 23:42, nop head via Discuss wrote:
If you export an STL file from OpenSCAD then the vertices of triangles
that meet have exactly the same numerical value. You don't need to do a
search with a tolerance to match them up. They come from the same members
in the CGAL data structure, so they produce exactly the same binary or text
value in the file. This is why you can recreate the topology without
ambiguity. For each edge of each triangle there will only be one other edge
of one other triangle so you can build a vertex, edge, face data structure
from the triangle soup.
It only goes wrong when OpenSCAD snaps two vertices that should be
different to the same numerical value. To avoid that I have to make sure
all my vertices are not closer than the OpenSCAD grid.
On Sun, 25 Feb 2024 at 15:12, Carsten Arnholm via Discuss <
discuss@lists.openscad.org> wrote:
On 25.02.2024 13:10, jon wrote:
I am not sure what people mean by "topological hole", nor am I sure that
everyone is using the same definition for "topology".
This is kind of equivalent to people having different opinions for what a
"wheel" is when talking about vehicles. Much like you are supposed to have
a common understanding of what a "wheel" is, topology in the context of a
surface mesh is a very specific thing and not subject to personal
interpretation.
To try to explain this, let us use a trivial example from OpenSCAD source:
linear_extrude(1)
polygon(points=[[-10,0],[+10,0],[0,10]]);
Assume this is executed in OpenSCAD and exported as STL. What do you get?
You get 8 triangles (and supposedly 2*3=6 vertices).
- top and bottom triangles (2)
- 3 rectangular sides made up of 2 triangles each (3*2=6)
The STL format is one of many possible ways of describing a solid object.
STL does it by describing the surface of the solid in the form of a
discretized triangle mesh (this is different from traditional CAD). Hence
the term surface mesh.
In formatted STL, the model becomes like shown below (I converted it from
OpenSCADs binary STL to formatted using 'polyfix'). In STL, a triangle is
called a 'facet'. If you count the facets, you will see there are exactly
8. Each facet (=triangle) has a surface normal vector defining 'outside',
the direction that is supposed to point away from the solid body. There is
also a 'loop' listing the 3 triangle coordinates in counter-clockwise order
as viewed from 'outside'.
solid example
facet normal 0 0 -1
outer loop
vertex -10 0 0
vertex 0 10 0
vertex 10 0 0
endloop
endfacet
facet normal 0 0 1
outer loop
vertex 10 0 1
vertex 0 10 1
vertex -10 0 1
endloop
endfacet
facet normal -0.70710678 0.70710678 0
outer loop
vertex -10 0 0
vertex 0 10 1
vertex 0 10 0
endloop
endfacet
facet normal -0.70710678 0.70710678 0
outer loop
vertex -10 0 0
vertex -10 0 1
vertex 0 10 1
endloop
endfacet
facet normal 0 -1 0
outer loop
vertex 10 0 0
vertex -10 0 1
vertex -10 0 0
endloop
endfacet
facet normal 0 -1 0
outer loop
vertex 10 0 0
vertex 10 0 1
vertex -10 0 1
endloop
endfacet
facet normal 0.70710678 0.70710678 0
outer loop
vertex 0 10 0
vertex 10 0 1
vertex 10 0 0
endloop
endfacet
facet normal 0.70710678 0.70710678 -0
outer loop
vertex 0 10 0
vertex 0 10 1
vertex 10 0 1
endloop
endfacet
endsolid
This representation is a 'triangle soup', a collection of independent
triangles without any shared information whatsoever. You can take 'no
shared information' to imply 'no topology'.
If you search the STL data for a particular coordinate set, say 'vertex
10 0 0' you will find it is repeated several times, in this case 3 times in
3 different 'facets'. The only way to tell whether these triangles are
actually supposed to be interpreted as connected to each other or not is to
try to match coordinates against each other. Thus, it is a question of
interpretation based on some assumptions.
In this case it is supposedly easy because the coordinates are exact,
but most of the time the coordinates are represented by finite precision
floating point numbers, there is no guarantee that neighboring triangles
will show exactly the same coordinates. This is true for both formatted and
binary STL.
Therefore, to read STL you have to introduce some scheme using coordinate
tolerances or whatever to tell whether almost identical coordinates should
be interpreted as one point or several points. This problem happens
only for STL. You have to guess what the file is supposed to mean, and
that is why different modelling software sometimes come to different
conclusions for the same STL files (and thus why STL is not a good choice
for exchanging models between applications).
To be clear, these issues are due to missing topological information in
STL files, even if such information existed at export (in the case of
OpenSCAD, in CGAL).
Let us introduce some topology.
Export the exact same model from OpenSCAD, using a different file format,
one that includes topology. Let us use the OFF format since it is supported
in OpenSCAD. The OFF representation looks like this:
OFF 6 8 0
-10 0 0
0 10 0
10 0 0
10 0 1
0 10 1
-10 0 1
3 0 1 2
3 3 4 5
3 0 4 1
3 0 5 4
3 2 5 0
3 2 3 5
3 1 3 2
3 1 4 3
As can be seen, this is a more compact format. The first line says it is
an OFF file containing 6 vertices and 8 facets. The next 6 lines contain
the x,y,z coordinates of the 6 vertices, and the vertex# = line# - 1. The
next 8 lines contain each facet definition: number of vertices in facet
(3=triangle) and the vertex# for each facet vertex.
Such a representation is not subject to interpretation problems like STL,
because each vertex is mentioned only once and triangles share the vertices
by referring to them.... this is the topology in this case. Other
formats, like OBJ are similar to this.
Unlike STL, there is no room for misinterpretation of what is connected
to what.
We all "know" that slicers require that the object be "manifold", and in
my mind manifold has a topological meaning, informally in my case.
Manifold is indeed a topological term. But saying "manifold" is too
imprecise. Since slicers expect a solid to be represented by a surface
mesh (STL, OFF, OBJ or whatever), they require the model to be exactly
2-manifold, as opposed to 1-manifold, 3-manifold, 4-manifold etc.
What does 2-manifold mean? It means every edge in the surface mesh is
referenced exactly 2 times. To explain this in more detail we have to
define the topological entities that are relevant here
vertex : a point with x,y,z coordinates and an id# that makes it
referrable
edge : a line referring to 2 vertices using vertex id#
face : a flat polygon referring to vertices using vertex id#
A face referring to 3 vertices is a flat triangle. So assume triangles
only for simplicity.
A triangle has 3 sides, i.e. 3 edges. Since the triangle vertices must be
listed in CCW order, the triangle edges are well defined, using the vertex
id#s. You can establish an edge Id# by combining the 2 vertex id#s in
sorted order. This is key to determining 'manifoldness'.
Two neighbouring triangles in a well defined model will refer to the same
edge. If you go through the model and count the number each edge is
referenced (implicitly), the answer should be 2 for each edge in a surface
mesh.
This means only 2 triangles can refer to the same edge for the model to
be a valid surface mesh. If the number is 1, it is a free edge and the edge
is not 2-manifold. If the number is 3 then 3 triangles share the same edge,
and that is not allowed for a surface mesh, because one of the triangles is
not on the surface (or it may be degenerate and should be removed).
To further illustrate manifoldness of a surface mesh take the above
example again, converting original from STL to OFF using 'polyfix'
$ polyfix topology.stl -out=.off
Parameters:
input_file = topology.stl
out = .off
polyhedron 0 ================= volume=100, dtol=0.01, atol=1e-06,
maxiter=10
iteration 0: vertices=24 faces=8
warning: nonmanifold edges: uc(1)=24
merged 18 vertices
total changes=18
no warnings
iteration 1: vertices=6 faces=8
total changes=0
no warnings
Summary:
polyhedron 0: vertices=6 faces=8 : no warnings
Writing: topology_1.off
The original STL file contains a polygon soup of 8 faces, 24 vertices
with no shared information between the faces.
The warning says that there are 8*3=24 edges with use-count=1, i.e. all
edges strictly 1-manifold. Then, the software applies some coordinate
tolerance rules and interprets some of the vertices to be the same, while
keeping track of the changing vertex references from the 8 faces. After
merging the vertices and updating the vertex references from the faces, the
edge use-count test is performed again. It results in no warnings, which
means all edges had use-count=2, i.e. all 2-manifold.
I understand that an STL file is a list of triangles which may or may not
create a manifold surface, but I feel as if the collection has topology,
even if the individual triangles do not.
In STL, the only topology you have is within the individual triangles
(CCW order of vertices + implicit definition of edges).
Am I thinking about this incorrectly?
As I tried to explain above, it is not a question of 'feeling', but
precise definition. You can get away with 'feeling' as long as the
software(s) you are using all apply the same rules, but chances are they
are not exactly the same and hence you get many threads like this.
Most (not all) such issues would go away simply by not using STL.
Carsten Arnholm
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org