Repository: mikedh/trimesh

Issue:
trimesh.path.raster.rasterize doesn't appear to render islands or nested paths/objects
It seems like when I try and raster something with multiple nested islands the internal features will not raster/render.

By the way I love this library and would happy pay someone to fix this bug if it can get resolved quickly.


![Screen Shot 2022-03-19 at 4 44 44 pm](https://user-images.githubusercontent.com/8863368/159110706-2446bb0a-89ba-433f-a2aa-b407eb7986cb.png)

The 2D path of this looks like:

![image](https://user-images.githubusercontent.com/8863368/159110592-68f067e1-7259-4863-bce2-454027bc9b7a.png)

But the internal squares do not appear:

![Screen Shot 2022-03-19 at 4 43 06 pm](https://user-images.githubusercontent.com/8863368/159110651-c13c8537-e825-4ce3-8b5f-aaafcd634355.png)




Discussion:

Patch:
diff --git a/setup.py b/setup.py
index 2bb1a1c0..4581d23c 100644
--- a/setup.py
+++ b/setup.py
@@ -72,7 +72,8 @@ current = (sys.version_info.major, sys.version_info.minor)
 lock = [((3, 4), 'lxml', '4.3.5'),
         ((3, 4), 'shapely', '1.6.4'),
         ((3, 4), 'pyglet', '1.4.10'),
-        ((3, 5), 'sympy', None)]
+        ((3, 5), 'sympy', None),
+        ((3, 6), 'svg.path', '4.1')]
 for max_python, name, version in lock:
     if current <= max_python:
         # remove version-free requirements
diff --git a/trimesh/base.py b/trimesh/base.py
index d1254612..80a65798 100644
--- a/trimesh/base.py
+++ b/trimesh/base.py
@@ -2506,8 +2506,9 @@ class Trimesh(Geometry3D):
                   normal,
                   **kwargs):
         """
-        Project a mesh onto a plane and then extract the polygon
-        that outlines the mesh projection on that plane.
+        Project a mesh onto a plane and then extract the
+        polygon that outlines the mesh projection on that
+        plane.
 
         Parameters
         ----------
@@ -2533,10 +2534,15 @@ class Trimesh(Geometry3D):
         projected : trimesh.path.Path2D
           Outline of source mesh
         """
+        from .path import Path2D
         from .exchange.load import load_path
         from .path.polygons import projected
 
-        return load_path(projected(mesh=self, normal=normal, **kwargs))
+        projection = projected(
+            mesh=self, normal=normal, **kwargs)
+        if projection is None:
+            return Path2D()
+        return load_path(projection)
 
     @caching.cache_decorator
     def area(self):
diff --git a/trimesh/path/exchange/svg_io.py b/trimesh/path/exchange/svg_io.py
index 66e43f39..0ddb42db 100644
--- a/trimesh/path/exchange/svg_io.py
+++ b/trimesh/path/exchange/svg_io.py
@@ -275,7 +275,10 @@ def _svg_path_convert(paths, force=None):
 
     for attrib, matrix in paths:
         # the path string is stored under `d`
-        path_string = attrib['d']
+        path_string = attrib.get('d', '')
+        if len(path_string) == 0:
+            log.warning('empty path string!')
+            continue
 
         # get the name of the geometry if trimesh specified it
         # note that the get will by default return `None`
diff --git a/trimesh/path/polygons.py b/trimesh/path/polygons.py
index fe634b53..ce420261 100644
--- a/trimesh/path/polygons.py
+++ b/trimesh/path/polygons.py
@@ -94,10 +94,14 @@ def enclosure_tree(polygons):
     if len(degrees) > 0 and degrees.max() > 1:
         # collect new edges for graph
         edges = []
+
+        # order the roots so they are sorted by degree
+        roots = roots[np.argsort([degree[r] for r in roots])]
         # find edges of subgraph for each root and children
         for root in roots:
             children = indexes[degrees == degree[root] + 1]
-            edges.extend(contains.subgraph(np.append(children, root)).edges())
+            edges.extend(contains.subgraph(
+                np.append(children, root)).edges())
         # stack edges into new directed graph
         contains = nx.from_edgelist(edges, nx.DiGraph())
         # if roots have no children add them anyway
@@ -675,6 +679,9 @@ def projected(mesh,
     Project a mesh onto a plane and then extract the polygon
     that outlines the mesh projection on that plane.
 
+    Note that this will ignore back-faces, which is only
+    relevant if the source mesh isn't watertight.
+
     Parameters
     ----------
     mesh : trimesh.Trimesh
@@ -692,11 +699,12 @@ def projected(mesh,
       Tolerance for discarding on-edge triangles.
     max_regions : int
       Raise an exception if the mesh has more than this
-      number of disconnected regions to fail quickly before unioning.
+      number of disconnected regions to fail quickly before
+      unioning.
 
     Returns
     ----------
-    projected : shapely.geometry.Polygon
+    projected : shapely.geometry.Polygon or None
       Outline of source mesh
 
     Raises
@@ -710,23 +718,28 @@ def projected(mesh,
 
     # the projection of each face normal onto facet normal
     dot_face = np.dot(normal, mesh.face_normals.T)
-    # check if face lies on front or back of normal
-    front = dot_face > tol_dot
-    back = dot_face < -tol_dot
-    # divide the mesh into front facing section and back facing parts
-    # and discard the faces perpendicular to the axis.
-    # since we are doing a unary_union later we can use the front *or*
-    # the back so we use which ever one has fewer triangles
-    # we want the largest nonzero group
-    count = np.array([front.sum(), back.sum()])
-    if count.min() == 0:
-        # if one of the sides has zero faces we need the other
-        pick = count.argmax()
+    if mesh.is_watertight:
+        # for watertight mesh, speed up projection by handling side with less faces
+        # check if face lies on front or back of normal
+        front = dot_face > tol_dot
+        back = dot_face < -tol_dot
+        # divide the mesh into front facing section and back facing parts
+        # and discard the faces perpendicular to the axis.
+        # since we are doing a unary_union later we can use the front *or*
+        # the back so we use which ever one has fewer triangles
+        # we want the largest nonzero group
+        count = np.array([front.sum(), back.sum()])
+        if count.min() == 0:
+            # if one of the sides has zero faces we need the other
+            pick = count.argmax()
+        else:
+            # otherwise use the normal direction with the fewest faces
+            pick = count.argmin()
+        # use the picked side
+        side = [front, back][pick]
     else:
-        # otherwise use the normal direction with the fewest faces
-        pick = count.argmin()
-    # use the picked side
-    side = [front, back][pick]
+        # for non-watertight mesh, only handle the front side of normal
+        side = dot_face > tol_dot
 
     # subset the adjacency pairs to ones which have both faces included
     # on the side we are currently looking at
@@ -774,6 +787,8 @@ def projected(mesh,
         scale = np.reshape(polygon.bounds, (2, 2)).ptp(axis=0).max()
         padding = scale * pad
         polygon = polygon.buffer(padding).buffer(-padding)
+    elif len(polygons) == 0:
+        return None
     else:
         # get all points for every AABB
         extrema = np.reshape([p.bounds for p in polygons], (-1, 2))
diff --git a/trimesh/path/raster.py b/trimesh/path/raster.py
index 33248917..664dd106 100644
--- a/trimesh/path/raster.py
+++ b/trimesh/path/raster.py
@@ -71,41 +71,33 @@ def rasterize(path,
     # the path indexes that are exteriors
     # needed to know what to fill/empty but expensive
     roots = path.root
+    enclosure = path.enclosure_directed
 
     # draw the exteriors
-    exteriors = Image.new(mode='1', size=resolution)
-    edraw = ImageDraw.Draw(exteriors)
+    result = Image.new(mode='1', size=resolution)
+    draw = ImageDraw.Draw(result)
 
     # if a width is specified draw the outline
     if width is not None:
         width = int(width)
         for coords in discrete:
-            edraw.line(coords.flatten().tolist(),
-                       fill=1,
-                       width=width)
+            draw.line(coords.flatten().tolist(),
+                      fill=1,
+                      width=width)
         # if we are not filling the polygon exit
         if not fill:
-            del edraw
-            return exteriors
+            return result
 
-    # draw the interiors
-    interiors = Image.new(mode='1', size=resolution)
-    idraw = ImageDraw.Draw(interiors)
-    for i, points in enumerate(discrete):
-        # draw the polygon on either the exterior or
-        # interior image buffer
-        if i in roots:
-            edraw.polygon(points.flatten().tolist(),
-                          fill=1)
-        else:
-            idraw.polygon(points.flatten().tolist(),
-                          fill=1)
-    # clean up the draw objects
-    # this is in the PIL examples and I have
-    # no idea if it this is actually necessary
-    del edraw
-    del idraw
-    # the final result is the exteriors minus the interiors
-    raster = ImageChops.subtract(exteriors, interiors)
+    # roots are ordered by degree
+    # so we draw the outermost one first
+    # and then go in as we progress
+    for root in roots:
+        # draw the exterior
+        draw.polygon(discrete[root].flatten().tolist(),
+                     fill=1)
+        # draw the interior children
+        for child in enclosure[root]:
+            draw.polygon(discrete[child].flatten().tolist(),
+                         fill=0)
 
-    return raster
+    return result
diff --git a/trimesh/repair.py b/trimesh/repair.py
index 07f72427..33ecba31 100644
--- a/trimesh/repair.py
+++ b/trimesh/repair.py
@@ -23,20 +23,23 @@ except BaseException as E:
     from .exceptions import ExceptionModule
     nx = ExceptionModule(E)
 
+try:
+    from .path.exchange.misc import faces_to_path
+except BaseException as E:
+    from .exceptions import closure
+    faces_to_path = closure(E)
+
 
 def fix_winding(mesh):
     """
-    Traverse and change mesh faces in-place to make sure winding
-    is correct, with edges on adjacent faces in
+    Traverse and change mesh faces in-place to make sure
+    winding is correct with edges on adjacent faces in
     opposite directions.
 
     Parameters
     -------------
-    mesh: Trimesh object
-
-    Notes
-    -------------
-    mesh.face : will reverse columns of certain faces
+    mesh : Trimesh
+      Source geometry to alter in-place.
     """
     # anything we would fix is already done
     if mesh.is_winding_consistent:
@@ -92,16 +95,13 @@ def fix_inversion(mesh, multibody=False):
     Parameters
     -------------
     mesh : trimesh.Trimesh
-      Mesh to fix.
+      Mesh to fix in-place.
     multibody : bool
       If True will try to fix normals on every body
-
-    Notes
-    -------------
-    mesh.face : may reverse faces
     """
     if multibody:
-        groups = graph.connected_components(mesh.face_adjacency)
+        groups = graph.connected_components(
+            mesh.face_adjacency)
         # escape early for single body
         if len(groups) == 1:
             if mesh.volume < 0.0:
@@ -355,3 +355,83 @@ def fill_holes(mesh):
 
     log.debug('Filled in mesh with %i triangles', np.sum(valid))
     return mesh.is_watertight
+
+
+def fan_stitch(mesh, faces=None):
+    """
+    Create a fan stitch over the boundary of the specified
+    faces. If the boundary is non-convex a triangle fan
+    is going to be extremely wonky.
+
+    Parameters
+    -----------
+    vertices : (n, 3) float
+      Vertices in space.
+    faces : (n,) int
+      Face indexes to stitch with triangle fans.
+
+    Returns
+    ----------
+    fan : (m, 3) int
+      New triangles referencing mesh.vertices.
+    """
+    if faces is None:
+        faces = np.arange(len(mesh.faces))
+
+    # get a sequence of vertex indices representing the
+    # boundary of the specified faces
+    # will be referencing the same indexes of `mesh.vertices`
+    points = [e.points for e in
+              faces_to_path(mesh, faces)['entities']
+              if len(e.points) > 3 and
+              e.points[0] == e.points[-1]]
+
+    # now create a triangle fan for each boundary curve
+    fan = [np.column_stack((
+        np.ones(len(p) - 3, dtype=int) * p[0],
+        p[1:-2],
+        p[2:-1]))
+        for p in points]
+
+    # get properties to avoid querying in loop
+    vertices = mesh.vertices
+    normals = mesh.face_normals
+
+    # find which faces are associated with an edge
+    edges_face = mesh.edges_face
+    tree_edge = mesh.edges_sorted_tree
+
+    # now we do a normal check against an adjacent face
+    # to see if each region needs to be flipped
+    for i, p, t in zip(range(len(fan)), points, fan):
+        # get the edges from the original mesh
+        # for the first `n` new triangles
+        e = t[:10, 1:].copy()
+        e.sort(axis=1)
+
+        # find which indexes of `mesh.edges` these
+        # new edges correspond with by finding edges
+        # that exactly correspond with the tree
+        query = tree_edge.query_ball_point(e, r=1e-10)
+        if len(query) == 0:
+            continue
+        # stack all the indices that exist
+        edge_index = np.concatenate(query)
+
+        # get the normals from the original mesh
+        original = normals[edges_face[edge_index]]
+
+        # calculate the normals for a few new faces
+        check, valid = triangles.normals(vertices[t[:3]])
+        if not valid.any():
+            continue
+        # take the first valid normal from our new faces
+        check = check[valid][0]
+
+        # if our new faces are reversed from the original
+        # Adjacent face flip them along their axis
+        sign = np.dot(original, check)
+        if sign.mean() < 0:
+            fan[i] = np.fliplr(t)
+
+    return np.vstack(fan)
diff --git a/trimesh/version.py b/trimesh/version.py
index 4bb78648..e234e8a2 100644
--- a/trimesh/version.py
+++ b/trimesh/version.py
@@ -1,1 +1,1 @@
-__version__ = '3.10.5'
+__version__ = '3.10.6'


Test patch:
diff --git a/tests/test_polygons.py b/tests/test_polygons.py
index ebe26ea2..963aa8cc 100644
--- a/tests/test_polygons.py
+++ b/tests/test_polygons.py
@@ -97,6 +97,17 @@ class PolygonTests(g.unittest.TestCase):
         assert g.np.allclose(
             [i.area for i in p], g.np.pi, atol=0.05)
 
+    def test_project_backface(self):
+        m = g.trimesh.Trimesh(
+            vertices=[[0, 0, 0], [0, 1, 0], [1, 0, 0]],
+            faces=[[0, 1, 2]])
+
+        front = m.projected(m.face_normals[0])
+        assert len(front.entities) == 1
+
+        back = m.projected(-m.face_normals[0])
+        assert len(back.entities) == 0
+
     def test_project_multi(self):
         mesh = (g.trimesh.creation.box() +
                 g.trimesh.creation.box().apply_translation([3, 0, 0]))
diff --git a/tests/test_raster.py b/tests/test_raster.py
index ce25b77a..d3cf91c4 100644
--- a/tests/test_raster.py
+++ b/tests/test_raster.py
@@ -57,6 +57,35 @@ class RasterTest(g.unittest.TestCase):
         # A different pitch results in a different image
         assert fill_2dpitch_cnt != fill_cnt
 
+    def test_nested(self):
+        # make a test path with nested circles
+        theta = g.np.linspace(0, g.np.pi * 2, 100)
+        unit = g.np.column_stack((g.np.cos(theta), g.np.sin(theta)))
+        radii = g.np.linspace(1.0, 10.0, 10)
+        g.np.random.shuffle(radii)
+        paths = []
+        for R in radii:
+            paths.append(g.trimesh.load_path(R * unit))
+        path = g.trimesh.path.util.concatenate(paths)
+
+        # split and extrude should both show 5 regions
+        assert len(path.split()) == 5
+        assert len(path.extrude(1.0)) == 5
+
+        pitch = path.extents.max() / 1000
+        origin = path.bounds[0] - pitch
+        resolution = (g.np.ceil(
+            path.extents / pitch) + 2).astype(int)
+
+        # rasterize using the settings
+        r = path.rasterize(
+            pitch=pitch, origin=origin, resolution=resolution)
+        # it's a boolean image so filled cells times
+        # pitch area should be about the same as the area
+        filled = g.np.array(r).sum() * pitch ** 2
+
+        assert g.np.isclose(filled, path.area, rtol=0.01)
+
 
 if __name__ == '__main__':
     g.trimesh.util.attach_to_log()
diff --git a/tests/test_repair.py b/tests/test_repair.py
index 8402e4d1..8016bdfd 100644
--- a/tests/test_repair.py
+++ b/tests/test_repair.py
@@ -168,6 +168,40 @@ class RepairTests(g.unittest.TestCase):
         m.fix_normals(multibody=True)
         assert g.np.isclose(m.volume, a.volume * 2.0)
 
+    def test_fan(self):
+
+        # start by creating an icosphere and removing
+        # all faces that include a single vertex to make
+        # a nice hole in the mesh
+        m = g.trimesh.creation.icosphere()
+        clip = m.vertex_faces[0]
+        clip = clip[clip >= 0]
+        assert len(clip) > 4
+        mask = g.np.ones(len(m.faces), dtype=bool)
+        mask[clip] = False
+
+        # should have been watertight
+        assert m.is_watertight
+        assert m.is_winding_consistent
+        m.update_faces(mask)
+        # now should not be watertight
+        assert not m.is_watertight
+        assert m.is_winding_consistent
+
+        # create a triangle fan to cover the hole
+        stitch = g.trimesh.repair.fan_stitch(m)
+        # should be an (n, 3) int
+        assert len(stitch.shape) == 2
+        assert stitch.shape[1] == 3
+        assert stitch.dtype.kind == 'i'
+
+        # now check our stitch to see if it handled the hole
+        repair = g.trimesh.Trimesh(
+            vertices=m.vertices.copy(),
+            faces=g.np.vstack((m.faces, stitch)))
+        assert repair.is_watertight
+        assert repair.is_winding_consistent
+
 
 if __name__ == '__main__':
     g.trimesh.util.attach_to_log()