Re: STL best practices & tools
The reason for overlapping objects in OpenSCAD is not to create STL files
with better characteristics, but to prevent CGAL from failing on the
model. It would indeed be nice if this was not necessary, but as nophead
has said, there's no reason that this practice needs to introduce extra
vertices if the overlaps are done correctly. Since the failure mode is
that you get no STL file at all due to CGAL errors, I don't see that an STL
file cleanup program would be relevant to addressing this issue.
On Sat, Jun 3, 2023 at 6:41 PM neri-engineering via Discuss <
discuss@lists.openscad.org> wrote:
---------- Forwarded message ----------
From: neri-engineering neri-engineering@protonmail.com
To: OpenSCAD general discussion Mailing-list discuss@lists.openscad.org
Cc:
Bcc:
Date: Sat, 03 Jun 2023 22:41:02 +0000
Subject: [OpenSCAD] STL best practices & tools
Greetings,
I want to begin to seek advice on an OpenSCAD-related project (improvement
or addition) in my writings below; however, first I offer a quick
introduction.
I use OpenSCAD to create hobby engineering designs and assembly
animations. I have shared some of these before. I want to share my latest
computer animation which was generated using OpenSCAD, along with the
top-level scripts used to generate it; in the case that someone wants to do
something similar they may draw upon my work for inspiration and ideas.
The animation itself (and I'm sorry if some people are offended with the
posting of an external link):
https://odysee.com/@Neri_Engineering/4wd-motor-mount-assy
The entry points into the program to generate the above computer animation:
https://sourceforge.net/p/nl10/code/HEAD/tree/scripts/4wd/motor/4wd-motor-mount-assembly-animation.sh
(entry point + camera work)
https://sourceforge.net/p/nl10/code/HEAD/tree/code/gears/4wd/motor/anim/4wd-motor-mount-assembly.scad
(movement of parts, part definitions)
At some point I could possibly “Nerf” down those animation scripts to
create something extremely barebones and simple, and then I could make a
video presentation/lecture describing it.
Next, I am looking for employment opportunities. BERKELEY GRAD (MATH+CS),
EXPERT IN 3D COMPUTER GRAPHICS, THREADED PROGRAMMING, LOW LEVEL NETWORK
PROGRAMMING. UNIX POWER USER. FREEBSD, LINUX. JAVA / C / PYTHON. IN
TEXAS, SEEKING TO RELOCATE. CURRENTLY EMPLOYED. HAVE REFERENCES.
Okay, now onto the main topic of this email.
As I was studying other open source projects related to OpenSCAD I noticed
something interesting. In particular I recall looking at some code to
generate spur gears, and other code that was for generating screw threads
(using the polyhedron() native construct in OpenSCAD).
I noticed that programmers have a habit of creating polyhedron that
overlap with their neighbors, so that when STL is generated, it consists of
one piece and not of many individual pieces.
Yes, it makes sense to do that. I do understand why.
But, it makes a large project unmanageable, in my opinion. For one,
usually, "fudging" the vertices on polyhedron() will result in very "jaggy"
objects, with extra vertices and extra little jaggies everywhere. This is
obviously undesirable.
Second, it's not a pure approach in the mathematical sense. When you
start doing boolean operations (add, subtract, intersect, etc.) with jaggy
and imprecise objects then things get very hairy and very quickly.
In all of my code, my mathematical intuition initially told me
instinctively to never fudge vertices in order to make polyhedron overlap,
and to instead keep everything as accurate and as precise as possible, with
the consequence that generated STL will be made up of many little pieces
(undesirable).
Now I am at a point where I need to address these issues, of having
generated STL that consists of many little pieces.
With time I will likely need to create STL to 3D print from, or to use to
make forms for injection molding, and with more time I will need to
transfer much of my work to other tools such as FreeCAD (Python scripts) in
the case where those parts need to be machined from metal, using CNC.
But, I was thinking about the possibility of creating a post-generation
"STL cleanup tool", and I'm sure that such tools already exist. I was
imagining a tool which is configurable with "epsilon values" which will
treat sufficiently close numbers as being equal (configurable of course),
and will determine which faces are co-planar and which ones aren't. I
already have lots of experience with this sort of technique from my days of
writing line-drawing algorithms that use full aliasing (no anti-aliasing)
with blocky pixels, yet which allow end point coordinates to be specified
in 64 bit floating point. You are then able to draw very old-fashioned and
retro-looking pixelated lines (which look similar to the Bresenham style of
line) yet you're able to perfectly overlap sub-segments of the line. For
example, if you draw your original line from (0.0,0.0) to (5.0,13.0), two
prime numbers that is, then you can draw a subsegment covering only half of
the original line (0.0,0.0) -> (2.5,6.5), where every single pixel in the
subsegment is almost guaranteed to cover a pixel in the original line
segment. I say "almost" because usually this sort of operation entails
viewing the 64 bit representation of a floating point number in 32 bits, in
order to determine whether or not two numbers are sufficiently close to be
deemed equal. There are always, or at least usually, going to be some very
rare cases where such calculations won't lead to desired results, due to
the nature of number approximations that usually happen in computers
(unless real number systems are used, which are computationally very
expensive).
I imagine using an approach similar to that of my near-perfect retro
line-drawing algorithm, in order to implement an STL cleanup tool which
combines STL pieces that "touch" into one solid object. ("Touch" within an
epsilon value which is configurable.) These are early ideas into such
functionality.
I have also in the past implemented a spacial 3D search tree, “R-tree” to
be exact, which optimizes the determination of whether or not two small
things are intersecting or not. When analyzing STL files full of many
small little pieces, it would make sense to optimize boolean operations
through the use of a structure such as an R-tree. There are research
papers written that describe the algorithm for the R-tree. The R-tree has
very favorable time complexity characteristics, and it would be well-suited
for this sort of operation. I implemented and used an R-tree (written in
Java) while working at a research laboratory at the University of
California, with excellent results.
So I ask, does such “STL clean-up” functionality already exist? I think
no doubt it would by now. But are such tools implemented correctly and are
they effective? Can they handle the cleanup of STL files that consists of
hundreds, or thousands of tiny pieces? For example I found myself needing
to implement my retro line drawer twenty two years ago because I didn't
find anything similar on the internet (and still can't). I needed that
"retro line look" but wanted precise subsegment-covering properties for my
Blockout video game, so I implemented my own line-drawing library.
I imagine some post-OpenSCAD piece of code, which handles STL files
outside the scope of OpenSCAD, to allow for cleanup of STL files. I
imagine this being written in Java, in C, or in Python. I also imagine
that if such a piece of code is successful enough, that it may be
incorporated into OpenSCAD “proper” eventually (which is a great tool by
the way!).
For these reasons I seek some guidance. I would like to potentially
embark on this mission of writing such a toolset in the near future, unless
such a toolset already exists, and unless it does a proper job.
This sort of work is right up my alley by the way. I excel in
computational geometry and the like. I think there would be extensive use
of recursive functions and intelligent ways of triangulating surfaces which
need to be split up and combined, in the ideal piece of code which I’m now
starting to imagine.
I interviewed with Materialise in Belgium (actually with a subsidiary in
Princeton NJ) but didn’t get the offer because of my unwillingness to take
the jab. They were receiving financial help from a medical device company
(a client of theirs), which influenced their decision to mandate the jab
for all of their employees.
What I’m trying to say is that I find it odd that someone such as myself,
with my level of intelligence, talent, skill, and ambition, isn’t able to
find a way to sustain himself doing the type of work that he is best at.
At the very least I deserve a chance to be a contributing member of larger
society. People such as myself oftentimes end up asking themselves,
whether the problem is internal to themselves or whether it’s a problem
with the people running our world.
Any feedback appreciated. on this sort of tool. I am in the early stages
of thinking about such a tool at this point. It’s the sort of thing I
would like to work on in the future; and, I would be very good at it. I've
been away from this email list for a while because I have been so busy with
my hobby projects.
Respectfully,
Nerius Anthony Landys
Sent with Proton Mail https://proton.me/ secure email.
---------- Forwarded message ----------
From: neri-engineering via Discuss discuss@lists.openscad.org
To: OpenSCAD general discussion Mailing-list discuss@lists.openscad.org
Cc: neri-engineering neri-engineering@protonmail.com
Bcc:
Date: Sat, 03 Jun 2023 22:41:02 +0000
Subject: [OpenSCAD] STL best practices & tools
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
On Jun 4, 2023, at 3:02 PM, Adrian Mariano avm4@cornell.edu wrote:
The reason for overlapping objects in OpenSCAD is not to create STL files with better characteristics, but to prevent CGAL from failing on the model. It would indeed be nice if this was not necessary, but as nophead has said, there's no reason that this practice needs to introduce extra vertices if the overlaps are done correctly. Since the failure mode is that you get no STL file at all due to CGAL errors, I don't see that an STL file cleanup program would be relevant to addressing this issue.
Sadly, OpenSCAD has had a history of fully compiling and creating STLs that are in error WITHOUT failing in CGAL. I wrote an STL validation script just to find things like infinitely thin cleavages in STLs generated by OpenSCAD. While I did that for a much older version of OpenSCAD, I have seen these errors even in recent versions of OpenSCAD.
- Revar
I have stumbled upon a very interesting project which actually uses much of the code I've written in the past. In a sense I'm re-doing CGAL but only to handle certain conditions that are common to me.
My STLs compile w/o warning or error. No CGAL warnings. In many cases however because I choose not to create overlapping polyhedron (in screw threads for example, I have hundreds of disjoint polyhedron touching at faces) the generated STL consists of disjoint polyhedron, which are touching at a face (not an edge, bear in mind). In fact I create my STLs such that many of the "pieces" have a sibling piece which has the [almost] exact same face, only facing in the opposite direction. Same vertices too. There are rounding errors of course which causes polyhedron to NOT be joined. I choose not to overlap things in my projects because this is just the mathematical side of me doing things. I am more of a perfectionist mathematician and less of an engineer even though I love engineering.
I am developing tools that parallel CGAL, but in a simpler language at first. This project is so interesting.
I have written spacial index trees in the past (R-tree, based on Guttman's 1984 paper; he's a PhD from Berkeley). I see a situation like this. I realize that this is Masters' or PhD level work but please bear with me, it's very interesting.
We place all the individual 3D polyhedron into an R-tree in O(N*log(N)) time complexity. Now we can do operations such as "give me all things that touch this piece" in O(log(N)) time more or less.
We build a topological graph, yes with nodes and edges, to represent things. For example one sort of graph would have the nodes being the polyhedron and the edges defining things like "this node touches this other node because their faces are touching - we can join/unionize them!".
So with an R-tree and with a graph structure and with the building block elements of doing CSG pairwise operations on objects, we can start to do unions, intersections, subtractions, in O(N*log(N)) time I think. No more quadratic bullshit. An entire thing can be cleaned up in near linear time. I can't believe that I already had much of this code lying around - graph library, R-tree and some other stuff.
In particular I want to write a cleanup tool for only my STL files, because they are structurally intact only they consist of disjoint solids, always touching at a face (not an edge!). Some people were complaining about them and this is embarrassing me.
Later on I could possibly expand on that functionality to provide more stuff, even improving CGAL itself perhaps.
I could see there being a web service or something to submit an STL to have it pass through a function with a certain cleanup operation (join solids which share a face for example).
The really funny thing is that I wrote much of this code already many years ago, and it was written as open source (LGPL v2.1 to be exact), and I was paid for it, while working at Trey Ideker's lab at UCSD, on a project called "Cytoscape". So now I am incorporating this open source code into my new project.
Working steadily towards this goal, and we'll see where we arrive. It's in Java now, which is a fairly safe language. If the code is very effective it can be rewritten to something better. This is just the project starting out. I will likely be plugging away at this for a month or so. Gives me something to do. Computational Geometry is kick ass. Very fun stuff.
https://sourceforge.net/projects/stl-ops/ <--- my project starting out, at infancy stage
Sent with Proton Mail secure email.
------- Original Message -------
On Sunday, June 4th, 2023 at 7:17 PM, Revar Desmera revarbat@gmail.com wrote:
On Jun 4, 2023, at 3:02 PM, Adrian Mariano avm4@cornell.edu wrote:
The reason for overlapping objects in OpenSCAD is not to create STL files with better characteristics, but to prevent CGAL from failing on the model. It would indeed be nice if this was not necessary, but as nophead has said, there's no reason that this practice needs to introduce extra vertices if the overlaps are done correctly. Since the failure mode is that you get no STL file at all due to CGAL errors, I don't see that an STL file cleanup program would be relevant to addressing this issue.
Sadly, OpenSCAD has had a history of fully compiling and creating STLs that are in error WITHOUT failing in CGAL. I wrote an STL validation script just to find things like infinitely thin cleavages in STLs generated by OpenSCAD. While I did that for a much older version of OpenSCAD, I have seen these errors even in recent versions of OpenSCAD.
- Revar