unfinished business

  of course, a thesis is never finished, only submitted. multiple cycles of submit and revise on my masters' thesis took up most of early 1998 (along with a well-earned vacation). so it wasn't until june that I was able to really start working on my phd. while working on my tree models for my masters, I had been keeping track of other research in the lab.

  george sealy had been working on converting models built using constructive solid geometry into volume models. one side effect of this is that volume models can be polygonized and rendered very fast using 3d accelerator cards. I thought that it would be useful to investigate interactive design of csg models using a technique similar to this. this could have many important applications in engineering design and solid modelling.

  the basic idea was to cast rays against the algebraic primitives that make up the model, and join the intersection points up into polygons. initially, I had vague thoughts of using an octree space-subdivision technique to determine what parts of a model were changing, and only recomputing these sections. unfortunately, the problem with this is that it's just too expensive to re-polygonize part of the model when the user moves it around.

real solution #9

  instead, the solution I came up with was to use a two-level subdivision scheme. the first scheme divides the polygonization of every object up into sections, each of which has a regular grid to store triangles in; the second octree scheme is used to work out which sections overlap each other. this lets us work out in real-time which polygons in which objects need to be intersected.

  using a standard triangle-intersection algorithm, we can split the polygonizations of objects against each other and calculate their boolean combination. spit out the combined polygonization to a 3d card, wrap a simple interactive-editor shell around it all, and voila! solid modelling has never been so easy. don't believe me? check it out for yourself. in august 1999 I travelled to los angeles to present my work at siggraph 99. you can check out the technical sketch on my meagre list of publications.

the shadow of the future

  of course, nothing is perfect. my current theory is still tied strongly back to the idea of casting rays against algebraic surfaces to create a polygonization. while this is a very general technique, the polygonizations that it produces are absolutely horrid. too many polygons, and those that are generated are usually wasted. since the space subdivision works, and works well, the next step is to re-design the polygonization with my new perspective.

  this is roughly where I was in december 1999, when a marvellous opportunity opened up at bungie software. while I am still enrolled part-time at otago in the phd program, and I have continued working on these ideas, the pace of my phd has slowed dramatically. however, it's not going to stop - there's just so many interesting avenues to explore!

updated 02.21.18
© chris butcher 2000-2003