search

azrafe7 / hxGeomAlgo

Small collection of computational geometry algorithms in Haxe.
http://azrafe7.github.io/hxGeomAlgo/index.html
Other
159 stars 13 forks source link

Bug in hxGeomAlgo Tess2 #13

Closed jimbok8 closed 7 years ago

jimbok8 commented 8 years ago

I have discovered a bug in the hxGeomAlgo Tess2 algorithm. This occurs when trying to triangulate a test case that I found on the github site brendankenny/libtess.js

The software demo page is: http://brendankenny.github.io/libtess.js/test/browser/expectations-viewer.html The test case is the "Moar intersections" (I have copied the coordinates below).

I am using a JavaScript test case using hxGeomAlgo.js, The bug occurs at hxGeomAlgo.js:3115 Uncaught TypeError: Cannot read property 'nodeUp' of nullhxGeomAlgo__$Tess2_Sweep.regionAbove @ hxGeomAlgo.js:3115hxGeomAlgo__$Tess2_Sweep.topRightRegion @ hxGeomAlgo.js:3167hxGeomAlgo__$Tess2_Sweep.checkForIntersect @ hxGeomAlgo.js:3390hxGeomAlgo__$Tess2_Sweep.walkDirtyRegions @ hxGeomAlgo.js:3455hxGeomAlgo__$Tess2_Sweep.addRightEdges @ hxGeomAlgo.js:3271hxGeomAlgo__$Tess2_Sweep.sweepEvent @ hxGeomAlgo.js:3573hxGeomAlgo__$Tess2_Sweep.computeInterior @ hxGeomAlgo.js:3692tesselate @ hxGeomAlgo.js:4154hxGeomAlgo_Tess2.tesselate @ hxGeomAlgo.js:2169window.onload @ index.js:110

I have tested the data against tess2.js at memononen/tess2.js and this evaluates the data correctly.

1.000, 0.000, -1.000, 0.000, 0.988, 0.156, -0.988, -0.156, 0.951, 0.309, -0.951, -0.309, 0.891, 0.454, -0.891, -0.454, 0.809, 0.588, -0.809, -0.588, 0.707, 0.707, -0.707, -0.707, 0.588, 0.809, -0.588, -0.809, 0.454, 0.891, -0.454, -0.891, 0.309, 0.951, -0.309, -0.951, 0.156, 0.988, -0.156, -0.988, 0.000, 1.000, -0.000, -1.000, -0.156, 0.988, 0.156, -0.988, -0.309, 0.951, 0.309, -0.951, -0.454, 0.891, 0.454, -0.891, -0.588, 0.809, 0.588, -0.809, -0.707, 0.707, 0.707, -0.707, -0.809, 0.588, 0.809, -0.588, -0.891, 0.454, 0.891, -0.454, -0.951, 0.309, 0.951, -0.309, -0.988, 0.156, 0.988, -0.156

jimbok8 commented 8 years ago

I think I have found the bug in "topRightRegion"

For the JavaScript version: OLD version: hxGeomAlgo__$Tess2_Sweep.topRightRegion = function(reg) { var dst = reg.eUp.get_Dst(); var reg1 = null; do reg1 = hxGeomAlgo__$Tess2_Sweep.regionAbove(reg1); while(reg1.eUp.get_Dst() == dst); return reg1; };

CORRECT version: hxGeomAlgo__$Tess2_Sweep.topRightRegion = function(reg) { var dst = reg.eUp.get_Dst(); do reg = hxGeomAlgo__$Tess2_Sweep.regionAbove(reg); while(reg.eUp.get_Dst() == dst); return reg; };

The OLD version ignored the input 'reg' and operated on the newly defined "reg1", which had been set to "null".

This now works OK in the JavaScript version and also in the Java version that I had previously created from the haxe version (hence the bug will also exist in the haxe version).

Jim

azrafe7 commented 8 years ago

Hey @jimbok8, thanks for the report and the investigation! :smiley:

I'll take a look at it and apply the suggested fix if I can't find anything wrong with it.