Sabbatical Log: November 11th

This blog series is running about a week behind my actual work, giving me time to clean things up.  The date the actual work was done is in the title, horizontal lines indicate when I stopped writing and started coding.

Another weekend, so another day I may not spend all that much time coding. We’ll see.

At the end of yesterday, I had my naive polygon partitioning half working. The approach I’ve decided on is as follows:

• If a polygon has fewer than 10 vertices, do the expensive algorithm
• Otherwise, try and split the polygon in half along either a vertical or horizontal line
  • Try up to 8 different lines per axis, evenly spaced
  • Take the the split that produces polygons of the closest “size”, in terms of number of vertices
  • Then try and partition the two new polygons, recursively

This did require a little more incidental algorithmic work, as I needed to determine whether a splitting line is valid (that is, does it produce exactly two new polygons) and then actually split a polygon along a line.

Determining validity was easy enough, just check whether the line intersects exactly two edges. Splitting was a little more complicated, and at the moment I’ve only implemented vertical splitting.

Time to wrap this up, and see if it I can finally load up a tree.

It’s working! I think.

I’ve verified my test cases by hand, but that’s pretty error prone – for example, the tree polygon has 18 vertices and is decomposed into 12 polygons. I don’t have a ton of confidence that I got the tests correct for that one, though the smaller tests I feel better about.

It’s also been a bit since I’ve done anything visual, which isn’t great. So I’m going to spend the rest of the day working on a debug overlay. I want to visualize bounding boxes, hit polygons, and move the “last collision”-point rendering code into something less hacky.

After a bit of work, I ended up here

Soooo, still some bugs to work out. My gut is that it’s actually a rendering issue, perhaps a placement issue. Unfortunately, it could just a well still be an algorithm error. I continue to dig.

After extensive digging, I’m pretty sure the algorithm is correct – so it’s some other error.

I added rendering of bounding boxes (even though those don’t really exist, conceptually), and discovered some bugs in the placement of polygons post decomposition. I’ve also added a number of alternative colors to the hit maps, to show the different polygons more clearly.

You can see that some things fall outside the bounds, and the whole thing is taller than it should be. Time to dig into the hitmap loading code.

While I’ve made a bit of progress, as the day winds down I’m inclined to toss most of this debug code. The divide (the frame buffer doing all the unit conversions) I went with has pushed a lot of logic into weird places, and I suspect there are some more fundamental errors in hitmap layout.

To illustrate, replacing all the complicated geometry of the actual tree base with something simpler…

…reveals quite a lot of distortion.

So tomorrow I think I’ll step back from this particular problem, focus on getting the debug overlay correctly showing bounds and anchors points – and come back to this multi-polygon problem when I’m better equipped to tackle it.

Continue onto November 12th