Bad Polyhedron Faces
On 11/23/2024 9:55 AM, Bob Carlson via Discuss wrote:
I have looked at the documentation when I saw Thrown Together
mentioned, but I could not find anything useful. What is Thrown
Together anyway?
I was hoping that somebody who actually knew everything that it did
would pipe up. Absent that, I'll take a stab...
- It paints the front side of faces yellow, and the back side purple.
If you see any purple, you have a problem. - It does not do differences; instead it displays the negative objects
in green. - It does not do intersections; instead it displays all objects.
The first is the major reason why I use it. (Hmm. Come to think of it,
I wonder why that part isn't the default. I don't know whether we
already have to separately draw both sides of each face; if we do then
we might as well default to drawing the back sides purple.)
Note: all colors mentioned are with the default color scheme and will
be different in other color schemes.
Something that has messed me up a few times has been when I've had
Thrown Together turned on and forgotten about it, because then
differences and intersections don't appear to work.
(sorry, late because I was on vacation)
On 11/23/2024 10:27 AM, Jordan Brown via Discuss wrote:
That check is relatively straightforward to implement in C++, but
painful to implement in OpenSCAD. (For n being the number of edges,
it's O(n) in C++, and I think it can be done in O(n log n) in
OpenSCAD. The problem is that you can't populate an array in
arbitrary order in OpenSCAD.)
I used a hash table to implement a quick check algorithm:
- For each edge (in the polyhedron, STL, etc), look up the edge in the
hash table
(where the hash function gives same index whether or not the ends of
the edge are swapped)
- If not found, add edge to hash table with count=1
- If found and direction is the same, increment edge's count in
hash table
- If found and direction is opposite, decrement edge's count in
hash table - Check that each entry in hash table has count of 0.
This algorithm matches vertex values exactly (or within a tolerance...)
so it doesn't matter if there is an indirect vertex array. This might be
considered O(n), although if the hash bucket size is in any way
proportional to n, then it's technically still O(n^2).
That check will let you ensure that the polyhedron is consistent, that
the faces are all wound in the same direction. It won't tell you
whether they are all wound clockwise-from-the-outside. Ref, e.g.,
https://xkcd.com/2403/ .
Once the polyhedron is verified manifold as above, I believe this other
check only requires shooting a single ray from a single face (plus edge
cases).
So, net, while it's a nuisance to do in OpenSCAD-language, it's not
awful to do the appropriate checks in C++. Not free, and maybe not
worth doing on every polyhedron construction, but not awful. (After
all, once you learn how to build the polyhedron correctly, re-checking
it is a waste of time)
Perhaps there could be a polyhedron(manifold = "check") option that
enforces the condition by checking it, and displays error information on
failure.
If we wanted it to, OpenSCAD could even correct an inside-out
polyhedron, or could attempt to correct an inconsistently-wound
polyhedron. (Can't correct a Klein bottle, though.) But that would
require running the check on every polyhedron, which seems like an
unreasonable processing expense.
The option could be like polyhedron(manifold = "force"). But repair is
probably too big and a vague a can of worms, as there are many things
that can be wrong, and many large programs just for that (meshlab, etc).
Consider the case of two cubes that touch along an edge:
cube(10);
translate([10,10,0]) cube(10);
If you represented this as a single polyhedron, that shared edge needs
to be represented twice, with one cube connecting two of the points
and the other cube connecting the other two points.
I think in this case the shared edge appears four times, and it's fine.
If it's changed to translate([11,11,0]), then the polyhedron is
disjointed but I think it's still fine.
Regards, Curt