• Waypoint 4: polyhedral nets: make sure you've done this before we return from break! 

Notes from Case study 5: Threaded Nets 

• The algorithm is described in section 3, which is copied below

• We looked closely at Figure 4 to help decode the text and verify our interpretation of it.

• We started with the paragraph "Join vertices"

  • We think the line below means : find vertices whose number of net faces is the same as the number of polyhedral faces.  For example, the green vertex in the polyhedron is adjacent to 3 faces of the cube; since it  is adjacent to 3  faces in the unfolded net, it satisfies the condition.
    We identify vertices in the net that are already adjacent to n connected faces, where the vertex is adjacent to n faces in the 3D mesh.

    • We suspect this is equivalent to:

      • "interior" vertices of the net

      • vertices from the polyhedron that only appear once in the net

        • indeed, the first sentences indicates that this process is attempting to find the ones that must be joined... so this first set are ones that DO NOT have multiples?

  • Then we think the next sentence says to "breadth-first" traverse from all these starting vertices and label each layer. (If a vertex is already labeled, we do not expand the traversal to it, as illustrated by the blue 2s.)
    For each of these vertices: the vertex will be adjacent to two boundary edges in the net. The vertices at the other ends of these edges will need to be joined, and we sore these two vertices in a set and mark their rigidity depth as 1.

New notes

• Audrey has tried to understand this and has hit a wall.

• The following sentences are where I have run into trouble. Not sure what the highlighted sentence means?
  The vertices at the other ends of these edges will need to be joined, and we store these two vertices in a set and mark their rigidity depth as 1. Next, we join any sets with overlapping vertices. We fnally iterate this joining procedure through the vertices of rigidity depth 1, until all vertices have been marked.

3. Algorithms

This section introduces our algorithm for constructing an optimal net and string path for a given 3D mesh (Figure 4).

Unfold the geometry: We begin by generating unfoldings of the mesh using a set of heuristic algorithms, including a steepest-edge cut tree, greatest-increase cut tree from Schlickenrieder [24] and a naive breadth-frst unfolding from the largest face. If no non-overlapping nets are found, we randomly split the mesh in half (e.g., by cutting along edges that are nearest to a plane that passes through the center of mass) and repeat the search on each half.

Join vertices: Next we use a breadth-frst search to identify pairs of vertices that need to be joined (Figure 4): We identify vertices in the net that are already adjacent to n connected faces, where the vertex is adjacent to n faces in the 3D mesh. These vertices have a rigidity depth of 0. For each of these vertices: the vertex will be adjacent to two boundary edges in the net. The vertices at the other ends of these edges will need to be joined, and we store these two vertices in a set and mark their rigidity depth as 1. Next, we join any sets with overlapping vertices. We fnally iterate this joining procedure through the vertices of rigidity depth 1, until all vertices have been marked.

Prune unwanted connections: We next remove unnecessarily joined vertices. The criteria for removing a vertex from a joined set are: (1) if removing the vertex from the set leaves only one vertex, then the other vertex must also be removed; (2) one of the vertices in the set must be connected by a single boundary edge to a joined vertex of greater rigidity depth; and (3) removing the vertex must leave each face with at least three joined vertices.

Optimize string path: Using the fnal set of vertex sets to be joined, we lastly fnd the string path that passes through each pair of joined vertices which minimizes a combination of its turning angles and total length. If the mesh has been partitioned into multiple pieces, we optimize the string path on each piece separately.

Time to embody the algorithm!

• 1 dimensional "grid" with cells holding 0 or 1

• Each cell has two neighbors

• To compute the next generation of a cell, we consider the cell + its two neighbors

  • This means our "algorithm" expects an binary string of length 3 --  how many possible inputs are there?

  • Our output is 0 or 1.

• How many possible algorithms (or "rules") are there?

  • __________

• Then we can describe an algorithm/rule in this model of computation using a single number:

• Mini project 2: Threaded Algorithms