Monday, September 25, 2006

No one has to be about to die for you to save a life...

Education. Not one of my normal rants, its just I've noticed that this country has heavily standardised the education system. By standadised I mean improved the worse case, and this seems to have been done at the cost of the best case. My mother teaches in primary (elementary) schools, in the past 5 years more and more plans and assorted paperwork have to be done before a class is taught. It seems to take up all of her time.

Ofsted is the sword hung continually over their heads - "if your plans arn't up to date, or your not teaching from them, we'll be in trouble". It means that huge quantities of her time are spent writing these lession plans (short, mid-range and long term plans) that used to be used directly on lesson time. Apparently NQTs (newly qualified teachers) have the habbit of just downloading plans from the internet, complete with lists of questions to ask the children, filing them, and then reading them just before the class is due to be taught.

This seems sick strange and wrong! The government may have stopped closed door teaching, the dirty old man who teaches nothing but fear of the establishment, but the great teaching, the lessons that inspire children to interest also dissapear. The childhood lessons that you remember are the strange ones that arn't scripted - the ones where you take apart the old class tape player "just because". The ones where you spent the whole morning on a painting because the teacher's having a bad day (cant do that now, heaven forbid missing Numercy Hour).

Ensuring wall to wall mediocrity is a fine goal for a police state, but something has to be done if we want to keep kids interested in the world. If kids are endlessly told to go and colour the picture in when they finish all their work ahead of the class, they might stop trying to work faster than their class.

I've always believed that play is the best way to learn, and that applied learning is endlessly more useful. My brother asks why they are studying detailed poetry in secondary (high) school, and how finding images of the 20th century will help him in life, over say installing windows or how to get a good deal when shopping. The only answer I can really think of is "to keep you busy so your parents can go to work".

But ok, being a realist I cant think of a better way to improve the worst case teaching apart from standardisation. Its a shame that it has to impact all teachers good and bad to work at all!

Saturday, September 16, 2006

Got thinking about it and was probably a little enthusiastic last night. Thought someone must have done this before and remembered java's RMI, which is about what I'm looking for (if you could talk to it from lisp). Trying to get lisp to talk RMI is an option, but the protocol is heavily based on serialization, which'd be a major pain. It'd also require more communication between the languages which, over ports, is never a good thing.

The other option already coded into java is CORBA (I was rofl when I found out there was a organisation called omg). This looked really good until I got to the bit about IDL. Tis a contract for the client, saying what the server will do. In java it is automagically converted into local CORBA objects for the remote (server) class. The problem is that if you want ALL the classes (as you do when your programming) you have to convert all the IDL; you have to specify whick classes you want called in advance, generate IDL and copy it to the client, where it has to be converted into client classes and linked in. This is pants if you want to use all the java library from list (and dont want to generate all the IDL) or want to write classes at runtime in lisp and have them available in java. (OK we could get going on dynamic IDL-generated class loading, but probably best not to...)

So the proposal is a string-based RMI, jacol has implemented most of this, but I'm not too sure its as simple as it could be. Here's my current thoughts on this:

There will be a java server listening on a port. Once connected there are two commands generated by the lisp end and handeled by the java server.
(new-object, class name, parameters...) => object number
(invoke-method, object, method, parameters...) => object number | primative
We'll communicate objects using ints. At no time will the lisp end have any access (beyond the level of a number and maybe classtime) to the contents of a class, this is the programmers mess to sort out.

Java server will have a hashtable of int->object and will perform a lookup to find the object to operate on. Running this as a java server should mean that its really fast loading as there is no warm up time for the compiler, and it is expecting to run swing code...

Now...we also want the lisp side to be able to set callbacks on certain events, eg - "java button 34 pushed, so lisp function (take-over-world 53) is run". There will only be a few situations where these are required eg, GUI, timeouts etc... and it introduces a whole world of pain from concurrency to the need for an always-on-lisp-function-table.

"So half way through evaluating a list function, someone clicks the "make the monkey bigger" button" this is an issue surrounding lisp concurrency.

One option would be to have a wrapper for a lisp stratement call back. Eg if the function demanded an action listener (or one of a select few classes), we create a new action listener would makes a rmi call to lisp. Lisp then has a similar server, that just takes a string command and (evals) it.

This gives us two directional communication -
  • lisp can tell java to do something now
  • lisp can tell java to call some lisp later if one of a finite number of events happen
  • java can tell lisp to do something now
  • java can't tell lisp to run something later... (although this should be kinda trivial)
Looks do-able, just need to look up concurrency issues for clisp...[edit]D'oh - ok I'm not posting much (at all) at the moment, but when that passing comment comes up first on a google search for "clisp concurrency" you know they havn't implemented it yet. Yet another example of the Holyer effect.

There is something very broken (in a good way for me) about google, it gives far too much preference to blogger.com subdomains! And it does all get indexed very, very fast compared to the rest of the web!

Friday, September 15, 2006

Now macs have all gots webcams, and seeing the current trend towards really shiny GUI buttons, why dooesn't Aqua now have buttons that really reflect what is going on in the room?

Right, I had a good go at lush and after too many errors I'm giving up. Not enough documentation - the Ogre toolkit looked awsome but without any documentation I thought I'd rather be back in Java. There were too many random crashes for my liking but Stack overflows are to be expected tho!:

? (fib 6000)

*** printf : sorry, stack full (Merci Yann)
?


My next effort is to get the jacol libary built under os x.... The plan here is to use the (if not) excellent (then slow) swing and jMonkey libaries from inside clisp. From what I can tell it (like lush) has been abandoned, but since I know a little Java I figured it was worth a go.

