NullPointerException in SweepLine

Posts regarding potential bugs, enhancement requests, and general feedback on use of dyn4j
zoom
Posts: 143
Joined: Sun Mar 17, 2013 3:57 pm
Location: Stockholm, Sweden
Contact:

NullPointerException in SweepLine

Postby zoom » Sun Dec 29, 2013 10:18 am

Sorry to spam the forums with multiple posts every time I dig into a new topic :oops:
I just ran into a null pointer exception in SweepLine#decompose.

at org.dyn4j.geometry.decompose.SweepLine.end(SweepLine.java:619)
at org.dyn4j.geometry.decompose.SweepLine.decompose(SweepLine.java:367)

I Guess vertex.right is null in the lines above this one:
https://code.google.com/p/dyn4j/source/ ... e.java#619

I haven't analyzed the data yet too see if there is some obvious mistake but here is the data I sent in:

Code: Select all

<71.82635498046875, 9.041028851841528>
 <71.96970245420596, 9.065084876518275>
 <72.84698496066702, 8.535128282291913>
 <72.85212905478721, 8.457094723203058>
 <75.51513682772148, 9.128348037567196>
 <76.70296532421452, 8.916850486978241>
 <77.19770569589713, 7.839325490691246>
 <76.46878594640248, 6.889293757782514>
 <72.87897848026506, 4.323094016359528>
 <73.03435152895737, 3.7155890257581383>
 <72.28207788606544, 2.9392849608061224>
 <71.82635498046875, 2.5678077743236867>
 <71.82635498046875, 2.327088393206619>
 <79.83867079209722, 9.051105711660203>
 <80.77425982846728, 8.60682542580367>
 <80.98318680154084, 7.578596633204889>
 <80.2861980012057, 4.982484879650631>
 <80.78947337898077, 4.9093922310236735>
 <81.17545575666367, 3.7803067422699828>
 <80.88830898145511, 0.7191905975341796>
 <83.86756474767769, 0.7191905975341798>
 <83.3037228572522, 3.4814833294392136>
 <83.22650414981284, 4.317255138051698>
 <83.85131080342165, 4.86468204040777>
 <84.6027957656383, 4.522519719761086>
 <86.30689112630213, 0.7191905975341797>
 <86.5126675216799, 0.7191905975341798>
 <83.38454864794507, 7.394201805656439>
 <83.1420168018937, 8.23834702740324>
 <83.76439112030559, 8.912651005533197>
 <84.61727129539887, 8.607441584597902>
 <90.77911618627967, 3.9450768276991264>
 <90.68350119873307, 4.186463422920709>
 <91.27661927304128, 4.893971888314738>
 <87.96678925945295, 6.9341776563845565>
 <87.063201992979, 7.494961973012931>
 <87.11877116838001, 8.545605841410751>
 <88.0375809687112, 9.090192593778918>
 <90.86590428326572, 8.348417452751162>
 <91.47713545841357, 9.133472470193109>
 <91.82635498046876, 9.121498206691484>
 <91.82635498046875, 10.874356739163366>
 <88.24220267307402, 10.81874283070839>
 <87.09631542746817, 11.230030782501522>
 <87.04442081666514, 11.493439722546299>
 <83.79384784722082, 11.0111243673198>
 <83.00124533525602, 11.679728579402237>
 <83.27803227672017, 12.669011445848815>
 <87.96270653524759, 18.961233250534043>
 <87.38910642299808, 19.046162528869065>
 <87.34845701745272, 19.113846687691975>
 <85.0528358856582, 15.624061496174741>
 <84.18031160855162, 14.961954221955967>
 <83.13059795574226, 15.245499974453281>
 <82.98295614572393, 16.322653086529236>
 <83.61481093483974, 19.383841952373963>
 <83.50431054838108, 19.412011233040054>
 <83.2461827904734, 20.134944673016733>
 <83.33428286242321, 20.71919059753418>
 <81.26695660158973, 20.719190597534183>
 <81.3254918038506, 19.672794961240943>
 <80.52308528217246, 18.897947111809234>
 <80.93042306619374, 16.341671492933468>
 <80.78517075508344, 15.343200570529769>
 <79.8612938938059, 15.032950367786151>
 <79.14041304036952, 15.619239996575383>
 <77.03927635833409, 19.45241054371343>
 <76.53289520480828, 18.99554850226785>
 <80.80971693242398, 12.308710628247649>
 <80.69335781522103, 11.439475329103534>
 <79.88071697360861, 11.153564647488462>
 <77.069238864496, 11.781242112827389>
 <76.51712027105569, 10.926269915496224>
 <72.59036653008536, 11.079427485464521>
 <72.55768655732842, 11.022371552157944>
 <71.82635498046875, 11.039997430350738>

William
Site Admin
Posts: 351
Joined: Sat Feb 06, 2010 10:23 pm

Re: NullPointerException in SweepLine

Postby William » Mon Dec 30, 2013 8:08 am

No worries, I'm not a forum Nazi.

I'll try to take a look at it some time today hopefully. In the meantime try EarClipping or Bayazit and see if those fail as well. I suspect that Bayazit won't but EarClipping may since it uses the same DCEL acceleration structure.

William

William
Site Admin
Posts: 351
Joined: Sat Feb 06, 2010 10:23 pm

Re: NullPointerException in SweepLine

Postby William » Mon Dec 30, 2013 8:16 am

I added a issue to google code to help track this.

William
Site Admin
Posts: 351
Joined: Sat Feb 06, 2010 10:23 pm

Re: NullPointerException in SweepLine

Postby William » Sun Jan 05, 2014 4:16 pm

Surprisingly, EarClipping was working, but Bayazit was not. I have fixed SweepLine NPE and added the Triangulator interface that both EarClipping and SweepLine implement. If you would test these out and let me know if your issue is fixed and the triangulations are what you are looking for. By default all polygons that come out of the decompose/triangulation methods are CCW winding since that's what dyn4j requires.

As far as triangulation is concerned, I was thinking an alternative might have been to use the Tessellator on the GPU. This isn't an option if you are using standard Java2D, but thought I might bring it up. Either way it was easy to add since both EarClipping and SweepLine perform a triangulation first anyway.

Bayazit is still broken however. It's due to it selecting a non-visible vertex for one of the operations. Fixing this may take some time, so I wanted to get this beta version out while I try to come up with a solution to this.

William
Attachments
dyn4j-v3.1.9-beta.jar
dyn4j 3.1.9 Beta
(346.15 KiB) Downloaded 136 times

zoom
Posts: 143
Joined: Sun Mar 17, 2013 3:57 pm
Location: Stockholm, Sweden
Contact:

Re: NullPointerException in SweepLine

Postby zoom » Sun Jan 05, 2014 6:28 pm

William wrote:Surprisingly, EarClipping was working, but Bayazit was not. I have fixed SweepLine NPE and added the Triangulator interface that both EarClipping and SweepLine implement. If you would test these out and let me know if your issue is fixed and the triangulations are what you are looking for. By default all polygons that come out of the decompose/triangulation methods are CCW winding since that's what dyn4j requires.


Apart from the NPEs I had a suspicion that SweepLine would also end up in endless loops sometimes, I had a hard time catching those and getting the data out. Due to the NPEs I switched to EarClipping which is plenty fast enough for my use case and haven't had problems with either NPEs or hangs since.

So right now I chucked the 3.1.9-beta at my application, switched to SweepLine and ran it for a while, after several attempts I finally got that hang and even better, managed to make a test case that reproduces it. The test case shows SweepLine running forever but EarClipping works.

Code: Select all

package nu.zoom.corridors.client.render;

import java.util.List;
import org.dyn4j.geometry.Convex;
import org.dyn4j.geometry.Vector2;
import org.dyn4j.geometry.decompose.Decomposer;
import org.dyn4j.geometry.decompose.EarClipping;
import org.dyn4j.geometry.decompose.SweepLine;
import org.junit.Assert;
import org.junit.Test;

public class DecomposeTest {

