I've spent the last two weeks trying to solve what is on the surface a relatively straightforward problem in 3D geometry. Maybe writing a little discourse on it will help me get things straight. Or maybe someone will read this and tell me this problem has been solved ages ago. Either way, let's go.

Say you've got a set of 2D vertices defining a region. The vertices are numbered 1 through N, giving the order in which you connect them to draw the region's outline. So far, no problem.

Now let's extend our region in the third dimension, giving it thickness. So now we've got TWO sets of identical vertices, offset along the vertical axis by the thickness of the region. All's still good.

Here's where things begin to get interesting. Now let's say you wanted to slice this 3D region with some plane and draw the cross section. Since the plane may slice between vertices, you have to look for intersections of the links joining the vertices, both the links within the upper and lower regions and the links between them, with the plane. This still is a relatively easy thing to do. So when you finish this, you've now got a set of M intersection points lying within the plane. Now you want to connect these points and draw your cross section. But in what order do you connect them? At first glance it seems relatively simple, but i can't seem to find a straightforward solution, either analytic or algorithmic, to this question. You have three types of intersections: intersections between the upper vertices, intersections between the upper and lower vertices, and intersections between the lower vertices. There should be some way to figure out, based on the connectivity of the original regions, the order in which the intersections are laid out.

This little sample case is just the tip of the iceberg though. What if your plane cuts a single region into two separate cross sections? For example, slicing a donut? You now have to figure out how to connect the intersections, and how to separate them into individual regions!

My common sense is telling me this is a problem that the graphics community must have solved long ago, but i can't find anything about it online. It's a subtly different question than your typical ray-tracing engine deals with, so it may not have been figured out. Or it has, but it's a proprietary algorithm that isn't freely distributed. At any rate, somebody help me! This is driving me nuts!

Seem to be falling into a regular weekly posting. I'll try to up the frequency.

Yesterday my beloved Chelsea were only able to manage a nil-nil draw against Birmingham City despite dominating the last 45 minutes and peppering City's goal with shots. However, that solitary point earned puts us top of the table, ahead of Arsenal on goal difference. With a showdown at Highbury on Saturday. Game on!

Current Winning Eleven 6 International squad: defenders Roberto Carlos, Lillian Thuram, Frank Rijkaard, and Marcel Desailly, midfielders Michael Ballack, Luis Figo, Harry Kewell, and Francesco Totti, and strikers Nuno Gomes and Hernan Crespo. I have got to stop playing this game.

Michael and i met up at the Edinburgh Castle last Friday evening for a few pints and a nice greasy newspaper full of fish and chips. We then picked up Victoria at BART and headed over to J-Town and the Fillmore to catch Paul Weller. We had a ticket for Veronica as well, but after expressing her desire to go a few weeks ago, she finally realized on Wednesday or Thursday: "Wait a minute ... i HATE Paul Weller!" Too bad for her, he was amazing. He played an acoustic set with just one accompanying guitarist, but created an awesome atmosphere with just a 12 string and a few simple effects. I particularly remember a few songs from his latest album Illumination, "He's The Keeper" from Heliocentric, and The Jam greats "English Rose", "Town Called Malice", and "That's Entertainment". Mike and i also managed to run into the majority of the old mod crowd, including Carlos and, surprise of surprises, Susan.

On Saturday i took Veronica to Stanford so she could take her business midterm online using my office connection. Instead of having to rely on our home connection and Comcast, which seems to be out about 25% of the time. We had cafeteria food for lunch, then headed home and bought tix online to see Sofia Coppola's Lost In Translation. An excellent excellent movie with an excellent excellent excellent soundtrack. I came away with an existentialist slant on the film. I can't remember the last movie i saw where i was hanging on every movement and facial expression of the characters.

We met up with my mom for dinner on Sunday on Burlingame Ave., then picked up some goodies at Copenhagen Bakery and had a nice dessert at my auntie's. On Monday we finally got around to watching our DVD of Frida. Not knowing anything about Frida Kahlo, i was a little surprised at the amount of time the film spent focusing on Diego Rivera. But a good flick nonetheless. I couldn't get Salma Hayek's joking Oscar campaigining from SNL out of my head.

The Joe Schmo Show is friggin hilarious. At last, a reality show that is openly fixed, unlike all the other reality shows that are privately fixed. And it takes this opportunity to mock the ridiculous crap that happens on all these shows. The eviction ceremonies, the stupid challenges ... Joe Schmo extrapolates them to their logical end and with great comic effect. But they stole one of my ideas! Granted, mine was sumo wrestler poop and theirs was dog doodoo, but c'mon!

And, of course, last week's top ten: