Abort from CGALEvaluator::evaluateCGALMesh::PolyReducer::add_edges about openscad HOT 23 CLOSED

Minimal crash:

projection(cut=true) translate([0,0,-4.999999]) cube(10, center=true);

from openscad.

This is a bit tricky. I added some source code comments in PolySetCGALEvaluator.cc. If anyone feels like a deep dive into CGAL, this is a good opportunity. I'm sure the solution is elegant once figured out though.

from openscad.

Can you tell me a little bit more about what a Polyset is?

My main questions are this:

Can the polygons in a PolySet be self-intersecting?
Do Polygons in a Polyset contain 'holes' or are they just convex polygons?

In my imagination, I can see that you could perhaps re-implement the CGAL->OpenGL code, so that instead of OpenGL output, it just gives output into a convex set of polygons, that are formed into a PolySet. The Tessellation would be performed by GLU.

My problem is this: the design of this will be somewhat similar to OGL_helper.h, and the question is, are you violating copyright by doing something somewhat similar to OGL_helper.h and claiming it GPL?

from openscad.

A PolySet is a container class for storing polygons, in order to move it to or from CGAL or other classes generating or consuming geometry. From the source code:

The PolySet class fulfils multiple tasks, partially for historical reasons.
FIXME: It's a bit messy and is a prime target for refactoring.

1) Store 2D and 3D polygon meshes from all origins
2) Store 2D outlines, used for rendering edges
3) Rendering of polygons and edges

PolySets have no guarantees, but whenever you want to pass something into CGAL, it must be checked or CGAL might barf. PolySets contain just pure geometry, no information about topology (apart from 2D outlines of 2D polygons).

We have a general tessellator, so direct use of glutess shouldn't be necessary.

Perhaps a stand-alon cmd-line tool is a better way of writing this code, but I guess it takes a bit of bootstrapping to get there.

Don't worry about the OGL_helper issue. OGL_helper is just an implementation using the public API of CGAL directly with no magic. Any code doing a similar thing is bound to look very very similar. This is about copyright and only verbatim and blatant copying of larger blocks of code would ever be an issue.

from openscad.

the tessellator is very interesting.. i see two different ones to tessellate DXF, dxftess-glu and dxftess-cgal, one uses GLU and one uses CGAL. which one would you recommend to use here?

sorry about the close/open, i hit the wrong button on accident.

from openscad.

The GLU-based tessellator is not 100% stable, so I'd suggest to go for the CGAL one for now, although it's a lot slower.

Btw., the dxf class should also be refactored eventually. Atm., all 2D data is stored in this class and it should be separated from DXF-specific functionality. It's just like this for historic reasons since 2D data was only available through DXF in the early days.

from openscad.

Thanks for the info.

I can do a square, but for some reason I am getting 'borders' in my resulting Polyset. The existing code does not appear to have 'borders'.

What are the 'borders' and when are they used?

I could also use some documentation about DxfData - how do the path indices work exactly? What is a 'dim'? How do you know which paths are the 'body' of the polygon and which are the 'holes'?

from openscad.

Border is used for 2D polyset to be able to draw a polygon outline, even though the polygon itself has been tessellated into triangles.

DxfData indices: Each polyline (or closed polygon) is a path, consisting of indices into the vertex array (points). The paths also has flags indicating closed polygons or inner paths (holes).

I know that this is not intuitive - it's a reason why I tagged both these classes as prime candidates for refactoring : /
One of the things which are messy is that the same data structure is used for storing data for calculation and for rendering. If we can create a separate data structure for rendering (view model), it would probably simplify this a fair bit.

from openscad.

Thanks again! Very helpful.

Just curious, if you know anything about building a Nef_polyhedron_2?

When I feed it two separate simple polygons (squares), they both have to be 'CounterClockwise', and it works OK.

But when I feed it a square with a circle 'hole' in the middle of the square, it only works if the Square is 'Clockwise' and the "Hole" is CounterClockwise. That seems backwards to me and is making it difficult to write my code.

Do you happen to know of a good place I can look to learn more about this? I think I can probably figure it out with some more debugging, but I thought you might have some ideas?

Thanks.

from openscad.

It's pretty common to describe outlines and holes with opposite vertex ordering.
Unfortunately, I haven't used any Nef_polyhendron_2 building methods apart from the normal one we use (feeding polygons or triangles after a tessellation). CGAL can be pretty non-intuitive.

For such experiments, I try to write the code stand-alone as a small cmd-line tool - it also makes it easier to ask for help from other places.

from openscad.

i think i am pretty close.

old way was this:

intersectin CGAL_Nef_polyhedron3 with another nef3 very-thin box, call 'convert_to_dxfdata()', dxftess, return Polyset

what I do is this:

intersect the Nef_polyhedron_3 with a CGAL::Plane_3, like you coded it.

the result is a Nef_polyhedron_3 that has a bunch of 3d points where z == 0.

iterate through the faces of that Nef_polyhedron_3

pull out the vertexes of the "outline" contours and the "hole" contours

Make a new Nef_polyhedron_2, the main Nef_polyhedron_2

loop through the contours, feedings the x + y points into a temporary Nef_polyhedron_2 constructor

Use 'join()' or 'intersection()' to combine the temporary nef_2 with the main Nef_2 depending on if its a 'hole' or a 'body'

Now take the main nef_2 and put it into an OpenSCAD CGAL_Nef_polyhedron (the .p2 member)

call convertToDxfData()