   private final Vector2[] testData1 = {
      new Vector2(-1277.0235595703125, 2115.5494863831605),
      new Vector2(-1277.0235595703125, 2104.7347184264263),
      new Vector2(-1275.9042506727417, 2104.9923997669994),
      new Vector2(-1275.0902048765192, 2104.4184586587235),
      new Vector2(-1275.0919618993644, 2104.397177851862),
      new Vector2(-1272.0396789765905, 2105.395773656894),
      new Vector2(-1270.919938932065, 2104.6997011576755),
      new Vector2(-1270.7851988833552, 2103.4116306505825),
      new Vector2(-1277.0235595703125, 2097.399485671647),
      new Vector2(-1277.0235595703125, 2097.036865234375),
      new Vector2(-1276.3566396807325, 2097.036865234375),
      new Vector2(-1272.4606031383762, 2101.211303357978),
      new Vector2(-1271.2404324747924, 2100.9421943370676),
      new Vector2(-1271.121489888675, 2100.674432798434),
      new Vector2(-1268.4313933731482, 2104.8510673423434),
      new Vector2(-1267.4775277154338, 2104.8279203234692),
      new Vector2(-1267.1025975327843, 2103.9830931406045),
      new Vector2(-1267.196497442808, 2100.3551033003528),
      new Vector2(-1267.0567977244593, 2100.216378116663),
      new Vector2(-1267.0722923859769, 2097.036865234375),
      new Vector2(-1264.3305615496781, 2097.036865234375),
      new Vector2(-1265.164023254697, 2100.1317865772003),
      new Vector2(-1264.4593321899172, 2101.0299010348062),
      new Vector2(-1263.3423234002275, 2100.9112637865464),
      new Vector2(-1261.0139681833493, 2097.036865234375),
      new Vector2(-1260.155258040146, 2097.036865234375),
      new Vector2(-1260.1132564042903, 2097.070149860997),
      new Vector2(-1260.0784382360916, 2097.055214633385),
      new Vector2(-1264.3823094415916, 2103.240814068967),
      new Vector2(-1264.8179755468534, 2103.951606041049),
      new Vector2(-1264.423427336613, 2104.649256150598),
      new Vector2(-1263.611493393691, 2104.7536751919415),
      new Vector2(-1257.0235595703125, 2100.3453477659245),
      new Vector2(-1257.0235595703125, 2100.791334885779),
      new Vector2(-1261.0127270059204, 2103.2827815142577),
      new Vector2(-1261.1866054361687, 2104.5562838984993),
      new Vector2(-1260.0907623519245, 2105.2310703229477),
      new Vector2(-1257.210127124702, 2104.4807474343443),
      new Vector2(-1257.0235595703125, 2104.6233023390796),
      new Vector2(-1257.0235595703125, 2116.130512231795),
      new Vector2(-1257.0382388073358, 2116.1683622698247),
      new Vector2(-1257.0235595703125, 2116.1854266637147),
      new Vector2(-1257.0235595703125, 2117.036865234375),
      new Vector2(-1257.7017407774574, 2117.036865234375),
      new Vector2(-1259.0670750168492, 2115.5722001623126),
      new Vector2(-1259.9205966107684, 2114.958694112713),
      new Vector2(-1260.8924517200146, 2115.377702224576),
      new Vector2(-1260.9591177897469, 2116.4201115241613),
      new Vector2(-1260.5605065998677, 2117.036865234375),
      new Vector2(-1262.2842672142572, 2117.036865234375),
      new Vector2(-1262.9432837248928, 2115.6463274470466),
      new Vector2(-1263.781054621851, 2114.9052176289674),
      new Vector2(-1264.8433202920128, 2115.2561760313015),
      new Vector2(-1265.0219567395015, 2116.337910946029),
      new Vector2(-1264.8715404394798, 2117.036865234375),
      new Vector2(-1266.6354254200173, 2117.036865234375),
      new Vector2(-1266.6654098158608, 2116.2643386268333),
      new Vector2(-1267.1173913778273, 2115.0020996385542),
      new Vector2(-1268.4145244856422, 2114.74846069912),
      new Vector2(-1269.3009067795608, 2115.7339112569475),
      new Vector2(-1269.6420891300347, 2117.036865234375),
      new Vector2(-1271.3618181810775, 2117.036865234375),
      new Vector2(-1271.0146167538264, 2116.2365408221863),
      new Vector2(-1271.345956767621, 2115.319392963282),
      new Vector2(-1272.271969702898, 2115.071845644556),
      new Vector2(-1272.9654404385574, 2115.7743850564493),
      new Vector2(-1273.8239800434415, 2117.036865234375),
      new Vector2(-1275.5802581239361, 2117.036865234375),
      new Vector2(-1275.1513964240917, 2116.535665271379),
      new Vector2(-1275.076942131551, 2115.488317486968),
      new Vector2(-1276.0204986768335, 2114.9428753317557),
      new Vector2(-1276.956086281257, 2115.4920489284323)
   };


