[osg-users] Delaunay triangulation bug
Dear OpenSceneGraph users, while using the Delaunay triangulation library, I found some cases where the triangles generated were intersecting other triangles, which is normally impossible in a Delaunay triangulation. The bug can be reproduced with the following set of points: x y-4542397 -132298,38-4542394,5 -132297,86 -4542393 -132297,75-4542391,5 -132297,91-4542390 -132298,31 -4542389 -132298,67-4542387,5 -132299,27 By entering the code in debug, I think the problem might come from the circumcircle center computation algorithm. Moreover, the use of float may not be sufficient in this case since the x values are quite far from 0, consequently the distance computations executed to know if a point is inside the circumcircle or not may be wrong. Using doubles instead of floats is obviously not a correct solution but it may solve the bug. What is your opinion on that bug? What is the best way to solve this issue? Thank you for your attention. Regards, Patrice GONZALEZ___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
Re: [osg-users] Delaunay triangulation bug
Hi You just rolling over limits of single precision float capabilities with this input. There are rounding on Y values up to 0.02 just if you convert those to float. Add there some arithmetic operations on such values and error will grow an order or two, you get the point. Cheers. 07.09.2012, 17:28, "Patrice Gonzalez" patrice.gonza...@cgxaero.com:Dear OpenSceneGraph users,while using the Delaunay triangulation library, I found some cases where the triangles generated were intersecting other triangles, which is normally impossible in a Delaunay triangulation. The bug can be reproduced with the following set of points: x y-4542397-132298,38-4542394,5-132297,86-4542393-132297,75-4542391,5-132297,91-4542390-132298,31-4542389-132298,67-4542387,5-132299,27By entering the code in debug, I think the problem might come from the circumcircle center computation algorithm. Moreover, the use of float may not be sufficient in this case since the x values are quite far from 0, consequently the distance computations executed to know if a point is inside the circumcircle or not may be wrong. Using doubles instead of floats is obviously not a correct solution but it may solve the bug.What is your opinion on that bug? What is the best way to solve this issue?Thank you for your attention.Regards,Patrice GONZALEZ,___osg-users mailing listosg-users@lists.openscenegraph.orghttp://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
Re: [osg-users] Delaunay triangulation bug
Hi, ok thank you for the answer. However, is there a simple way to compile OpenSceneGraph with double values instead of float? Cheers Sergey Polischuk pol...@yandex.ru wrote:Hi You just rolling over limits of single precision float capabilities with this input. There are rounding on Y values up to 0.02 just if you convert those to float. Add there some arithmetic operations on such values and error will grow an order or two, you get the point. Cheers. 07.09.2012, 17:28, Patrice Gonzalez patrice.gonza...@cgxaero.com:Dear OpenSceneGraph users, while using the Delaunay triangulation library, I found some cases where the triangles generated were intersecting other triangles, which is normally impossible in a Delaunay triangulation. The bug can be reproduced with the following set of points: x y-4542397-132298,38-4542394,5-132297,86-4542393-132297,75-4542391,5-132297,91-4542390-132298,31-4542389-132298,67-4542387,5-132299,27 By entering the code in debug, I think the problem might come from the circumcircle center computation algorithm. Moreover, the use of float may not be sufficient in this case since the x values are quite far from 0, consequently the distance computations executed to know if a point is inside the circumcircle or not may be wrong. Using doubles instead of floats is obviously not a correct solution but it may solve the bug. What is your opinion on that bug? What is the best way to solve this issue? Thank you for your attention. Regards, Patrice GONZALEZ, ___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
Re: [osg-users] Delaunay triangulation bug
Hi Patrice, On 7 September 2012 16:01, Patrice Gonzalez patrice.gonza...@cgxaero.comwrote: ok thank you for the answer. However, is there a simple way to compile OpenSceneGraph with double values instead of float? By default the OSG chooses double over float in places where it's configurable such as for the default Matrix and Plane classes as these are all critical for handling models with large model scales. The DelaunayTriangulator is configurable right now though. One could add support for it work in doubles internally but this won't solve all the precision problems though, the right way to solve it is the use robust predicate maths for the incircle and orientation test rather than rely on fix precision maths. To read up on this have a look at: http://www.cs.cmu.edu/~quake/robust.html Robert. ___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
