Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

render fails with polyhedron + cylinder union() #2398

Open
poindexter9 opened this issue May 21, 2018 · 6 comments
Open

render fails with polyhedron + cylinder union() #2398

poindexter9 opened this issue May 21, 2018 · 6 comments

Comments

@poindexter9
Copy link

poindexter9 commented May 21, 2018

It seems that this code:

polyhedron([
	[4, 0, 1], [0, 4, 1], [-4, 0, 1], [0, -4, 1],
	[4, 0, 5], [0, 4, 5], [-4, 0, 5], [0, -4, 5],
	[15, 0, 5], [0, 15, 5], [-15, 0, 5], [0, -15, 5],
	[15, 0, 6], [0, 15, 12], [-15, 0, 18], [0, -15, 24],
	[0, 15, 6], [-15, 0, 12], [0, -15, 18], [15, 0, 24],
	[50, 0, 6], [0, 50, 12], [-50, 0, 18], [0, -50, 24],
	[0, 50, 6], [-50, 0, 12], [0, -50, 18], [50, 0, 24],
	[50, 0, 0], [0, 50, 0], [-50, 0, 0], [0, -50, 0],
	[0, 0, 0],
	[0, 0, 1],
], [
	[20, 24, 29],
	[29, 28, 20],
	[21, 25, 30],
	[30, 29, 21],
	[22, 26, 31],
	[31, 30, 22],
	[23, 27, 28],
	[28, 31, 23],
	[28, 29, 32],
	[29, 30, 32],
	[30, 31, 32],
	[31, 28, 32],
	[0, 3, 33],
	[3, 2, 33],
	[2, 1, 33],
	[1, 0, 33],
	[5, 4, 0],
	[0, 1, 5],
	[6, 5, 1],
	[1, 2, 6],
	[7, 6, 2],
	[2, 3, 7],
	[4, 7, 3],
	[3, 0, 4],
	[9, 8, 4],
	[4, 5, 9],
	[10, 9, 5],
	[5, 6, 10],
	[11, 10, 6],
	[6, 7, 11],
	[8, 11, 7],
	[7, 4, 8],
	[16, 12, 8],
	[8, 9, 16],
	[17, 13, 9],
	[9, 10, 17],
	[18, 14, 10],
	[10, 11, 18],
	[19, 15, 11],
	[11, 8, 19],
	[24, 20, 12],
	[12, 16, 24],
	[25, 21, 13],
	[13, 17, 25],
	[26, 22, 14],
	[14, 18, 26],
	[27, 23, 15],
	[15, 19, 27],
	[21, 24, 16],
	[16, 13, 21],
	[22, 25, 17],
	[17, 14, 22],
	[23, 26, 18],
	[18, 15, 23],
	[20, 27, 19],
	[19, 12, 20],
]);

cylinder(d=120, h=0.3);

Crashes both OpenSCAD-Nightly and OpenSCAD with this error message:

terminate called after throwing an instance of 'boost::exception_detail::clone_impl<boost::exception_detail::error_info_injector<boost::bad_any_cast>>'
what(): boost::bad_any_cast: failed conversion using boost::any_cast
Aborted

When you click Render.


Want to back this issue? Post a bounty on it! We accept bounties via Bountysource.

@kintel
Copy link
Member

kintel commented May 21, 2018

The backtrace indicates a crash inside CGAL's union code (tested with CGAL 4.11):