First up this error shows up after ./configure --prefix=/sw/bin (cause I'm a fink user) and doing make

;; Compiling file /Users/tomkelly/Desktop/jacol-0.33/lib/md2.lisp ...
*** - invalid byte #xE9 in CHARSET:ASCII conversion

Tis a character encoding thingy (guess the old version of clisp wasn't utf8 friendly). A little searching showed and answer in an old log page. So it seems to build if you change the 'pre:' section in the Makefile to (alternative fix)
...
pre:
clisp -q -c build.lisp
clisp -Efile ISO-8859-1 -Eterminal ISO-8859-1 -Emisc ISO-8859-1 -q -c ./lib/md5.lisp;
cp ./lib/md5.fas ./src/lisp;

rc:

...


next up I didnt want to install this fly by night (read: no native os x) thing onto my system (and beside make install didn't really work). I changed the jacol-0.33/bin/jacol script by replacing the relevant line with:
JACOL_HOME="../"
then I could start the server-
/jacol-0.33/bin$ jacol -jp 2424 -s
Java server listening on port 2424
Lisp server listening on port 16763
To get me a java server running on port 2424. A basic test says it works - woo!
~/Desktop/jacol-0.33/examples/dates $ ../../bin/jacol date-formatter.lisp
18:46:03 2006
September 2006 AD
The time is 06 46 04
Your time zone is BST
Your time zone is also British Summer Time

But I did end changing the /bin/jacol script file to point to the absolute location of JACOL_HOME. Guess I'm just a linux l4m3r...swing demo works too -


(I always have to get one picture into a post....) Right, so now what do I have to do to be able to call java fns from inside the clisp interactive environment thingy?

Then I decided that I've got way to much free time at the moment for it to be this easy, so I'm trying to write my own socket based RMI for lisp. The trick is with these things to make sure that someone else you can talk to has finished the same thing, or that there are lots of people doing the same thing around you doing the same thing.I have neither - most of the lisp/java crossovers are abandoned....

Monday, September 11, 2006


"The Starcraft AI isn't very I"
"...but it's kinda A"

Here's a thought, if you have a very small circular polygon, and grow the edges outwards (camp skeleton stylee) then it is just an approximation of a Voronoi:

If a and b are polygons and we give each edge a negative weight then where they intersect we get a voronoi tesselation of sorts. By giving the sides different negative speed we immitate a voronoi where each point has a shape that grows out of it. (We could even change the shape as it grows outwards, but thats getting ahead of ourselves)

Now of course this is pointless (as the voronoi has a lower time complexity) for circles. However if we wanted to create an interesting brick wall, instead of circles we could use brick shapes... suddenly we are in the situation where we can grow interesting bricks to fit the shape of the walls. So different shaped bricks can be mixed and matched with suitable input polygon generators.

(from a punt in cambridge, just downstream of the mathematical bridge, or rob's version)
(tower of london from the river side)
There is still a problem when we then get to texturing corners. As explained by Legakis, 2D texturing dont work right on the corners of buildings:


His approach was to cut the building up into a bunch of lego (more like duplo) blocks (funny that he ended up needing a straight skleton implementation to shrink the mortar between the bricks in correctly) . Each block was then textured according to its meta data and situation eg 'next to a window and on the side = this type of block'. This doesn't give much scope for interaction between the bricks, but it does look like a really fast algorithm!

There's some serious potential for improvement here - we push the camp skeleton into 3D and then give it an input volume (bounded by the outer wall and a shrunk wall thickness). Then we create brick shaped (tiny) input polygons in the centre of the bricks and let them grow outwards into one another to fill all the spaces. We get a nicely tesselated brick wall out of it! We'd need to remember to set different speeds on different sides to keep a proportioned brick shape -

(grey are input polygons with various negative weights, other bold lines are camp skeleton output-should extrapolate to 3D too....)
This is too much detail for today's graphcis cards, but from this we could render the bump/displacement maps to make walls look really good. There would be some work in defining where the centre of bricks would go, and possibly the need to tweak Felkel's skeleton implementation to give priority to one brick after an intersection (to keep them square) but it should all work kinda nicely in the end....

I guess we would let the brick volumes intersect, then shrink them back in again to create the morar. The outside surfaces could have a roof-like straight skeleton applied to them to make them bevelled.

Well thats enough work for a pHD, but I've been thinking about this and I think Bristol has left a giant gap in my education - working with other people (who arn't nerds). Think its time I got a job behind a bar.

Random thoughts:
  • If a straight skeleton is created, then we can take another line pattern, say a 'curve' and exturude it along the edges of the skeleton? It wouldn't change the intersection points and would need to be scaled for the different weights, but it may be a faster way to make more complicated rooves:
  • People keep comming to this page for a straight skeleton implemetation (often in java). I think I'd better write one that I dont mind publishing. Think I'll get all the ideas correct in lush first and then throw it into java. I tried seperating out my code from sity the other night, but was far too tightly coupled to get it out gracefully (and its crap).

Sunday, September 10, 2006

Now onwards! just having a go at getting lush to compile on my mac/os x 10.4. Why? well I'm a convert of paul graham's and want to learn lisp, but I'm also into graphics so lush seems about right. I'm a little concerned that it doesn't get updates more than once a year, but may well be a fun toy.

Finally got it built by following the readme and the obvious google links. Once it I was trying to run the demos I kept getting errors like this


*** error : cannot configure OpenGL
libglut.so could not be found.
please make sure GLUT or libMesaglut3 is installed.
Both the library and the development packages are needed.
(see /Users/tomkelly/Desktop/lush-1.2/packages/opengl/opengl-config.lsh for more details)


turned out I also needed to fink install glut, sdl-image & sdl to get the correct .so libraries to run the demo. I just installed it locally to try it out, then ran the lush1.2/demos/RUNME script and it gave me a neat (if slow) menu. I was kinda supprised how little code made the menu (compared to say - java & swing).


Really neat stuff - I gotta learn lisp and learn it good. I've got two things I want to work on nowish -
  • Terrain generation. I've just started reading papers, such as those about the ROAM algorithm - seems really compact algorithm for regular terrain meshes. I kinda invented it in my head the night before, realised how obvious the idea was and then found it online. Realtime mesh decimation (with things like animated deforms or 3D objects) seems like a fun thing to do. Annoyingly the US is way out front in this with the Lawrence Livermore Labs turning out some great papers. First thing is to look through the options - the types of decimation (removing a point, edge or triangle) in combination with organisational schemes (bintrees, octrees, triangle trees or BSP), ideally being able to plug each into each other to get some quick readings would be neat - perhaps lush will help me out on this. It'd be cool to come up with a non-regular mesh decimation technique that allowed for real-time deformations and animations...
  • A rigerous camp skeleton implementation would be fantastic and would be a really good start for a rewrite sity. General plan would be to work out the details, implement it and get it right in lisp then take back into java.
Come to that I find that graham is really into the web based apps, makes me feel a bit out in the cold...all the stuff thats really heating up at the moment is the web sheneagoats. Perhaps I need to get into the games market more - nah working in games would be too much like hard work after all those rumours of how hard they push people at EA.

Blogger rant - would it be that hard for the bloggy people to make uploaded images appear the cursor position? ;) Still I really like the beta version!

Sunday, August 27, 2006

Right, got thesis all printed and is now being bound. Will put it in the post today, but Mike gave me a longer deadline. Still no news on when/if I have to come and present it...

Just trying out google base, (woo for free file hosting by google). But has totally failed to upload my 10Mb pdf 4 times, from my pc and from another http server.

Now No. 3 on a google search for sity...Will put thesis online in a couple of days...

Lol, just added a hit counter to the bottom of the site, two interesting developments already - This is the top result for a google search of "pages like utube" and David Eppstein has a link to this page. Well that and I get 2 hits a day ;)

Finally also found the original straight skeleton paper. Was only invented in 1995...

All printed and done. Waste of paper if you ask me...

Tuesday, August 22, 2006

right, time to get some test renders out of this mess!-







Strange thing is today I only just used java's do...while construct for the first time. I think thats very wrong, just goes to show that convention can be damaging. It would have solved some ugly cludges I've put in, and made the code much nicer and simpler. Since if you thinking about ugly code your not thinking about what your doing it just goes to show that the language you think in does effect your results.



I switched to the beta version of blogger today, seems to have fixed my two gripes with blogger - the 80% failure rate when uploading images and the strange need for republishing to static pages. Big up guys!


oops, oh dear it looks like the pirates beat the straight skeleton in the google video download charts (however google is beating uTube 2:1 for pirate video hits, and is also not-quite-as-bad-a-quality-as-youtube):



Title Page Views Downloads
Fairy Lights 40 1
Voronoi computation 9 0
big test render 12 0
camp skeleton 30 0
crazy clown land 11 0
first city flyby 53 0
irregular weighted straight skeleton (camp skeleton) construction 22 0
more pirates! 469 4
mungo 12 0
night glow 6 0
pirates ahoy 800 6
straight skeleton animination 47 0
straight skeleton eve demo 38 0
trippy debugging 242 1
vornoi tesselation art 9 0
weighted straight skeleton 26 0
weighted straight skeleton 33 0
Totals 1859 12

-

I've wasted minutes of the lives of 1859 people...


Monday, August 21, 2006

First attempt at mental ray on a large city:

The city wasn't really worked on (that would take weeks to get right) but shows a lot of the types of buildings you can make with it - from overhanging rooves to flat ones with walls. A little silly because the rooves run into each other, and a bit too bleached out but its a good start. I'm considering leaving the streets without geometry just to add a bit of contrast...

Most of today was spent botching together some roof code so it works consitently enough for large cities. Tomorrow I'm going to make a proper grammar (now load and save are working) and see if I can get a 1Km square render out of maya....

lol also found the remote command to run maya over the network:
/usr/aw/maya/bin/Render -im ~/../mental/new -r mr -v 4
-x 600 -y 600 -of tiff -cam persp -rt 4 filename.mb

works great for a 600 square image in filename.mb using 4 threads and mental ray (mr) to a tiff file called "new".
Not quite sure how to set up final gather settings, I'm hoping they are in the maya binary you send. I know from last time i ran the command "y > /tmp/file" (go on try this....) on snow that i've got at least 4GB of tmp space to render tmp images into, and that snow doesnt clean or limit access to the tmp folder. This may be useful for animations at a later date.

Sunday, August 20, 2006

Right back from holiday last night so its time to get this thing published.

I think I've decided to publish all the code and the write up once it's been graded. I finally found the Bristol IP Policy, and it seems like its mine to do as I like with. I have half a mind to try and get some commercial recognition, but trying to deal with RED would be a chore and Sity is a long way from being commercially useful. Will probably release the material under the GPL, since I dont like the idea of people making money (without sharing the code) out of what I've done at bristol. I guess I've still got copyright stuff so I can commercialis(z!)e it at will. Would be cool to keep developing and turn it properly open source, would make the jMonkey team very happy to have a custom city generator custom made for them! But we're looking at hundreds of hours of work! I think the most likely track is to take it up as a phD, I just gotta find a CS department with a computational geometry department that doesn't suck! The alternative is to go underground and keep developing in the evenings until the program shows enough commerical promise to go live....

Strange thing is no one has ever talked about IP rights at bristol, I'm sure when I started the IP rights got assigned to the universtiy - I wonder when they changed it around. They seem to talk big about business, but as David May admitted, they've only had one commercial sucess with their MEng course, and with credentials like that (and James Barlow on the loose) I'd rather do it on my own.

Oh, and google video is back! Woo for a non Murdoch owned alternative to uTube! No more waiting for verification.... Look - our daft dog trying to burry a spade (something ironic there?) but failing big time:

Friday, August 11, 2006

:)

Its been sent off for a draft reading. I didnt read the last half pretty well and I think the format the department demands make the business stuff look thin and the academic stuff hard to find.

Strange that the website says they collect the thesisis for an online library but one doesn't exist.

Quite a few new bits and pieces were left out that will go unpublished (such as a cool reflection wrapper class, my plans for meta-java using the class loader) because of the fixed word limit, and 6 appendices is more than anyone'll read anywhoo. Its a shame becase the business stuff should have been left for the buisness plan as business and academia are pretty incompatible goals. Much of it I felt I was writing just to prove I knew stuff that was tested for in other units (the design stuff), but hopefully shows some of the thought that went into it. Much better would have been to let us decide the format. 1 business plan and 3 short academic style papers would have saved everyone a lot of reading (and a lot of trees). It is kinda insulting (to us and them) gettomg us to read papers that give complex and speedy overviews of a topic and then expect us to only be able to write a monolog about the processes we went through.

well enough of that I'm offta cornwall for a week in the rain :)

Thursday, August 10, 2006

Woo! all done.
50 pages, 25 pages of appendices, 17K words... seems a little pointless as it will only end up as another unread appendix...

should probably do a user guide while I have the chance... Will read the thing over tomorrow morning (I hate this, I almost have to read it out loud to stop myself skim reading) and send a copy to neill and colin.

