Mesh face grouping


Is there a way in compas to represent mesh faces as triangle faces groups?

e.g. mesh = mesh.from_vertices_and_faces_and_facegroups(v,f,g)

If I understand correctly, compas mesh can be represented by both triangle and polygonal faces. I assume in the viewer, for display reasons, internally polygons are triangulated and the border is displayed as a polyline.

The reason to ask:
I would like to display a mesh that have holes similar to NGon representation in Rhino:

hi petras,

i don’t understand the question.
both of the “one face” examples in your image already work.

for visualisation, all non-triangle faces are indeed converted to triangles during the display process.
in the past, the second “one face” example would have not looked correct because the centroid of the face was used to generate the triangulation. however, now (in the WIP version of COMAS 2.0) we use earclipping which should produce the correct result.

are you looking for something else?


Sorry for misleading question (the screenshots are rhino meshes).

The question was how in compas Mesh you could store mesh faces with holes?

Is it correct to say that for this specific case (a mesh face with hole), I should just use **kwargs with additional property for
a) grouping triangle faces
b) another property for naked edge loops?

On another subject of Earclipping.
I also used “earclipping” recently from this source code.
In some cases I had issues that the while loop does not stop running .

Meanwhile I also tried another Earclipping implementation that seems to do some additional checks. I do not know if, but maybe it can be useful:

    class Ear:
        Represents an ear of a polygon. An ear is a triangle formed by three consecutive vertices of the polygon.

        def __init__(self, points, indexes, ind):
            Initialize an Ear instance.

                points (list): List of vertex coordinates.
                indexes (list): List of vertex indexes.
                ind (int): Index of the current vertex.
            self.index = ind
            self.coords = points[ind]
            length = len(indexes)
            index_in_indexes_arr = indexes.index(ind)
   = indexes[(index_in_indexes_arr + 1) % length]
            if index_in_indexes_arr == 0:
                self.prew = indexes[length - 1]
                self.prew = indexes[index_in_indexes_arr - 1]
            self.neighbour_coords = [points[self.prew], points[]]

        def is_inside(self, point):
            Check if a given point is inside the triangle formed by the ear.

                point (list): Coordinates of the point to check.

                bool: True if the point is inside the triangle, False otherwise.
            p1 = self.coords
            p2 = self.neighbour_coords[0]
            p3 = self.neighbour_coords[1]
            p0 = point

            d = [
                (p1[0] - p0[0]) * (p2[1] - p1[1]) - (p2[0] - p1[0]) * (p1[1] - p0[1]),
                (p2[0] - p0[0]) * (p3[1] - p2[1]) - (p3[0] - p2[0]) * (p2[1] - p0[1]),
                (p3[0] - p0[0]) * (p1[1] - p3[1]) - (p1[0] - p3[0]) * (p3[1] - p0[1]),

            if d[0] * d[1] >= 0 and d[2] * d[1] >= 0 and d[0] * d[2] >= 0:
                return True
            return False

        def is_ear_point(self, p):
            Check if a given point is one of the vertices of the ear triangle.

                p (list): Coordinates of the point to check.

                bool: True if the point is a vertex of the ear triangle, False otherwise.
            if p == self.coords or p in self.neighbour_coords:
                return True
            return False

        def validate(self, points, indexes, ears):
            Validate if the ear triangle is a valid ear by checking its convexity and that no points lie inside.

                points (list): List of vertex coordinates.
                indexes (list): List of vertex indexes.
                ears (list): List of other ear triangles.

                bool: True if the ear triangle is valid, False otherwise.
            not_ear_points = [
                points[i] for i in indexes if points[i] != self.coords and points[i] not in self.neighbour_coords
            insides = [self.is_inside(p) for p in not_ear_points]
            if self.is_convex() and True not in insides:
                for e in ears:
                    if e.is_ear_point(self.coords):
                        return False
                return True
            return False

        def is_convex(self):
            Check if the ear triangle is convex.

                bool: True if the ear triangle is convex, False otherwise.
            a = self.neighbour_coords[0]
            b = self.coords
            c = self.neighbour_coords[1]
            ab = [b[0] - a[0], b[1] - a[1]]
            bc = [c[0] - b[0], c[1] - b[1]]
            if ab[0] * bc[1] - ab[1] * bc[0] <= 0:
                return False
            return True

        def get_triangle(self):
            Get the indices of the vertices forming the ear triangle.

                list: List of vertex indices forming the ear triangle.
            return [self.prew, self.index,]

    class Earcut:
        A class for triangulating a simple polygon using the ear-cutting algorithm.

        def __init__(self, points):
            Initialize an Earcut instance with the input points.

                points (list): List of vertex coordinates forming the polygon.
            self.vertices = points
            self.ears = []
            self.neighbours = []
            self.triangles = []
            self.length = len(points)

        def update_neighbours(self):
            Update the list of neighboring vertices.
            neighbours = []
            self.neighbours = neighbours

        def add_ear(self, new_ear):
            Add a new ear to the list of ears and update neighboring vertices.

                new_ear (Ear): The new ear triangle to be added.

        def find_ears(self):
            Find valid ear triangles among the vertices and add them to the ears list.
            i = 0
            indexes = list(range(self.length))
            while True:
                if i >= self.length:
                new_ear = _.Ear(self.vertices, indexes, i)
                if new_ear.validate(self.vertices, indexes, self.ears):
                i += 1

        def triangulate(self):
            Triangulate the polygon using the ear-cutting algorithm.
            indexes = list(range(self.length))

            num_of_ears = len(self.ears)

            if num_of_ears == 0:
                raise ValueError("No ears found for triangulation.")
            if num_of_ears == 1:

            while True:
                if len(self.ears) == 2 and len(indexes) == 4:

                if len(self.ears) == 0:
                    raise IndexError("Unable to find more ears for triangulation.")
                current = self.ears.pop(0)



                # Check if prew and next vertices form new ears
                prew_ear_new = _.Ear(self.vertices, indexes, current.prew)
                next_ear_new = _.Ear(self.vertices, indexes,
                if (
                    prew_ear_new.validate(self.vertices, indexes, self.ears)
                    and prew_ear_new.index not in self.neighbours
                if (
                    next_ear_new.validate(self.vertices, indexes, self.ears)
                    and next_ear_new.index not in self.neighbours

And often the earclipping has to be done on 2D, so the 3D to 2D transformation maybe needed:

    class Triagulator:
        def get_frame(_points, _orientation_point=None):
            """create a frame from a polyline"""

            # create a normal by averaging the cross-products of a polyline
            normal = Vector(0, 0, 0)
            count = len(_points)
            center = Point(0, 0, 0)
            is_closed = distance_point_point(Point(*_points[0]), Point(*_points[-1])) < 0.01
            sign = 1 if is_closed else 0

            for i in range(count - sign):
                num = ((i - 1) + count - sign) % (count - sign)
                item1 = ((i + 1) + count - sign) % (count - sign)
                point3d = _points[num]
                point3d1 = _points[item1]
                item2 = _points[i]
                normal += cross_vectors(item2 - point3d, point3d1 - item2)
                center = center + point3d
            center = center / count

            # get the longest edge
            longest_segment_length = 0.0
            longest_segment_start = None
            longest_segment_end = None

            for i in range(len(_points) - sign):
                point1 = _points[i]
                point2 = _points[
                    (i + 1) % len(_points)
                ]  # To create a closed polyline, connect the last point to the first one.

                segment_length = distance_point_point(point1, point2)

                if segment_length > longest_segment_length:
                    longest_segment_length = segment_length
                    longest_segment_start = point1
                    longest_segment_end = point2

            # create x and y-axes for the frame
            x_axis = Vector.from_start_end(longest_segment_start, longest_segment_end)
            y_axis = cross_vectors(normal, x_axis)
            y_axis = Vector(y_axis[0], y_axis[1], y_axis[2])
            # create the frame
            center = centroid_points(_points)
            frame = Frame(center, x_axis, y_axis)

            # orient the from the orientation point to the opposite direction
            reversed = False
            if _orientation_point is not None:
                signed_distance = distance_point_plane_signed(_orientation_point, Plane.from_frame(frame))
                if signed_distance > 0.001:
                    frame = Frame(frame.point, -x_axis, y_axis)
                    reversed = True
            # output
            return frame, reversed

        def from_points(points):
            polygon = Polygon(points=points)
            frame = _.Triagulator.get_frame(points)
            xform, reversed = Transformation.from_frame_to_frame(frame, Frame.worldXY())
            ear_cut = _.Earcut(polygon.points)

            return Mesh.from_vertices_and_faces(polygon.points, ear_cut.triangles)

i reacted to quickly, you are correct, faces with holes are indeed not possible at the moment. so the bottom right image doesn’t work.

with the current implementation it is not an easy thing to add though. we would need to switch to a face class instead of the list implementation we use now. although this is something we have considered (also for vertices and edges) i don’t really see it happening soon…

in the meantime, you could use the face attributes to store information about holes, as a workaround.
perhaps something along the lines of the following…

polygon = Polygon.from_sides_and_radius_xy(6, 1)
hole = Polygon.from_sides_and_radius_xy(6, 0.5)
mesh = Mesh.from_polygons([polygon])


mesh.face_attribute(0, 'holes', [hole])

however, in the above, the vertices of the hole are not really part of the mesh.
you could also add the vertices of the hole geometry and refer to those in the face attribute.
or you could even add the vertices and the face of the hole geometry and make a reference to that face in the parent face attribute…

it certainly is. earclipping is rather important and the current implementation is indeed rather basic. if you can improve it, please submit a PR :slight_smile:

This is what I was looking for, thank you. Then I can have a two level representation:
a) a mesh that contains outer loops that constructs mesh faces
b) face attribute for this parent face for a more detailed description meaning a list of faces+vertices referring to triangulation of holes and inner loops.

I never done this on compas github repository, but would be more than happy to learn how to :slight_smile: