# Copyright (c) 2018-2022 Manfred Moitzi
# License: MIT License
from __future__ import annotations
from typing import (
    List,
    Sequence,
    Tuple,
    Iterable,
    Iterator,
    TYPE_CHECKING,
    Union,
    Set,
    Dict,
    TypeVar,
    Type,
    NamedTuple,
)
from ezdxf.math import (
    Matrix44,
    Vec3,
    BoundingBox,
    UVec,
    NULLVEC,
    is_planar_face,
    subdivide_face,
    normal_vector_3p,
    safe_normal_vector,
    subdivide_ngons,
    area,
    OCS,
)

if TYPE_CHECKING:
    from ezdxf.eztypes import (
        UCS,
        Polyface,
        Polymesh,
        GenericLayoutType,
        Mesh,
    )

T = TypeVar("T")


class EdgeStat(NamedTuple):
    """Named tuple of edge statistics."""

    count: int  # type: ignore
    balance: int


Face = Sequence[int]
Edge = Tuple[int, int]
EdgeStats = Dict[Edge, EdgeStat]


class MeshBuilderError(Exception):
    pass


class NodeMergingError(MeshBuilderError):
    pass


class MultipleMeshesError(MeshBuilderError):
    pass


class DegeneratedPathError(MeshBuilderError):
    pass


class NonManifoldMeshError(MeshBuilderError):
    pass


def open_faces(faces: Iterable[Face]) -> Iterator[Face]:
    """Yields all faces with more than two vertices as open faces
    (first vertex index != last vertex index).
    """
    for face in faces:
        if len(face) < 3:
            continue
        if face[0] == face[-1]:
            yield face[:-1]
        else:
            yield face


def normalize_faces(
    faces: List[Sequence[int]],
    *,
    close=False,
) -> Iterator[Sequence[int]]:
    """Removes duplicated vertices and returns closed or open faces according
    the `close` argument. Returns only faces with at least 3 edges.
    """
    for face in open_faces(faces):
        new_face = [face[0]]
        for index in face[1:]:
            if new_face[-1] != index:
                new_face.append(index)
        if len(new_face) < 3:
            continue
        if close:
            new_face.append(new_face[0])
        yield tuple(new_face)


def all_edges(faces: Iterable[Face]) -> Iterator[Edge]:
    """Yields all face edges as int tuples."""
    for face in open_faces(faces):
        yield from face_edges(face)


def face_edges(face: Face) -> Iterable[Edge]:
    """Yields all edges of a single open face as int tuples."""
    size = len(face)
    for index in range(size):
        yield face[index], face[(index + 1) % size]


def get_edge_stats(faces: Iterable[Face]) -> EdgeStats:
    """Returns the edge statistics.

    The Edge statistic contains for each edge `(a, b)` the :class:`EdgeStat` as
    tuple `(count, balance)` where the vertex index `a` is always smaller than
    the vertex index `b`.

    The edge count is how often this edge is used in faces as `(a, b)` or
    `(b, a)` and the balance is the count of edge `(a, b)` minus the count of
    edge `(b, a)` and should be 0 in "healthy" closed surfaces.
    A balance not 0 indicates an error which may be double coincident faces or
    mixed face vertex orders.

    """
    new_edge = EdgeStat(0, 0)
    stats: EdgeStats = {}
    for a, b in all_edges(faces):
        edge = a, b
        orientation = +1
        if a > b:
            edge = b, a
            orientation = -1
        # for all edges: count should be 2 and balance should be 0
        count, balance = stats.get(edge, new_edge)
        stats[edge] = EdgeStat(count + 1, balance + orientation)
    return stats


def estimate_face_normals_direction(
    vertices: Sequence[Vec3], faces: Sequence[Face]
) -> float:
    """Returns the estimated face-normals direction as ``float`` value
    in the range [-1.0, 1.0] for a closed surface.

    This heuristic works well for simple convex hulls but struggles with
    more complex structures like a torus (doughnut).

    A counter-clockwise (ccw) vertex arrangement is assumed but a
    clockwise (cw) arrangement works too but the values are reversed.

    The closer the value to 1.0 (-1.0 for cw) the more likely all normals
    pointing outwards from the surface.

    The closer the value to -1.0 (1.0 for cw) the more likely all normals
    pointing inwards from the surface.

    """
    n_vertices = len(vertices)
    if n_vertices == 0:
        return 0.0

    mesh_centroid = Vec3.sum(vertices) / n_vertices
    count = 0
    direction_sum = 0.0
    for face in faces:
        if len(face) < 3:
            continue
        try:
            face_vertices = tuple(vertices[i] for i in face)
        except IndexError:
            continue
        face_centroid = Vec3.sum(face_vertices) / len(face)
        try:
            face_normal = normal_vector_3p(
                face_vertices[0], face_vertices[1], face_vertices[2]
            )
        except ZeroDivisionError:
            continue
        try:
            outward_vec = (face_centroid - mesh_centroid).normalize()
        except ZeroDivisionError:
            continue
        direction_sum += face_normal.dot(outward_vec)
        count += 1
    if count > 0:
        return direction_sum / count
    return 0.0


def flip_face_normals(
    faces: Sequence[Sequence[int]],
) -> Iterator[Sequence[int]]:
    for face in faces:
        yield tuple(reversed(face))


def volume6(a: Vec3, b: Vec3, c: Vec3) -> float:
    """
    Returns six times the volume of the tetrahedron determined by abc
    and the origin (0, 0, 0).
    The volume is positive if the origin is on the negative side of abc,
    where the positive side is determined by the right-hand--rule.
    So the volume is positive if the ccw normal to abc points outside the
    tetrahedron.

    This code is taken from chull.c; see "Computational Geometry in C."
    """
    return (
        a.z * (b.x * c.y - b.y * c.x)
        + a.y * (b.z * c.x - b.x * c.z)
        + a.x * (b.y * c.z - b.z * c.y)
    )


def area_3d(polygon: Sequence[Vec3]) -> float:
    try:
        ocs = OCS(safe_normal_vector(polygon))
    except ZeroDivisionError:
        return 0.0
    return area(ocs.points_from_wcs(polygon))


# Mesh Topology Analysis using the Euler Characteristic
# https://max-limper.de/publications/Euler/index.html