   @Test(timeout=5000)
   public void testEndlessLoopEarClipping() {
      Decomposer decomposer = new EarClipping();
      List<Convex> result = decomposer.decompose(testData1);
      Assert.assertNotNull(result);
   }
   
   @Test(timeout=5000)
   public void testEndlessLoopSweepLine() {
      Decomposer decomposer = new SweepLine();
      List<Convex> result = decomposer.decompose(testData1);
      Assert.assertNotNull(result);
   }
}



William wrote:As far as triangulation is concerned, I was thinking an alternative might have been to use the Tessellator on the GPU. This isn't an option if you are using standard Java2D, but thought I might bring it up. Either way it was easy to add since both EarClipping and SweepLine perform a triangulation first anyway.


That is for sure on my todo-list, the whole point of this little game is actually so that I can learn modern day OpenGL, I'm slowly catching up so I hope to get to the tesselator shaders eventually. But since dyn4j already had decomposers and they even produced triangles along the way it was a quicker way for me to get up and running :)

William wrote:Bayazit is still broken however. It's due to it selecting a non-visible vertex for one of the operations. Fixing this may take some time, so I wanted to get this beta version out while I try to come up with a solution to this.


I'll use the beta and adapt my renderer to triangles. If nothing else I can switch back to 3.1.8 and EarClipping-convexes, they work beautifully. I must say, dyn4j is a treasure chest of good stuff :)

William
Site Admin
Posts: 351
Joined: Sat Feb 06, 2010 10:23 pm

Re: NullPointerException in SweepLine

Postby William » Mon Jan 06, 2014 6:44 am

Thank you for the test case. I created an issue on the google code page to track it.

I've already tracked down the problem and have a good idea of what needs to be done now. It should be a quick fix.

EarClipping should be fast enough as well (n^2 in the worst case). The great thing is that you can easily swap the algorithms in and out since they have the same interface if it becomes an issue.

William

William
Site Admin
Posts: 351
Joined: Sat Feb 06, 2010 10:23 pm

Re: NullPointerException in SweepLine

Postby William » Mon Jan 06, 2014 8:21 pm

Again, thanks for this test case, it was very useful. I believe I have fixed the problem of infinite looping in the SweepLine class and would like you to test it when you get a chance.

William
Attachments
dyn4j-v3.1.9-beta2.jar
dyn4j-3.1.9-beta2
(346.4 KiB) Downloaded 139 times

zoom
Posts: 143
Joined: Sun Mar 17, 2013 3:57 pm
Location: Stockholm, Sweden
Contact:

Re: NullPointerException in SweepLine

Postby zoom » Sat Jan 11, 2014 4:32 am

I found another poly that (3.1.9-beta2) SweepLine gets stuck on. Earclipping has no problem.

Code: Select all

