Assignment 3

Download the assignment archive, and unzip the compressed file. You should have a directory named DGP2016-A3 containing a README.txt file and several subdirectories. Follow these instructions. You should upload your completed assignment through Canvas. As in previous assignments, your submission may have bugs, but it has to compile and the application has to run. Otherwise I will not grade your assignment.

In this assignment you will implement the wrl/ImageFaceSetSelection class For this you have to edit the following two files


You should copy your implementations of the classes core/Faces, io/SaveStl, and io/LoadStl from Assignment 1 as well as core/HalfEdges.hpp, core/HalfEdges.cpp, core/PolygonMesh.hpp, and core/PolygonMesh.cpp, from Assignment 2 into the Assignment 3 src directory.

wrl/ImageFaceSet class has been modified to support the selection of vertices, edges, faces, and corners. Explicitly, the following public methods have been added.

bool         hasVertexSelection();
bool         hasEdgeSelection();
bool         hasFaceSelection();
bool         hasCornerSelection();
int          getNumberOfSelectedVertices();
int          getNumberOfSelectedEdges();
int          getNumberOfSelectedFaces();
int          getNumberOfSelectedCorners();
vector<int>& getVertexSelection();
vector<int>& getEdgeSelection();
vector<int>& getFaceSelection();
vector<int>& getCornerSelection();

The arrays are not allocated when an instance of the ImageFaceSet class is constructed, but when the first call to one of the following method is made: getVertexSelection(), getEdgeSelection(), getFaceSelection(), and getCornerSelection(). Once created, the size of each array must be equal to the number of corresponding elements of the polygon mesh.

The methods hasVertexSelection(), hasEdgeSelection(), hasFaceSelection(), and hasCornerSelection() can be used to determine whether or not the arrays have been allocated. Once allocated, they are initialized with the value -1, which indicate that none of the elements are selected. An element is selected if the corresponding selection value is non-negative. The selection arrays can be used to represent a partition of the corresponding elements, which the parts corresponding to the different array values, including -1.

The methods getNumberOfSelectedVertices(), getNumberOfSelectedEdges(), getNumberOfSelectedFaces(), and getNumberOfSelectedCorners() count how many values are different from -1.

The DGP2016 application has been modified to support this selection mechanism. First of all, the io/SaveWrl class has been modified in such a way that the selection arrays are saved as additional fields of IndexedFaceSet node. The names of these new fields are vertexSelection, edgeSelection, faceSelection, and cornerSelection. The type of these fields is MInt32, which is the same as for the coordIndex, normalIndex, colorIndex, and texCoordIndex arrays. The field is not included in the input file if the number of corresponding elements is zero. When one or more of these fields is included in the output file, the resulting file is not standard compliant. However, the io/LoadWrl class has also been modified to parse these non-compliant files, and restore the selections.

The user interface has also been modified to support the selection functionality. First of all, the OpenGL rendering loop now is able to visualize the various selected elements. How a particular scene is rendered can be controlled using the Rendering panel shown above. Non-selected elements are rendered using a corresponding default colors shown in this panel. The default color can be edited. Clicking on the rightmost color label brings up a color editor. Selected elements are rendered using colors from static internal tables which cannot be edited. Different colors are assigned to different selection values.

The methods that you have to implement in the ImageFaceSetSelection class are called from the Selection panel, shown above. The first three rows allow you to chose the default values assigned to newlly selected elements, as well as the color used to render them. The panel also comprises a number of buttons. Every time that one of these buttons is pressed, a callback is executed which traverses the current SceneGraph, and calls a corresponding public method from the ImageFaceSetSelection class for each ImageFaceSet found. Read the implementation of the gui/GuiPanelSelection class for details.

The ImageFaceSetSelection class

Note that all the methods and variables of this class are static. As a result, this class should not be instantiated.

The following methods set the private variables _selectedVertexIndex _selectedEdgeIndex _selectedFaceIndex. They are called to specify the default value used to select new vertices. They should not be called with negative values.

static void setSelectedVertexIndex(const int value);
static void setSelectedEdgeIndex(const int value);
static void setSelectedFaceIndex(const int value);

The following methods set all the values of the corresponding selection arrays to -1, which indicates that no element is selected.

static void clearVertices(IndexedFaceSet& ifs);
static void clearEdges(IndexedFaceSet& ifs);
static void clearFaces(IndexedFaceSet& ifs);

The following methods modify the values of the corresponding selection arrays. If a value is equal to to -1, it is changed to the corresponding default selection value. If a value is not equal to to -1, it is changed to -1.

static void invertVertices(IndexedFaceSet& ifs);
static void invertEdges(IndexedFaceSet& ifs);
static void invertFaces(IndexedFaceSet& ifs);

