Raster tool path planner crashes on the closed shapes.

[IKapitaniuk]

I was testing the functionality of the Noether package, to be more precise, the raster tool path planner, on the CAD generated meshes. It seems there are some implicit assumptions that prevent from using the meshes with the closed surfaces; at least, I haven't found that they are somehow mentioned.
For instance, when I import an ordinary box mesh, the algorithms of getting the average norm is failed:

...
avg_norm[0] += norm[0]*area;
avg_norm[1] += norm[1]*area;
avg_norm[2] += norm[2]*area;
avg_area += area;
...
avg_norm[0] /= avg_area;
avg_norm[1] /= avg_area;
avg_norm[2] /= avg_area;
...

This way of weighting always gives the zero normal vector for the mesh with the closed surface. It is a well-known fact. Of course, it is not a problem when the mesh is generated by the 3D scanning of the object located on the table since the mesh model wouldn't have the bottom so that the averaged normal vector will be well defined, but it is a real problem for the CAD models which has a volume.
Another problem I have encountered regarding the volume of a CAD model is that the vtkIntersectionPolyDataFilter returns all points of intersection, above and below the surface with the non-zero thickness when usually I need just the upper one. It messes up the following steps of the cutting and offsetting. Because of this, It seems that there is an implicit assumption that the mesh surface has to have only one side. And again, it holds for 3D scans, but not a case for CAD models.

My question is, does the Noether package suppose to work with the CAD models? If so, what exactly the restrictions/assumptions on the mesh model?

[gavanderhoorn]

@Levi-Armstrong @jrgnicho @marip8: we ran into these issues while trying to setup a cad -> noether -> tesseract/trajopt pipeline.

IIRC, you've done something similar, so running into these problems surprised us.

Are there any assumptions/conventions in Noether which we're not aware of/adhering to?

[mpowelson]

In my experience we usually split up the mesh into surfaces prior to raster planning. This could be done using the mesh segmentation code in noether, PCL, or some other method. That said, I do know that @drchrislewis is working on a new raster method that works on closed surfaces, but I'm not sure if it is open source.

It's based on this this project I believe.

[drchrislewis]

@gavanderhoorn I am working on an alternate method for raster generation. It will become open source. It is based on the heat method for computing distances over surfaces. I hope to be done soon. My best guess is two weeks, but other responsibilities may inhibit my progress. The distance computations are very reliable. However, converting lists of vertices within a constant distance from the start-curve to a set of raster strokes is non-trivial. Bifurcations occur on complex objects.

[gavanderhoorn]

Thanks @mpowelson and @drchrislewis.

From what you write it appears there is an (implicit?) assumption that meshes passed to Noether's planning pipeline are not closed, but actual surfaces.

In hind-sight, that would make sense (seeing as it's a library used mostly for planning raster paths across surfaces), but apparently we didn't take this into account.

@drchrislewis: the heat distribution approach sounds like a nice improvement. Will it be added to Noether, or a stand-alone package? It's the same method @Levi-Armstrong has mentioned a few times (at ROSCon and other (virtual) meetups), correct?

[Levi-Armstrong]

The heat method @drchrislewis is describing the one I have been presenting on. Also there is a PR by @jrgnicho which adds a plan slicer which should work on closed surface but I do not know for sure.

[drchrislewis]

@gavanderhoorn Yes, I'm sure Levi has mentioned the heat method. Noether has always had issues with closed surfaces. Segmentation takes a very long time, and is finicky. The heat method will have a very similar interface as Noether. It will either be another package in Noether or stand alone. It has much different dependencies. It uses suitesparse and lapack, but not vtk or pcl. Right now it is stand alone. Noether provides a more standard parallel cutting plane implementation for raster path generation on surfaces and an edge path generator. I have no intention to add edge path generation to the heat method, so it might be nice to have a repo does it all tool path planning library.

[gavanderhoorn]

Stand-alone package + repository sounds fine to me. I was just curious as to what the plan was.

[gavanderhoorn]

Talking to @IKapitaniuk it seems perhaps #21 also bit us.

[IKapitaniuk]

Ok, thanks. Looking forward to testing the new package.
In that case, the only issue is not very obvious crashing due-to the way of calculating of weighted average. I will rename the current issue accordingly.

Of course, nothing can help in the case of a perfectly symmetric object such as a box, a sphere, or a cylinder since normal vectors from either side will eliminate each other.
A bit more tricky part that that algorithm fails for any closed surface.
The problem is that VTK stores inside the structure the normalized vectors. Analytically it can be written as
normal = Cross(v1,v2)/(2area),
where v1 and v2 are two edges and the corresponding area of the triangular polygon.
The current way of averaging can be written as follows:
SumOf(normalS) = 0.5* SumOf(Cross(v1,v2)).
Exactly this summation of the cross products gives us the zero vector for a closed surface. As a possible solution, I would suggest, for instance, using the squared value of a polygon area, i.e. avg_norm[0] += norm[0]areaarea;
In that case we can get the average normals as 0.5* SumOf(Cross(v1,v2)*area) what is a well-defined vector for non-symmetric objects.

Or, just change nothing, but add the proper exception handling to avoid simple crashing if the package is just not supposed to work with the closed surfaces.