#8	0x000000010055a192 in void boost::throw_exception<boost::bad_any_cast>(boost::bad_any_cast const&) at /Users/kintel/code/OpenSCAD/openscad/../libraries/install/include/boost/throw_exception.hpp:69
#9	0x000000010074038d in unsigned int boost::any_cast<unsigned int>(boost::any&) at /Users/kintel/code/OpenSCAD/openscad/../libraries/install/include/boost/any.hpp:268
#10	0x000000010073ff62 in CGAL::SNC_FM_decorator<CGAL::SNC_structure<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> >::determine_facet(CGAL::internal::In_place_list_iterator<CGAL::SNC_in_place_list_shalfedge<CGAL::SNC_indexed_items::SHalfedge<CGAL::SNC_structure<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> > >, std::__1::allocator<CGAL::SNC_in_place_list_shalfedge<CGAL::SNC_indexed_items::SHalfedge<CGAL::SNC_structure<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> > > > >, std::__1::vector<CGAL::internal::In_place_list_iterator<CGAL::SNC_in_place_list_shalfedge<CGAL::SNC_indexed_items::SHalfedge<CGAL::SNC_structure<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> > >, std::__1::allocator<CGAL::SNC_in_place_list_shalfedge<CGAL::SNC_indexed_items::SHalfedge<CGAL::SNC_structure<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> > > > >, std::__1::allocator<CGAL::internal::In_place_list_iterator<CGAL::SNC_in_place_list_shalfedge<CGAL::SNC_indexed_items::SHalfedge<CGAL::SNC_structure<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> > >, std::__1::allocator<CGAL::SNC_in_place_list_shalfedge<CGAL::SNC_indexed_items::SHalfedge<CGAL::SNC_structure<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> > > > > > > const&, CGAL::Unique_hash_map<CGAL::internal::In_place_list_iterator<CGAL::SNC_in_place_list_shalfedge<CGAL::SNC_indexed_items::SHalfedge<CGAL::SNC_structure<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> > >, std::__1::allocator<CGAL::SNC_in_place_list_shalfedge<CGAL::SNC_indexed_items::SHalfedge<CGAL::SNC_structure<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> > > > >, int, CGAL::Handle_hash_function, std::__1::allocator<int> > const&, std::__1::vector<CGAL::internal::In_place_list_iterator<CGAL::SNC_in_place_list_shalfedge<CGAL::SNC_indexed_items::SHalfedge<CGAL::SNC_structure<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> > >, std::__1::allocator<CGAL::SNC_in_place_list_shalfedge<CGAL::SNC_indexed_items::SHalfedge<CGAL::SNC_structure<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> > > > >, std::__1::allocator<CGAL::internal::In_place_list_iterator<CGAL::SNC_in_place_list_shalfedge<CGAL::SNC_indexed_items::SHalfedge<CGAL::SNC_structure<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> > >, std::__1::allocator<CGAL::SNC_in_place_list_shalfedge<CGAL::SNC_indexed_items::SHalfedge<CGAL::SNC_structure<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> > > > > > > const&) const at /Users/kintel/code/OpenSCAD/openscad/../libraries/install/include/CGAL/Nef_3/SNC_FM_decorator.h:424
#11	0x000000010073acbc in CGAL::SNC_FM_decorator<CGAL::SNC_structure<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> >::create_facet_objects(CGAL::Plane_3<CGAL::Cartesian<CGAL::Gmpq> > const&, std::__1::__list_iterator<CGAL::Object, void*>, std::__1::__list_iterator<CGAL::Object, void*>) const at /Users/kintel/code/OpenSCAD/openscad/../libraries/install/include/CGAL/Nef_3/SNC_FM_decorator.h:654
#12	0x0000000100732b75 in CGAL::SNC_external_structure<CGAL::SNC_indexed_items, CGAL::SNC_structure<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> >::categorize_facet_cycles_and_create_facets() const at /Users/kintel/code/OpenSCAD/openscad/../libraries/install/include/CGAL/Nef_3/SNC_external_structure.h:1280
#13	0x00000001007aefca in void CGAL::SNC_external_structure<CGAL::SNC_indexed_items, CGAL::SNC_structure<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> >::build_after_binary_operation<CGAL::ID_support_handler<CGAL::SNC_indexed_items, CGAL::SNC_decorator<CGAL::SNC_structure<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> > > >(CGAL::ID_support_handler<CGAL::SNC_indexed_items, CGAL::SNC_decorator<CGAL::SNC_structure<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> > >&) at /Users/kintel/code/OpenSCAD/openscad/../libraries/install/include/CGAL/Nef_3/SNC_external_structure.h:1404
#14	0x00000001007a6107 in void CGAL::Binary_operation<CGAL::SNC_structure<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> >::operator()<CGAL::Nef_polyhedron_3<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool>::OR>(CGAL::SNC_point_locator<CGAL::SNC_decorator<CGAL::SNC_structure<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> > >*, CGAL::SNC_structure<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> const&, CGAL::SNC_point_locator<CGAL::SNC_decorator<CGAL::SNC_structure<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> > > const*, CGAL::SNC_structure<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> const&, CGAL::SNC_point_locator<CGAL::SNC_decorator<CGAL::SNC_structure<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> > > const*, CGAL::Nef_polyhedron_3<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool>::OR const&) at /Users/kintel/code/OpenSCAD/openscad/../libraries/install/include/CGAL/Nef_3/Binary_operation.h:581
#15	0x00000001007a305f in CGAL::Nef_polyhedron_3<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool>::join(CGAL::Nef_polyhedron_3<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> const&) const at /Users/kintel/code/OpenSCAD/openscad/../libraries/install/include/CGAL/Nef_polyhedron_3.h:1456
#16	0x00000001007a2ba4 in CGAL::Nef_polyhedron_3<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool>::operator+(CGAL::Nef_polyhedron_3<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> const&) const at /Users/kintel/code/OpenSCAD/openscad/../libraries/install/include/CGAL/Nef_polyhedron_3.h:1506
#17	0x00000001007a2a1f in CGAL::Nef_nary_union_3<CGAL::Nef_polyhedron_3<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> >::unite() at /Users/kintel/code/OpenSCAD/openscad/../libraries/install/include/CGAL/Nef_nary_union_3.h:46
#18	0x0000000100791179 in CGAL::Nef_nary_union_3<CGAL::Nef_polyhedron_3<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> >::add_polyhedron(CGAL::Nef_polyhedron_3<CGAL::Cartesian<CGAL::Gmpq>, CGAL::SNC_indexed_items, bool> const&) at /Users/kintel/code/OpenSCAD/openscad/../libraries/install/include/CGAL/Nef_nary_union_3.h:57
#19	0x0000000100790905 in CGALUtils::applyOperator(std::__1::list<std::__1::pair<AbstractNode const*, std::__1::shared_ptr<Geometry const> >, std::__1::allocator<std::__1::pair<AbstractNode const*, std::__1::shared_ptr<Geometry const> > > > const&, OpenSCADOperator) at /Users/kintel/code/OpenSCAD/openscad/src/cgalutils-applyops.cc:101

@poindexter9
Copy link
Author

@t-paul: do you see something wrong with this model?

I am thinking that this rule may have been broken:

exactly two faces should meet at any polyhedron edge.

Specifically in each of the four corners, where the taller block has one triangle towards the vertical "corner edge", and the less tall block has one as well, but there is also a third triangle pointing inwards towards the model center.

I'm not sure about this rule:

if two faces have a vertex in common, they should be in the same cycle face-edge around the vertex.

I have not (yet at least) understood the second part of that sentence.

@poindexter9
Copy link
Author

So anyway,

I still do not understand the second rule:

if two faces have a vertex in common, they should be in the same cycle face-edge around the vertex.

So I simply ignored it.

I then made a model where I followed this rule:

exactly two faces should meet at any polyhedron edge.

The logical consequence of this rule is that I have to "triangulate" everything manually for any model slightly more complex than a cube, far as I can tell. I did, and it works great. No more crashes, no more assertion failures either.

I "triangulated" in a way that I suppose is logical to a human being, and that is simple to implement in code. That ended up increasing the amount of triangles by several magnitudes though. So both preview and render is really, really slow.

It was also a hell of a lot of work. Using this method, about 10% of the work in using polyhedron() is defining points and shapes, an 90% is slicing things up into triangles where each side touch one other triangle.

I also made another model using this home-made rule for polyhedron():

"For each line of each face you define, if there is a point along that line which is used in another face, make sure to include that point in the definition of the current face as well."

It turns out that OpenSCAD is much better at turning faces into triangles than I am, as one can see after turning on "View --> Show Edges". Following the above rule worked exactly as well as doing everything manually, no assertions or failures either. It also previews and renders a lot faster than the manual method.

Long story short, I think the wiki should probably state somewhere, for other newbies like me, the following rules:

"1) For each edge of each face you define, if there is a point along that line which is used in another face, make sure to include that point in the definition of the current face as well. This ensures that OpenSCAD can properly turn the face into a triangle where each side touch exactly one other triangle.

  1. Make sure not to define two faces that meet at only a single point. This ensures that CGAL can render the shape without raising any assertions."

Instead of the current rules that a) force a lot of manual work and b) is incomprehensible.

Another idea would be to have OpenSCAD do the above automatically?

In theory, it should be possible to take any faces that share a single point and check if any of their edges are exactly parallel. If so, and iff one of the edges is shorter than the other, automatically include the (previously non-shared) end point of the shorter edge in the face with the longer edge.

If afterwards two faces have at least one point in common, check that they also have at least two points in common. If not, show a warning during preview (because CGAL will certainly throw an assertion during render).

(After those two checks, turn faces into triangles as usual.)

Not sure if it is realistic to implement, but if it was, it could potentially save a bunch of time for the next newbie...

@kintel
Copy link
Member

kintel commented May 28, 2018

Thanks for being patient!
Some notes/responses:

  • We have a meta-issue for automatic mesh repair. It contains some ideas and work in progress: Simple mesh repair on import #1580
  • Another way of describing what you mention in the end is that any mesh should be "topologically watertight": If you were to move any one point in space, it will never cause a crack to appear in the mesh.
  • If you feel you have a good way of explaining this to the next victim, it would be very much appreciated if you'd take the opportunity to edit the wiki; most of the wiki is user-contributed. Projects like this exist because of distributed volunteer effort!

@nophead
Copy link
Member

nophead commented May 28, 2018

if two faces have a vertex in common, they should be in the same cycle face-edge around the vertex.

I think that just means faces that share a vertex should have the same winding order. I.e. all clockwise when viewed from the outside.

@kintel
Copy link
Member

kintel commented Mar 29, 2024

Status as of 2024-03-24:

  • No longer crashes
  • The model still doesn't render since the design isn't a manifold topology

@kintel kintel changed the title render crash with polyhedron + cylinder union() render fails with polyhedron + cylinder union() Mar 29, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

4 participants