Quicksort
As far as I know, polyhedron faces isn't triangulated in rendering just in
preview. That is the main reason I searched for a polygon triangulation.
Apparently, when CGAL rejects a face as non-planar, OpenSCAD tries to
triangulate it: the alternative procedure. But sometimes this doesn't work
either.
I don't need to sort 40000 array values. I was only doing a time analysis to
compare different methods. Remember that the quicksort exemplified in the
manual, to be robust, should be restricted to handle vectors with 3000
elements. That is the limit for the worst (very unlikely) case, but you
never know.
--
View this message in context: http://forum.openscad.org/Quicksort-tp17044p17079.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
As I said before in another thread, OpenSCAD should provide a good set of
list processing operators. And sorting is a very basic one. After all, lists
are the only available data structure in the language.
Besides, CGAL has lots of computational geometry methods and very very few
of them are accessible by the language. My dream is to have a general
OpenSCAD interface to CGAL library for people who wants to dig in the CGAL
world.
To dough: I like F-rep too. It is a very general paradigm but it requires
some mathematical-oriented mind. I see no way to include F-rep without a
robust optimized kernel to support it. If CGAL is able to give that support,
it would a good path to pursuit.
--
View this message in context: http://forum.openscad.org/Quicksort-tp17044p17080.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
As far as I know, polyhedron faces isn't triangulated in rendering just
in preview.
Yes CGAL maintains polygonal facets if they are planar but when you create
an STL file it gets triangulated at that point.
On 12 April 2016 at 16:01, Ronaldo rcmpersiano@gmail.com wrote:
As I said before in another thread, OpenSCAD should provide a good set of
list processing operators. And sorting is a very basic one. After all,
lists
are the only available data structure in the language.
Besides, CGAL has lots of computational geometry methods and very very few
of them are accessible by the language. My dream is to have a general
OpenSCAD interface to CGAL library for people who wants to dig in the CGAL
world.
To dough: I like F-rep too. It is a very general paradigm but it requires
some mathematical-oriented mind. I see no way to include F-rep without a
robust optimized kernel to support it. If CGAL is able to give that
support,
it would a good path to pursuit.
--
View this message in context:
http://forum.openscad.org/Quicksort-tp17044p17080.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
As I wrote in the other thread, quicksort alone will not speed up your code
from O(n²) to O(n log n). What you need, is a sorter operating over a
balanced tree. Thus: better "ask" for this. BUT: this approach needs
function pointers, as you will have to provide a predicate for general
sorting. So better wait for OpenSCAD2, use a richer programming language, or
try your luck and ask for an API ;-)
--
View this message in context: http://forum.openscad.org/Quicksort-tp17044p17083.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
Ronaldo wrote:
As far as I know, polyhedron faces isn't triangulated in rendering just in
preview. That is the main reason I searched for a polygon triangulation.
Apparently, when CGAL rejects a face as non-planar, OpenSCAD tries to
triangulate it: the alternative procedure. But sometimes this doesn't work
either.
Ronaldo, it sounds like you are writing your own polygon triangulation
software in order to work around a possible bug in polyhedron(). There is
some argument to polyhedron(), involving a non-planar face, that works in
preview, but doesn't work in rendering.
Can you describe the bug in more detail, maybe provide a failing test case?
On 12 April 2016 at 14:37, Parkinbot rudolf@parkinbot.com wrote:
As I wrote in the other thread, quicksort alone will not speed up your code
from O(n²) to O(n log n). What you need, is a sorter operating over a
balanced tree. Thus: better "ask" for this. BUT: this approach needs
function pointers, as you will have to provide a predicate for general
sorting. So better wait for OpenSCAD2, use a richer programming language,
or
try your luck and ask for an API ;-)
--
View this message in context:
http://forum.openscad.org/Quicksort-tp17044p17083.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
doug.moen wrote
Ronaldo, it sounds like you are writing your own polygon triangulation
software in order to work around a possible bug in polyhedron(). There is
some argument to polyhedron(), involving a non-planar face, that works in
preview, but doesn't work in rendering.
Can you describe the bug in more detail, maybe provide a failing test
case?
I don't have a failing test case anymore. I integrated the polygon
triangulation in my system and have no more the issues I had before.
I am working on a system that allows solid (sets with manifold boundaries)
modelling using polyhedron primitive with faces defined by Bezier patches
and planar (or almost) faces. It evolved very well but I faced now and then
with annoying messages by CGAL of non-planar faces. The analysis of the face
definition usually shown that the face was planar (for instance, all
vertices had the same x coordinate). Sometimes the alternate construction
solved the trouble. Sometimes not. So, I decided to write my own polygon
triangulation algorithm which unhappily is not good enough and took too much
of my time. The discussions on simple polygon test, plane fitting and
sorting, all came from that target. That is the story.
I have no way to say that I was facing a bug. I don't know what is being
considered for OpenSCAD2. But, it would be nice to have access to this sort
of geometrical methods that are in the core of CGAL. And a richer set of
list processing functions.
--
View this message in context: http://forum.openscad.org/Quicksort-tp17044p17086.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
On Apr 12, 2016, at 11:01 AM, Ronaldo rcmpersiano@gmail.com wrote:
Besides, CGAL has lots of computational geometry methods and very very few
of them are accessible by the language. My dream is to have a general
OpenSCAD interface to CGAL library for people who wants to dig in the CGAL
world.
Ronaldo,
Keep in mind that OpenSCAD isn’t primarily a wrapper around CGAL. We use it as a last resort to perform certain types of computational geometry operations. Due to severe performance challenges with CGAL, we’re actively looking for ways to reduce our dependency on CGAL.
To dig into the CGAL world, I would recommend using their officially supported SWIG bindings as a starting point.
-Marius
On Apr 12, 2016, at 10:44 AM, Ronaldo rcmpersiano@gmail.com wrote:
Apparently, when CGAL rejects a face as non-planar, OpenSCAD tries to
triangulate it: the alternative procedure. But sometimes this doesn't work
either.
“sometimes this doesn’t work” sounds like a bug.
CGAL frequently rejects polygons as non-planar, if those polygons were specified using floating point vertices. We have workarounds for that, but our workaround are only as good as our test cases. Any additional corner cases breaking this would be valuable input allowing us to be more robust.
As a side-note for anyone wondering: The polygon triangulator built into CGAL isn’t very robust and crashes on some of our test cases. We thus had to switch to a more robust implementation, currently libtess2, as mentioned earlier in this thread.
-Marius
"CGAL frequently rejects polygons as non-planar, if those polygons were
specified using floating point vertices. We have workarounds for that, but
our workaround are only as good as our test cases."
I suggest that polyhedron() should automatically triangulate any face with
more than 3 vertices, since in this case floating point vertices are always
used.
On 13 April 2016 at 11:16, Marius Kintel marius@kintel.net wrote:
On Apr 12, 2016, at 10:44 AM, Ronaldo rcmpersiano@gmail.com wrote:
Apparently, when CGAL rejects a face as non-planar, OpenSCAD tries to
triangulate it: the alternative procedure. But sometimes this doesn't
work
either.
“sometimes this doesn’t work” sounds like a bug.
CGAL frequently rejects polygons as non-planar, if those polygons were
specified using floating point vertices. We have workarounds for that, but
our workaround are only as good as our test cases. Any additional corner
cases breaking this would be valuable input allowing us to be more robust.
As a side-note for anyone wondering: The polygon triangulator built into
CGAL isn’t very robust and crashes on some of our test cases. We thus had
to switch to a more robust implementation, currently libtess2, as mentioned
earlier in this thread.
-Marius
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
kintel wrote
Keep in mind that OpenSCAD isn’t primarily a wrapper around CGAL. We use
it as a last resort to perform certain types of computational geometry
operations. Due to severe performance challenges with CGAL, we’re actively
looking for ways to reduce our dependency on CGAL.
To dig into the CGAL world, I would recommend using their officially
supported SWIG bindings as a starting point.
Thank you for the clarification and reference. I imagined that. And it was
the reason why I did not submitted a feature request following a Parkinbot
suggestion. Anyway it was just a dream...:)
--
View this message in context: http://forum.openscad.org/Quicksort-tp17044p17104.html
Sent from the OpenSCAD mailing list archive at Nabble.com.