feed that DXFData to dxf_tesselate()

now we have the PolySet, which gets returned.

my problem right now is im crashing the shared_ptr , hopefully can fix that tongiht

from openscad.

Very nice!
Feel free to point me to a branch if you want me to look at anything.

from openscad.

Thanks for the help. I have it half-working,

  projection(cut=true) translate([0,0,-4.999999]) cube(10, center=true); 

no longer crashes. However. This is giving me a problem:

projection(cut=true) {
cube(4);
translate([-4,-4]) cube(4);
}

In OpenSCAD GIT HEAD, this produces blankness. Emptiness. Nothingness.

In my patch, it creates a square, and a triangle. I narrowed it down to the dxf_tesselate function. I feed it a DXF which is fine, but it poops out three triangles instead of four.

Here is the DXFdata:

DxfData
 num points: 7
 num paths: 2
 num dims: 0
 points: 
  x y: -4 -4
  x y: 0 -4
  x y: 0 0
  x y: -4 0
  x y: 4 0
  x y: 4 4
  x y: 0 4
 paths: 
  path:0
  is_closed: 1
  is_inner: 1
  index[0]==0
  index[1]==3
  index[2]==2
  index[3]==1
  index[4]==0
  path:1
  is_closed: 1
  is_inner: 1
  index[0]==2
  index[1]==6
  index[2]==5
  index[3]==4
  index[4]==2
DxfData end

Here is the PolySet result of feeding to dxf_tesselate:

PolySet:
 dimensions:2
 convexity:0
 num polygons: 3
 num borders: 2
 polygons data:
  polygon begin:
   vertex:4 0 0
   vertex:4 4 0
   vertex:0 4 0
  polygon begin:
   vertex:0 0 0
   vertex:-4 0 0
   vertex:0 -4 0
  polygon begin:
   vertex:-4 0 0
   vertex:-4 -4 0
   vertex:0 -4 0
 borders data:
  border polygon begin:
   vertex:-4 -4 0
   vertex:0 -4 0
   vertex:0 0 0
   vertex:-4 0 0
  border polygon begin:
   vertex:0 0 0
   vertex:4 0 0
   vertex:4 4 0
   vertex:0 4 0
PolySet end

I almost would rather have a blank result than this 'square becomes a triangle' thing. . . I will keep working....

from openscad.

OK, I narrowed it down to the FIXME inside of dxftess-cgal...

My struggle now is to understand point_info_t and Grid2d

What are they? how do they work? I will investigate the source code and try to figure it out...

from openscad.

You might get pretty arbitrary results when intersection exactly on the boundary of an object..
Also, the tessellator isn't too fond of self-intersecting (or self-touching) polygons - that's why you get the error.
try translate([-3.99, -3.99]) instead and it will probably work.

from openscad.

Hm, I have to admit I've tried to avoid dealing with the CGAL tessellation stuff.
I would have to read through the code and de-mystify it myself :/

Grid2d is an optimization for merging vertices that are close to each other. This class tends to cause more problems than it solves, but it used to be essential. It should probably be replaced by a connectivity-away vertex merge class.

from openscad.

Here is my patch as it stands. It does not crash on the bug reported by caliston, above. It produces a rectangle. Which I assume is correct?

As for polygons that share a vertice, well, it shows a warning message, and typically 'loses' one of the triangles when rendering (i.e. a checkerboard might have triangles where 'squares' should be on the edges of the board). It doesn't crash though.

master...caliston1

The inner loop through the half-facet cycles could be much cleaner but they come from my code back when I was trying to avoid copyright violation with regards to GL_helper.h

Also the code could simply go straight from Nef_poly3 into a polyset, but i felt that going through Nef_poly2 first would be more likely to be 'computationally correct', or at least it would reuse the well tested code inside of OpenSCAD without inventing some new gadget that can break.

PS.

The problem here with two squares sharing a vertex is actually not the tessellator inside of PolySetCGALEvaluator.cc, it is somewhere after that. I can actually get good PolySets out of PolySetCGALEvaluator.cc even with squares sharing a single vertex. But that is beyond the scope of this bug so I have abandoned exploring this topic for now.

PPS.

The regression tests 'expected' images do not have a cube, but when I test with my code, I get a cube. Not sure why.

Thank you again for the help and information.

from openscad.

Regarding the regression test. I added the cube (extruded 2D projection) to trigger the bug. The expected files don't have a cube since it hasn't been possible to generate them correctly.
Once you've verified that the cube is correct, you can generate a the expected files with
TEST_GENERATE=1 ctest -R name-of-test

You probably need -C All to get to run the more heavy projection tests.

from openscad.

Hi don,

What's the state on this one - I forgot to follow it up - is the branch stable enough to merge?

from openscad.

my main concern about my code is that i dont understand the 'grid' stuff. i just commented a bunch of it out. the tests passed, but it makes me wonder if the tests were hitting the 'grid' code in the first place.

i never got around to creating the new regression test result either.

sorry, real life has interrupted the openscad work lately.

from openscad.

Hi Marius

I think it is good enough. Here is the latest version of the bug fix. I have simplified the code a bit.

master...caliston1

Please let me know what you think.

(PS, I accidentally pushed the new test-images to Master instead of to the caliston1 branch... sorry about that... no source code was affected other than the testdata .scad file.... let me know if you want me to undo)

from openscad.

Accepted Don's fix. Thanks a lot Don!

from openscad.

thank you for the info on openscad's inner mysteries.

from openscad.