Wednesday, August 09, 2006

Finished writeup of the straight skeleton last night, although I could add an extra section about straight angled corder and weights, It seems long enough as it is!

I think i've got mental ray figured out, it all seems to be about the ambient light and final scatter. Looks really nice doesnt it?

I'm giving a quick description of the Voronoi tesselation and then onto a description of Sity's grammar. Thats going to involve lots of horrible diagrams and explinations of my meta data system.

Found another insntance of the Holyer effect - "concave voronoi", damn self refencing internet. I demand a DAG replace the web.

I wonder if theres a convention for quoting the source from whom you copied the reference from using google scholar? If you get an ammusingly-authored reference into google scholar, I'm sure you can get hundreds of published papers to quote "Sutherland and Cohen - the use of scissors in line clipping (1968)"

Right I reached what I thought was my goal for the word count by midday on Wednesay, I'm so not going to write another 12K words in the rest of the week, but hopefully make a lot of pretty pictures (worth at least 1K words each)

I've also just found out that:
  • Rob's got Maya 7 and mental ray installed on snow
  • snow's got 2 processors
  • snow's got 5GB memory
  • no one is using snow in the holiday
  • you can run maya from the command line
This means that there is a chance I can render out a massive image of an entire city in mental ray. Everything in mental ray looks cool. Lol then again if only I could get into the graphics department's cluster, I might be able to match the resolution of the printer that sits behind colin

Hmmm... have just realised that UML just isnt designed to deal with reflection gracefully, expect lots of annoying notes saying what a connection really it!

Well end of today and I'm up to 14K words, 45ish pages, 4 appendices (although one is naff) and 2 pages of references . There's a 50 page limit, so I guess its time to make constant references to an appendix to annoy the reader. It may even be sensible to put all the results into an appendix. Should be able to do all except the user guide and results tomorrow :)

Tuesday, August 08, 2006

Lol woke up to find my mental ray rendering option had dissapeared, luckily this post was near the top of google results! Yay for mental ray!:
Still not quite sure how to get the perfect images that you see in some the publications, I cant find the ambience bounce option that is present in mighty radiosity...

Wrote a lot of words today about the straight skeleton hoodicky. Now up to 9.800 words and 30 pages. Lets hope the rest is a little more brief, some could be cut out to the appendix, but a lot of it is my own work built around someone elses so i dont really want to relegate it that far. but anyway it looks like I'm over half way to the thesis 'minimum' of 50 pages. Its a bit of an arbitrary limit.

It was one of those days when trying to concentrate on any one section would just result in me adding more to a different, unconnected chapter. Not very good really.

I did however manage to use the phrase "hollow point" and produce a reasonable argument to name my modifications to the straight skeleton as a "camp skeleton"

I just realised that I dont really want to give the source code of the project to anyone. It does seem kinda childish, I guess I thought about this when I signed up for a degree but dont remember now. It feels like its all my work, and since I'm paying Bristol for tuition it feels unfair that Bristol owns the IP to the work. I wonder if this will change when they start screwing (I guess they've already started) students out of more tuition. It would certainally make bristol's business credientials (its outstanding positive feature) more plausable and attractive to business minded students. But I guess I'll leave it up on the website for a while. I think the critical thing here is that there is no work here that couldn't be hacked together by a C guru with the right libraries in 24 hours...

To be honest for the amount that they are charging students to go to bristol my honest advice for computer scientists is to move to california and use the same money (as an in-state student) to get into one of the UC campuses near silicon valley. People would become much better scientists in that culture, and have a the inside track to a dev job with one of the big companies over there (unlike being a sales and marketing monkey if you join in the uk).

Monday, August 07, 2006

First day of right up. Kinda cheating here, but used my notes on research (3K words), tidied them up and wrapped it all up in some business plan fluff, in total 5,207 words (not that a high word count == good!) .This just about covers the background section of the thesis, described on the course website as

Background - why what you have done is a good idea. What work your project builds upon. Explain your new idea or application. Remember this is aimed at a technically competent person. [15 pages]In here you are explaining all the specialist knowledge that we need to understand the particular branch of computer science you have been involved with.

This was not a particularly clear starting point, so I just explained what sity is, who will want it & why - and moved onto a review of papers in the area interspaced with my own comments and observations. I'm not sure what 'specialist knowledge' means but apart from a short section on the skelton and voronoi (the details of which are much better saved for the implementation chapter), I'm sure words like 'roof', 'road' and 'house' are kinda self explanitory. Also some stuff about the point of view of the people who will be using it (artists hopefully) and how it should be easy to us, but again leaving the meat of the discussion to a technical chapter.

and i dedicated it to green & blacks....(ginger in particular) not sure if your allowed to dedicate thesi but I just did....
Lol, righty ho last dev day today, so time to crank up the outputs.


I can now have buildings with overhanging rooves, ridges marking the boundries between stories and different walls with different slopes.



In breaking news, a google search for sity no places this blog at number 4. In your face sity communications. I guess thats what you get for having a blog with google...good rankings even if no one links to the blog!

Tomorrow I'm starting writing up. I think I should have a reasonable draft to show colin by the end of the week (then I'm off on holiday for another week)...Chapter headings to include:
  • research
  • voronoi
  • straight skeleton
  • overview of method
  • gui
  • engineering
  • a user guide
