4 different views of our loaded die, represented as a triangle mesh.
Do this project alone or in groups of two, as you prefer.
Due: Friday, September 20 2019 (11:59pm)
File: Mesh(pdf)
Please use the visualization tool for verifying your answers.
Points: 25
Submission: a PDF file upload
Due: Friday, September 27 2019 (11:59pm)
See below
In this assignment you will learn about the most widely used way to represent surfaces for graphics: triangle meshes. A triangle mesh is just a collection of triangles in 3D, but the key thing that makes it a mesh rather than just a bag of triangles is that the triangles are connected to one another to form a seamless surface. The textbook and lecture slides discuss the data structures used for storing and manipulating triangle meshes, and in this assignment we will work with the simplest kind of structure: an indexed triangle mesh.
Your job in this assignment is to write a simple mesh generation and processing utility that is capable of building triangle meshes to approximate some simple curved surfaces, and also can add some information to existing meshes. It reads and writes meshes stored in the popular OBJ file format, a text format with one line for each vertex and face in the mesh.
Suppose we wish to generate a mesh for a loaded die as shown below:
The cube extends from -1 to 1 in each of the \(x\), \(y\), and \(z\) directions. Each face has the following texture applied:
We could represent this mesh by listing out each triangle. Each triangle would be specified by 3 points in 3D space (i.e., the locations of each of its vertices), 3 points in 2D space (i.e., the \(uv\)-space texture coordinates of each of its vertices), and 3 unit-length 3D vectors (i.e., the normals of the surface at each vertex). This is sufficient to represent this mesh, but you may notice that we are repeating some information; for instance, the position of each corner of the cube is shared by at least 3 different triangles. Additionally, each triangle represents a flat surface, and thus the normals at each of its vertices are all equivalent. (Later, we will use triangles to approximate curved surfaces where this is not the case.) We can reduce this repetition by introducing an indexing scheme.
The OBJ file format is one such indexing scheme, and is the one we'll be using in this assignment. In this format, the positions of all vertices are listed first, and then triangles are specified by providing 3 integers that index into this list of positions. Texture coordinates and normals are abstracted similarly; thus, each triangle is specified by 3 position indices, 3 texture coordinate indices, and 3 normal indices.
Vertex Position: A vertex position is specified on a single line by the letter "v" followed by 3 floating point
numbers that represent the \(x\), \(y\), and \(z\) coordinates of the point.
Texture Coordinate: A texture coordinate is specified by the letters "vt" followed by 2 floating point numbers
that represent the \(u\) and \(v\) coordinates respectively.
Vertex Normal: A vertex normal is specified by the letters "vn" followed by 3 floating point numbers
that represent the normal vector. (The OBJ file format does not require that these be
unit length, but we will require it for this assignment.)
Triangle Faces: Triangles are specified with the letter "f" followed by 3 groups of indices.
Groups of indices can be a single integer (indexing the vertex position), two integers
separated by a "/" (indexing the vertex position and texture coordinate respectively),
two integers separated by "//" (indexing the vertex position and vertex normal respectively),
and three integers each separated with a "/" (indexing the position, texture coordinates, and
normals). Please note all indices in the OBJ file format are 1-based!
Vertices should be specified in counter-clockwise order, assuming you are looking down
at the outer surface of the triangle (i.e., the triangle's normal is pointed towards you).
Given all of this information, we can specify the loaded die above with the following OBJ file:
v 1.0 -1.0 -1.0 v 1.0 -1.0 1.0 v -1.0 -1.0 1.0 v -1.0 -1.0 -1.0 v 1.0 1.0 -1.0 v 1.0 1.0 1.0 v -1.0 1.0 1.0 v -1.0 1.0 -1.0 vt 1.0 1.0 vt 0.0 1.0 vt 0.0 0.0 vt 1.0 0.0 vn 1.0 0.0 0.0 vn -1.0 0.0 0.0 vn 0.0 1.0 0.0 vn 0.0 -1.0 0.0 vn 0.0 0.0 1.0 vn 0.0 0.0 -1.0 f 1/1/4 2/2/4 3/3/4 f 1/1/4 3/3/4 4/4/4 f 1/4/1 5/1/1 6/2/1 f 1/4/1 6/2/1 2/3/1 f 2/4/5 6/1/5 7/2/5 f 2/4/5 7/2/5 3/3/5 f 3/2/2 7/3/2 8/4/2 f 3/2/2 8/4/2 4/1/2 f 4/2/6 8/3/6 5/4/6 f 4/2/6 5/4/6 1/1/6 f 5/1/3 8/2/3 7/3/3 f 5/1/3 7/3/3 6/4/3
Note that even though there are 12 total triangles, there are only 8 unique locations for each triangle vertex, so there is no point in listing them multiple times. Similarly, each vertex has only 1 of 4 total texture coordinates, and each vertex has 1 of 6 total normals. This scheme allows us to eliminate the redundancy of listing these values once for each triangle. Also note that many vertices can share a position, but each can have different texture coordinates and normals; for instance, each corner of the mesh is shared by at least 3 triangles, but each may face a different direction and therefore may have its own normal.
For this assignment, we've provide a small library to help you build your utility. It contains data structures for dealing with vectors and meshes stored in the OBJ format.
The math package contains two classes, Vector2 and Vector3, for
dealing with 2D and 3D vectors respectively. They also contain many methods such as vector
addition and subtraction, dot and cross products, and component-wise operators. If you need
to modify a vector in some way, chances are there is already a method that will do what you
want—there is rarely a need to extract the individual components of a vector.
Please be aware that these classes contain in-place methods, even if they return a vector! This means that it is easy to make a mistake like the following:
Vector3 a = new Vector3(...), b = new Vector3(...); Vector3 c = a.add(b); // Don't do this!In the snippet above, the
add() method modifies a and assigns it to c. This
is almost certainly not what you want. Instead, consider the following code:
Vector3 c = a.clone().add(b);This creates a copy of a and modifies it instead, leaving the original a unchanged. This may seem awkward, but it allows for very concise code when performing many successive operations on vectors:
x.add(y).cross(z).normalize();When in doubt, please consult the Javadocs. They're there for your benefit!
The meshgen package contains data structures for operating on OBJ-style meshes.
They are very similar in structure to the OBJ file itself; vertex positions are stored as Vector3s
in an ArrayList, and similarly for vertex texture coordinates and vertex normals. Faces of
the mesh are represented via the OBJFace class, which defines a polygon on the mesh
by listing integers for each vertex which index into the position, texture coordinate, and normal arrays.
This structure allows you to reuse repeated positions, texture coordinates, and normals, which
will come in handy when generating the geometries mentioned above.
The OBJMesh class provides methods for reading and writing OBJ files; thus, to create a mesh, you simply
create a new instance of the OBJMesh class, fill in the appropriate class members, and call writeOBJ().
The class supports both 0- and 1-based indexing, allowing you to either conform to the Java
standard or OBJ standard as you set the mesh data. You can switch between indexing schemes via the indexBase
static variable, which by default is 0. Either way, meshes are automatically converted to 1-based indexing before
being written to file.
Some useful methods include the setVertex() method in OBJFace, which allows you to set the
indices for the position, texture coordinate, and normal for a particular vertex simultaneously. Also of note
are OBJMesh's getPosition(), getUV(), and getNormal() methods, which
retrieve the appropriate vectors from the mesh data, taking the indexing issues mentioned above into account.
To get the basecode, if you already have the course framework repository on your machine, do git pull in the folder "frameworks_cs4620fa19/".
If you don't have the basecode on your machine, you can download it by git clone:
git clone https://github.com/smarschner/frameworks_cs4620fa19Once you have the basecode downloaded, you can find the functions to be implemented in
MeshGen.java.
For this homework, you are going to filled in the code to finish a command line tool MeshGen, it has two main functions:
1. Building a mesh (sphere and cylinders).
2. Generate normals for user-input meshes.
java MeshGen -g <sphere|cylinder> [-n <divisionsU>] [-m <divisionsV>] -o <outfile.obj>or put arguments directly in the Run Configurations:
For this usage, the first required input argument is the geometry specifier, and the second is the output filename. If the geometry specifier is one of the fixed strings sphere or cylinder, a triangle mesh is generated that approximates that shape, where the number of triangles generated is controlled by the optional -n and -m options (details below), and written to the output OBJ file.
A triangle mesh that is an approximation of a smooth surface should have
normal vectors stored at the vertices that indicate the direction normal to the
exact surface at that point.
When generating the predefined shapes, you
generate points that are on the surface, and for each you should also calculate
the normal vector that is perpendicular to the surface at that point.
Additionally, the generated meshes will have texture coordinates. Note that you should take advantage
of the indexed storage scheme where possible; for full credit, you should make sure that
if two triangles meet at a position in space, that position should only be specified once
in the resulting OBJ file. Similarly, if two vertices have both the same location and texture
coordinates, those texture coordinates should only be specified once; if they share the same
location and normal, then the normal should only be specified once. (Duplicate normals and texture coordinates
are allowed, but only as long as they are used at different places on the mesh.)
In this task you will implement functions OBJMesh cylinder(int divisionsU) and
OBJMesh sphere(int divisionsU, int divisionsV).
Those two functions take divisionsU and divisionsV as input, compute the vertices, uvs, vertex normals, and faces, and
store them in an OBJMesh object.
Here is an example of generating a triangle mesh in an OBJMesh object.
// Put three vertices into to the mesh outputMesh.positions.add((new Vector3(0.0f, 1.0f, 0.0f))); // 0 outputMesh.positions.add((new Vector3(-1.0f, 0.0f, 0.0f))); // 1 outputMesh.positions.add((new Vector3(1.0f, 0.0f, 0.0f))); // 2 // Put three uvs into the mesh outputMesh.uvs.add((new Vector2(0.0f, 0.0f))); // 0 outputMesh.uvs.add((new Vector2(1.0f, 0.0f))); // 1 outputMesh.uvs.add((new Vector2(0.5f, 0.5f))); // 2 // Put a normal into the mesh outputMesh.normals.add((new Vector3(0,0,1))); // 0 // initialize an OBJFace object, which represents a face in the mesh OBJFace triangle = new OBJFace(3, true, true); // (number of vertices for this face, hasUV, hasNormal) // set the vertices for this triangle in counterclockwise order triangle.setVertex(0, 0, 0, 0); // (index of vertex in this triangle face, index of the vertex position, index of uv, index of normal) triangle.setVertex(1, 1, 1, 0); triangle.setVertex(2, 2, 2, 0); // Put this triangle into the mesh outputMesh.faces.add(triangle);When the method
OBJMesh sphere(int divisionsU, int divisionsV) is correctly implemented,
you will get an OBJ file of a sphere (16x32) by running MeshGen.java with arguments " -g sphere -n 16 -m 32 -o sphere.obj".
To help you debug your implementation, we also provide a visualization tool;
you can view the generated mesh by dragging the OBJ file to the window, and can select an image to apply a texture to it. (see below under Testing your implementation for details of this tool)
An example result is shown below.
The cylinder has radius \(1\) and height \(2\) and is centered at the origin; its longitudinal axis is aligned with the \(y\)-axis. It is tessellated with \(n\) divisions arranged radially around the outer surface. The two ends of the cylinder are closed by disc-shaped caps parallel to the \(xz\)-plane.
The vertices around the rims of the cylinder share 2 or more normals and texture coordinates, though they share the same positions. Each cap consists of \(n\) vertices arranged in a circle as well as a single point where the cap intersects the \(y\)-axis. This point is incorporated into each triangle that makes up the cap.
Along the cylinder's shell (i.e., excluding its caps), texture coordinates in the \(u\) dimension run from \(0\) to \(1\) in a counterclockwise direction as viewed from the \(+y\) direction. There is a texture seam (where \(u=0\) meets \(u=1\)) along vertices that have a \(z\)-coordinate of \(-1\). Multiple texture coordinates occur at the same position in space to allow this discontinuity. Coordinates run from \(0\) to \(0.5\) in the \(v\) dimension, increasing in the \(+y\) direction. The texture coordinates for the two caps are circles inscribed in the upper-left (for the \(-y\) cap) and upper-right (for the \(+y\) cap) quadrants of the unit square in the \(uv\)-plane, with the \(+u\) direction corresponding to the \(+x\) direction in 3D space, and the \(+v\) direction corresponding to the \(-z\) direction for the top cap, and the \(+z\) direction for the bottom cap. The -m flag is ignored for the cylinder.
The sphere has radius \(1\) and is centered at the origin in 3D coordinates. It is tessellated in latitude-longitude fashion, with \(n\) divisions around the equator and \(m\) divisions from pole to pole along each line of longitude. Note that \(m\) divisions requires \(m+1\) vertices from pole to pole. The North pole is at \((0,1,0)\), the South pole at \((0,-1,0)\), and points on the Greenwich meridian have coordinates \((0,y,z)\) with \(z > 0\).
The mesh is generated with vertex normals that are normal to the exact sphere, and with texture coordinates \((u,v)\) where \(u\) depends only on longitude, with \(u=0\) at longitude 180 degrees West and \(u=1\) at 180 degrees East, and where \(v\) depends only on latitude, with \(v=0\) at the South Pole and \(v=1\) at the North pole. Each quadrilateral formed by two adjacent longitude lines and two adjacent latitude lines is divided on the diagonal to form two triangles.
The texture coordinates along the180th meridian are duplicated: one texture coordinate has \(u=0\) and the other has \(u=1\), to enable the discontinuity required for correct wrapping of a image texture across the seam. The pole has \(n\) different texture coordinates, to enable nearly-appropriate texture in the row of triangles adjacent to the pole. Every other triangle around each pole becomes degenerate, i.e., collapses into a line; these degenerate triangles should be omitted.
The default value of \(n\) should be 32, and the default value of \(m\) should be 16. You may assume that both arguments will always be greater than 2.
If you have your sphere and cylinder correctly implemented, you could attach texture to your mesh in our view tool. Here is an example result for cylinder and sphere.
For this usage, the user provides an input OBJ mesh file, which the program reads in. The mesh is assumed to have no normals (if normals are included in the input file, they are ignored). The program then generates approximate normals at each vertex as described below, and writes the resulting mesh to the user-provided output file.
To run the function with arguments, you can either run following command in terminal:java MeshGen -i <infile.obj> -o <outfile.obj>or put arguments directly in the Run Configurations:
Since the original surface which the mesh approximates is forgotten (if there even was one), we need some way to make up plausible normals. There are a number of ways to do this, and we'll use a simple one for this assignment: the normal at a vertex is the average of the geometric normals of the triangles that share this vertex.
Your first thought might be to do this as a loop over vertices, with an inner loop over the triangles that share that vertex:
for each vertex v
normal[v] = (0,0,0)
for each triangle t around v
normal[v] += normal of triangle
normal[v].normalize()
With the appropriate data structures, this is possible, but in our case there's no efficient way to do the inner loop: our data structure tells us what vertices belong to a triangle, but the only way to find triangles that belong to a vertex is to search through the whole list of triangles. This is possible but would be quadratic in the mesh size, which is bad news for large meshes.
However, it's simple to do it with the loops interchanged:
for each vertex v
normal[v] = (0,0,0)
for each triangle t
for each vertex v around t
normal[v] += normal of triangle t
for each vertex v
normal[v].normalize()
This way the inner loop can efficiently visit just the necessary vertices. Nifty!
There are many opportunities to expand your implementation and receive extra credit. Some ideas are listed below.
A torus is a doughnut-shaped surface defined by a major radius, affecting the size of the hole, and a minor radius, affecting the thickness of the ring. Add torus to the list of geometries generated by your program. Your code should create a torus with major radius \(1\) and minor radius \(r\) (controlled by an additional -r flag with a default of \(0.25\)). Its \(u\) coordinates are like the sphere, and the \(v\) coordinate runs from \(0\) to \(1\) around the inside of the torus, with the direction arranged so that the texture is right-reading from the outside (i.e., the texture is not flipped when mapped to the surface). Like the sphere, it has a seam on the \(-z\) half of the \(yz\)-plane, and it has a similar seam around the inner surface of the doughnut hole; vertices along each seam share a pair of texture coordinates, and single vertex, at the position \((0, 0, r-1)\) where the seams meet, shares 4 texture coordinates.
There are many opportunities to expand your implementation. Some ideas are listed below.
If you implement any of the above options, please provide sample input and/or output with your submission that demonstrates that your code is functioning correctly.
Since your program just writes a file full of inscrutable numbers, you need some way to look at the results. We have provided a mesh visualization tool that works in your browser, available here. To view a mesh, click "Select OBJ File" (or just drag an OBJ file onto the window). If the mesh has texture coordinates, you can upload an image texture by clicking "Select Texture File" (or, again, just drag the image file onto the window). The viewer optionally shows the wireframe structure and vertex normals of the mesh. Coordinate axes may also be displayed; \(+x\) is red, \(+y\) is green, and \(+z\) is blue. If triangle faces are wound in the wrong direction, they appear yellow and will not be textured.
There are a number of additional programs to visualize meshes, for example Blender, ObjViewer, MeshLab, or p3d.in. Be careful, though! Some of these programs add normals to your meshes if they don't already exist, or if they're malformed.
In addition, the OBJMesh class contains the isValid() method to check that your mesh conforms to the OBJ standard, and the compare() method to check if two different meshes are equivalent (ignoring the order in which faces are defined). Thus, another way to verify your code is correct is to compare your output to reference meshes, which are included in the data directory. Reference meshes are given for the cylinder and sphere with default arguments. To receive full credit, your output must be equivalent to ours, and generate no warnings when used with the verbose option. (We will have other reference meshes to test your code against in addition to the ones provided.) In addition, we have provided two meshes without normals (a bunny and a horse), as well as examples of what the meshes should look like when normals have been estimated. Be patient with the horse example, as it contains many triangles and may take a while to process.
For ease of grading, please handin a ZIP file to CMS. The ZIP file should contain the MeshGen.java and a README file that contains:
If there is anything else you would like to put in your solution (e.g., meshes you generated for extra credit, or other implementation in OBJFace.java etc), please place add it in the ZIP file and submit.