private final Vector2[] testData2 = {
      new Vector2(169.1416032719501, 43.554870831590996),
      new Vector2(165.12038421579865, 39.94712327598281),
      new Vector2(165.01733949336142, 39.280052684215526),
      new Vector2(160.00098891796975, 34.18185043334961),
      new Vector2(161.48793243106027, 34.1818504333496),
      new Vector2(163.13232251250386, 36.150588917809294),
      new Vector2(163.7112768646376, 36.783683268472004),
      new Vector2(164.42836853405993, 36.68192266760234),
      new Vector2(167.09865641928596, 40.382348772692225),
      new Vector2(167.877643677884, 41.01692408350048),
      new Vector2(168.82665933889518, 40.61677932024483),
      new Vector2(168.9715427481903, 39.58242636067556),
      new Vector2(168.43168622248103, 36.72474393395388),
      new Vector2(168.65095787123087, 36.67214754264457),
      new Vector2(168.99268888243853, 35.74550576849868),
      new Vector2(168.8355605524554, 34.18185043334962),
      new Vector2(171.501148545648, 34.18185043334962),
      new Vector2(171.18692272466407, 36.07396812520156),
      new Vector2(171.6663957224415, 36.705909094304104),
      new Vector2(172.23425546760217, 36.689804384142775),
      new Vector2(171.354817943026, 39.44222341373178),
      new Vector2(171.13491081989812, 40.30521515633293),
      new Vector2(171.8396738199488, 40.85878016311799),
      new Vector2(172.66080707357645, 40.572243439877425),
      new Vector2(175.69681138318617, 36.68665776759129),
      new Vector2(176.06456106870652, 36.87010429737165),
      new Vector2(176.77872459259143, 36.36827415361618),
      new Vector2(178.7202212899152, 34.18185043334961),
      new Vector2(179.84043884277344, 34.18185043334961),
      new Vector2(179.84043884277347, 34.43223689288292),
      new Vector2(174.96608411846668, 39.184544374996804),
      new Vector2(174.93645703749942, 39.67392974799891),
      new Vector2(171.08512994569588, 43.08080083828676),
      new Vector2(170.71342438165473, 44.32401531947587),
      new Vector2(171.61295511776754, 45.26368047534241),
      new Vector2(175.2664832777762, 47.493559308346136),
      new Vector2(174.9779029618782, 48.059648366847604),
      new Vector2(175.5272104059404, 48.93582543773451),
      new Vector2(178.87327978240245, 51.73304174965181),
      new Vector2(178.68040387924196, 52.17831785073633),
      new Vector2(179.53449258722782, 53.11891766928541),
      new Vector2(179.84043884277344, 53.40097328074292),
      new Vector2(179.84043884277344, 54.18185043334961),
      new Vector2(179.57699342630002, 54.18185043334961),
      new Vector2(176.75222737873577, 51.280653687281415),
      new Vector2(176.4436696887102, 51.215990147831555),
      new Vector2(172.46467797606184, 46.97734026831735),
      new Vector2(171.36087667224368, 47.16805865165288),
      new Vector2(170.84100303227967, 48.19415156431357),
      new Vector2(171.51704898158212, 50.90512199021725),
      new Vector2(170.94596501222244, 51.11415465907416),
      new Vector2(170.8125343544852, 52.42568794856254),
      new Vector2(171.01961724108352, 54.18185043334961),
      new Vector2(168.87875538035456, 54.18185043334962),
      new Vector2(169.0935156956158, 51.94867991879095),
      new Vector2(168.50399043578798, 50.992976571593864),
      new Vector2(168.3082255092885, 51.0075765591254),
      new Vector2(169.01568260099765, 47.855986471626714),
      new Vector2(168.39308005351188, 47.01292011188349),
      new Vector2(167.34000755748798, 47.15809403002359),
      new Vector2(164.2812685612533, 50.79888688244585),
      new Vector2(164.26710967028285, 50.78620518070249),
      new Vector2(163.08367801584484, 51.15166104897637),
      new Vector2(160.14611399013035, 54.18185043334961),
      new Vector2(159.84043884277344, 54.18185043334961),
      new Vector2(159.84043884277344, 53.50912176985284),
      new Vector2(160.8165019345809, 52.59872123996942),
      new Vector2(160.83172513819702, 52.440438908747105),
      new Vector2(164.82520143245554, 48.77948592677119),
      new Vector2(165.1064657409055, 47.66949675430108),
      new Vector2(165.01464331153534, 47.57856114285639),
      new Vector2(168.9697373369313, 44.79470713449518)};

