Assignment 1

Fabian Prada

Part I

1)STL Data Structures

stlTriangle: This class stores the coordinates of the vertices for a single triangle.

Attributes

(int) Index: This is the position of the triangle in the Triangle list.

(float) Coordinates: x_1,y_1,z_1;x_2,y_2,z_2;x_3,y_3,z_3. Stores the (x,y,z) position of each of the vertices V_1,V_2,V_3 respectively.

stlTriangulation: This class stores the required attributes of the triangulation.

Attributes

(int) Number of triangles.

(stlTriangle[Number of triangles]) Triangle List: Store a pointer to each triangle.

2)STL Implementation

Initialization

The initialization is done from a octahedron triangulation (T(0)). This triangulation contains 8 triangles. Each triangle knows the values x_1,y_1,z_1;x_2,y_2,z_2;x_3,y_3,z_3 of its vertices coordinates.

Subdivision

Input: Triangulation T(i) where all attributes are initiallized.

Step 1: Create a new Triangulation object T(i+1) that will store a new Triangle list. This new Triangle List stores 4 times the number of triangles of T(i).

Step 2: For each triangle in T(i) calculate its midpoints and project them to the sphere. Let M_1 be the normalized midpoint of V_1V_2, M2 the normalized midpoint of V_2V_3, and M_3 of V_3V_1. Add to the Triangle List of T(i+1), the triangles (V_1,M_1,M_3);(V2_M_2,M_1);(V_3,M_3,M_1); and (M_1,M_2,M_3).

Step 3: Once all the traingles of T(i) have been processed, the triangulation T(i+1) is complete and we can return to step 1 to refine the subdivision.

Part II

1)OFF Data Structures

Triangle: This class stores the attributes of a single triangle.

Attributes

(int) Index: This is the position of the triangle in the Triangle list.

(int) Vertices: V_1, V_2, V_3. These values stores the position of each of the triangle's vertices in the Vertex List. Vertices V_1, V_2 and V_3 are always in positive direction according to the outher normal of the sphere.

(int) Neighbour Triangles: t_1, t_2, t_3. These values stores the position of the neighbour triangles in the Triangle List. The value t_1 always refers to the neighbour triangle adjacent to edge V_1V_2, t_2 is always adjacent to V_2V_3, and t_3 is always adjacent to v_3V_1.

(int) Midpoints: M_1, M_2, M_3. These values stores the position of each of the triangle's midpoints in the Vertex List. The point M_1 is always the midpoint of V_1V_2, t_2 is always midpoint of V_2V_3, and t_3 of V_3V_1.

Triangulation: This class stores the main attributes of the triangulation.

Attributes

(int) Number of triangles.

(int) Number of vertices.

(Triangle[Number of triangles]) Triangle List: Store a pointer to each triangle.

(float[Number of vertices][3]) Vertex List: Stores the coordinates x,y,z of each vertex.

2)OFF Implementation

Initialization

The initialization is done from a octahedron triangulation (T(0)). This triangulation contains 8 triangles and 6 vertices. For each triangle, the values V_1,V_2,V_3,t_1,t_2, and t_3, are stored satisfying the orientation criteria explained above. The values M_1,M_2 and M_3 are set to -1, to indicate they are not initialized yet.

Subdivision

Input: Triangulation T(i) where all attributes are initiallized, except by the midpoints of the triangles.

Step 1: Create a new Triangulation object T(i+1) that will store a new Triangle list and a new Vertex List.

Step 2: Copy all the elements in the Vertex List of T(i) to the vertex list of T(i+1).

Step 3: Proccess each triangle of T(i).

Each triangle in the Traingle List of T(i) is proccesed once. When a triangle is proccessed it ask to its midpoits if they are already initialized. If a midpoint is not initialized it is added in the last position of the Vertex List of T(i+1). Then, the triangle which is proccessed tell to the concerned neighbour (in T(i)) to update the index of the recently added midpoint.

When the triangle of index k in T(i) is proccesed, it generates 4 triangles in T(i+1) whose indices are always 4*k,4*k+1,4*k+2,4*k+3. The triangle of index 4*k correspond to the triangle s_1 in the figure. The vertices of this triangle are always V_1=V_1, V_2=M_1, and V_3=M3, and the neighbour t_2 is s_4 ( which is the triangle of index 4*k+3). The triangles of indices 4*k+1,4*k+2,4*k+3 are defined analogously.

If a midpoint of the triangle being porccessed was already initialized, this means the concerned neighbour triangle was already proccessed. For instance if M_1 was already initialized, this is because t_1 was already processed. Therefore, the interior triangles of t_1 are already added to the new triangulation (in the positions 4*Index(t_1),4*Index(t_1)+1,4*Index(t_1)+2,,4*Index(t_1)+3). Then, we are ready to state new neighbour relation for s_1,s_2 and their counterparts in t_1. An analogous procedure apply whenever M_2 or M_3 was already initialized.

Step 4: All the attributes of T(i+1) are already initialized, except by the midpoints of the triangles. Then we are ready to refine the subdivison again by returning to Step 1.

3)Results

Octahedron
Subdivision 1
Subdivision 2
Subdivision 3
Subdivision 4