delaunayHull: Removing dangling face

[GoogleCodeExporter]

 1) Start Recast Demo. Select Solo Mesh. Select Input Mesh "x.obj". (In attach)
 Parameters by default. Click Build:
http://img.mentalx.org/77539009.jpg

 2) Change Cell Size to 0.31:
http://img.mentalx.org/48100030.jpg
 All correct.

 3) Change Cell Size to 0.32:
http://img.mentalx.org/17588624.jpg
 Warning again.

 4) Change Cell Size back to 0.30 (as by default):
http://img.mentalx.org/26480347.jpg
 No warning. Hmmm.

I got warning in 0.34, 0.35 too.

Original issue reported on code.google.com by execm...@gmail.com on 13 Jun 2011 at 10:10

Attachments:

• x.obj

[GoogleCodeExporter]

I got the warning only for 0.34 in your mesh in a recent version (around r346), 
just for the record.

Original comment by sgraf1...@gmail.com on 29 Oct 2012 at 9:04

[GoogleCodeExporter]

In addition, the triangulation error vanishes when using maxSampleDistance = 
0.0f. It warns about failed triangulations (9 times) though: "buildPolyDetail: 
Could not triangulate polygon, adding default data.". Using no sampleDistance 
resolves the issue for my more complex mesh.

Original comment by sgraf1...@gmail.com on 30 Oct 2012 at 3:34

[GoogleCodeExporter]

I can verify that using maxSampleDistance of 0.0 fixed the bad triangles in my 
test case as well.  I would still very much appreciate it if this issue got 
some attention though...

Original comment by jeff.dic...@digitalextremes.com on 30 Oct 2012 at 3:45

[GoogleCodeExporter]

I've been getting this recently too. I've spent some time looking into it and 
it appears to be because of some invalid edges being created by completeFacet, 
which is called during Delaunay hull construction.

Sometimes polys that have more than 3 points on the circumference of a circle 
accept points without doing the extra edge intersection tests, because of 
numerical imprecision (the calculations for circum circle radius and distance 
have different imprecition).

And sometimes when there are colinear points in the poly, the hull passed in 
has point indices that aren't sorted (this may be valid, I don't know, but it 
seems related), which means that when initialising the circum circle the point 
chosen may already be causing intersecting edges.

The solution then is to always perform the edge intersection tests (after the 
vcross2 check), not just when inside the 'espilon circum circle'. I have a 
suspicion that this will also fail occasionally, again because of imprecision 
in the tests themselves, but this should be much less common than the current 
(still rare) failures.

I've made some changes locally and they fix both x.obj and my other test cases.

Mikko, how would I go about submitting a patch? Shame this isn't on github as 
I'd have done it already ;)

Original comment by B.Hymers on 4 Jan 2013 at 11:36