Computational Geometry Final Project

Jonathan Pompa

Project Objectives

The overall objective of this project is to take a three dimensional wireframe and make it into a three dimensional surface mesh. The process by which this will be accomplished is:
  • Read in Frame Data
  • Determine the mean direction of the plane
  • Rotate the frame so that its mean is orthogonal to the X-Y plane
  • Project the frame onto the X-Y plane
  • Draw a mesh inside the polygon
  • Move the mesh up inside the original 3D frame

    • Actual Results

    Rotating the Frame

    Assuming the data comes as points oriented around the frame in a counter clock-wise direction, the points are read in from a file which is simply a list of points. The data is stored in a linked list of structs. Each node holds an x, y, and z coordinate and a pointer to the next node. The head holds data but the tail does not. The tail is linked to itself to provide a stopping condition in a search.

    These are VRML representations of the data. They are shown as the original data (red), as the rotated frame(green), and as the projection on the X-Y plane(black).

    Frame 1
    Frame 2
     
     

    Determine the direction

    Traveling around the frame, the vectors from each point to its neighbors are calculated and used to compute a cross product. The sum of all of the cross product vectors is kept as the frame is traversed. Since the cross product vector is orthogonal to the plane containing two vectors, each vector represents the perpendicular to the plane at a particular point. Longer vectors carry more weight in the sum because they form longer cross vectors. This allows an "average" vector orthogonal to the frame to be found.

    The code for this works well and has been written to inclue all points, wrapping around the head/tail of the list.

    Rotation and Projection

    The Cosine of an angle is unique between zero and Pi and between zero and -Pi. Using this fact, the program takes the vector and calculates its angle relative to the z axis. First, if the z component of the vector is positive, the program rotates the vector so that it is parallel with the positive z axis and it rotates it parallel to the negative z axis if the vector starts pointed downward. This deals with the mirror effect of the cosine curve.

    The program first determines the angle from the vector to the z axis on the Y-Z plane and finds the sine and cosine of that angle. It then multiplies the vector of each point in the list by the rotation matrix to align it with the z axis. The process is repeated for rotation about the Y-axis. When this is done, the mean normal vector of the frame is parallel to the Z-axis. The frame can then be projected onto the X-Y plane by ignoring the Z component of the coordinates. Everything to this point was done in a program called "3d2d"

    Meshing

    I originally intended to just copy the "tri.c" code into my program to do the meshing of the polygon now projected on a plane. This did not prove practical because the tri code uses a different data structure than I had. I did not want to go through every function of tri to convert it to my data structure so I decided to leave it as a separate program. I modified it to use the incoming data from my 3d2d program and changed it to output just a list of points and triangles. This output acts as the seed for my meshing program which stands separately.

    The meshing program is called "mesh". It takes the argument "datafile" as both of the other programs do. They all take care of their file extensions and name alterations. The drawback of having three programs is having many datafiles in a directory after they run and having to type three things to get a result. The advantage is not having to rewrite the tri.c code and being able to debug code that is approximately 1/3 as long.

    The method of meshing is simple. A maximum line length is specified in the program and it is used to check against every edge of every triangle of the triangulation. If an edge exceeds the maximum length, a point is added at the midpoint of the edge. That point is connected to the opposite vertex of the triangle and the original triangle is broken in two. The triangles are stored as a linked list so a new one can be added easily. Each of the new triangles is then checked again for edge lengths. The points are stored in an array so that they are easy to index. They are referenced by the triangles by number so that the triangle vertex connections are independent of the point coordinates. This is done to help with the later mesh refinement.

      
    This is the series of transformations that occurs to make a mesh.

    The Mesh generation algorithm works when the maximum length is large. I have a logic problem in the code which causes the meshing to become unstable when long thin triangles are encountered. The size at which this happens is different for every polygon and is not predictable.

     
    This is something I will have to fix.

    Mesh Optimization

    This is the "youngest" part of my code and is incorporated into the mesh program. It takes each point that has been added by the mesh algorithm and moves it to the geometric average of the distance to all of its neighbors. This is not a good energy minimization model but it works for a quick test of the rest of the code. The process is repeated until all of the points stop moving then the resulting mesh is printed in a VRML file.

    This all works well if there were no boundary points added during the meshing. The program recognizes the original points of the frame as immobile but it thinks all added points can be moved in relation to their neighbors. When an edge is too long, the meshing program adds a new point to the boundary, preserving the shape but creating smaller elements. This makes the boundary mobile and leads to some problems with mesh optimization.

     
    No edge points were added here.
     
    Oops! Edge points should be stationary.

    The problem will be easy to fix by adding another element to the points data structure. This will be a flag identifying points that are on the boundary and excluding them from the optimization process. The points can be found easily because they all are on lines that are included in only one triangle. Interior points are included in lines that belong to two triangles.

    Progress from Tuesday to Thursday

    I have fixed these problems. The boundary points are immobile as the mesh is generated and the mesh is now built by maximum area instead of maximum length. This seems to eliminate the long skinny triangles. I have also gone to an iterative point adding process where the program adds points, smooths the mesh and then checks again to see if it needs to add points. The mesh is not pretty, but it turns out reasonably smooth for a first try. Here are some examples in 2D.
     
    These are much better than before and the mesh size can be arbitrarily small.
    I can now work in 3D and here are some examples. They look like minimum area skinning of a surface.
      
    3D Plane
      
    3D Pyramid
      
    3D Notch
     

    Running the Program

    I'm sorry this is not all one program, but I did not leave myself time to convert the code in "tri.c" to my data structure and incorporate it into the program. The process of meshing this thing is accomplished by running three programs in series.
    Requirements are a data file with a list (in three dimensional coordinates) of points around a frame, and the programs 3d2d, tri, and mesh. The mesh size can be adjusted by changing the value of MAXAREA in the mesh program.
    To run this type:
    ./3d2da "datafile"
    ./tri "datafile"
    ./mesh "datafile"
     
    The output can be seen as a VRML file called "datafilemesh.wrl"
    email jp8p+@andrew.cmu.edu