NOTE: A Newer version of this tutorial may exist. Click here to go to the never version

<--Back to Projects

COS 426 Assignment #2:Mesh Processing

Chris Tralie
Platform: Windows Vista SP1 Using Microsoft Visual Studio 2005
Assignment Specification

Click here for the binary executables (run from the command line)

Data Structure Description

My data structure setup for this program was as follows:

Transformations and Warps

Random Noise

void R3Mesh::RandomNoise(double noise);
Adds noise of a random amount and direction to the position of every vertex
meshpro -noise 0.01 meshpro -noise 0.1


void R3Mesh::Fun(double omega, double factor);
Do a sine bulge along the z-axis, using the x-axis as the argument to the sine, with frequency omega and amplitude factor.
meshpro -subdivide
meshpro -fun 30 0.2


void R3Mesh::Scale(double sx, double sy, double sz);
Scale the mesh by increasing the distance from every vertex to the origin by a factor given for each dimension (sx, sy, sz).


meshpro -scale 0.5 1 2


void R3Mesh::Rotate(double angle, const R3Line& axis);
Rotate the mesh counter-clockwise by an angle (in radians) around a line specified by a point (x, y, z) and a direction vector (dx, dy, dz).
No screenshot provided, since this one is self-explanatory and not-interesting (and hard to show with a screenshot).
Sample Execution:
meshpro -rotate 1 1 0 0 0 1
Rotates the mesh about the z-axis placed at (x=1, y=1)


void R3Mesh::Inflate(double offset);
Move every vertex by a given offset along its normal direction (this relies first on the successful execution of the compute vertex normals routine). This is as if every point were moved along the gradient of the surface (like moving out to an adjacent level set of an implicit suface).
Original meshpro -inflate -0.01
(This one is technically "deflating" since the parameter is negative)
meshpro -inflate 0.01 meshpro -inflate 0.1 meshpro -inflate 1

Deform According to Point Correspondences

void R3Mesh::Deform(R3Point *source_points, R3Point *target_points, int npoints, double t);
Deform according to point correspondences: Warp the mesh by a deformation defined by point correspondences provided in an ascii file with six numbers on each line: x y z x' y' z'. The position of every vertex in the output mesh should be offset by a Gaussian weighted average of the offsets implied by the point correspondences (x,y,z) -> (x',y',z'). The t parameter should control the "amount" of offset, so that t = 0 gives the original mesh, t = 1 gives the deformed mesh, and other t values interpolate or extrapolate. I chose to use the distance between the points in each correspondence as the width of the Gaussian.
meshpro -deform corr.txt 1 meshpro -deform corr.txt 10 meshpro -deform corr.txt -1

Filtering Operations


void R3Mesh::Smooth(double sigma)
Smooth the mesh by moving every vertex to a position determined by a weighted average of its immediate neighbors (wiht weights determined by a Gaussian function of distance in R3)

Use the equation G(dx,dy,dz, sigma) = e ^ (-(dx^2 + dy^2 + dz^2) / sigma^2), where dx, dy, and dz are the distance of a neighbor point from a central point

meshpro -smooth 5

meshpro -smooth 500


void R3Mesh::Sharpen(double sigma)
Accentuate details in the mesh by moving every vertex away from the position determined by a weighted average of its neighbors (with weights determined by a Gaussian function).
If S is the smoothed position, P is the original position, Pí = P + t*(P-S)

meshpro -sharpen 5

meshpro -sharpen 500

Remeshing Operations

Subdivide Faces

void R3Mesh::Subdivide(void);
Replace every triangle by four new ones. Create a new vertex at the midpoint of every edge, create new triangles between the vertices, and remove the original triangles.
meshpro -subdivide meshpro -subdivide


Compute Normals

void R3Mesh::ComputeVertexNormals(void);
Compute the surface normal at every vertex by taking a weighted average of the normals for the attached faces, where the weights are determined by the areas of the faces (like estimating the gradient of a level surface at discrete points). I take advantage of the fact that every vertex in my data structure points to its neighboring faces.
NOTE: No screenshot or mesh available; this operation is used in the inflate operation.

Geometry Operations

Surface of Revolution

void R3Mesh::SurfaceOfRevolution(const R3Mesh& profile_curve, 
    const R3Line& axis_of_revolution, double rotation_angle_step);
