11.9.06


"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).