Triangular tessellation algorithm for trimmed surfaces.

    This function can be directly used as an input to :func:`.make_triangle_mesh` using ``tessellate_func`` keyword
    argument.

    :param v1: vertex 1
    :type v1: Vertex
    :param v2: vertex 2
    :type v2: Vertex
    :param v3: vertex 3
    :type v3: Vertex
    :param v4: vertex 4
    :type v4: Vertex
    :param vidx: vertex numbering start value
    :type vidx: int
    :param tidx: triangle numbering start value
    :type tidx: int
    :param trims: trim curves
    :type trims: list, tuple
    :param tessellate_args: tessellation arguments
    :type tessellate_args: dict
    :return: lists of vertex and triangle objects in (vertex_list, triangle_list) format
    :type: tuple

def surface_trim_tessellate(v1, v2, v3, v4, vidx, tidx, trims, tessellate_args):
    """ Triangular tessellation algorithm for trimmed surfaces.

    This function can be directly used as an input to :func:`.make_triangle_mesh` using ``tessellate_func`` keyword
    argument.

    :param v1: vertex 1
    :type v1: Vertex
    :param v2: vertex 2
    :type v2: Vertex
    :param v3: vertex 3
    :type v3: Vertex
    :param v4: vertex 4
    :type v4: Vertex
    :param vidx: vertex numbering start value
    :type vidx: int
    :param tidx: triangle numbering start value
    :type tidx: int
    :param trims: trim curves
    :type trims: list, tuple
    :param tessellate_args: tessellation arguments
    :type tessellate_args: dict
    :return: lists of vertex and triangle objects in (vertex_list, triangle_list) format
    :type: tuple
    """
    # Tolerance value
    tol = 10e-8
    tols = tol ** 2
    vtol = ((tols, tols), (-tols, tols), (-tols, -tols), (tols, -tols))

    # Start processing vertices
    vertices = [v1, v2, v3, v4]
    for idx in range(len(vertices)):
        for trim in trims:
            cf = 1 if trim.opt['reversed'] else -1
            uv = [p + (cf * t) for p, t in zip(vertices[idx].uv, vtol[idx])]
            if linalg.wn_poly(uv, trim.evalpts):
                if trim.opt['reversed']:
                    if vertices[idx].opt_get('trim') is None or not vertices[idx].opt_get('trim'):
                        vertices[idx].inside = False
                        vertices[idx].opt = ['no_trim', True]  # always triangulate
                else:
                    vertices[idx].inside = True
                    vertices[idx].opt = ['trim', True]  # always trim
            else:
                if trim.opt['reversed']:
                    if vertices[idx].opt_get('no_trim') is None or not vertices[idx].opt_get('no_trim'):
                        vertices[idx].inside = True

    # If all vertices are marked as inside, then don't generate triangles
    vertices_inside = [v1.inside, v2.inside, v3.inside, v4.inside]
    if all(vertices_inside):
        return [], []

    # Generate edges as rays
    edge1 = ray.Ray(v1.uv, v2.uv)
    edge2 = ray.Ray(v2.uv, v3.uv)
    edge3 = ray.Ray(v3.uv, v4.uv)
    edge4 = ray.Ray(v4.uv, v1.uv)

    # Put all edge rays to a list
    edges = [edge1, edge2, edge3, edge4]

    # List of intersections
    intersections = []

    # Loop all trim curves
    for trim in trims:
        pts = trim.evalpts
        for idx in range(len(pts) - 1):
            # Generate a ray from trim curve's evaluated points
            trim_ray = ray.Ray(pts[idx], pts[idx + 1])

            # Intersection test of the trim curve's ray with all edges
            for idx2 in range(len(edges)):
                t1, t2, status = ray.intersect(edges[idx2], trim_ray)
                if status == ray.RayIntersection.INTERSECT:
                    if 0.0 - tol < t1 < 1.0 + tol and 0.0 - tol < t2 < 1.0 + tol:
                        intersections.append([idx2, t1, edges[idx2].eval(t=t1)])

    # Add first vertex to the end of the list
    vertices.append(v1)

    # Local vertex numbering index
    nvi = 0

    # Process vertices and intersections
    tris_vertices = []
    for idx in range(0, len(vertices) - 1):
        # If two consecutively-ordered vertices are inside the trim, there should be no intersection
        if vertices[idx].inside and vertices[idx + 1].inside:
            continue

        # If current vertex is not inside the trim, add it to the vertex list
        if not vertices[idx].inside:
            tris_vertices.append(vertices[idx])

        # If next vertex is inside the trim, there might be an intersection
        if (not vertices[idx].inside and vertices[idx + 1].inside) or \
                (vertices[idx].inside and not vertices[idx + 1].inside):
            # Try to find all intersections (multiple intersections are possible)
            isects = []
            for isect in intersections:
                if isect[0] == idx:
                    isects.append(isect)

            if isects:
                # Find minimum t value and therefore minimum uv value of the intersection
                t_min = 1.0 + tol
                uv_min = []
                for isect in isects:
                    if isect[1] < t_min:
                        t_min = isect[1]
                        uv_min = isect[2]

                # Check uv for min max
                for pi in range(2):
                    if uv_min[pi] - tol <= 0.0 <= uv_min[pi] + tol:
                        uv_min[pi] = 0.0
                    elif uv_min[pi] - tol <= 1.0 <= uv_min[pi] + tol:
                        uv_min[pi] = 1.0

                # Create a vertex with the minimum uv value
                vert = Vertex()
                vert.id = vidx + nvi
                vert.uv = uv_min

                # Add to lists
                tris_vertices.append(vert)

                # Increment local vertex numbering index
                nvi += 1

    # Triangulate vertices
    tris = polygon_triangulate(tidx, *tris_vertices)

    # Check again if the barycentric coordinates of the triangles are inside
    for idx in range(len(tris)):
        tri_center = linalg.triangle_center(tris[idx], uv=True)
        for trim in trims:
            if linalg.wn_poly(tri_center, trim.evalpts):
                if trim.opt['reversed']:
                    if tris[idx].opt_get('trim') is None or not tris[idx].opt_get('trim'):
                        tris[idx].inside = False
                        tris[idx].opt = ['no_trim', True]  # always triangulate
                else:
                    tris[idx].inside = True
                    tris[idx].opt = ['trim', True]  # always trim
            else:
                if trim.opt['reversed']:
                    if tris[idx].opt_get('no_trim') is None or not tris[idx].opt_get('no_trim'):
                        tris[idx].inside = True

    # Extract triangles which are not inside the trim
    tris_final = []
    for tri in tris:
        if not tri.inside:
            tris_final.append(tri)

    return tris_vertices, tris_final