Monday, June 19, 2006

Right, eventually found the error causing my line intersections to be asymmetrical - it was a missing minus sign in the library code I wrote while I was really ill 3 months ago. This is why computer science degrees are more time consuming (or time-wasting) than most. If you miss that minus sign its your 5 hours trying to find it. Tis also why good programmers are orders of magnitude better than bad ones- if you know your going to have to find a needle in a haystack, it had better be a well designed haystack.

The next modification is to fix the issue of escaping bisectors (roof edges). If they hit an opposite edge at exactly the right place, between intersections (as happens with regular roofs), the standard intersection fails every so often. The text book way to do this is to project the ray-plane problem into 2d (by dropping a dimension) and using the Jordan curve idea. The standard implementation (Alan Chalmer-esque) doesn't deal with borderline cases (where the ray just grazes the plane) in a reliable manner. This diagram shows modifications for how I think it should work.

The next of my grand schemes to sink was the algorithm i wrote about last Thursday, to convert the 2D skeleton to 3D planes. The problem was to make the right choice at each vertex, without resorting to doing minimum angle computations (which would of had to be in 3D for 0-weighted camp skeleton edges). Linking from one point to the next always in an uphill direction is fine, untill we consider split events, where there are multiple ups and downs throughout an edge. The alteration was to keep a hashtable of dots and lists of dots, indexing the possible roof edges at each vertex. Then it was simple to get each edge to store a list of related points, and then traverse. Ill be keeping the Thursday data structures tho - they let someone correlate output points to input points, and I have another grand design for that scrap of data.

The next technical thing to come up was that when a split operation occurs (when a bisector reaches another face before colliding with either of the bisectors on either side), it splits the opposite edge into two. This is well described by Felkel (see my inset, right), but needed modifying because Felkel used lists of points that constitute a circuit of points. In reality this is unescessary and I just use a big ol' hashSet.

If its not obvious all this corelDraw pics are what I plan to use as illustrations in the writeup! Its often easier to create the pretty pictures first and then make the code changes as it makes you think about the details.

As ever I didn't get the skeleton quite as far as I wanted. It should have been possible to create them with non-planar bases, especially since most of my maths is already in 3D, but it'd be new work (havn't found it documented anywhere) so theres bound to be mines. It'd be really useful for creating the ground floor of a house on a hill, or projecting windows or butresses onto walls that change their slope half way up.

Onwards and upwards (just as long as its away from another week of maths) - tomorrow I'll start on the street layout and making a hundred houses at a time. Buzzwords I expect to use tomorrow: random-walk, point cloud, downhill search, camp skeleton,Voronoi polygons.

One final thought is my ponderings on how to construct floorplan procedurally to include details such as bay windows.
  • A good idea already out there is to take a floorplan that is already union'ed bunch of primitive shapes and grow it upwards. This would mean knowing what we wanted as the building was starting out.
  • The alternative is to start with a concave building 'core' and for each face project extensions, such as another wing, butress or balcony onto it from the side of the building. This would make it much harder to fit the building onto a plot (top-down), but make more elaborate features easier.
Both are doable, and I'm leaning towards the first idea. This'll be the week after this' work.

1 comment:

  1. Colin Dalton09:22


    Now that you have a relatively organised 'haystack'it sounds like your making progress. Couldn't additions such as bay windows and extensions be treated as independent geometry and positioned/aligned with the main structure to create the illusion? - unless you're planning to render the buildings with transparency the resulting redundant faces within shouldn't be too expensive. Looking forward to seeing the hundred buildings. I've included another minus sign at the end of this comment in case you need another one. -