B. Half-edge and Mesh datastructure

1. Half-edge data-structure

In the Polygon, the line segments form a continuous cycle, connecting the vertices in order. These directed line segments are called half-edge. If an edge is shared by two faces, it can be decomposed into 2 twin half-edges, which have the opposite directions and each face can have a half-edge. The half-edge adjacencies define the connectivity of faces.

One incident face and one incident vertex are stored in each half-edge. In a face, a vertex always has an outgoing half-edge which starts at this vertex. Starting from the end vertex of the half-edge, the next half-edge could be found, until it comes back to the start vertex and forms a cycle. The ordering of the vertices determines the direction of the face normal according to right-hand rule.

2. COMPAS Mesh

A COMPAS mesh is a polygon mesh, represented using a half-edge data strucutre, where most information is stored in the half-edges - these are the primary objects.

The basic elements of COMPAS mesh are vertices, faces, and half-edges.

vertices stores the xyz coordinates of the vertices.
faces contains all the indices of the vertex key in order that make up the face.
half-edge contains the index of a vertex key, the end vertex key of the outgoing half-edge, and the face key it belongs to.

3. Building a Mesh

3.a: construct mesh from scratch

Meshes can be built from scratch by adding vertex-per-vertex and face per face. Mesh.add_face() would generate half-edges at the same time. As long as one vertex or face is added to the mesh, it could be visualized with a Plotter.

# ==============================================================================
# Import
# ==============================================================================
from compas.datastructures import Mesh
from compas_plotters import MeshPlotter

# ==============================================================================
# Build a Mesh
# ==============================================================================
mesh = Mesh()

a = mesh.add_vertex(x=0, y=0, z=0) 
b = mesh.add_vertex(x=10, y=0, z=0) 
c = mesh.add_vertex(x=10, y=10, z=0)
d = mesh.add_vertex(x=0, y=10, z=0)

mesh.add_face([a, b, c, d])

# ==============================================================================
# Visualization
# ==============================================================================
plotter = MeshPlotter(mesh, figsize=(12, 7.5))
plotter.draw_vertices(radius=0.5)
plotter.draw_faces()
plotter.show()

3.b: alternative Mesh constructors

Here are some alternative constructors to build a Mesh.

# ==============================================================================
# Import
# ==============================================================================
from compas.datastructures import Mesh
from compas_plotters import MeshPlotter

# ==============================================================================
# Parameters
# ==============================================================================
row = 5
col = 5
unit_len = 10

# ==============================================================================
# Mesh from vertices and faces
# ==============================================================================
vertices = []
faces = []

for i in range(row + 1):
    for j in range(col + 1):
        vertices.append([i * unit_len, j * unit_len, 0])

        if i < row and j < col:
            faces.append([i * (row + 1) + j, (i + 1) * (row + 1) + j, (i + 1) * (row + 1) + j + 1, i * (row + 1) + j + 1])

cablenet_mesh = Mesh.from_vertices_and_faces(vertices, faces)

# ==============================================================================
# Visualization
# ==============================================================================
plotter = MeshPlotter(cablenet_mesh, figsize=(12, 7.5))
plotter.draw_vertices(radius=0.5)
plotter.draw_faces()
plotter.show()

print(cablenet_mesh.summary())

Mesh summary vertices: 36 edges: 60 faces: 25

4. Mesh Serialization

Similar to Network, a mesh could be serialized and loaded again.

import os

HERE = os.path.dirname(__file__)
FILE = os.path.join(HERE, 'cablenet.json')

cablenet_mesh.to_json(FILE)

import os
from compas.datastructures import Mesh

HERE = os.path.dirname(__file__)
FILE = os.path.join(HERE, 'cablenet.json')

cablenet = Mesh.from_json(FILE)

5. Vertices, Faces, Edges

Vertices, faces and edges of the mesh data structure could be accessed using the corresponding methods, which returns generator objects that have to be consumed by iteration. We can print and see what is inside the generator.

# access the vertices, faces and edges of the mesh
for vertex in cablenet_mesh.vertices():
    print("vertex", vertex)  # vertex key

for face in cablenet_mesh.faces():
    print("face", face)  # face key

for edge in cablenet_mesh.edges():
    print("edge", edge)  # (u, v) of the edge

In CSDII, notation vkey means vertex key, fkey means face key and (u, v) means the vkey pair for edges. With the keys, more relevant information of the mesh could be accessed.

for vkey in cablenet_mesh.vertices():
    # xyz coordinates of the vertex
    xyz = cablenet_mesh.vertex_coordinates(vkey)
    print("vertex:", vkey, "coordinates:", xyz)

for fkey in cablenet_mesh.faces():
    # vertex keys of the face
    f_vkeys = cablenet_mesh.face_vertices(fkey)
    print("face:", fkey, "vkyes:", f_vkeys)

for (u, v) in cablenet_mesh.edges():
    print("edge:", (u, v))

6. Topology

Similar to Network, a mesh can answer several topological questions about itself and its components.

6.a: Vertex

Ex 1: Highlight vertex 20 in the cable-net mesh.

vkey = 20
nbrs = cablenet_mesh.vertex_neighbors(vkey)

Ex 2: Find faces connected to vertex 20.

face_nbrs = cablenet_mesh.vertex_faces(vkey)

Ex 3: Count the neighbors of all vertices.

from compas.utilities import i_to_red

vertex_text = {}
facecolor = {}
max_vertex_degree = cablenet_mesh.vertex_max_degree()
min_vertex_degree = cablenet_mesh.vertex_min_degree()

for vkey in cablenet_mesh.vertices():
    vertex_degree = cablenet_mesh.vertex_degree(vkey)
    vertex_text[vkey] = str(vertex_degree)
    facecolor[vkey] = i_to_red((vertex_degree - min_vertex_degree) / (max_vertex_degree - min_vertex_degree))

6.b: Face

Ex 1: Count the neighbors of all faces.

from compas.utilities import i_to_green

face_text = {}
facecolor = {}
max_face_degree = cablenet_mesh.face_max_degree()
min_face_degree = cablenet_mesh.face_min_degree()

for fkey in cablenet_mesh.faces():
    face_degree = cablenet_mesh.face_degree(fkey)
    face_text[fkey] = str(face_degree)
    facecolor[fkey] = i_to_green((face_degree - min_face_degree) / (max_face_degree - min_face_degree))

Ex 2: Highlight the vertices and half-edges of face 12.

fkey = 12
f_vkeys = cablenet_mesh.face_vertices(fkey)
f_halfedges = cablenet_mesh.face_halfedges(fkey)

Ex 3: Highlight neighbor faces of face 12.

face_nbrs = cablenet_mesh.face_neighbors(fkey)

Ex 4: Calculate the area of face 12.

face_area = cablenet_mesh.face_area(fkey)

100

6.c: Boundary

Mesh data-structure provides methods to find vertices, faces and edges on the boundary of the mesh.

vkeys = cablenet_mesh.vertices_on_boundary()
fkeys = cablenet_mesh.faces_on_boundasry()
edges = cablenet_mesh.edges_on_boundary()

# vertices
vertex_facecolor = {}
vertex_text = {}
for vkey in vkeys:
    vertex_text[vkey] = str(vkey)
    vertex_facecolor[vkey] = (255, 0, 0)

# faces:
face_facecolor = {}
for fkey in fkeys:
    if cablenet_mesh.is_face_on_boundary(fkey) is False:
        face_facecolor[fkey] = (150, 255, 150)

# edges:
edgecolor = {}
for (u, v) in edges:
    edgecolor[u, v] = (0, 0, 255)

7. Attributes

Additional data of the Mesh vertices, faces and edges could be saved with attributes.

7.a: extract attributes

Here are some methods to extract attributes of a specific vertex.

for vkey, attr in cablenet_mesh.vertices(data=True):
    print(vkey, attr)
    print(cablenet_mesh.vertex_attributes(vkey))
    print(cablenet_mesh.vertex_attribute(vkey, 'x'))

0 {'x': 0, 'y': 0, 'z': 0} {'x': 0, 'y': 0, 'z': 0} 0

Here are the methods to get multiple attributes or a specific attribute of all the vertices.

print(cablenet_mesh.vertices_attributes('xyz'))
print(cablenet_mesh.vertices_attributes('x'))

[[0, 0, 0], [0, 10, 0], [0, 20, 0], [0, 30, 0], [0, 40, 0], [0, 50, 0], [10, 0, 0], [10, 10, 0], [10, 20, 0], [10, 30, 0], [10, 40, 0], [10, 50, 0], [20, 0, 0], [20, 10, 0], [20, 20, 0], [20, 30, 0], [20, 40, 0], [20, 50, 0], [30, 0, 0], [30, 10, 0], [30, 20, 0], [30, 30, 0], [30, 40, 0], [30, 50, 0], [40, 0, 0], [40, 10, 0], [40, 20, 0], [40, 30, 0], [40, 40, 0], [40, 50, 0], [50, 0, 0], [50, 10, 0], [50, 20, 0], [50, 30, 0], [50, 40, 0], [50, 50, 0]] [[0], [0], [0], [0], [0], [0], [10], [10], [10], [10], [10], [10], [20], [20], [20], [20], [20], [20], [30], [30], [30], [30], [30], [30], [40], [40], [40], [40], [40], [40], [50], [50], [50], [50], [50], [50]]

7.b: set attributes

The methods to extract attributes can also be used to set attributes.

Move vertex 20 along positive x-axis 1 unit and along positive y-axis 2 unit. Update the mesh.

vkey = 20
ori_x = cablenet_mesh.vertex_attribute(vkey, "x")  # get x attribute of the vertex
ori_y = cablenet_mesh.vertex_attribute(vkey, "y")  # get y attribute of the vertex
cablenet_mesh.vertex_attribute(vkey, "x", ori_x + 1)  # set x attribute of the vertex
cablenet_mesh.vertex_attribute(vkey, "y", ori_y + 2)  # set y attribute of the vertex

7.c: update attributes

UsingMesh.update_default_edge_attributes(), Mesh.update_default_face_attributes() and Mesh.update_default_edge_attributes()could customize the default attributes of the elements. Now create new attributes q(force density) and f(axial force) for all edges and extract them.

cablenet_mesh.update_default_edge_attributes({'q': 1.0, 'f': 0.0})

for (u, v), attr in cablenet_mesh.edges(data=True):
    print((u, v), attr)
    print(cablenet_mesh.edge_attributes((u, v)))
    print(cablenet_mesh.edge_attribute((u, v), 'q'))

# get attribute of all edges
print(cablenet_mesh.edges_attributes('qf'))
print(cablenet_mesh.edges_attributes('q'))

(0, 6) {'q': 1.0, 'f': 0.0}

7.d: find elements by attributes

Mesh.vertices_where(), Mesh.faces_where() and Mesh.edges_where() can find elements of the mesh under a specific or a set of conditions.

vkeys = cablenet_mesh.vertices_where({'x': 10})

vkeys = cablenet_mesh.vertices_where({'x': 10, 'y': 10})

Ex: Smooth the mesh (optional)

Set a new vertex attribute "fixed", and by default False. Find the vertices in the corners and set the value to True. Fixed these vertices and smooth the mesh by moving every free vertex to the centroid of its neighbors using Mesh.smooth_centroid().

cablenet_mesh.update_default_vertex_attributes({'fixed': False})

for vkey in cablenet_mesh.vertices():
    vertex_degree = cablenet_mesh.vertex_degree(vkey)
    if vertex_degree == 2:
        cablenet_mesh.vertex_attribute(vkey, 'fixed', True)

fixed_vertices = list(cablenet_mesh.vertices_where({'fixed': True}))
cablenet_mesh.smooth_centroid(fixed=fixed_vertices)

PreviousA. Cablenet and Faces NextC. Mesh in Rhino

Last updated 3 years ago