E2. Data Structures

Task: extend edge_strip method

In this exercise, we will look into Mesh.edge_strip(edge). The current method only works for quad meshes, where all the mesh faces have four vertices. This exercise aims at extending this algorithm for general n-polygon meshes, where faces have an even number of vertices, e.g. Rectangle, hexagon, octagon, etc.

edge_strip and halfedge_strip source code

Firstly let's read the source code of edge_strip and halfedge_strip. There are a few ways to navigate to the source code.

• Search edge_strip in the Api Reference, then click [source]

• Open the COMPAS folder in VS code. Go to Edit > Find in Files, or use shortcut ctrl+shift+F (Windows) or Cmd+shift+F (Mac). Search edge_strip.

• In your VS code, hover your mouse over edge_strip, a preview of the declaration will appear. Right-click on edge_strip and click go to Definition or Ctrl+Click.

Now let's read the source code of edge_strip.

def edge_strip(self, edge):
    """Find all edges on the same strip as a given edge.

    Parameters
    ----------
    edge : tuple of int
        The identifier of the starting edge.

    Returns
    -------
    list of tuple of int
        The edges on the same strip as the given edge.
    """
    edges = []
    v, u = edge
    while True:
        edges.append((u, v))
        face = self.halfedge[u][v]
        if face is None:
            break
        vertices = self.face_vertices(face)
        if len(vertices) != 4:
            break
        i = vertices.index(u)
        u = vertices[i - 1]
        v = vertices[i - 2]
    edges[:] = [(u, v) for v, u in edges[::-1]]
    u, v = edge
    while True:
        face = self.halfedge[u][v]
        if face is None:
            break
        vertices = self.face_vertices(face)
        if len(vertices) != 4:
            break
        i = vertices.index(u)
        u = vertices[i - 1]
        v = vertices[i - 2]
        edges.append((u, v))
    return edges

What the algorithm does is that:

1. Given a start edge (u, v);

2. Find the face that (u, v) belongs to;

1: start searching from half-edge(u, v); 2. find the face that the half-edge belongs to;

3. Find the half edges on the face; find the half-edge that's on the same strip of the start edge;

4. Find the half-edge pointing in opposite direction; This edge is the new start edge (u, v);

3. find the half-edge on the same strip from all half-edges on the face; 4. find the half-edge with opposite orientation, and repeat step 1-4;

5. Repeat step 1 to step 4 until the half-edge is on the boundary, where the face that the half-edge belongs to doesn't exist;

6. Flip the edge directions of all the half-edges that have been found so far. Flipping the directions make sure that all the edges found on the strip will point in the same direction; find the pair half-edge of the initial start edge (u, v); repeat step 1 to step 4 until the half-edge is on the boundary.

5. stop searching when the half-edge is on the boundary; 6. find the half-edge in opposite direction to the start, and repeat step 1-4 until step 5 is encountered.

halfedge_strip finds half-edges that are in the same orientation as the start half-edge (u, v), which corresponds to step 1 to step 5 of edge_strip.

Quad Topology

ex2_quad.py provides you the script to find edge strips in a quad mesh using the current Mesh.mesh_strip method. A random edge "start" is chosen from the quad mesh, which is shown in red. All the edges on the strip are shown in green. Mesh.edge_strip(start) finds edges that are in the orientation as the "start" edge. Thus, looping through all the edges, we can find the faces where the edges belong, except when the edge is on the boundary. The edge strip is colored red.

ex2_quad.py

from compas.datastructures import Mesh
from compas_plotters import Plotter

# generate a mesh grid from meshgrid
mesh = Mesh.from_meshgrid(nx=5, dx=2)

# choose a random edge sample from the mesh
start = mesh.edge_sample()[0]

# find edge strips
edges = mesh.edge_strip(start)

# find halfedge strips
# edges = mesh.halfedge_strip(start)

# find strip faces
faces = []
for u, v in edges:
    if mesh.halfedge_face(u, v) is not None:
        faces.append(mesh.halfedge_face(u, v))

# visualization edge settings
edgecolor = {}
edgewidth = {}
for edge in edges:
    edgecolor[edge] = (0, 1, 0)
    edgewidth[edge] = 2.0
edgecolor[start] = (1, 0, 0)

# visualization face settings
facecolor = {}
for face in faces:
    facecolor[face] = (1, 0.7, 0.7)

# plotter
plotter = Plotter()
artist = plotter.add(mesh,
                     facecolor=facecolor,
                     edgecolor=edgecolor,
                     edgewidth=edgewidth,
                     sizepolicy='relative',
                     vertexsize=0.5,
                     )

plotter.zoom_extents()
plotter.show()
 

edgePstrip

halfedge_strip

Extend the edge_strip method

Now you can extend the algorithm so that it works for polygon faces with even numbers of vertices. You can write your own edge_strip function in your script and test it on the hexagon mesh.

Expected outcome

5KB

hexagon.json

ex2.py

import os
from compas.datastructures import Mesh
from compas_plotters import Plotter

# deserialization the hexagon mesh
HERE = os.path.dirname(__file__)
FILE = os.path.join(HERE, 'data', 'hexagon.json')
mesh = Mesh.from_json(FILE)

# choose a random edge sample from the mesh
start = mesh.edge_sample()[0]

# find edge strips
# =====================================================================
# Modify the edge_strip(mesh, edge) algorithm for general n-gon meshes,
# which currently work for quad meshes.
# The algorithm should stop when n-gon with an odd number of sides is encountered.

def edge_strip(mesh, edge):
        """Find all edges on the same strip as a given edge. """
        edges = []
        v, u = edge
        while True:
            edges.append((u, v))
            face = mesh.halfedge[u][v]
            if face is None:
                break
            vertices = mesh.face_vertices(face)
            if len(vertices) != 4:
                break
            i = vertices.index(u)
            u = vertices[i - 1]
            v = vertices[i - 2]
        edges[:] = [(u, v) for v, u in edges[::-1]]
        u, v = edge
        while True:
            face = mesh.halfedge[u][v]
            if face is None:
                break
            vertices = mesh.face_vertices(face)
            if len(vertices) != 4:
                break
            i = vertices.index(u)
            u = vertices[i - 1]
            v = vertices[i - 2]
            edges.append((u, v))
        return edges

# ====================================================================

# find edge strips
edges = edge_strip(mesh, start)

# find strip faces
faces = []
for u, v in edges:
    if mesh.halfedge_face(u, v) is not None:
        faces.append(mesh.halfedge_face(u, v))

# visualization edge settings
edgecolor = {}
edgewidth = {}
for (u, v) in edges:
    edgecolor[(u, v)] = (0, 1, 0)
    edgewidth[(u, v)] = 2.0
    edgecolor[(v, u)] = (0, 1, 0)
    edgewidth[(v, u)] = 2.0
edgecolor[start] = (1, 0, 0)

# visualization face settings
facecolor = {}
for face in faces:
    facecolor[face] = (1, 0.7, 0.7)

# plotter
plotter = Plotter()
artist = plotter.add(mesh,
                     facecolor=facecolor,
                     edgecolor=edgecolor,
                     edgewidth=edgewidth,
                     )

plotter.zoom_extents()
plotter.show()

Bonus Task: Checkered pattern

In this bonus task, you need to develop the checkered pattern on a quad mesh starting from a random face. Checkered pattern contains two colors where a single checker is surrounded on all four sides by a checker of a different color. You can set different attributes to the mesh faces to differ the checkers.

The following pictures are the random face where you can start from, and the checked pattern that you are expected to achieve.

Start face

Expected outcome

Hint

The information of the faces can be saved as a face_attribute. For example, is_colored: True / False for faces on the checked pattern.

We should also try to find a way to check every face only one using the mesh data-structure. Here is one possible solution:

1. Start from a random face 5, set face_attribute: is_colored: True. Create an empty list to_check, and add face 5 into it.

2. Check the neighbouring faces of face 5. If the face_attribute of face 5: is_colored is True, set the face_attribute of all the neighbouring faces is_colored: False. Vice versa. Now face 5 is checked and should be deleted from to_check list. The neighbouring faces are added to the to_check list.

3. Pick the last element in the to_check list, face 6 in this case.

4. Check the neighbouring faces of face 6. Set face_attribute based on the attribute of face 6. Delete face 6 from the to_check list, and added the faces that have not been checked (face 10, 7, 2) in to the to_check list. Face 6 has been checked, which you can tell by the fact that it already has a face_attribute. Thus, face 6 doesn't need to be added to the to_check list again.

5. Repeat step 1-4 until the to_check list is empty, which means all faces on the mesh are checked.

You can look up depth_first_searchas a reference.

Code

ex3.py

from compas.datastructures import Mesh
from compas_plotters import Plotter

# generate a mesh grid from meshgrid
mesh = Mesh.from_meshgrid(nx=5, dx=2)

# choose a random face sample from the mesh
start = mesh.face_sample()[0]

# develop checkered pattern

# Hint1: you can use face attribute to store the color information
# e.g. "is_colored": True / False
# To should avoid an infitie loop, you should find a way to check the face and its neighbours only once

# Hint2: Mesh.face_neighbors, Mesh.update_default_face_attribute, Mesh.face_attribute

# visualization face settings
facecolor = {}
facecolor[start] = (1, 0.7, 0.7)
# Hint3: visualize the faces based on the face attribute you set. 

# plotter
plotter = Plotter()
artist = plotter.add(mesh,
                     facecolor=facecolor,
                     sizepolicy='relative',
                     vertexsize=0.5,
                     )

plotter.zoom_extents()
plotter.show()