The following methods modify the values of the corresponding selection arrays using methods from the PolygonMesh class that you implemented in Assignment 2. An edge is a boundary edge if there is only one face incident to it. An edge is a regular edge if there are exactly two faces incident to it. Ans an edge is singular if there are three or more faces incident to it. A vertex is a boundary vertex if it is the end of at least one boundary edge, and the vertex is an internal vertex otherwiae. A vertex is a regular vertex if the complete subgraph of the dual graph containing all the faces incident to the given vertex is connected, and the vertex is a singular vertex otherwise. A face is a boundary face if it is incident to at least one boundary edge (alternatively vertex). A face is regular if all its incident vertices and edges are regular, and the face is a singulart face otherwise.

static void boundaryVertices(IndexedFaceSet& ifs);
static void boundaryEdges(IndexedFaceSet& ifs);
static void boundaryFaces(IndexedFaceSet& ifs);
static void regularVertices(IndexedFaceSet& ifs);
static void regularEdges(IndexedFaceSet& ifs);
static void regularFaces(IndexedFaceSet& ifs);
static void singularVertices(IndexedFaceSet& ifs);
static void singularEdges(IndexedFaceSet& ifs);
static void singularFaces(IndexedFaceSet& ifs);

The following methods modify the values of the corresponding selection arrays by transfering values between incident elements. The default selection values are assigned to the target element for each selected element, independently of the target selection value.

static void fromVerticesToFaces
(IndexedFaceSet& ifs, vector& faceSelection);
static void fromVerticesToFaces(IndexedFaceSet& ifs);
static void fromVerticesToEdges(IndexedFaceSet& ifs);
static void fromEdgesToVertices(IndexedFaceSet& ifs);
static void fromEdgesToFaces
(IndexedFaceSet& ifs, vector& faceSelection);
static void fromEdgesToFaces(IndexedFaceSet& ifs);
static void fromFacesToVertices(IndexedFaceSet& ifs);
static void fromFacesToEdges(IndexedFaceSet& ifs);

The following methods modify the values of the corresponding selection arrays by enumerating the Shape nodes of the SceneGraph, and then assigning the resulting Shape index number to all the elements.

static void setShapeIndex(const int value);
static void shapeVertices(IndexedFaceSet& ifs);
static void shapeEdges(IndexedFaceSet& ifs);
static void shapeFaces(IndexedFaceSet& ifs);

The following methods select elements according to a partition of the vertices of the IndexedFaceSet into connected components of the primal graph. The edges and faces are automatically partitioned into corresponding partitions taking into account the incidence relations. These partitions do not have to be computed explicitly. The connected components are enumerated, and all the elements of each connected component are assigned the connected component index as the selection value. The implementation of the connected components algorithm is discussed in this page assignment3-connected.

static void connectedComponentsPrimal
(const Edges& edges, Partition& partition,
 vector& vertexToPart);
static void connectedVertices(IndexedFaceSet& ifs);
static void connectedEdges(IndexedFaceSet& ifs);
static void connectedFaces(IndexedFaceSet& ifs);

All the previous methods result into changes of values in the selection arrays, but neither to the the connectivity, nor to the geometry of the polygon meshes. The following methods result in changes to the connectivity and/or geometry of the meshes.

The following methods delete selected elements, as well as all the incident elements which become invalid after deleting the selected elements. Vertices which become isolated, and no longer incident to any face, are deleted as well. The remaining vertices are enumerated, and all the vertex references are corrected to reflect the new vertex indices. The fundamental operation is deletion of faces. Deletion of vertices and edges can be reduced to the deletion of all the faces incident to the selected elements. The implementation of the selected face deletion algorithm is discussed in this page assignment3-delete.

static void deleteSelectedFaces
(IndexedFaceSet& ifs, vector& faceSelection);
static void deleteVertices(IndexedFaceSet& ifs);
static void deleteEdges(IndexedFaceSet& ifs);
static void deleteFaces(IndexedFaceSet& ifs);

The following methods cut the mesh throug selected edges, resulting in meshes with more vertices and edges, but the same number of faces. The fundamental operation is cutting through selected and singular edges. Cutting through selected faces is defined as cuting through the singular edges and the regular edges common to pairs of faces with different selection labels. The implementation of the algorithm to cut through selected and singular edges is discussed in this page assignment3-cut.

static void cutThroughSelectedEdges
(IndexedFaceSet& ifs, vector& edgeSelection);
static void cutEdges(IndexedFaceSet& ifs);
static void cutFaces(IndexedFaceSet& ifs);

Algorithm Details

Test Files

A number of simple test files have been added to the assets directory. Since the polygon meshes described in these files are small, they can be used to debug your implementation. Some of these files contain scene graphs with multiple IndexedFaceSet nodes, some contain regular polygon meshes, and some contain singular polygon meshes. Some meshes have boundaries and others do not.