CGAL users discussion list

[Thorben Kröger <>]

On Tuesday 13 October 2009 07:24:30 Marc Pouget wrote:
> Please give us more details about your expectations and experiments
> if you want some feedback

OK, bear with me then :-)

I want to estimate normals on digital surfaces obtained from a segmentation. 
In our case, the digital surfaces are comprised of the surface-elements of 
voxels, so the surfaces lie in-between the voxels. They are not sub-pixel 
accurate by definition and thus typical stair-like artefacts are obvious.

Initial tests based on the Jet_fitting_3 example code for a polyhedral mesh 
did not result in any good estimates even for large (32 vertices) 
neighborhoods; the normal orientation varied a lot from vertex to 
neighbouring 
vertex even for quite smooth parts of my surface.

Therefore, I tested everything on a simple testcase, two plots of which are 
attached to this mail:

On the plot "snapshot_plane.png" you see onto the side of a sampled plane, 
which has the typical stair artefacts. A 3D view is in "snapshot_plane_2.png"

I hand crafted code to triangulate this plane to exclude any possible errors 
in wrong triangulations, then fed the vertices and edges to a 
CGAL::Polyhedron_incremental_builder_3 to build the polyhedron.

I based my code on the cgal jet fitting example "Mesh_estimation.cpp".

I randomly chose one vertex and put debug code into the 
Monge_via_jet_fitting.h header to output the list of vertices considered. 
These are drawn as blue '*' symbols around the vertex. This looks all ok.

Next, I examined the ouput of the monge fit for the chosen vertex. The 
results 
are the colored arrows which originate in the chosen vertex.

- the green arrow represents the TRUE normal of the plane as constructed
- the deep red arrow is the estimated normal using the vertex plus the 
  surrounding blue '*' points with the complete CGAL jet-fitting method
- the pink arrows are the maximal and minimal principal direction as given
  by the monge fit procedure. You can see that they are off.
- the orange arrows look very much ok, and the orange normal is completely 
  correct (the sign doesn't matter of course):
  These are just the eigenvectors obtained from the PCA analysis in the
  code, the polynomial fitting results are _not_ considered

How can it be that I arrived at this result? At the moment I am suspecting a  
bug in CGAL, but of course I cannot exclude a bug or thinking error on my 
part; are there any requirements I might have disregarded? Any definitions of 
angles etc. I might have used in the wrong way?

I'll be happy to send code along and try to reduce it to a more minimal 
testcase if necessary; at the moment I pass data for visualization purposes 
to 
Matlab, so the code is run as a Matlab Mex file, therefor it's a bit "messy" 
to debug for anyone not using Matlab.

Thanks for your time,

Thorben

Attachment: snapshot_plane.png
Description: PNG image

Attachment: snapshot_plane_2.png
Description: PNG image