class MeshDiagnose:
    def __init__(self, mesh: MeshBuilder):
        self._mesh = mesh
        self._edge_stats: EdgeStats = {}
        self._bbox = BoundingBox()
        self._face_normals: List[Vec3] = []

    @property
    def vertices(self) -> Sequence[Vec3]:
        """Sequence of mesh vertices as :class:`~ezdxf.math.Vec3` instances"""
        return self._mesh.vertices

    @property
    def faces(self) -> Sequence[Face]:
        """Sequence of faces as ``Sequence[int]``"""
        return self._mesh.faces

    @property
    def face_normals(self) -> Sequence[Vec3]:
        """Returns all face normal vectors  as sequence. The ``NULLVEC``
        instance is used as normal vector for degenerated faces. (cached data)

        """
        if len(self._face_normals) == 0:
            self._face_normals = list(self._mesh.face_normals())
        return self._face_normals

    @property
    def bbox(self) -> BoundingBox:
        """Returns the :class:`~ezdxf.math.BoundingBox` of the mesh. (cached data)"""
        if not self._bbox.has_data:
            self._bbox = self._mesh.bbox()
        return self._bbox

    @property
    def n_vertices(self) -> int:
        """Returns the vertex count."""
        return len(self.vertices)

    @property
    def n_faces(self) -> int:
        """Returns the face count."""
        return len(self.faces)

    @property
    def n_edges(self) -> int:
        """Returns the unique edge count. (cached data)"""
        return len(self.edge_stats)

    @property
    def edge_stats(self) -> EdgeStats:
        """Returns the edge statistics as a ``dict``. The dict-key is the edge
        as tuple of two vertex indices `(a, b)` where `a` is always smaller than
        `b`. The dict-value is an :class:`EdgeStat` tuple of edge count and edge
        balance, see :class:`EdgeStat` for the definition of edge count and
        edge balance. (cached data)
        """
        if len(self._edge_stats) == 0:
            self._edge_stats = get_edge_stats(self.faces)
        return self._edge_stats

    @property
    def euler_characteristic(self) -> int:
        """Returns the Euler characteristic:
        https://en.wikipedia.org/wiki/Euler_characteristic

        This number is always 2 for convex polyhedra.
        """
        return self.n_vertices - self.n_edges + self.n_faces

    @property
    def is_edge_balance_broken(self) -> bool:
        """Returns ``True`` if the edge balance is broken, this indicates a
        topology error for closed surfaces. A non-broken edge balance reflects
        that each edge connects two faces, where the edge is clockwise oriented
        in the first face and counter-clockwise oriented in the second face.
        A broken edge balance indicates possible topology errors like mixed
        face vertex orientations or a non-manifold mesh where an edge connects
        more than two faces. (cached data)

        """
        return any(e.balance != 0 for e in self.edge_stats.values())

    @property
    def is_manifold(self) -> bool:
        """Returns ``True`` if all edges have an edge count < 3. (cached data)

        A non-manifold mesh has edges with 3 or more connected faces.

        """
        return all(edge.count < 3 for edge in self.edge_stats.values())

    @property
    def is_closed_surface(self) -> bool:
        """Returns ``True`` if the mesh has a closed surface.
        This method does not require a unified face orientation.
        If multiple separated meshes are present the state is only ``True`` if
        **all** meshes have a closed surface. (cached data)

        Returns ``False`` for non-manifold meshes.

        """
        return all(edge.count == 2 for edge in self.edge_stats.values())

    def total_edge_count(self) -> int:
        """Returns the total edge count of all faces, shared edges are counted
        separately for each face. In closed surfaces this count should be 2x
        the unique edge count :attr:`n_edges`. (cached data)
        """
        return sum(e.count for e in self.edge_stats.values())

    def unique_edges(self) -> Iterable[Edge]:
        """Yields the unique edges of the mesh as int 2-tuples. (cached data)"""
        return self.edge_stats.keys()

    def estimate_face_normals_direction(self) -> float:
        """Returns the estimated face-normals direction as ``float`` value
        in the range [-1.0, 1.0] for a closed surface.

        This heuristic works well for simple convex hulls but struggles with
        more complex structures like a torus (doughnut).

        A counter-clockwise (ccw) vertex arrangement for outward pointing faces
        is assumed but a clockwise (cw) arrangement works too but the return
        values are reversed.

        The closer the value to 1.0 (-1.0 for cw) the more likely all normals
        pointing outwards from the surface.

        The closer the value to -1.0 (1.0 for cw) the more likely all normals
        pointing inwards from the surface.

        There are no exact confidence values if all faces pointing outwards,
        here some examples for surfaces created by :mod:`ezdxf.render.forms`
        functions:

            - :func:`~ezdxf.render.forms.cube` returns 1.0
            - :func:`~ezdxf.render.forms.cylinder` returns 0.9992
            - :func:`~ezdxf.render.forms.sphere` returns 0.9994
            - :func:`~ezdxf.render.forms.cone` returns 0.9162
            - :func:`~ezdxf.render.forms.cylinder` with all hull faces pointing
              outwards but caps pointing inwards returns 0.7785 but the
              property :attr:`is_edge_balance_broken` returns ``True`` which
              indicates the mixed vertex orientation
            - and the estimation of 0.0469 for a :func:`~ezdxf.render.forms.torus`
              is barely usable

        """
        return estimate_face_normals_direction(self.vertices, self.faces)

    def has_non_planar_faces(self) -> bool:
        """Returns ``True`` if any face is non-planar."""
        return not all(
            is_planar_face(face) for face in self._mesh.faces_as_vertices()
        )

    def volume(self) -> float:
        """Returns the volume of a closed surface or 0 otherwise.

        .. warning::

            The face vertices have to be in counter-clockwise order, this
            requirement is not checked by this method.

            The result is not correct for multiple separated meshes in a single
            MeshBuilder object!!!

        """
        if self.is_closed_surface:
            volume = 0.0
            for face in self._mesh.tessellation(3):
                volume += volume6(face[0], face[1], face[2])
            return volume / 6.0
        return 0.0

    def surface_area(self) -> float:
        """Returns the surface area."""
        v = self.vertices
        surface_area = 0.0
        for face in self._mesh.open_faces():
            polygon = [v[i] for i in face]
            surface_area += area_3d(polygon)
        return surface_area

    def centroid(self) -> Vec3:
        """Returns the centroid of all vertices. (center of mass)"""
        if self.n_vertices > 0:
            return Vec3.sum(self.vertices) / self.n_vertices
        return NULLVEC


