Hidden Line Removal
The inspiration for this project came from wanting to overcome some limitations I hit when using a tool for this purpose. The problem statement is relatively straightforward: given a triangle mesh, we want to draw the wireframe - this much is easy - but, the key is to determine the line segments that should be shown, when considering the mesh's self-occlusion. By this I mean, does one part of the mesh cover up another? The covered segments should not be drawn, for example, the back side of the mesh.
This is another of the projects which has been enabled by the new software rasterizer in NQADE. This is a great tool to have in the toolbox when approaching graphics problems.
The purpose of this exercise is to create an SVG vector image, consisting of all these segments - this then gets processed to g-code to drive a pen plotter. I don't currently have space to set up my plotter to test the output, but I have gotten some very promising results as output. The limitations on the other tool were from the resolution of the target that it rendered to being capped at the resolution of the browser window that it runs in - I tried making the window as large as possible but it would still miss small segments on high detail models. My software rasterizer does not have this limitation, as it can run at whatever arbitrary resolution up to the capacity of the system RAM. You can notice some issues based on the lower resolution of the above image, but it's not really practical to include images of the size that I'm dealing with for this project on this page.
How It Works
To lay out the problem, we start by gathering all the triangles on the mesh. You can do an early rejection pass by looking at the dot product of each triangle's normals with the view direction. This gets rid of triangles which are facing away from the camera, if the angle is obtuse, since they could not possibly contribute segments to the output. We enforce this by having every triangle consider all three segments that make it up, so that we don't miss edge segments.
The next step is to render the model as triangles. This gives depth data for all pixels which the model covers. What comes next is a little more complicated - the core concept is I keep a small state machine while doing Bresenham's algorithm to draw the lines for each triangle, with duplicates removed. There is a small depth bias applied, so that the segment is definitely kept in front of the model while being drawn. I encountered some artifacts like the one below, where this depth bias is not sufficient. I resolved this by checking how many segments are produced from the evaluation from a given line. If it is above some threshold, I apply a small additional depth bias, and run it again. This will not handle all cases, especially the one where a long line was segmented many times as expected behavior.
The SVG file format is relatively straightforward, it's an XML-based affair that defines all the strokes that make up the image. For my purposes I only need line segments, so it was very straightforward to write with the standard C++ I/O functions. Will update with pictures once I am able to test it on the hardware.