title: Efficient object-space hidden surface removal
body: <p>I have the following problem: I need to generate 2d views of a 3d model. Under normal cicrcumstances this would of course be trivial: just render everything to the screen using the painter's algorithm or a similar technique. Unfortunately, the output needs to be 2d geometry so that it can be sent to CAD packages. This means that the hidden surface removal must be done on the vector level rather than the pixel level, which renders most of the standard methods (painter's algorithm, z-buffer, etc.) unusable.</p>
  
  <p>The most common technique I found to perform object-space hidden surface removal is to use a BSP tree, which in theory works just fine. So I implemented that, but performance wasn't even remotely acceptable, which isn't entirely surprising given its O(n<sup>2</sup>) complexity. The test scene I'm using has about 4800 triangles after backface culling, but I expect the algorithm will need to handle scenes with about 5 or 10 times that number, which quickly becomes rather large when you need to square it. The (lack of) speed of our geometry library doesn't exactly help either.</p>
  
  <p>I've since tried different ways of trying to work around this performance problem, mainly based around the idea of dividing up the triangles in smaller groups to reduce the impact of the O(n<sup>2</sup>), such as octrees (over half the polygons were stored in the root node) and dividing the 2d-projected scene in a 10x10 grid to reduce the number of triangles per square (works, but the reduction in polygon intersections is outweighed by the need to repeat the process a 100 times).</p>
  
  <p>Today I had another go by projecting all the triangles to 2D and seeing which ones intersect by first testing if the bounding squares overlap and then testing each edge intersection (3x3 = 9) for every combination of two polygons. For the line intersection I bypassed the geometry library by using the algorithm described <a href="http://paulbourke.net/geometry/lineline2d/" rel="nofollow">here</a>. In total, about 11.6 million line intersections are performed, taking about 30 seconds, which is still far too long (I'd say the absolute maximum runtime would be around 5 seconds), never mind that this is only part of the algorithm.</p>
  
  <p>I'm starting to run out of ideas on how to solve this performance problem and was hoping that any of you would have some good ideas for a better algorithm. All of the ones I can think of are all O(n<sup>2</sup>).</p>