Monday, July 31, 2006

Last week of coding. Lets get these things looking a bit more like houses! Plan for the week is:
  • walls and overhangs
  • different roofs
  • windows
  • drainpipes
although I will probably only get through the first two of these without a lot of g'n'b's. Next week will see me doing the write up. So I should have a draft of the write up to Colin by the 12th August. I'm then away for a week (going to the balloon fiesta in bristol for a day too...). I'll probably have a few hours that week to tidy the draft. I'll then spend a day or two adding any suggestions from Colin and getting it printed out.. I'll then sign it and send it unbound to Colin for submission I guess...

Lol, have also figured out (with a little help) how to create an offline version of my blog using

wget -e robots=off -E -H -p, --random-wait -r -l inf

They bar you from downloading images from their servers...even when they muck up converting gif's to png's and filling up space on their servers...

Thursday, July 27, 2006

(appologies for image size, blogger thinks its acceptable to convert a 60KB gif to a 500KBpng....)
I was wondering where all the heap space was going- above was a kinda cool looking bug. Its what hapen if the street front of a house becomes reall small. Its interesting that as we take the voronoi to the limit, it creates very 'straight skeleton'-like structures for us...

...a bit more work tinkering with internals and I have a system that gives everybody a garden. The very cool thing in this next grab is that most houses are rectangular. I never told it to do this, it seems to be a fairly fundamental geometric thing - if you want a house near a straight street, then the best shape for it is a rectange. Note the neat way the voronoi deals with the corner cases with minimal effort...!

What we have is a parameters for distance from all other houses, another for distance from the street, which is added to (optionally) on one front to create a front of the house.

Am now really confident in the project. I only have a weeks coding left, but feel it now produces results that highlight the effort thats gone into the mathsay bits. I've also done the analysis on my grades from bristol and it looks like that as long as I pass this I'll get the degree I was aiming for. wooo!

Wont be up to much tomorrow or this weekend. The hippyfest that is the cambridge folk festival is in town... (photos here)

Overview of process so far. I gotta go and plan how to create the houses & roofs nicely!:

Wednesday, July 26, 2006

OK... spent the morning looking at more Voronoi problems...then I came to the conclusion that I'd never fix it all up in time to complete this project.

So I went back and made the code more fault tolerant. If performing the voronoi on a block didn't work, it was left blank. I think I can get away with this with the current rate of errors by letting these areas be 'parks'. I really hated doing this (perhaps I should have done it a week ago really), but I also want to see the back of this project.

First block of houses with different houses on each block:

Right, one is good, many is better!:
Unfortunatley displaying a city this big in real time brings my computer to its knees. The poly counts are only going to get bigger... Solved this by only adding one giant mesh to the screen rather than one per polygon. It ment I lost my 1337 feature that clicking on a roof brought up the screen with the roof options tho...

One of the important aspects to talk about in the write up is how when we unable to use a routine a special exception is thrown (when assertions are turned off). This allows me catch errors I recogonise, but still recieve abnormal errors as they develop....

Now moving onto adding gardens and making the houses a little more square.

Tuesday, July 25, 2006

First up: addressing a new problem in the voronoi tesselation. Apon closer inspection the parametric form for line clipping was only giving consistent results to 10E-3. This ment that the rounding errors were getting a bit silly in places, and I was ending up with non simple polygons. Therefore I had to change the tolerance for a line starting at a previously defined point to this 10E-3 figure...

Monday, July 24, 2006

Right dissapeared at the end of last week due to lack of ait conditioning and an enthusiastic dentist who decided it would be better to remove four teeth than two...

First up concave tesselation. Basically it works!:

Got stuck on some borderline cases tho. Spent a while looking at it....

... then I got fed up with all that I went on a leak hunt. I found a couple of cases where hashtables of geometry (so that when you click on something we can select the correct waterfall) weren't emptied. This ment 100's of megabytes of geometry that wasn't removed from memory. Creating multiple cities would bring my modest machine to its knees. Tis much better this way.
You can get memory leaks in Java!.

For future reference this is the best way i've found to clear up after a JMonkey swing window. Not sure its leak proof, but isn't too bad:

protected void onQuit()

ListIterator lit = rootNode.getChildren().listIterator();
while (lit.hasNext()); lit.remove();


// the might be to blame for inter-display reactions? (also in MagicWindowMonkey)


for (Texture t: textures)TextureManager.releaseTexture(t);

eventDispatch = null;
geometryToWaterfall = null;
geometryToInPlug = null;
geometryToOutPlug = null;
toUpdate = null;

Next up was some more bug fixing on the Straight Skeleton:
  • If there are still incompleted parts of the puzzle/points still to be processed - these are disguarded, and the appropriate edges added to the output. We might get these edges on a symetrical shape where one point is left between two edge collided pairs on either side.
  • Secondly the steepness of parallel lines' bisectors examined. I think (this should be proved by someone with better abstract thought than me) that more than two fast bisectors cannot co-exist in one active list (see inset)/

Wednesday, July 19, 2006

First up was a series of test on the concave Voronoi. As you can see it tesselates the enron logo nicely, even with the point on the trunk added last. I expected problems here because it has to trace around the edges to find all the points for the trunk points

Lol, you know when your in trouble when you come to find references for your work and the top google hit is yourself. I think this should be known as the (Ian) Hoyler effect due to the number of his courses where the top hit for a subject is his own website.

Some more testing (I forgot to switch assertions on this morning) and the convex voronoi needed polishing a bit:
Its to do with getting double readings when a bisector enters or leaves a shape due to rounding errors (particularly common in parametric form equations ive noticed....). While the algorithm could be fooled into giving the wrong output, I dont think that case will come up (famous last words I'm sure). "I'm only an undergrad, I'm not paid enough to fix this...."

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:
TRACE 300343:

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

1 49.72% 49.72% 525 300181
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
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
1 49.77% 49.77% 440 300164
2 0.57% 50.34% 5 300455

3 0.57% 50.90% 5 300368 java.lang.StrictMath.acos
4 0.45% 51.36% 4 300385
5 0.45% 51.81% 4 300421
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

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.

Monday, July 17, 2006

Here are the diagrams of what was causing a problem on friday with upside down buildings - i'd forgotten that I find the normal of a plane by taking a cross product of its edge-vectors. This only works on a convex polygons without 180 degree (non) bends. I ended up just using trial and error - creating the transform, finding its area and flipping the normal if the area's not positive. I've asked Neill if theres a better way, but I'm fairly any solution would be O(n) in the number of edges, so I cant be far off.

By my contorted time scale I've got 3 weeks left of programming to go (given myself a bit more after last week). I'm a bit dissapointed Ive done so little, but I guess thats how software development goes. I was amazed to find the number of line of code I write each day is only about 500. Feels like a lot more. Lets hope that having my wisdom teeth out on thursday doesn't slow this down any more.

Spent the rest of the afternoon hunting the above borderline bug in the straight skeleton procedure:

Friday, July 14, 2006

Fist thing finds me trying to track down a strange bug. The whole system is ment to run of one random seed, so that by changing one number you get a similar, but different city. I ran into problems becuase I kept getting different cities for the same number, and traced the problem into the Voronoi routine.

The strange thing is computer programs should be deterministic - given the same input they shuld create the same output, there is nothing else they can do unless some outside system changes something. After checking that there were no calls to Random in the Voronoi package I checked there was only one thread running at a given time. Both looked ok. After more digging it turned out that the Java library HashMap was to blame.

I guess some optimisation in java reuses objects, and this in someway sets up HashMap so it is different every time. The return order of a HashMap is also non-deterministic aka 'different every time'. Switching to a LinkedHashMap fixes the problem with minimal (programmer) overhead.

I am a golden god. Crashes 4/5 runs on a city this large, but it runs.

Wednesday, July 12, 2006

AAARGH, just one of those days. All the algorithms were never designed (or tested - my bad) to work on polygons with 180 degree 'corners'. Everything from the straight skeleton to the thing that outputs faces as triangles has broken. I decided that it was inivitable that these corners would occur and there was nothing to do but fix it. I patched up the skeleton to work with the case where all edges had the same speed, but perhaps it needs a lot of futher work to work when the edges dont have the same speed.

dont have anything more to say here right now, except maybe AAAAARGH again.

Tuesday, July 11, 2006

First up I got the Vornoi running on dots with regular intervals. This was just a case of breaking many borderline conditions. The diagram below gives the most explainable, but there was also much fiddling 'until it worked'. I'm never happy in these situations, you never know when you might hit the exact case that make it fall over!-

I wrote a lot of code to clean up the Voronoi output. Something that finds the size of a polygon/block and if its smaller than some limit merge it with a neighbouring block. Heres an output of the block map (finally some real results) the cool thing is you can just keep hitting a key and it generates another. I'm supprised how good the voronoi it looks without any tinkering, I was expecting to have to do a lot to make streets look like streets etc...
You can see where some blocks have been randomly merged into their neighbours and where some that were too small also got merged, for example the hammer shape in the middle of the above pic. Solid results at last :)

Every five attempts at running it crashes with a mysterious 'zero length edge' message while shrinking the blocks, I'm about to go and look into it....

Monday, July 10, 2006

Here's a post dated blog entry for monday! I got the different block pattern generators working together. So here are some examples of the kind of block patterns we get out:
As you can can see the mixed one looks really authentic! The only problem is my Voronoi tesselator really doesn't like evenly spaced blocks at an angle, I guess thats tomorrows job.

I also fixed up the straight skeleton to create bevelled edges. This will be used to shrink the edges of the blocks away from the road centres to create a road network:

This got me caught up in fixing a lot of the guts of the sity program to create flat panels in the correct locations!

Wednesday, July 05, 2006

I rewrote a section of code to automagically assign the values from a set of hashsets to the waterfalls as they are instanced. It searches all the public local fields and if any match the names of stored parameters, sets them up:

Field[] myFields = getClass().getFields();
// hashtables to check for values
LookUp lookup[] = { LUInt, LUDouble, LUBoolean, LURest };
for (LookUp look : lookup)
for (Field f : myFields)
Object l = look.find(f.getName());
if (l != null)
f.set(this, l);
catch (IllegalAccessException e)

This means that instead of:

public class FREEZER_Dot extends FREEZER implements NOISE_Dot
public List getPoint()

int type = gInt("dotStyle");
System.err.println("type is given as "+dotStyle);

I can just:

public class FREEZER_Dot extends FREEZER implements NOISE_Dot
public int dotStyle;

public List getPoint()
System.err.println("type is given as "+dotStyle);

because it is able to associate the name in the variable list (dotStyle) with the local field dotStyle :) It also works with the inherited variables system I've got too (that parent waterfalls can set state for their children)

Next up is the point generators. I just decided to create three - spiral, rectilinear (manhatten) and concentric circles. These generators are used for positioning the blocks. I used wikipedia to find the parametric form of spirals.
Spiral, circular and block(with lots of noise) point layouts:

Tuesday, July 04, 2006

Was ill today (shoddy drug interactions) so here is some comic relief of what I made last weekend with my lil brother -

Monday, July 03, 2006

Sucess! I got the voronoi tesseleation working to my satisfaction. Turned out that I'd caused myself a three day diversion by making the tolerance at which vertices were merged too large, but feels very good to have something that will run.

I ran randomised tests upto 2million cases without any trouble, but I've yet to test it heavily with regular shapes.

hmm... didnt get much done on friday but went on a binge sunday morning after the pub on the gui, the trick to this seams to be too much green and blacks dark chocolate (better than coffee for coding sprees). Apparently there's not any caffeine in chocolate, but something in there works just as well (tho others say 150g of chocolate is the same as a cup of coffee). The stange this is that although I dont rembember the first few hours it seems to work really well. You can now click on output geometry and it selects the component that created it in the other window. You can also ask it output a specific subset with fixed inputs but random changes each time, for example you can see a window from a house generated 10 times in a row. The last addition on sunday was being able to output the current tesselation to maya easily.

Debugging information rendered out in maya:

Tommorow I move onto the roads!
Update I couldn't resist checking the regular tesselation (eg square roads) and it failed when the points where in a random order (nasty crash somewhere) but was ok for a regular ordering, so i'm happy:

Sunday, July 02, 2006

Hehe, went on a bit of a gui bender and set it up to remember (via a hashtable) which output geometry came from which input waterfalls - it means you can click on a wall and have it say what made it. Should be really useful for detailed debugging.

Next up was fixing the problem of Random. The whole program used one Random object, so that all results would be repeatable. However it turns out that it needs each frozen/instanced waterfall to have its own random source, that is used to generate random sources for all the children. This makes parts of the tree also reproducable.

The next trick I wanted to get it to do was generate just one part of the tree (say a particular style of window) over and over again so that you can get an idea what it looks like. This means finding the input values to a instanced waterfall, then re-running it with different Random objects. To save the random object it was initally given I used this old trick to serialize the Random object as it isn't cloneable. The whole tree is then searched using brute-force to locate the first instance of the specified waterfall. It then stores the input parameters and attempts to bail out. The the input sheet it moved to the origin and the input state of the instanced waterfall is run over and over again to give an impression of what the output will look like...