Below are a list of tips for doing project #2. Here's a quick access list:
You may find the Standard Template Library (STL) useful for managing some of your data structures like queues, hash tables, and dynamic arrays (for the growing list of vertices and triangles).
Dynamic arrays can be implemented with the Vector template. Once you've built a Vector of vertices or triangles, you'll need to copy it into the Mesh data structure. Don't forget to set the numVerts and numTris variables in that data structure. For the Vertex data structure, you only need to copy in the "coord" field, though you can copy in the normal into the "norm" field if you happened to compute it (scanalyze will guess reasonable normals if you don't supply them).
Hash tables do not actually appear to be standard in STL. You can instead use a "map" data structure, or you can use the "hash" function supplied with SGI's version of the STL. You can construct your index into the map or hash table using the i,j,k coordinates of a cube. The i,j,k coordinates can be computed by setting the seed cube coordinates to 0,0,0 and computing i,j,k's relative to that origin. Negative i, j, or k shouldn't be a problem.
Try to divide the work among your team members so that each of you can test your component independently of the other. One possible division of labor would be to have one person work on evaluating weighted signed distance values (WSD) and the other to implement the marching algorithm.
As noted in the pseudocode/detail page, you can test the success of your range image resampling by converting the resulting depth map into a range grid with DepthMap::buildRangeGrid(), followed by writing it to a ply file. In addition, you should be computing the weight at each depth map location and storing it in the "conf" field of the depth map. The ply file will get written with this confidence information. You can then look at the file with scanalyze and select "Render->Confidence" and "Render->Emissive". After increasing the resolution, the red-white shading should resemble the confidence image shown in lecture.
To test the weighted signed distance evaluator, create a low resolution volume and evaluate the weighted signed distance (WSD) at each voxel in the volume. One tricky part is to set up the right volume dimensions and origin. To get this right, you need to compute a bounding box that encompasses all meshes. One simple thing to do is to create a BBox3f object and then grow the bounding box with BBox3f::update() by passing it each range grid point transformed by the scanalyze .xf transformation. Once you have the object bounding box, you can allocate a volume based on a desired resolution, and compute WSD's at each voxel.
You can then visualize the result by creating a Mesh object that contains the coordinate of each voxel that has a neighbor of opposite sign. After writing the mesh to a file (with no triangles, which is fine), you can load it into scanalyze and do "Render->Points" and "Render->Emissive" to look at the pseudo-reconstruction.
Testing the marching cubes code can be done in two phases. In the first, you can test out the triangle extraction by creating a simple volume with a signed distance (e.g., the closest signed distance from the surface of a sphere) and then processing each cube. The result will be a triangle mesh that doesn't have shared vertices.
In the second phase, using the same volume or an evaluator of the signed distance to a sphere, you can test out the marching algorithm that walks the surface using a cube queue and hash table.
As noted in the pseudocode, you can compute the weight variations due to sampling rate using normals and gradients of the depth map. The gradient of the Z value will give you dZ/dx and dZ/dy and can be computed by simple finite differences in the x and y directions, respectively, or by using a gradient operator with larger support, such as the Sobel operator (see, e.g., the 457 or 557 lecture notes on image processing). The question remains as to how to convert this gradient into a weight based on the dot product of the normal with the viewing direction.
Here's one way to think about this. The derivatives are tangent to the surface, Z(x,y). These derivatives point in the directions (1, 0, dZ/dx) and (0, 1, dZ/dy). The normal is formed by the cross-product of these two tangent vectors:
n = (0, 1, dZ/dy) cross (1, 0, dZ/dx) = (dZ/dx, dZ/dy, -1)
(dZ/dx, dZ/dy, -1)
n = -------------------------------
sqrt[(dZ/dx)^2 + (dZ/dy)^2 + 1]
Dotting with the viewing direction, (0,0,-1), we get:
1
n dot v = -------------------------------
sqrt[(dZ/dx)^2 + (dZ/dy)^2 + 1]
So, for a flat surface facing the viewer, dZ/dx = dZ/dy = 0, and the weight is one. As these derivatives increase, the weight decreases as
expected. In general, it can be convenient to raise this weight to an
exponent, i.e., use (n dot v)^k, where k is a number like 1 or 2.
Important: if any of the voxels in a cube have a WSD that actually has zero weight associated with it (making the WSD meaningless), you should generate no triangles for that cube. For this reason, the hash table should contain cubes that know both the WSD's of the voxels and the sum of weights of the voxels (or at least a flag denoting an "invalid" voxel). If you do this correctly, your mesh will not continue into regions where there is no data, which is what you want.
The marching cubes code has fields for "value" (which corresponds to WSD), as well as "confidence", "intensity", and "matDiff". To get your code to work, you only need to worry about getting a WSD into the value field. If your scanner returns intensity (e.g., for a grayscale scanner) or color data, then you could, if you like, blend this data when computing weighted signed distances and interpolate it when computing new vertices.
In any case, you do have weight information, which is synonymous with "confidence", so you can optionally store the sums of weights at each voxel in the confidence field and interpolate it across edges. Scanalyze can render the confidence over the mesh, but it's expecting the confidence to lie in the range [0.0..1.0]. To achieve this, you should divide the sum of weights by the total number of scans that were input to the reconstruction algorithm.
Note that in order to save any of this extra data in the mesh file, you will have to set the appropriate flag with the mesh, i.e., hasConfidence, hasIntensity, hasColor, all of which are set to zero by default. Generating any of this extra information (confidence, intensity, color, and normal) are all optional.
For some reason, this has not caused trouble in the past, even when writing to the 256th element in edgetable.cpp. Evidently, it hasn't caused any trouble in this class as well, but it's best to play it safe.