In the previous homework you learned how to generate 3D clouds of points from a pair of 2D data sets. In this homework, you will generate meshes from the clouds of points. You will save the meshes in Inventor and/or VRML format. Read through the whole text before starting to work.

In order to create a mesh you have to find a way of connecting neighboring points with edges to form triangles. Finding neighboring points can, in general, be a complicated matter. Fortunately, the very way we generated the points provides neighborhood information. The data sets are scanned using a projector and a camera (gray coding method). This means that in the projector view, the left view, the X_p coordinates represent the point's stripe number, while in the camera view, the right view, the Y_c coordinate represents the row number in the view. Both are integers as you can easily verify yourself. The pair {X_p, Y_c} gives a natural parameterization of the mesh. In this parameterization, the point {X_p, Y_c} has at most four neighbors: {X_p-1, Y_c}, {X_p+1, Y_c}, {X_p, Y_c-1}, {X_p, Y_c+1}.

Task 1: Prove to yourselves that this parameterization correctly represents neighborhood relationships between points in the 3D data set.

You will have to modify the MATLAB code you wrote last week to generate an ASCII ".range" file. Range files organize points according to the parameterization described above. The format of a range file is summarized below:

Note that Xr, Yr, and Zr are the 3D coordinates that you generated using triangulation. Nrow is the maximum of Y_c, while Ncol is the maximum of X_p. You will place these on the first line of the range file. The next Ncol lines will contain the Xr, Yr, and Zr of the points from {0,0} to {Ncol,0}, the next Ncol line will contain the Xr, Yr, and Zr of the points from {0,1} to {Ncol,1}, and so on.

If you don't have data for a give pair of {X_p, Y_c} you will write Xr = Yr = x, and Zr = x.

It is useful to normalize the coordinates before writing them out into the range file. Normalization consists in translating the points such that the cloud's center of gravity is translated into the origin and then scaling such that the absolute value of the coordinates is less then one. You will not do any scaling at this point. Also, you should not normalize {x, x, x} values.

Here is an example:

236 246
x x x
x x x
x x x
x x x
x x x
x x x
1.39352 -8.28044 6.95516
1.45983 -8.27747 6.90222
1.5566 -8.27831 6.91911
1.62074 -8.27508 6.86122
1.70058 -8.2738 6.83921
1.74504 -8.26812 6.73656
1.83091 -8.2676 6.72831
1.89218 -8.26402 6.66409
1.97433 -8.26304 6.64729
2.04026 -8.26004 6.59374
x x x
x x x
x x x
x x x
x x x
x x x
x x x
5.37078 -8.48754 10.7455
5.42981 -8.48334 10.6689
5.49309 -8.47965 10.6017
5.53959 -8.47396 10.498
5.6085 -8.47097 10.4434
...

This file format is used later by the alignment and volume carving tools so make sure you get it right.

Task 2: Modify your code to write out a range file at the end of the triangulation procedure (with normalization, translation only).

You will also have to produce a ".params" file. The format for a params file is summarized in the following table:

Here is an example:

# Scale and translation from range date to camera frame (cm)
src 1.00000000
trc -4.65601512 -1.59718542 172.60735398

# Rigid body motion from camera to projector
tcp 76.80637107 -17.74639690 -35.14276573
rcp
0.88839168 0.09715148 -0.44868898
-0.02649762 0.98657392 0.16115139
0.45832095 -0.13127636 0.87903835

# Intrinsic camera parameters
kcam -0.44153276
fxcam 2689.85483872
fycam 2539.68919704
cxcam 319.50000000
cycam 239.50000000

# Intrinsic projector parameters
fxprj 1495.21893057
fyprj 1208.35520126
cxprj 319.00000000
cyprj 239.50000000

# Origin of area of interest in the (xpimg,ycimg) grid
rngx0 128
rngy0 88

Lines beginning with a # are comments.

Task #3: Modify the triangulation program to generate params files as well.

Now that we have neighborhood information in the range files you will write code to generate meshes from these files. Given that a fair amount of processing is required to generate a mesh we recommend the you write your program in C or C++.

As you will see, there are lots of missing points in the range files ( of form {x, x, x}). There are three causes for that:

• The projector didn't see an object there
• The camera didn't see an object there
• You failed to identify the object due to noise

In the first two cases the hole is legitimate and should be left untouched. In the third case you should try to fill it up using interpolation from the neighboring points. You will have to decide which case applies to a specific point. Hint: look at the number of missing points in the neighborhood.

After you've dealt with holes, you can go ahead and generate a mesh. This is done by looking at all combinations of quadruples {X_p,Y_c}, {X_p+1,Y_c}, {X_p,Y_c+1}, {X_p+1,Y_c+1} and connecting one of the diagonals. An easy way of deciding which diagonal to connect is to always pick the shorter of the two. A better way is to use a curvature minimizing method.

Your program will output meshes in ASCII Inventor and VRML formats. The only difference between the two is the first line:

#Inventor V2.1 ascii

for Inventor,and:

#VRML V1.0 ascii

for VRML.

Except for the first line, lines starting with # are comments.

Files in these formats describe a tree structure. For the `inner nodes' of the tree (nodes that have descendents) the syntax is:

Separator {

.... descendent nodes ....

}

The leaf nodes may be property nodes (color, texture, coordinates for vertices, translations, rotations, etc) or shapes (cone, cylinder, cube, sphere, triangle mesh, ...). A property node affects all shape nodes that come after it in the scope of its parent "Separator" node (all shapes that come after the closing bracket of that Separator node are not affected by the property.) To define a triangle mesh, you must give the 3D coordinates of the vertices and then tell Inventor how to connect the points. To specify coordinates, use the Coordinate3 property node. The syntax is:

Coordinate3 {

point [

}

You instruct Inventor to draw your mesh and specify the point connectivity using the "IndexedFaceSet" shape node:

IndexedFaceSet {

coordIndex [

}

where v01, v02, v03 are the indices of the vertices of the first triangle, v11, v12, v13 are the indices of the vertices of the second triangle, and so on. The indexing starts at 0 (vertex 0 has 3D coordinates (x0, y0, z0)). IndexedFaceSet works with polygonal faces (not only triangular); -1 is used to tell Inventor that the vertices for a particular face are over. Be aware that the order in which you enumerate the vertices matters (it gives the orientation of your triangle: the winding should be counter clockwise when looking at the face of the triangle.)

Your complete Inventor file should look something like this:

#Inventor V2.1 ascii

Separator {

Coordinate3 {

}

IndexedFaceSet {

}

Save the file in a ".iv" file for Inventor format, or a ".wrl" file for VRML. You can view your meshes using ivview for Inventor on SGI machines, or Netscape for VRML.

Task #4: Write a program that takes a range file and generates a mesh in Inventor and VRML formats. Fill holes where appropriate. Use the shortest diagonal method.

Task #5: Write another program, similar to the previous one, but that generates meshes using curvature minimization.

Task #6: Download the three data sets in www.multires.caltech.edu/teaching/courses/3DP/hws/hwk2/ and run your programs on them. You should turn in the ".iv" and ".wrl" files. This should be a pointer to their location on the web. The three stereo pairs are: