Quicksort
doug.moen wrote
I suggest that polyhedron() should automatically triangulate any face with
more than 3 vertices, since in this case floating point vertices are
always
used.
That would be nice. It is what I currently do in my code with the (not
robust) simple polygon triangulation I have written. However, as Sloan
suggested with a question in another thread, there is not a unique
triangulation for non-planar polygons. And worst, and to be fair, there is
no polygon well defined by a non-planar polygonal.
--
View this message in context: http://forum.openscad.org/Quicksort-tp17044p17105.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
Ronaldo said "However, as Sloan
suggested with a question in another thread, there is not a unique
triangulation for non-planar polygons. And worst, and to be fair, there is
no polygon well defined by a non-planar polygonal."
The case we care most about is almost-planar polygons, which would be
planar except for floating point imprecision. In that case, the various
choices will be visually indistinguishable, I would guess. If the user
provides a seriously non-planar polygon (due to a bug in the user's code,
not due to floating point imprecision), then if we choose a bad
triangulation, the user can deal with the issue by fixing their code.
Also, it's possible to make a judgement that some triangulations are better
than others.
In the triangulation thread, somebody suggested to look at the Wings3D
triangulator.
https://github.com/dgud/wings/blob/master/src/wings_tesselation.erl
%% Triangulates a quad, tries to make the triangulation so nice
%% patterns emerges, or otherwise along the shortest diagonal, Then
%% checking that normals for the triangles are consistent with the
%% normal for the quad. Falls back to the general triangulator if
%% normals are inconsistent (= concave or otherwise strange quad).
triangulate_quad(F, Vs, TriV0, FsSet0, #we{vp=Vtab}=We0) ->
I don't really understand the code, however, the comment indicates that you
can use normals, plus heuristics, to choose a nice triangulation.
The code you referred is intended to triangulate quads not a more general
polygonal. For quads, there is only two alternatives to check. That would
be nice for meshes.
2016-04-13 13:56 GMT-03:00 doug moen doug@moens.org:
Ronaldo said "However, as Sloan
suggested with a question in another thread, there is not a unique
triangulation for non-planar polygons. And worst, and to be fair, there is
no polygon well defined by a non-planar polygonal."
The case we care most about is almost-planar polygons, which would be
planar except for floating point imprecision. In that case, the various
choices will be visually indistinguishable, I would guess. If the user
provides a seriously non-planar polygon (due to a bug in the user's code,
not due to floating point imprecision), then if we choose a bad
triangulation, the user can deal with the issue by fixing their code.
Also, it's possible to make a judgement that some triangulations are
better than others.
In the triangulation thread, somebody suggested to look at the Wings3D
triangulator.
https://github.com/dgud/wings/blob/master/src/wings_tesselation.erl
%% Triangulates a quad, tries to make the triangulation so nice
%% patterns emerges, or otherwise along the shortest diagonal, Then
%% checking that normals for the triangles are consistent with the
%% normal for the quad. Falls back to the general triangulator if
%% normals are inconsistent (= concave or otherwise strange quad).
triangulate_quad(F, Vs, TriV0, FsSet0, #we{vp=Vtab}=We0) ->
I don't really understand the code, however, the comment indicates that
you can use normals, plus heuristics, to choose a nice triangulation.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
On Apr 13, 2016, at 11:47 AM, doug moen doug@moens.org wrote:
I suggest that polyhedron() should automatically triangulate any face with more than 3 vertices, since in this case floating point vertices are always used.
We do have occasional reports from people who are dependent on quads generated by certain primitives being preserved into downstream software. This is kind of challenging due to the current planarity issues with CGAL. Not sure if this is a workflow we realistically can keep supporting though.
Another issue is that when triangulating all primitives, we get hit by some performance regressions due to CGAL performing significantly more work when processing the resulting geometry. Since we’re already struggling with performance, I decided to not impose another performance hit when I last worked on that. I’m not 100% sure when CGAL performs the operation of merging planar areas into one polygon; perhaps we could manually trigger that.
-Marius
Thanks, it makes sense that there would be a performance hit with extra
facets. And the issue with downstream quads did not occur to me. I guess
that OFF supports quads.
So that means, after converting the vertices to rational numbers, that each
face either is planar, or isn't. If it's planar, then CGAL won't have a
problem. If it isn't planar, then we must triangulate. This sounds simple,
but obviously there are hidden complexities or we wouldn't have this bug.
On 13 April 2016 at 13:41, Marius Kintel marius@kintel.net wrote:
On Apr 13, 2016, at 11:47 AM, doug moen doug@moens.org wrote:
I suggest that polyhedron() should automatically triangulate any face
with more than 3 vertices, since in this case floating point vertices are
always used.
We do have occasional reports from people who are dependent on quads
generated by certain primitives being preserved into downstream software.
This is kind of challenging due to the current planarity issues with CGAL.
Not sure if this is a workflow we realistically can keep supporting though.
Another issue is that when triangulating all primitives, we get hit by
some performance regressions due to CGAL performing significantly more work
when processing the resulting geometry. Since we’re already struggling with
performance, I decided to not impose another performance hit when I last
worked on that. I’m not 100% sure when CGAL performs the operation of
merging planar areas into one polygon; perhaps we could manually trigger
that.
-Marius
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
On Apr 13, 2016, at 13:54 PM, doug moen doug@moens.org wrote:
[…] This sounds simple, but obviously there are hidden complexities or we wouldn't have this bug.
Yes - we still don’t know what this mug might be though. Ronaldo: Any reproducible input would be welcome.
-Marius
Keep in mind that we can mark the new edge generated when quad is
converted to triangle.
This could be preserved - where possible) in the chain and so preference
for quads can be maintained by a suitable un-triangulate function. Also
some file formats allow marking of these - e.g. 3ds.
Two possibilities here:
a) preserve the original quads
b) derive “good” quads - perhaps even from data that was originally generated as triangles
Doing a) is just a matter of marking, and then removing, the extra edges. Doing b) is a bit more interesting (and harder)
--
Kenneth Sloan
KennethRSloan@gmail.com
Vision is the art of seeing what is invisible to others.
On Apr 13, 2016, at 18:33 , Mark Schafer mschafer@wireframe.biz wrote:
Keep in mind that we can mark the new edge generated when quad is converted to triangle.
This could be preserved - where possible) in the chain and so preference for quads can be maintained by a suitable un-triangulate function. Also some file formats allow marking of these - e.g. 3ds.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org