Take the cross sectional area described in profile_curve and rotate it by discrete amounts equal to rotation_angle_step around the line axis_of_revolution until it has rotated by 2PI. Join up each adjacent rotation of the cross section with faces. I relied heavily on my Rotation Routine here.

meshpro -revolution file:profile real:px real:py real:pz real:vx real:vy real:vz real:angle_step
Where profile is a mesh that's only vertices (no faces) describing the cross-sectional area
The axis is (px, py, pz) * t * (vx, vy, vz) for a real number t
angle_step is the discrete rotation between adjacent faces
NOTE: The mesh "" is ignored, but something needs to provided since I didn't get a chance to modify meshpro.cpp enough to deal with just an output mesh.

For this example, I used the cross-section provided in, which is the implicit curve defined by x = cos(a)+2; y = 0; z = sin(a) (a = [1/2*PI, 3/2*PI])
meshpro -revolution 0 0 0 0 0 1 0.1
Rotate around the z-axis, using an angle step of 0.1 radians
meshpro -revolution 0 1 0 0 0 1 0.05
Rotate around an offset of the z-axis this time, and use a smaller quantization for the angle (0.05 radians). Note how it's wider this time because of the placement of the rotation axis.
meshpro -revolution 0 0 0 1 0 0 0.1
Rotate around the x-axis with a quantization of 0.1 radians

Surface Sweep

void R3Mesh::SurfaceSweep(const R3Mesh& crosssection_polygon, const R3Mesh& centerline_curve);
Take a cross-sectional area, provided in a mesh crosssection_polygon, and move it along the curve specified by another mesh, centerline_curve, to sweep out a surface from that area. In order for this to work and to have the right volume, the cross-sectional area needs to be rotated each time

In order to figure out how to rotate the cross-sectional area in each successive application of the sweep, I had to keep track of vectors that represented changes between points in the centerline curve. Taking the cross product of two of these successive vectors (v1 X v2, as shown in the picture above), gives the axis of rotation. Then, the angle between them gives the amount by which to rotate about that axis (I used the dot product to figure out theta).

I used the same cross-sectional area as in the surface of revolution, except I moved it across a line this time instead of rotating about an axis
NOTE: Once again, providing "" as the input mesh is garbage, because the input mesh is simply ignored (the mesh is constructed from other paramters; namely, the cross-section area and the curve along which that area moves)
NOTE ALSO: The cross-sectional area is in, and the sweep line is in
meshpro -sweep


void R3Mesh::Fractalize(int nlevels);
Create fractal detail by recursively subdividing every triangle of an input mesh into four (as in the Subdivide feature) and moving every new vertex by a random offset vector (as in the Random Noise feature) with magnitude proportional to the original edge length.
meshpro -fractalize
Original planar surface (after applying subdivide many times to one square to make the file
meshpro -fractalize

Topological Fixup

Fill Holes

void R3Mesh::FixHoles(void);

Create triangles covering the holes of a mesh by connecting vertices on the boundary of every hole. Find holes by detecting a loop of edges that only have one face on them.
I created the following algorithm to do this:
  1. Loop through all of the edges until an edge with only one neighboring face is found
  2. Create an STL vector object that holds vertices, and add the first two vertices of that edge. Call them v1 and v2.
  3. Get a list of all of the neighboring vertices of v2. If any of the edges between v2 and its neighbors have only one face attached, then add the neighbor to the set, and repeat the process for that vertex (recurse out)
  4. If at any point in time, a neighbor vertex of the last vertex added is equal to the first vertex, that means the loop has been completed. Create a new vertex that's a weighted average of the loop vertices, and create faces between all of the loop vertices and that new center vertex
  5. The recursion process will terminate when a hole has been filled, and the entire process will finished when all edges are checked

meshpro -fixholes

The surface of revolution I made has gaps at the top and the bottom. I used this algorithm to close that surface

meshpro -fixholes

Miscellaneous Operations

Creat a Mesh from an Image

int R3Mesh::ReadImage(const char *filename)

Create a mesh from a 2D image, with the x and y axes representing the pixel position in the image, and the z axis representing luminance of each pixel.

meshpro -image chris.jpg

meshpro -image gaussian.jpg

Art Contest Submissions

Expected Point Earnings

Bold means required
Random Noise1
Compute Normals2
Surface of Revolution2
Surface Sweep2
Fill Holes2
Create Mesh from Image2
Art Contest Submission1

<--Back to Projects