Programming Project 05
Computational facial recognition is growing. Starting with the iPhone X it has even available on smartphones. In this project we examine some of the mathematics behind it. Some of the initial research in facial recognition was by Dr. Anil Jain here at MSU.
Use of advanced data structures such as lists, sets, and dictionaries are prohibited.
In the field of Computer Graphics, creating and handling shapes is fundamental. Any shape can be represented by what is called a polygon mesh—a collection of vertices, edges and faces that define the shape. A triangle mesh is a common type of polygon mesh where each face is a triangle. The vertices are the points of the shape in 3d space. Each vertex has x,y and z values representing its location in Euclidean space. The vertices are connected by edges that form the triangles. Figure 1 shows an example of triangle mesh representing a dolphin.
Figure 1 Triangle mesh (Wikipedia)
Figure 2 shows the vertices, edges and faces of a cube represented by a triangle mesh. The vertices are the points of the mesh, the edges are the lines connecting two vertices, and the faces are the triangles that are parts of the surface connecting 3 vertices.
Figure 2 vertices, edges and faces of a cube (Wikipedia)
Each face of the triangle mesh is a triangle, that contains 3 vertices and 3 edges. Any two faces of the mesh are connected by only one edge. There are many of geometrical properties we can compute for mesh triangles. The face normal is the perpendicular vector of the plane that this triangle is part of. Figure 3 shows the meaning of face normal. In the figure, the triangle has 3 vertices a, b and c.
Figure 3 Face normal
To compute the normal of this face (triangle), we need to specify the coordinates of the two sides, side 1 that connects the vertices a and b, and side 2 that connects the vertices a and c. For example, if point a has coordinates (a1, a2, a3) and point b has coordinates (b1, b2, b3) . The coordinates of the vector ab representing Side 1 are (b1- a1, b2 - a2, b3 - a3) .
The normal is the cross product of the two sides. The cross product is a mathematical operation that finds the perpendicular vector of two vectors (note that the × symbol stands for cross product, not multiplication). The cross product is defined as follows:
æ v1 ö æ w1 ö
Let’s assume that we have two vector v and w: ç v ÷ and ç w ÷ . The cross product between v and w is:
ç 2 ÷ ç 2 ÷
ç v ÷ ç w ÷
è 3 ø è 3 ø
æ v2w3 - v3w2 ö
v ´ w = ç v w - vw ÷
ç 3 1 1 3 ÷
ç vw - v w ÷
è 1 2 2 1 ø
Another property that we can compute is the area of a face (triangle). Figure 4 shows the meaning of face area. In the figure, the triangle has 3 vertices a, b and c. We need to specify 3 sides, side 1 that connects the vertices a and b, side 2 that connects the vertices a and c, and side 3 that connects the vertices b and c. Then, we need to calculate the distances (ab, ac, and bc) between the vertices. The distance between two points in a three dimensional - 3D - coordinate system can be calculated as:
d =After that we calculate the area using Heron’s formula :
Area =p ( p - ab)( p - ac)( p - bc)
p = ab + ac + bc
Figure 4 Face area
There are many ways to store the mesh data, the coordinates of all vertices and the vertices of each face should be all listed in the file. In this project, we will use .off data files with the following format:
500 1000 0
3 496 493 88
the first line in the file is the word “off” which is the file format. The second line contains three fields where each is 5 characters wide (right-justified, digits only): the first field is the number of vertices, the second field is the number of faces, and the third field is number of edges. We only need the first two numbers. In this example, we have 500 vertices and 1000 faces. The following lines contains 3 fields where each is 15 characters wide (right-justified): these are the coordinates of all vertices (3 floating numbers represent x,y and z of each vertex). For example, the first vertex has the coordinates x= - 12.621730, y= 17.675560, z= -21.116800. Each vertex should have an index starting from 0. So, the first line is the coordinates of vertex 0 , then next line has is the coordinates of vertex 1 and so on.
Similarly, each line representing a face contains the number 3 then the indices of the vertices of that face. So, the first face has the vertices 0, 4 and 1. The second face has the vertices 1, 2 and 0 and so on. Each line in the face data contains 4 fields with length 2, 5, 5, 5 characters wide (right-justified), respectively
In this project, we open the off file for reading the mesh data. Then we compute some geometrical features of the mesh. The field width specification defined above allows you to use slicing to extract values from each line.
Your code should include at least the following functions:
1. open_file() --------à fp :
This function takes no parameters, and then uses the try-except format to prompt for a filename, open the data file and return the file pointer if successful. Your function should be able to catch the error and print the error message if it fails to open; and then reprompt. It will reprompt until successful.
2. read_face_data(fp, index) ---à int, int, int:
This function takes as an input:
This function should return the indices of the 3 vertices that makes the face which are of type int. Note that sometimes you will be in the middle of the file and you want to access lines on the top. In this case the method fp.seek(0) could be used (see note below).
You should skip the first word of the file using readline() function. The second line has the number of vertices and the number of faces of this mesh. The faces indices starts from 0. In the previous example, we have 500 vertices and 1000 faces. That mean the next 500 lines contain the vertices coordinates, and the following 1000 lines are for all faces. The field width specification defined in the background allows you to use slicing to extract values from each line. Hint: loop until you find a line starting with the number 3 that indicates the start of the face data; then start counting indices.
3. read_vertex_data(fp, index) ---à float, float, float:
This function takes as an input:
This function should return the coordinates of the vertex which are of type float. The field width specification defined in the background allows you to use slicing to extract values from each line. The indices of the vertices starts from 0. Hint: use multiple fp.readline() to skip the first two lines and then for i in range() to skip to your desired index.
It should return the 3 coordinates of cross-product as floats rounded to 5 digits.
5. compute_distance(x1,y1,z1,x2,y2,z2) ----à float:
This function computes the Euclidian distance between two points. It takes as inputs:
It should return the distance as a float rounded to 2 digits.
The Euclidean distance D between two points A and B with coordinates(x1,y1,z1) and
(x2,y2,z2), respectively is computed as follows:
𝑫𝑫 = �(𝒙𝒙𝒙𝒙 − 𝒙𝒙𝒙𝒙)𝒙𝒙 + (𝒚𝒚𝒙𝒙 − 𝒚𝒚𝒙𝒙)𝒙𝒙 + (𝒛𝒛𝒙𝒙 − 𝒛𝒛𝒙𝒙)𝒙𝒙
This function takes as inputs:
You should first find the vertices of the face from the mesh file using the face_index and the read_face_data function. That function returns 3 vertices. You can capture the three vertices returned from the functoion like this:
first, second, third = read_face_data(fp, face_index) You will find the normal at the first vertex. For each vertex you need their three coordinates; read_vertex_data can be used. Note that to calculate the normal vector, you need to calculate the coordinates of the sides first.
The vector components (vector coordinates) through two points (initial and terminal points) in three-dimensional space is calculated as the difference between the coordinates of each point. For example, if A and B are the initial and terminal points with coordinates (x1,y1,z1) and
(x2,y2,z2)respectively, the coordinates of vector AB are:
Find the vectors of the two sides and then take their cross product using your compute_cross
7. compute_face_area(fp, face_index)----à float:
This function calculate the face area. Figure 4 explains how the face normal is computed. It takes as an input:
It should return the area of the face which is of type float rounded to 2 digits. The function
compute_distance() is useful in this function.
8. is_connected_faces(fp, f1_ind, f2_ind) -------à Boolean:
This function checks if two faces are connected. Two faces are connected if they share 2 vertices. So you can expect that each face might be connected with three other faces, one for each side.
The function takes the file pointer and the faces’ indexes and checks if they have two common vertices. The function returns True if the two faces are connected, or False otherwise.
This function takes as an input:
9. check_valid(fp,index,shape)-----à Boolean:
This function checks if the face or vertex index is valid. It takes as input:
In the main function, use the nine (9) functions above to complete the mission!
When the program starts, a welcome message is displayed. Then call the open_file()
function to open the mesh file. After that, display the menu and ask to choose one option from it:
1- display the information of the first 5 faces 2- compute face normal
If the choice is not valid, display an error message and reprompt until a valid choice is entered. A choice is valid if it is an integer and between 1 and 7.
DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma
Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t
Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th
1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of
1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of