William
Site Admin
Posts: 351
Joined: Sat Feb 06, 2010 10:23 pm

Re: NullPointerException in SweepLine

Postby William » Sat Jan 11, 2014 4:23 pm

Great, thanks for taking the time to test this for me. I believe I've tracked this problem down as well. Give the attached jar a try.

William
Attachments
dyn4j-v3.1.9-beta3.jar
dyn4j v3.1.9 beta 3
(346.35 KiB) Downloaded 137 times

zoom
Posts: 143
Joined: Sun Mar 17, 2013 3:57 pm
Location: Stockholm, Sweden
Contact:

Re: NullPointerException in SweepLine

Postby zoom » Sat Jan 11, 2014 6:17 pm

Yeah, sorry ;) This causes a NPE in SweepLine
Edit: For clarification, on beta3.

Code: Select all

   private final Vector2[] testData3 = {
      new Vector2(101.00555850575881, -8.251811893308789),
      new Vector2(100.26689781146466, -9.083823411432645),
      new Vector2(96.94821588376446, -11.7055706436662),
      new Vector2(97.14952437828954, -12.041382313936344),
      new Vector2(96.52805491285025, -12.966682720529612),
      new Vector2(92.86044240545272, -16.544219644251775),
      new Vector2(92.62732662151383, -16.931942034302477),
      new Vector2(91.53866577148438, -18.01345273498935),
      new Vector2(91.53866577148438, -18.079132080078125),
      new Vector2(92.40367025335983, -18.079132080078125),
      new Vector2(95.1075406705432, -15.119228411072653),
      new Vector2(96.29337173062352, -14.821083718530657),
      new Vector2(96.82943814094435, -15.310192588474651),
      new Vector2(99.10851323195877, -11.81065224922159),
      new Vector2(99.74473211542617, -11.074757051175819),
      new Vector2(100.65687383363243, -11.330171298416978),
      new Vector2(100.92891534358786, -12.190471029630817),
      new Vector2(100.50218747333787, -15.06775202938379),
      new Vector2(100.69363967530582, -15.08461196434083),
      new Vector2(101.21003061852332, -16.1673853555485),
      new Vector2(101.1323541311826, -18.079132080078125),
      new Vector2(103.20993706272863, -18.07913208007813),
      new Vector2(102.94507216619829, -16.49432102529932),
      new Vector2(103.04388583755971, -15.36280421094929),
      new Vector2(103.93577876573967, -14.946584251559814),
      new Vector2(103.20645455938963, -12.857154252993347),
      new Vector2(102.89939278809051, -11.741962073613996),
      new Vector2(103.66161937112157, -10.84108458375145),
      new Vector2(104.87513085909818, -11.088289159509706),
      new Vector2(111.32623838511132, -16.906543367053665),
      new Vector2(110.8454311296485, -15.9207398306675),
      new Vector2(111.05276202842644, -15.637280653284162),
      new Vector2(107.38384429574796, -12.722633998834645),
      new Vector2(107.07030639733776, -11.776062029625038),
      new Vector2(107.71623447180899, -11.00329137161576),
      new Vector2(108.65646228217794, -11.272057410727214),
      new Vector2(111.17054986040327, -12.399835691203007),
      new Vector2(111.09838606732836, -11.742250652166543),
      new Vector2(103.68524333129122, -8.901662532088451),
      new Vector2(103.0613351230734, -8.159367109962448),
      new Vector2(103.3601620920359, -7.229913263901768),
      new Vector2(111.53866577148438, -3.416931961242139),
      new Vector2(111.53866577148438, 1.9208688735961914),
      new Vector2(91.73666130083187, 1.9208688735961912),
      new Vector2(100.71722976355093, -7.24110252685272)
   } ;


Return to “Bugs, Enhancements, Feedback”

Who is online

Users browsing this forum: Bing [Bot] and 1 guest