I think about a day each for those (or less, I've already got most of the illustrations). About 2K words for each probably so about 12K in total. Should be able to do it mostly in a week!

Friday, August 04, 2006

Righty ho then...got fed up of arbitrary limits on city sizes due to speed of dump to Maya....so wrote an .obj export. Once the files are in .obj format (and because i do a bunch of optimisations of only outputting each vertex once now, am thinking the jMonkey bit would also benefit a lot from this...) maya can import in seconds and display (lighted in real time) a 400mx400m section of city without any problems...

And a 1Km by 1Km (the obj file alone, with no normals is 30mb...) Adding more detail to these houses suddenly looks like a daunting task, doors and windows would be something like x6 effect on the polycount. Lets put the solution to this down to More's Law...

Have also added a simple load and save facility (that doesnt really work) to allow waterfalls to be written to disk as serialised objects, and read back again. Something is stopping it working and the stack traces are unuseful! Probably best to leave this until after writeup has been submitted - I intend to go on a big bug hun tto make the thing more presentable. I dont pretend to get rid of them all, I dont pretend that I can, but I may be get to the point where it doesn't crash in a 10 minute demo!

One of the main problems in programming speed seems to be familiriarity with the code. I wonder if it should be possible to add automated tests to a program that checks that the programmer understands what they are doing?

Thursday, August 03, 2006

Todays job is to get interesting roof shapes into the buildings. The idea is to repeatedly use a straight skeleton transform to create the walls and roof of a building the changes in wall angle will and sudden additions (such as adding an overhanging roof) will be handelled by a DFA like structure that will use a priority queue.

This is a lot of work for the second (or third) last day of development. If the straight skeleton doesn't work as expected under these condition I'll have to roll it back!

I'm also beginning to think about the writeup. Previous years' thesi that I've read dont seem to be so hot on diagrams as I anticipates (ok so this is a geometry based project, but i didnt see any UML in my skim reading either).

In other news I'm trying out opera as a browser and liking it a lot. Probably the way forward as firefox becomes more mainstream and prone to malware!

Wednesday, August 02, 2006


Had more problems with me forgetting myself - the Collections.shuffle(List) command was used and of course this made the decisions made random. This was replaced by Collections.shuffle(List, Random), to make the result deterministic to my program. I also had a go with a static code anyalsis technique - finding all instance of HashSet or HashMap (due to VM optimisation these arn't deterministic), as well as System.exit s used in debugging that got forgotten about. Still trying to track down a NullPointer in the new roof union, strangely it only occurs with fat walls, something about merging all sides of a cell is my guess!

The Voronoi and camp skeleton algorithms complement each other. The skeleton creates very rigid geometry, with interesting exceptions that appeal to the eye as man made. The Voronoi is able to clean up these anomalyies into something that is suitable for additional computation.


Here's a description of the unioning procedure I made up it runs in linear time compared to the number of points added, so I'm quite happy with it. Theres also a render of a 200mx200m square sity, the maya transfre was so slow after 3K triangles, that I gave up on the cenre bit...

Tuesday, August 01, 2006

Wrote a thing that merges the panel of a roof into one, this will let us create walls and overhanging roofes with ease. So far the results arn't perfect, but look promising:




Kinda cool things are: houses share one wall, so houses will have built several walls of their preffered hight around them. The top of the walls can be bevelled, using the skeleton procedure too!

Lol found the bug that was making some of the walls come out upside down: When we traverse the hashset of points when merging the woof panels into a wall, it is critical that the first panel output to sheet builder is a positive one, else theres a chance sheetbuilder will decide up is down. To solve this we just ensure that the first point traversed is on the edge of the shape (corelDraw to come tomrw!

da Jesus of suburbia:

I don't really like the walls, a bit too twee for my liking, perhaps an option to have them in the back gardens, and then ensure the default is to use them sparingly.

Tomorrow is onto the dredded task of making roofs with overhangs and roofs with hatchings. Will probably take rest of week/project!

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 -Dphotos1.blogger.com,twak.blogspot.com --random-wait -r -l inf http://twak.blogspot.com


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()
{
renderer.setCamera(null);

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

rootNode.removeFromParent();

// the might be to blame for inter-display reactions? (also in MagicWindowMonkey)
display.getDisplaySystem().close();
display.getRenderer().clearVBOCache();
display.close();

renderer.clearQueue();
renderer.clearVBOCache();

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


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:
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.

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!