Tuesday, July 18, 2006

Still working on skeleton random bugs. The latest seems to be that something is having trouble outputtting the following coords.

this sheet's coords {0.0,0.24464974069081158}
this sheet's coords {3.0070841037895164,13.538877338152522}
this sheet's coords {3.007084103789568,13.538877338152654}
this sheet's coords {3.0070841037895804,13.538877338152666}
this sheet's coords {3.0070841037896,13.538877338152648}
this sheet's coords {3.0070841037896088,13.538877338152634}
this sheet's coords {3.007084103789639,13.538877338152457}
this sheet's coords {3.7687341944905004,0.0}


This is the centre of multi-sided regular shape (circle with edges...) and shouldn't be that hard to tesselate. Implementing a fit that noticess that all the points are the same to the 12 or 13 dp may be an option. Theres a thought - the chances are that this no longer a simple polygon due to the rounding errors we've seen. Soln then is to examine each point as it is added to the sheetbuilder and if its within 10E-10 of the last one, not to add it.

Apart from a huge memory leak (I've asked Ian for help finding that one) I'm fairly happy with this sofar. However I tried running a profiling tool on the code, and it turns out that the vast majority of the run time is spent trying to find which cell a point lies in at the start of the voronoi routine:


TRACE 300245:
geom.Vec2d.pointIn(Vec2d.java:104)
cloud.Lightning.setup(Lightning.java:80)
cloud.Lightning.(Lightning.java:25)
ssbd.FREEZER_CityPlanner.doFreeze(FREEZER_CityPlanner.java:62)
ssbd.FREEZER.freeze(FREEZER.java:99)
ssbd.FREEZER.freezeThis(FREEZER.java:147)
ssbd.FREEZER_Root.doFreeze(FREEZER_Root.java:49)
ssbd.FREEZER_Root.bigFreeze(FREEZER_Root.java:60)
ssbd.FREEZER_Root.bigFreeze(FREEZER_Root.java:66)
sity.testRun.testSpeed(testRun.java:20)
TRACE 300343:
geom.FlatPoint.(FlatPoint.java:26)
geom.Vec2d.pointIn(Vec2d.java:104)
cloud.Lightning.setup(Lightning.java:80)
cloud.Lightning.(Lightning.java:25)
ssbd.FREEZER_CityPlanner.doFreeze(FREEZER_CityPlanner.java:62)
ssbd.FREEZER.freeze(FREEZER.java:99)
ssbd.FREEZER.freezeThis(FREEZER.java:147)
ssbd.FREEZER_Root.doFreeze(FREEZER_Root.java:49)
ssbd.FREEZER_Root.bigFreeze(FREEZER_Root.java:60)
ssbd.FREEZER_Root.bigFreeze(FREEZER_Root.java:66)


Because its really quite hot and I dont fancy tackling breaking up blocks into smaller houses until its cooler, I decided to fix the above by putting attempting to find out which cells where closest to a point before searching for one to insert it into. This will increase the overhead on small puzzles, but hopefully speed the big ones up nicely


before:
1 49.72% 49.72% 525 300181 java.net.SocketInputStream.socketRead0
2 1.70% 51.42% 18 300249 geom.Vec2d.pointIn
3 1.04% 52.46% 11 300306 geom.FlatPoint.
4 0.95% 53.41% 10 300322 java.io.FileOutputStream.writeBytes
5 0.47% 53.88% 5 300379 java.util.ArrayList.
6 0.38% 54.26% 4 300373 geom.ThreeToTwo.toFlat
7 0.38% 54.64% 4 300371 java.lang.StrictMath.acos
8 0.38% 55.02% 4 300355 java.util.ArrayList.add
after:
1 49.77% 49.77% 440 300164 java.net.SocketInputStream.socketRead0
2 0.57% 50.34% 5 300455 javax.media.j3d.Transform3D.

3 0.57% 50.90% 5 300368 java.lang.StrictMath.acos
4 0.45% 51.36% 4 300385 javax.media.j3d.Transform3D.
5 0.45% 51.81% 4 300421 javax.media.j3d.Transform3D.
6 0.45% 52.26% 4 300287 geom.Vec2d.pointIn
7 0.34% 52.60% 3 300379 geom.SheetBuilder.normalisePlaneLocation
8 0.34% 52.94% 3 300518 javax.media.j3d.Transform3D.

20% speed up. Not much, but good for half and hours work!


Premature optimiz(s)ation is the root of all evil. Unecessary optimisation is the root of 80% of evil research projects.


Last thing I set up the voronoi to work with concave shapes. The only way I could think to do this was using straight is-in-area-check (left). This is slow but simple (a motto I should have taken to heart from the start of this project) method. If anyone ever comes to re-do this work it should all work really nicely with Fortune's Voronoi algorithm. Seems to work on simple shapes (see dull video below). I have no doubt that borderline cases for this will not be fun to debug at a later date. The idea is to use this to break a block up into plots by placing points at regular intervals around a block and using the voronoi. But because blocks can be concave (due to merges in the previous stage) it had to modified for cocaves too.

No comments:

Post a Comment