Figure 1: conics.15887.pts data	Figure 2: kd-tree	Figure 3: tangent plane normals
Figure 4: mechpart.4102.pts data	Figure 5: kd-tree	Figure 6: tangent plane normals

1. Read in a list of 3D points (x_i = (x,y,z))
2. Use the conics.15887.pts or mechpart.4102.pts input file (see Figure 1).
3. Find the point cloud bounding box: two points min and max with the minimum and maximum coordinates of the point cloud, respectively.
4. Create a kd-tree on the points (see Figure 2).
5. For each point x_i compute its tangent plane esimate Tp(x_i):
   1. Obtain Nbhd(x_i), the k-nearest neighbours of point x_i; use k = 5.
   2. Calculate the mean o_i of Nbhd(x_i).
   3. Perform Principal Component Analysis on each Nbhd(x_i) by calculating and sorting the eigenvalues & eigenvectors of the neighborhood.
   4. Set the normal n_i to the eigenvector associated with the smallest eigenvalue: the normal represents the orientation of the tangent plane at the neighborhood centroid, or origin, or mean, o_i (see Figure 3).
   5. Store all of Nbhd(x_i), o_i, and n_i in an instance of a new TangentPlane object, and add its pointer to a list (STL vector) of pointers to TangentPlane.
6. You now should have a list of tangent plane estimates at each point: Tp(x_i).
7. Output your normals to a plain text file in the following format:
   o₀
   n₀
   o₁
   n₁
   ...
   o_n
   n_n
   where each o_i, n_i is the center and normal of tangent plane Tp(x_i).
8. Sample output can be found here: conics.15887.tp.
9. You can view your output with the kdtree program. Load your tangent plane file and then check the "Normals" checkbox in the View menu. The program was last compiled on a Linux PC running Fedora Core 3 with g++ v3.4.3 and so should run on most of the FX net Linux boxes (but not on the Suns).
   Usage:
   • left mouse: move camera in xy-plane (up/down, left/right)
   • scroll mouse: truck in and out (along camera's view-axis)
   • CTRL-left mouse: yaw/pitch camera
   • CTRL-scroll mouse: roll camera

1. README file containing assignment and solution descriptions, e.g., program design, description of algorithm, etc., if appropriate.
2. INSTALL file containing any specific compliation quirks peculiar to your program, e.g.,
   Compilation: make.
3. USAGE file containing any specific usage quirks peculiar to your program, e.g.,
   Usage: ./phase1 < conics.15887.pts where ./phase1 is the executable and conics.15887.pts is the input.
4. src/ directory with source code.