class MeshBuilder:
    """A simple Mesh builder. Stores a list of vertices and a faces list where
    each face is a list of indices into the vertices list.

    The :meth:`render_mesh` method, renders the mesh into a DXF MESH entity.
    The MESH entity supports ngons in AutoCAD, ngons are polygons with more
    than 4 vertices.

    Can only create new meshes.

    """

    def __init__(self):
        self.vertices: List[Vec3] = []
        # face storage, each face is a tuple of vertex indices (v0, v1, v2, v3, ....)
        self.faces: List[Sequence[int]] = []

    def bbox(self) -> BoundingBox:
        """Returns the :class:`~ezdxf.math.BoundingBox` of the mesh.

        .. versionadded:: 0.18

        """
        return BoundingBox(self.vertices)

    def copy(self):
        """Returns a copy of mesh."""
        return self.from_builder(self)

    def diagnose(self) -> MeshDiagnose:
        """Returns the :class:`MeshDiagnose` object for this mesh.

        .. versionadded:: 0.18

        """
        return MeshDiagnose(self)

    def get_face_vertices(self, index: int) -> Sequence[Vec3]:
        """Returns the face `index` as sequence of :class:`~ezdxf.math.Vec3`
        objects.

        .. versionadded:: 0.18

        """
        vertices = self.vertices
        return tuple(vertices[vi] for vi in self.faces[index])

    def get_face_normal(self, index: int) -> Vec3:
        """Returns the normal vector of the face `index` as :class:`~ezdxf.math.Vec3`,
        returns the ``NULLVEC`` instance for degenerated  faces.

        .. versionadded:: 0.18

        """
        face = self.get_face_vertices(index)
        try:
            return safe_normal_vector(face)
        except (ValueError, ZeroDivisionError):
            return NULLVEC

    def face_normals(self) -> Iterator[Vec3]:
        """Yields all face normals, yields the ``NULLVEC`` instance for degenerated
        faces.

        .. versionadded:: 0.18

        """
        for face in self.faces_as_vertices():
            try:
                yield safe_normal_vector(face)
            except (ValueError, ZeroDivisionError):
                yield NULLVEC

    def faces_as_vertices(self) -> Iterator[List[Vec3]]:
        """Yields all faces as list of vertices."""
        v = self.vertices
        for face in self.faces:
            yield [v[index] for index in face]

    def open_faces(self) -> Iterator[Face]:
        """Yields all faces as sequence of integers where the first vertex
        is not coincident with the last vertex.

        .. versionadded:: 0.18

        """
        yield from open_faces(self.faces)

    def add_face(self, vertices: Iterable[UVec]) -> None:
        """Add a face as vertices list to the mesh. A face requires at least 3
        vertices, each vertex is a ``(x, y, z)`` tuple or
        :class:`~ezdxf.math.Vec3` object. The new vertex indices are stored as
        face in the :attr:`faces` list.

        Args:
            vertices: list of at least 3 vertices ``[(x1, y1, z1), (x2, y2, z2),
                (x3, y3, y3), ...]``

        """
        self.faces.append(self.add_vertices(vertices))

    def add_vertices(self, vertices: Iterable[UVec]) -> Face:
        """Add new vertices to the mesh, each vertex is a ``(x, y, z)`` tuple
        or a :class:`~ezdxf.math.Vec3` object, returns the indices of the
        `vertices` added to the :attr:`vertices` list.

        e.g. adding 4 vertices to an empty mesh, returns the indices
        ``(0, 1, 2, 3)``, adding additional 4 vertices returns the indices
        ``(4, 5, 6, 7)``.

        Args:
            vertices: list of vertices, vertex as ``(x, y, z)`` tuple or
                :class:`~ezdxf.math.Vec3` objects

        Returns:
            tuple: indices of the `vertices` added to the :attr:`vertices` list

        """
        start_index = len(self.vertices)
        self.vertices.extend(Vec3.generate(vertices))
        return tuple(range(start_index, len(self.vertices)))

    def add_mesh(
        self,
        vertices: List[Vec3] = None,
        faces: List[Face] = None,
        mesh=None,
    ) -> None:
        """Add another mesh to this mesh.

        A `mesh` can be a :class:`MeshBuilder`, :class:`MeshVertexMerger` or
        :class:`~ezdxf.entities.Mesh` object or requires the attributes
        :attr:`vertices` and :attr:`faces`.

        Args:
            vertices: list of vertices, a vertex is a ``(x, y, z)`` tuple or
                :class:`~ezdxf.math.Vec3` object
            faces: list of faces, a face is a list of vertex indices
            mesh: another mesh entity

        """
        if mesh is not None:
            vertices = Vec3.list(mesh.vertices)
            faces = mesh.faces

        if vertices is None:
            raise ValueError("Requires vertices or another mesh.")
        faces = faces or []
        indices = self.add_vertices(vertices)

        for face_vertices in open_faces(faces):
            self.faces.append(tuple(indices[vi] for vi in face_vertices))

    def render_mesh(
        self,
        layout: GenericLayoutType,
        dxfattribs=None,
        matrix: Matrix44 = None,
        ucs: UCS = None,
    ):
        """Render mesh as :class:`~ezdxf.entities.Mesh` entity into `layout`.

        Args:
            layout: :class:`~ezdxf.layouts.BaseLayout` object
            dxfattribs: dict of DXF attributes e.g. ``{'layer': 'mesh', 'color': 7}``
            matrix: transformation matrix of type :class:`~ezdxf.math.Matrix44`
            ucs: transform vertices by :class:`~ezdxf.math.UCS` to :ref:`WCS`

        """
        dxfattribs = dict(dxfattribs) if dxfattribs else {}
        vertices = self.vertices
        if matrix is not None:
            vertices = matrix.transform_vertices(vertices)
        if ucs is not None:
            vertices = ucs.points_to_wcs(vertices)  # type: ignore
        mesh = layout.add_mesh(dxfattribs=dxfattribs)
        with mesh.edit_data() as data:
            # data will be copied at setting in edit_data()
            # ignore edges and creases!
            data.vertices = list(vertices)
            data.faces = list(self.faces)  # type: ignore
        return mesh

    def render_normals(
        self,
        layout: GenericLayoutType,
        length: float = 1,
        relative=True,
        dxfattribs=None,
    ):
        """Render face normals as :class:`~ezdxf.entities.Line` entities into
        `layout`, useful to check orientation of mesh faces.

        Args:
            layout: :class:`~ezdxf.layouts.BaseLayout` object
            length: visual length of normal, use length < 0 to point normals in
                opposite direction
            relative: scale length relative to face size if ``True``
            dxfattribs: dict of DXF attributes e.g. ``{'layer': 'normals', 'color': 6}``

        """
        dxfattribs = dict(dxfattribs) if dxfattribs else {}
        for face in self.faces_as_vertices():
            count = len(face)
            if count < 3:
                continue
            center = Vec3.sum(face) / count
            try:
                n = safe_normal_vector(face)
            except ZeroDivisionError:
                continue
            if relative:
                _length = (face[0] - center).magnitude * length
            else:
                _length = length
            layout.add_line(center, center + n * _length, dxfattribs=dxfattribs)

    @classmethod
    def from_mesh(cls: Type[T], other: Union[MeshBuilder, Mesh]) -> T:
        """Create new mesh from other mesh as class method.

        Args:
            other: `mesh` of type :class:`MeshBuilder` and inherited or DXF
                :class:`~ezdxf.entities.Mesh` entity or any object providing
                attributes :attr:`vertices`, :attr:`edges` and :attr:`faces`.

        """
        # just copy properties
        mesh = cls()
        assert isinstance(mesh, MeshBuilder)
        mesh.add_mesh(mesh=other)
        return mesh  # type: ignore

    @classmethod
    def from_polyface(cls: Type[T], other: Union[Polymesh, Polyface]) -> T:
        """Create new mesh from a  :class:`~ezdxf.entities.Polyface` or
        :class:`~ezdxf.entities.Polymesh` object.

        """
        if other.dxftype() != "POLYLINE":
            raise TypeError(f"Unsupported DXF type: {other.dxftype()}")

        mesh = cls()
        assert isinstance(mesh, MeshBuilder)
        if other.is_poly_face_mesh:
            _, faces = other.indexed_faces()  # type: ignore
            for face in faces:
                mesh.add_face(face.points())
        elif other.is_polygon_mesh:
            vertices = other.get_mesh_vertex_cache()  # type: ignore
            for m in range(other.dxf.m_count - 1):
                for n in range(other.dxf.n_count - 1):
                    mesh.add_face(
                        (
                            vertices[m, n],
                            vertices[m, n + 1],
                            vertices[m + 1, n + 1],
                            vertices[m + 1, n],
                        )
                    )
        else:
            raise TypeError("Not a polymesh or polyface.")
        return mesh  # type: ignore

    def render_polyface(
        self,
        layout: GenericLayoutType,
        dxfattribs=None,
        matrix: Matrix44 = None,
        ucs: UCS = None,
    ):
        """Render mesh as :class:`~ezdxf.entities.Polyface` entity into
        `layout`.

        Args:
            layout: :class:`~ezdxf.layouts.BaseLayout` object
            dxfattribs: dict of DXF attributes e.g. ``{'layer': 'mesh', 'color': 7}``
            matrix: transformation matrix of type :class:`~ezdxf.math.Matrix44`
            ucs: transform vertices by :class:`~ezdxf.math.UCS` to :ref:`WCS`

        .. versionchanged:: 0.18

            Uses the :meth:`tessellation` method to process ngons with more the
            4 vertices which can handle concave faces.

        """
        dxfattribs = dict(dxfattribs) if dxfattribs else {}
        polyface = layout.add_polyface(dxfattribs=dxfattribs)
        t = MeshTransformer.from_builder(self)
        if matrix is not None:
            t.transform(matrix)
        if ucs is not None:
            t.transform(ucs.matrix)
        polyface.append_faces(
            t.tessellation(max_vertex_count=4),
            dxfattribs=dxfattribs,
        )
        return polyface

    def render_3dfaces(
        self,
        layout: GenericLayoutType,
        dxfattribs=None,
        matrix: Matrix44 = None,
        ucs: UCS = None,
    ):
        """Render mesh as :class:`~ezdxf.entities.Face3d` entities into
        `layout`.

        Args:
            layout: :class:`~ezdxf.layouts.BaseLayout` object
            dxfattribs: dict of DXF attributes e.g. ``{'layer': 'mesh', 'color': 7}``
            matrix: transformation matrix of type :class:`~ezdxf.math.Matrix44`
            ucs: transform vertices by :class:`~ezdxf.math.UCS` to :ref:`WCS`

        .. versionchanged:: 0.18

            Uses the :meth:`tessellation` method to process ngons with more the
            4 vertices which can handle concave faces.

        """
        dxfattribs = dict(dxfattribs) if dxfattribs else {}
        t = MeshTransformer.from_builder(self)
        if matrix is not None:
            t.transform(matrix)
        if ucs is not None:
            t.transform(ucs.matrix)
        for face in t.tessellation(max_vertex_count=4):
            layout.add_3dface(face, dxfattribs=dxfattribs)

    @classmethod
    def from_builder(cls: Type[T], other: MeshBuilder) -> T:
        """Create new mesh from other mesh builder, faster than
        :meth:`from_mesh` but supports only :class:`MeshBuilder` and inherited
        classes.

        """
        # just copy properties
        mesh = cls()
        assert isinstance(mesh, MeshBuilder)

        # DO NOT COPY CACHES!
        mesh.vertices = list(other.vertices)
        mesh.faces = list(other.faces)
        return mesh  # type: ignore

    def merge_coplanar_faces(self, passes: int = 1) -> MeshTransformer:
        """Returns a new :class:`MeshBuilder` object with merged adjacent
        coplanar faces.

        The faces have to share at least two vertices and have to have the
        same clockwise or counter-clockwise vertex order.

        The current implementation is not very capable!

        .. versionadded:: 0.18

        """
        mesh = self
        for _ in range(passes):
            mesh = _merge_adjacent_coplanar_faces(mesh.vertices, mesh.faces)
        return MeshTransformer.from_builder(mesh)

    def subdivide(self, level: int = 1, quads=True) -> MeshTransformer:
        """Returns a new :class:`MeshTransformer` object with all faces subdivided.

        Args:
             level: subdivide levels from 1 to max of 5
             quads: create quad faces if ``True`` else create triangles
        """
        mesh = self
        level = min(int(level), 5)
        while level > 0:
            mesh = _subdivide(mesh, quads)  # type: ignore
            level -= 1
        return MeshTransformer.from_builder(mesh)

    def optimize_vertices(self, precision: int = 6) -> MeshTransformer:
        """Returns a new mesh with optimized vertices. Coincident vertices are
        merged together and all faces are open faces (first vertex != last
        vertex). Uses internally the :class:`MeshVertexMerger` class to merge
        vertices.

        .. versionadded:: 0.18

        """
        mesh = MeshVertexMerger(precision=precision)
        mesh.add_mesh(mesh=self)
        return MeshTransformer.from_builder(mesh)

    def subdivide_ngons(self, max_vertex_count=4) -> Iterator[Sequence[Vec3]]:
        """Yields all faces as sequence of :class:`~ezdxf.math.Vec3` instances,
        where all ngons which have more than `max_vertex_count` vertices gets
        subdivided.
        In contrast to the :meth:`tessellation` method, creates this method a
        new vertex in the centroid of the face. This can create a more regular
        tessellation but only works reliable for convex faces!

        .. versionadded:: 0.18

        """
        yield from subdivide_ngons(self.faces_as_vertices(), max_vertex_count)

    def tessellation(
        self, max_vertex_count: int = 4
    ) -> Iterator[Sequence[Vec3]]:
        """Yields all faces as sequence of :class:`~ezdxf.math.Vec3` instances,
        each face has no more vertices than the given `max_vertex_count`. This
        method uses the "ear clipping" algorithm which works with concave faces
        too and does not create any additional vertices.

        .. versionadded:: 0.18

        """
        from ezdxf.math.triangulation import mapbox_earcut_3d

        for face in self.faces_as_vertices():
            if len(face) <= max_vertex_count:
                yield face
            else:
                yield from mapbox_earcut_3d(face)

    def mesh_tessellation(self, max_vertex_count: int = 4) -> MeshTransformer:
        """Returns a new :class:`MeshTransformer` instance, where each face has
        no more vertices than the given `max_vertex_count`.

        The `fast` mode uses a shortcut for faces with less than 6 vertices
        which may not work for concave faces!

        .. versionadded:: 0.18

        """
        mesh = MeshVertexMerger()
        for face in self.tessellation(max_vertex_count=max_vertex_count):
            mesh.add_face(face)
        return MeshTransformer.from_builder(mesh)

    def flip_normals(self) -> None:
        """Flips the normals of all faces by reversing the vertex order inplace.

        .. versionadded:: 0.18

        """
        self.faces = list(flip_face_normals(self.faces))

    def separate_meshes(self) -> List[MeshTransformer]:
        """A single :class:`MeshBuilder` instance can store multiple separated
        meshes. This function returns this separated meshes as multiple
        :class:`MeshTransformer` instances.

        .. versionadded:: 0.18

        """
        return list(separate_meshes(self))

    def normalize_faces(self) -> None:
        """Removes duplicated vertex indices from faces and stores all faces as
        open faces, where the last vertex is not coincident with the first
        vertex.

        .. versionadded:: 0.18

        """
        self.faces = list(normalize_faces(self.faces, close=False))

    def face_orientation_detector(
        self, reference: int = 0
    ) -> FaceOrientationDetector:
        """Returns a :class:`FaceOrientationDetector` or short `fod` instance.
        The forward orientation is defined by the `reference` face which is
        0 by default.

        The `fod` can check if all faces are reachable from the reference face
        and if all faces have the same orientation. The `fod` can be reused to
        unify the face orientation of the mesh.

        """
        return FaceOrientationDetector(self, reference=reference)

    def unify_face_normals(
        self, *, fod: FaceOrientationDetector = None
    ) -> MeshTransformer:
        """Returns a new :class:`MeshTransformer` object with unified
        face normal vectors of all faces.
        The forward direction (not necessarily outwards) is defined by the
        face-normals of the majority of the faces.
        This function can not process non-manifold meshes (more than two faces
        are connected by a single edge) or multiple disconnected meshes in a
        single :class:`MeshBuilder` object.

        It is possible to pass in an existing :class:`FaceOrientationDetector`
        instance as argument `fod`.

        Raises:
            NonManifoldError: non-manifold mesh
            MultipleMeshesError: the :class:`MeshBuilder` object contains multiple disconnected meshes

        .. versionadded:: 0.18

        """
        return unify_face_normals_by_majority(self, fod=fod)

    def unify_face_normals_by_reference(
        self,
        reference: int = 0,
        *,
        force_outwards=False,
        fod: FaceOrientationDetector = None,
    ) -> MeshTransformer:
        """Returns a new :class:`MeshTransformer` object with unified
        face normal vectors of all faces.
        The forward direction (not necessarily outwards) is defined by the
        reference face, which is the first face of the `mesh` by default.
        This function can not process non-manifold
        meshes (more than two faces are connected by a single edge) or multiple
        disconnected meshes in a single :class:`MeshBuilder` object.

        The outward direction of all face normals can be forced by stetting
        the argument `force_outwards` to ``True`` but this works only for closed
        surfaces, and it's time-consuming!

        It is not possible to check for a closed surface as long the face normal
        vectors are not unified. But it can be done afterward by the attribute
        :meth:`MeshDiagnose.is_closed_surface` to see if the result is
        trustworthy.

        It is possible to pass in an existing :class:`FaceOrientationDetector`
        instance as argument `fod`.

        Args:
            reference: index of the reference face
            force_outwards: forces face-normals to point outwards, this works
                only for closed surfaces, and it's time-consuming!
            fod: :class:`FaceOrientationDetector` instance

        Raises:
            ValueError: non-manifold mesh or the :class:`MeshBuilder` object
                contains multiple disconnected meshes

        .. versionadded:: 0.18

        """
        mesh = unify_face_normals_by_reference(
            self, reference=reference, fod=fod
        )
        if force_outwards:
            _force_face_normals_pointing_outwards(mesh, reference)
        return mesh


class MeshTransformer(MeshBuilder):
    """A mesh builder with inplace transformation support."""

    def transform(self, matrix: Matrix44):
        """Transform mesh inplace by applying the transformation `matrix`.

        Args:
            matrix: 4x4 transformation matrix as :class:`~ezdxf.math.Matrix44`
                object

        """
        self.vertices = list(matrix.transform_vertices(self.vertices))
        return self

    def translate(
        self, dx: Union[float, UVec] = 0, dy: float = 0, dz: float = 0
    ):
        """Translate mesh inplace.

        Args:
            dx: translation in x-axis or translation vector
            dy: translation in y-axis
            dz: translation in z-axis

        """
        if isinstance(dx, (float, int)):
            t = Vec3(dx, dy, dz)
        else:
            t = Vec3(dx)
        self.vertices = [t + v for v in self.vertices]
        return self

    def scale(self, sx: float = 1, sy: float = 1, sz: float = 1):
        """Scale mesh inplace.

        Args:
            sx: scale factor for x-axis
            sy: scale factor for y-axis
            sz: scale factor for z-axis

        """
        self.vertices = [
            Vec3(x * sx, y * sy, z * sz) for x, y, z in self.vertices
        ]
        return self

    def scale_uniform(self, s: float):
        """Scale mesh uniform inplace.

        Args:
            s: scale factor for x-, y- and z-axis

        """
        self.vertices = [v * s for v in self.vertices]
        return self

    def rotate_x(self, angle: float):
        """Rotate mesh around x-axis about `angle` inplace.

        Args:
            angle: rotation angle in radians

        """
        self.vertices = list(
            Matrix44.x_rotate(angle).transform_vertices(self.vertices)
        )
        return self

    def rotate_y(self, angle: float):
        """Rotate mesh around y-axis about `angle` inplace.

        Args:
            angle: rotation angle in radians

        """
        self.vertices = list(
            Matrix44.y_rotate(angle).transform_vertices(self.vertices)
        )
        return self

    def rotate_z(self, angle: float):
        """Rotate mesh around z-axis about `angle` inplace.

        Args:
            angle: rotation angle in radians

        """
        self.vertices = list(
            Matrix44.z_rotate(angle).transform_vertices(self.vertices)
        )
        return self

    def rotate_axis(self, axis: UVec, angle: float):
        """Rotate mesh around an arbitrary axis located in the origin (0, 0, 0)
        about `angle`.

        Args:
            axis: rotation axis as Vec3
            angle: rotation angle in radians

        """
        self.vertices = list(
            Matrix44.axis_rotate(axis, angle).transform_vertices(self.vertices)
        )
        return self


def _subdivide(mesh, quads=True) -> MeshVertexMerger:
    """Returns a new :class:`MeshVertexMerger` object with subdivided faces
    and edges.

    Args:
         quads: create quad faces if ``True`` else create triangles

    """
    new_mesh = MeshVertexMerger()
    for vertices in mesh.faces_as_vertices():
        if len(vertices) < 3:
            continue
        for face in subdivide_face(vertices, quads):
            new_mesh.add_face(face)
    return new_mesh


class MeshVertexMerger(MeshBuilder):
    """Subclass of :class:`MeshBuilder`

    Mesh with unique vertices and no doublets, but needs extra memory for
    bookkeeping.

    :class:`MeshVertexMerger` creates a key for every vertex by rounding its
    components by the Python :func:`round` function and a given `precision`
    value. Each vertex with the same key gets the same vertex index, which is
    the index of first vertex with this key, so all vertices with the same key
    will be located at the location of this first vertex. If you want an average
    location of all vertices with the same key use the
    :class:`MeshAverageVertexMerger` class.

    Args:
        precision: floating point precision for vertex rounding

    """

    # can not support vertex transformation
    def __init__(self, precision: int = 6):
        """
        Args:
            precision: floating point precision for vertex rounding

        """
        super().__init__()
        self.ledger: Dict[Vec3, int] = {}
        self.precision: int = precision

    def add_vertices(self, vertices: Iterable[UVec]) -> Face:
        """Add new `vertices` only, if no vertex with identical (x, y, z)
        coordinates already exist, else the index of the existing vertex is
        returned as index of the added vertices.

        Args:
            vertices: list of vertices, vertex as (x, y, z) tuple or
                :class:`~ezdxf.math.Vec3` objects

        Returns:
            indices of the added `vertices`

        """
        indices = []
        precision = self.precision
        for vertex in Vec3.generate(vertices):
            key = vertex.round(precision)
            try:
                indices.append(self.ledger[key])
            except KeyError:
                index = len(self.vertices)
                self.vertices.append(vertex)
                self.ledger[key] = index
                indices.append(index)
        return tuple(indices)

    def index(self, vertex: UVec) -> int:
        """Get index of `vertex`, raises :class:`IndexError` if not found.

        Args:
            vertex: ``(x, y, z)`` tuple or :class:`~ezdxf.math.Vec3` object

        (internal API)
        """
        try:
            return self.ledger[Vec3(vertex).round(self.precision)]
        except KeyError:
            raise IndexError(f"Vertex {str(vertex)} not found.")

    @classmethod
    def from_builder(cls, other: MeshBuilder) -> MeshVertexMerger:
        """Create new mesh from other mesh builder."""
        # rebuild from scratch to create a valid ledger
        return cls.from_mesh(other)


class MeshAverageVertexMerger(MeshBuilder):
    """Subclass of :class:`MeshBuilder`

    Mesh with unique vertices and no doublets, but needs extra memory for
    bookkeeping and runtime for calculation of average vertex location.

    :class:`MeshAverageVertexMerger` creates a key for every vertex by rounding
    its components by the Python :func:`round` function and a given `precision`
    value. Each vertex with the same key gets the same vertex index, which is the
    index of first vertex with this key, the difference to the
    :class:`MeshVertexMerger` class is the calculation of the average location
    for all vertices with the same key, this needs extra memory to keep track of
    the count of vertices for each key and extra runtime for updating the vertex
    location each time a vertex with an existing key is added.

    Args:
        precision: floating point precision for vertex rounding

    """

    # can not support vertex transformation
    def __init__(self, precision: int = 6):
        super().__init__()
        self.ledger: Dict[
            Vec3, Tuple[int, int]
        ] = {}  # each key points to a tuple (vertex index, vertex count)
        self.precision: int = precision

    def add_vertices(self, vertices: Iterable[UVec]) -> Face:
        """Add new `vertices` only, if no vertex with identical ``(x, y, z)``
        coordinates already exist, else the index of the existing vertex is
        returned as index of the added vertices.

        Args:
            vertices: list of vertices, vertex as ``(x, y, z)`` tuple or
            :class:`~ezdxf.math.Vec3` objects

        Returns:
            tuple: indices of the `vertices` added to the
            :attr:`~MeshBuilder.vertices` list

        """
        indices = []
        precision = self.precision
        for vertex in Vec3.generate(vertices):
            key = vertex.round(precision)
            try:
                index, count = self.ledger[key]
            except KeyError:  # new key
                index = len(self.vertices)
                self.vertices.append(vertex)
                self.ledger[key] = (index, 1)
            else:  # update key entry
                # calculate new average location
                average = (self.vertices[index] * count) + vertex
                count += 1
                # update vertex location
                self.vertices[index] = average / count
                # update ledger
                self.ledger[key] = (index, count)
            indices.append(index)
        return tuple(indices)

    def index(self, vertex: UVec) -> int:
        """Get index of `vertex`, raises :class:`IndexError` if not found.

        Args:
            vertex: ``(x, y, z)`` tuple or :class:`~ezdxf.math.Vec3` object

        (internal API)
        """
        try:
            return self.ledger[Vec3(vertex).round(self.precision)][0]
        except KeyError:
            raise IndexError(f"Vertex {str(vertex)} not found.")

    @classmethod
    def from_builder(cls, other: MeshBuilder) -> MeshAverageVertexMerger:
        """Create new mesh from other mesh builder."""
        # rebuild from scratch to create a valid ledger
        return cls.from_mesh(other)


class _XFace:
    __slots__ = ("fingerprint", "indices", "_orientation")

    def __init__(self, indices: Face):
        self.fingerprint: int = hash(indices)
        self.indices: Face = indices
        self._orientation: Vec3 = VEC3_SENTINEL

    def orientation(self, vertices: Sequence[Vec3], precision: int = 4) -> Vec3:
        if self._orientation is VEC3_SENTINEL:
            orientation = NULLVEC
            v0, v1, *v = [vertices[i] for i in self.indices]
            for v2 in v:
                try:
                    orientation = normal_vector_3p(v0, v1, v2).round(precision)
                    break
                except ZeroDivisionError:
                    continue
            self._orientation = orientation
        return self._orientation


def _merge_adjacent_coplanar_faces(
    vertices: List[Vec3], faces: List[Face], precision: int = 4
) -> MeshVertexMerger:
    oriented_faces: Dict[Vec3, List[_XFace]] = {}
    extended_faces: List[_XFace] = []
    for face in faces:
        if len(face) < 3:
            raise ValueError("found invalid face count < 3")
        xface = _XFace(face)
        extended_faces.append(xface)
        oriented_faces.setdefault(
            xface.orientation(vertices, precision), []
        ).append(xface)

    mesh = MeshVertexMerger()
    done = set()
    for xface in extended_faces:
        if xface.fingerprint in done:
            continue
        done.add(xface.fingerprint)
        face = xface.indices
        orientation = xface.orientation(vertices, precision)
        parallel_faces = oriented_faces[orientation]
        face_set = set(face)
        for parallel_face in parallel_faces:
            if parallel_face.fingerprint in done:
                continue
            common_vertices = face_set.intersection(set(parallel_face.indices))
            # connection by at least 2 vertices required:
            if len(common_vertices) > 1:
                if len(common_vertices) == len(parallel_face.indices):
                    face = merge_full_patch(face, parallel_face.indices)
                else:
                    try:
                        face = merge_connected_paths(
                            face, parallel_face.indices
                        )
                    except (NodeMergingError, DegeneratedPathError):
                        continue
                done.add(parallel_face.fingerprint)
                face_set = set(face)
        v0 = list(remove_colinear_face_vertices([vertices[i] for i in face]))
        mesh.add_face(v0)
    return mesh


VEC3_SENTINEL = Vec3(0, 0, 0)


def remove_colinear_face_vertices(vertices: Sequence[Vec3]) -> Iterator[Vec3]:
    def get_direction(v1: Vec3, v2: Vec3):
        return (v2 - v1).normalize()

    if len(vertices) < 3:
        yield from vertices
        return

    # remove duplicated vertices
    _vertices: List[Vec3] = [vertices[0]]
    for v in vertices[1:]:
        if not v.isclose(_vertices[-1]):
            _vertices.append(v)

    if len(_vertices) < 3:
        if len(_vertices) == 1:
            _vertices.append(_vertices[0])
        yield from _vertices
        return

    start = _vertices[0]
    prev_vertex = VEC3_SENTINEL
    current_direction = VEC3_SENTINEL
    start_index = 0

    # find start direction
    yield start
    while current_direction is VEC3_SENTINEL:
        start_index += 1
        try:
            prev_vertex = vertices[start_index]
        except IndexError:
            yield prev_vertex
            return
        current_direction = get_direction(start, prev_vertex)

    yielded_anything = False
    _vertices.append(start)
    for vertex in _vertices[start_index:]:
        try:
            if get_direction(start, vertex).isclose(current_direction):
                prev_vertex = vertex
                continue
        except ZeroDivisionError:
            continue
        yield prev_vertex
        yielded_anything = True
        start = prev_vertex
        current_direction = get_direction(start, vertex)
        prev_vertex = vertex

    if not yielded_anything:
        yield _vertices[-2]  # last vertex


def merge_connected_paths(
    p1: Sequence[int], p2: Sequence[int]
) -> Sequence[int]:
    def build_nodes(p: Sequence[int]):
        nodes = {e1: e2 for e1, e2 in zip(p, p[1:])}
        nodes[p[-1]] = p[0]
        return nodes

    current_path = build_nodes(p1)
    other_path = build_nodes(p2)
    current_node = p1[0]
    finish = p1[0]
    connected_path = [current_node]
    while True:
        try:
            next_node = current_path[current_node]
        except KeyError:
            raise NodeMergingError
        if next_node in other_path:
            current_path, other_path = other_path, current_path
        if next_node == finish:
            break
        current_node = next_node
        if current_node in connected_path:
            # node duplication is an error, e.g. two path are only connected
            # by one node:
            raise NodeMergingError
        connected_path.append(current_node)

    if len(connected_path) < 3:
        raise DegeneratedPathError
    return connected_path


def merge_full_patch(path: Sequence[int], patch: Sequence[int]):
    count = len(path)
    new_path = []
    for pos, node in enumerate(path):
        prev = path[pos - 1]
        succ = path[(pos + 1) % count]
        if prev in patch and succ in patch:
            continue
        new_path.append(node)
    return new_path


class Lump:
    def __init__(self, face: Face):
        self.edges: Set[Edge] = set()
        self.faces: List[Face] = [face]
        for a, b in face_edges(face):
            # sort vertex indices to guarantee: edge a,b == edge b,a
            self.edges.add((a, b) if a <= b else (b, a))

    def is_connected(self, other: Lump) -> bool:
        return not self.edges.isdisjoint(other.edges)

    def merge(self, other: Lump):
        self.faces.extend(other.faces)
        self.edges.update(other.edges)


def merge_lumps(lumps: Iterable[Lump]) -> List[Lump]:
    merged_lumps = _merge_lumps(lumps)
    prior_len = 0
    while 1 < len(merged_lumps) != prior_len:
        prior_len = len(merged_lumps)
        merged_lumps = _merge_lumps(merged_lumps)
    return merged_lumps


def _merge_lumps(lumps: Iterable[Lump]) -> List[Lump]:
    merged_lumps: List[Lump] = []
    for lump in lumps:
        for base in merged_lumps:
            if lump.is_connected(base):
                base.merge(lump)
                break
        else:
            merged_lumps.append(lump)
    return merged_lumps


def separate_meshes(m: MeshBuilder) -> Iterator[MeshTransformer]:
    """Returns the separated meshes in a single :class:`MeshBuilder` instance
    as multiple :class:`MeshTransformer` instances.
    """
    # At the beginning each face is a separated lump and all connected faces
    # should be merged:
    disconnected_lumps = list(
        merge_lumps(Lump(face) for face in open_faces(m.faces))
    )
    if len(disconnected_lumps) > 1:
        vertices = m.vertices
        # create new separated meshes:
        for lump in disconnected_lumps:
            mesh = MeshVertexMerger()
            for face in lump.faces:
                mesh.add_face(vertices[i] for i in face)
            yield MeshTransformer.from_builder(mesh)
    else:
        yield MeshTransformer.from_builder(m)


def have_away_pointing_normals(f0: Sequence[Vec3], f1: Sequence[Vec3]) -> bool:
    """Returns ``True`` if the normals of the two faces are pointing
    away from the center of the two faces.

    .. warning::

        This does not work for any arbitrary face pair!

    """
    c0 = Vec3.sum(f0) / len(f0)
    c1 = Vec3.sum(f1) / len(f1)
    n0 = normal_vector_3p(f0[0], f0[1], f0[2]) * 0.5
    n1 = normal_vector_3p(f1[0], f1[1], f1[2]) * 0.5
    e0 = c0 + n0
    e1 = c1 + n1
    # distance of centroids
    d0 = c0.distance(c1)
    # distance of normal end points
    d1 = e0.distance(e1)
    return d1 > d0


def face_normals_after_transformation(m: Matrix44) -> bool:
    """Returns the state of face-normals of the unit-cube after the
    transformation `m` was applied.

        - ``True``: face-normals pointing outwards
        - ``False``: face-normals pointing inwards

    The state before the transformation is outward-pointing face-normals.

    """
    from .forms import cube

    unit_cube = cube(True).transform(m)
    bottom, _, _, _, _, top = unit_cube.faces_as_vertices()
    # it is not necessary to check all 3 axis!
    return have_away_pointing_normals(bottom, top)


def _make_edge_mapping(faces: Iterable[Face]) -> Dict[Edge, List[Face]]:
    mapping: Dict[Edge, List[Face]] = {}
    for face in faces:
        for edge in face_edges(face):
            mapping.setdefault(edge, []).append(face)
    return mapping


class FaceOrientationDetector:
    """
    Helper class for face orientation and face normal vector detection. Use the
    method :meth:`MeshBuilder.face_orientation_detector` to create an instance.

    The face orientation detector classifies the faces of a mesh by their
    forward or backward orientation.
    The forward orientation is defined by a reference face, which is the first
    face of the mesh by default and this orientation is not necessarily outwards.

    This class has some overlapping features with :class:`MeshDiagnose` but it
    has a longer setup time and needs more memory than :class:`MeshDiagnose`.

    Args:
        mesh: source mesh as :class:`MeshBuilder` object
        reference: index of the reference face

    .. versionadded:: 0.18

    """

    def __init__(self, mesh: MeshBuilder, reference: int = 0):
        self._mesh = mesh
        self.edge_mapping: Dict[Edge, List[Face]] = _make_edge_mapping(
            mesh.faces
        )
        self.reference = reference
        self.is_manifold = True  # 2-manifold is meant
        self.forward: Dict[int, Face] = dict()
        self.backward: Dict[int, Face] = dict()
        self.classify_faces(reference)

    @property
    def has_uniform_face_normals(self) -> bool:
        """Returns ``True`` if all reachable faces are forward oriented
        according to the reference face.
        """
        return len(self.backward) == 0

    @property
    def all_reachable(self) -> bool:
        """Returns ``True`` if all faces are reachable from the reference face
        same as property :attr:`is_single_mesh`.
        """
        return len(self._mesh.faces) == sum(self.count)

    @property
    def is_single_mesh(self) -> bool:
        """Returns ``True`` if only a single mesh is present same as property
        :attr:`all_reachable`.
        """
        return self.all_reachable

    @property
    def count(self) -> Tuple[int, int]:
        """Returns the count of forward and backward oriented faces."""
        return len(self.forward), len(self.backward)

    @property
    def forward_faces(self) -> Iterator[Face]:
        """Yields all forward oriented faces."""
        return iter(self.forward.values())

    @property
    def backward_faces(self) -> Iterator[Face]:
        """Yields all backward oriented faces."""
        return iter(self.backward.values())

    def classify_faces(self, reference: int = 0) -> None:
        """Detect the forward and backward oriented faces.

        The forward and backward orientation has to be defined by a `reference`
        face.
        """

        def add_forward(f: Face):
            forward[id(f)] = f

        def add_backward(f: Face):
            backward[id(f)] = f

        def add_face_to_process(f: Face, orientation: bool):
            key = id(f)
            if key not in forward and key not in backward:  # unprocessed face!
                process_faces.append((f, orientation))

        def add_adjacent_faces_to_process_queue(f: Face, orientation: bool):
            for edge in face_edges(f):
                # find adjacent faces at this edge with same edge orientation:
                linked_faces = edge_mapping[edge]
                if len(linked_faces) > 1:
                    # these faces are backward oriented faces:
                    for linked_face in linked_faces:
                        if linked_face is f:  # skip legit current face
                            continue
                        add_face_to_process(linked_face, not orientation)

                # find all adjacent faces at this edge with reversed edges:
                try:
                    linked_faces = edge_mapping[edge[1], edge[0]]
                except KeyError:
                    # open surface or backward oriented faces present
                    continue
                if len(linked_faces) == 1:
                    add_face_to_process(linked_faces[0], orientation)
                else:  # non-manifold mesh
                    # none of the linked face is processed!
                    self.is_manifold = False

        self.reference = int(reference)
        self.is_manifold = True
        edge_mapping = self.edge_mapping
        forward: Dict[int, Face] = dict()
        backward: Dict[int, Face] = dict()
        # the reference face defines the forward orientation
        process_faces: List[Tuple[Face, bool]] = [
            (self._mesh.faces[reference], True)
        ]
        while len(process_faces):
            # current face and orientation, True = forward, False = backward
            face, face_orientation = process_faces.pop(0)
            if face_orientation:
                add_forward(face)
            else:
                add_backward(face)
            add_adjacent_faces_to_process_queue(face, face_orientation)

        self.forward = forward
        self.backward = backward

    @property
    def is_closed_surface(self) -> bool:
        """Returns ``True`` if the mesh has a closed surface.
        This method does not require a unified face orientation.
        If multiple separated meshes are present the state is only ``True`` if
        **all** meshes have a closed surface.

        Returns ``False`` for non-manifold meshes.

        """
        if not self.is_manifold:
            return False
        empty: List[Face] = []
        edge_mapping = self.edge_mapping
        # For a closed surface all edges have to connect exact 2 faces.
        for edge in edge_mapping.keys():
            forward_connected_faces = edge_mapping.get(edge, empty)
            reversed_edge = edge[1], edge[0]
            backward_connected_faces = edge_mapping.get(reversed_edge, empty)
            if (
                len(forward_connected_faces) + len(backward_connected_faces)
                != 2
            ):
                return False
        return True

    def is_reference_face_pointing_outwards(self) -> bool:
        """Returns ``True`` if the normal vector of the reference face is
        pointing outwards. This works only for meshes with unified faces which
        represent a closed surfaces, and it's a time-consuming calculation!

        """
        from ezdxf.math import is_face_normal_pointing_outwards

        faces = list(self._mesh.faces_as_vertices())
        reference_face = faces[self.reference]
        return is_face_normal_pointing_outwards(faces, reference_face)


def unify_face_normals_by_reference(
    mesh: MeshBuilder,
    *,
    fod: FaceOrientationDetector = None,
    reference: int = 0,
) -> MeshTransformer:
    """Unifies the orientation of all faces of a :class:`MeshBuilder` object.
    The forward orientation is defined by a reference face, which is the first
    face of the `mesh` by default. This function can not process non-manifold
    meshes (more than two faces are connected by a single edge) or multiple
    disconnected meshes in a single :class:`MeshBuilder` object.
    Returns always a copy of the source `mesh` as :class:`MeshTransformer`
    object.

    Args:
        mesh: source :class:`MeshBuilder` object
        fod: an already created :class:`FaceOrientationDetector`
            instance or ``None`` to create one internally.
        reference: index of the reference face for the internally created
            :class:`FaceOrientationDetector` instance

    Raises:
        NonManifoldError: non-manifold mesh
        MultipleMeshesError: :class:`MeshBuilder` object contains multiple
            disconnected meshes

    """
    if fod is None:
        fod = FaceOrientationDetector(mesh, reference)

    def backward_selector(detector: FaceOrientationDetector):
        return detector.backward

    return _unify_face_normals(mesh, fod, backward_selector)


def unify_face_normals_by_majority(
    mesh: MeshBuilder,
    *,
    fod: FaceOrientationDetector = None,
) -> MeshTransformer:
    """Unifies the orientation of all faces of a :class:`MeshBuilder` object.
    The forward orientation is defined by the orientation of the majority of
    the faces.
    This function can not process non-manifold meshes (more than two faces are
    connected by a single edge) or multiple disconnected meshes in a single
    :class:`MeshBuilder` object.
    Returns always a copy of the source `mesh` as :class:`MeshTransformer`
    object.

    Args:
        mesh: source :class:`MeshBuilder` object
        fod: an already created :class:`FaceOrientationDetector`
            instance or ``None`` to create one internally.

    Raises:
        NonManifoldError: non-manifold mesh
        MultipleMeshesError: :class:`MeshBuilder` object contains multiple
            disconnected meshes

    """
    if fod is None:
        fod = FaceOrientationDetector(mesh)

    def backward_selector(detector: FaceOrientationDetector):
        count0, count1 = detector.count
        return detector.backward if count0 >= count1 else detector.forward

    return _unify_face_normals(mesh, fod, backward_selector)


def _unify_face_normals(
    mesh: MeshBuilder,
    fod: FaceOrientationDetector,
    backward_selector,
) -> MeshTransformer:
    """Unifies all faces of a MeshBuilder. The backward_selector() function
    returns the face ledger which represents the backward oriented faces.
    """
    if not fod.is_manifold:
        raise NonManifoldMeshError("non-manifold mesh")
    if not fod.all_reachable:
        raise MultipleMeshesError(
            f"not all faces are reachable from reference face #{fod.reference}"
        )

    new_mesh = MeshTransformer()
    new_mesh.vertices = list(mesh.vertices)
    if not fod.has_uniform_face_normals:
        backward = backward_selector(fod)
        faces = []
        for face in mesh.faces:
            if id(face) in backward:
                faces.append(tuple(reversed(face)))
            else:
                faces.append(tuple(face))
        new_mesh.faces = faces  # type: ignore
    else:
        new_mesh.faces = list(mesh.faces)
    return new_mesh


def _force_face_normals_pointing_outwards(
    mesh: MeshBuilder, reference: int = 0
) -> None:
    """Detect the orientation of the reference face and flip all face normals
    if required.

    Requirements: all face normals have to be unified and the mesh has a closed
    surface

    """
    from ezdxf.math import is_face_normal_pointing_outwards

    faces = list(mesh.faces_as_vertices())
    reference_face = faces[reference]
    if not is_face_normal_pointing_outwards(faces, reference_face):
        mesh.flip_normals()


def normalize_mesh(mesh: MeshBuilder) -> MeshTransformer:
    """Returns a new mesh with these properties:

        - one mesh: removes all meshes except the first mesh starting at the
          first face
        - optimized vertices: merges shared vertices
        - normalized faces: removes duplicated face vertices and faces with less
          than 3 vertices
        - open faces: all faces are open faces where first vertex != last vertex
        - unified face-orientation: all faces have the same orientation (ccw or cw)
        - ccw face-orientation: all face-normals are pointing outwards if the
          mesh has a closed surface

    Raises:
        NonManifoldMeshError: non-manifold mesh

    """
    new_mesh = mesh.optimize_vertices()
    new_mesh.normalize_faces()
    fod = new_mesh.face_orientation_detector(reference=0)

    if not fod.is_manifold:
        raise NonManifoldMeshError("non-manifold mesh")

    if not fod.all_reachable:  # extract first mesh
        new_mesh = list(separate_meshes(new_mesh))[0]
        fod = new_mesh.face_orientation_detector(reference=0)

    if not fod.has_uniform_face_normals:
        new_mesh = unify_face_normals_by_reference(new_mesh, fod=fod)
        fod = new_mesh.face_orientation_detector()

    if fod.is_closed_surface and not fod.is_reference_face_pointing_outwards():
        new_mesh.flip_normals()
    return new_mesh
