Fix hull and minkowski color caching

nicklockwood · nicklockwood · commit 067bf7ced859 · 2025-10-12T17:54:06.000+01:00
diff --git a/ShapeScript/Geometry.swift b/ShapeScript/Geometry.swift
@@ -140,12 +140,13 @@ public final class Geometry: Hashable {
         debug: Bool = false
     ) {
         var material = material
+        var useMaterialForCache = false
         var children = children
         var type = type
         switch type {
         case var .extrude(paths, options):
-            (paths, material) = paths.fixupColors(material: material)
-            (options.along, material) = options.along.fixupColors(material: material)
+            (paths, material) = paths.vertexColorsToMaterial(material: material)
+            (options.along, material) = options.along.vertexColorsToMaterial(material: material)
             type = .extrude(paths, options)
             switch (paths.count, options.along.count) {
             case (0, 0):
@@ -158,7 +159,9 @@ public final class Geometry: Hashable {
                 assert(children.isEmpty)
                 type = .extrude([], .default)
                 children = paths.map { path in
-                    Geometry(
+                    var path = path
+                    (path, material) = path.vertexColorsToMaterial(material: material)
+                    return Geometry(
                         type: .extrude([path], options),
                         name: nil,
                         transform: .identity,
@@ -170,7 +173,7 @@ public final class Geometry: Hashable {
                 }
             }
         case .lathe(var paths, let segments):
-            (paths, material) = paths.fixupColors(material: material)
+            (paths, material) = paths.vertexColorsToMaterial(material: material)
             type = .lathe(paths, segments: segments)
             switch paths.count {
             case 0:
@@ -196,7 +199,7 @@ public final class Geometry: Hashable {
             }
         case var .fill(paths):
             // TODO: why didn't we apply the same logic as above for fill?
-            (paths, material) = paths.fixupColors(material: material)
+            (paths, material) = paths.vertexColorsToMaterial(material: material)
             type = .fill(paths)
             switch paths.count {
             case 0:
@@ -208,7 +211,9 @@ public final class Geometry: Hashable {
             assert(children.isEmpty)
         case let .mesh(mesh):
             material = mesh.polygons.first?.material as? Material ?? material
-        case .union, .xor, .difference, .intersection, .stencil, .hull, .minkowski:
+        case .hull, .minkowski:
+            useMaterialForCache = true
+        case .union, .xor, .difference, .intersection, .stencil:
             material = children.first?.material ?? .default
         case .group:
             if debug {
@@ -225,9 +230,13 @@ public final class Geometry: Hashable {
         self._sourceLocation = sourceLocation
         self.debug = debug
 
+        var hasVariedMaterials = false
         var isOpaque = material.isOpaque
         func flattenedCacheKey(for geometry: Geometry) -> GeometryCache.Key {
             isOpaque = isOpaque && geometry.material.isOpaque
+            if !hasVariedMaterials, geometry.material != material {
+                hasVariedMaterials = true
+            }
             return GeometryCache.Key(
                 type: geometry.type,
                 material: geometry.material == material ? nil : geometry.material,
@@ -238,18 +247,19 @@ public final class Geometry: Hashable {
             )
         }
 
-        self.cacheKey = GeometryCache.Key(
+        let childKeys = type.isLeafGeometry ? [] : children.map(flattenedCacheKey)
+
+        // Must be set after child keys are generated
+        self.isOpaque = isOpaque
+        self.cacheKey = .init(
             type: type,
-            material: nil,
+            material: useMaterialForCache && hasVariedMaterials ? material : nil,
             smoothing: smoothing,
             transform: .identity,
             flipped: transform.isFlipped,
-            children: type.isLeafGeometry ? [] : children.map(flattenedCacheKey)
+            children: childKeys
         )
 
-        // Must be set after cache key is generated
-        self.isOpaque = isOpaque
-
         // Compute the overestimated, non-transformed bounds
         switch type {
         case .difference, .stencil:
@@ -601,9 +611,10 @@ private extension Geometry {
         case let .loft(paths):
             mesh = Mesh.loft(paths).makeWatertight()
         case let .hull(vertices):
-            let m = Mesh.convexHull(of: vertices, material: Material.default, isCancelled: isCancelled)
+            let m = Mesh.convexHull(of: vertices, material: material, isCancelled: isCancelled)
             let meshes = ([m] + childMeshes(callback)).map { $0.materialToVertexColors(material: material) }
-            mesh = .convexHull(of: meshes, isCancelled: isCancelled).fixupColors(material: material)
+            mesh = .convexHull(of: meshes, isCancelled: isCancelled)
+                .vertexColorsToMaterial(material: material).replacing(material, with: nil)
         case .minkowski:
             var children = ArraySlice(children.enumerated().sorted {
                 switch ($0.1.type, $1.1.type) {
@@ -648,14 +659,16 @@ private extension Geometry {
                 sum = first.flattened(callback).materialToVertexColors(material: first.material)
             }
             while let next = children.popFirst() {
-                if let path = next.path?.transformed(by: next.transform) {
+                if var path = next.path?.transformed(by: next.transform) {
+                    path = path.materialToVertexColors(material: next.material)
                     sum = sum.minkowskiSum(with: path, isCancelled: isCancelled)
                 } else {
                     let mesh = next.flattened(callback).materialToVertexColors(material: next.material)
                     sum = sum.minkowskiSum(with: mesh, isCancelled: isCancelled)
                 }
             }
-            mesh = sum.fixupColors(material: material).makeWatertight()
+            mesh = sum.vertexColorsToMaterial(material: material)
+                .replacing(material, with: nil).makeWatertight()
         case let .fill(paths):
             mesh = Mesh.fill(paths.map { $0.closed() }, isCancelled: isCancelled).makeWatertight()
         case .union, .lathe, .extrude:
@@ -756,70 +769,130 @@ private extension Geometry {
     }
 }
 
-private extension Collection<Path> {
+private extension [Path] {
+    /// Returns the uniform color of all vertices, or nil if they have different colors
+    var uniformVertexColor: Color? {
+        let uniformColor = first?.uniformVertexColor ?? .white
+        return allSatisfy { $0.uniformVertexColor == uniformColor } ? uniformColor : nil
+    }
+
     /// Convert uniform point colors to a material instead
-    func fixupColors(material: Material) -> ([Path], Material) {
+    func vertexColorsToMaterial(material: Material) -> ([Path], Material) {
         guard material.texture == nil else {
-            return (Array(self), material)
-        }
-        var current: Color?
-        for path in self {
-            for point in path.points {
-                if current == nil {
-                    current = point.color
-                } else if point.color != current {
-                    var material = material
-                    material.albedo = .color(.white)
-                    return (Array(self), material)
-                }
+            return (self, material)
+        }
+        if let uniformVertexColor {
+            if uniformVertexColor == .white {
+                return (self, material)
             }
+            var material = material
+            material.albedo = .color(uniformVertexColor)
+            return (map { $0.withColor(nil) }, material)
         }
         var material = material
-        material.albedo = (current ?? material.color).map { .color($0) }
-        return (map { $0.withColor(nil) }, material)
+        material.albedo = .color(.white)
+        return (self, material)
+    }
+}
+
+extension Path {
+    /// Returns the uniform color of all vertices, or nil if they have different colors
+    var uniformVertexColor: Color? {
+        let uniformColor = points.first?.color
+        return points.allSatisfy { $0.color == uniformColor } ? (uniformColor ?? .white) : nil
+    }
+
+    /// Convert uniform point colors to a material instead
+    func vertexColorsToMaterial(material: Material) -> (Path, Material) {
+        guard material.texture == nil else {
+            return (self, material)
+        }
+        if let uniformVertexColor {
+            if uniformVertexColor == .white {
+                return (self, material)
+            }
+            var material = material
+            material.albedo = .color(uniformVertexColor)
+            return (withColor(nil), material)
+        }
+        var material = material
+        material.albedo = .color(.white)
+        return (self, material)
+    }
+
+    /// Convert material color to vertex colors
+    func materialToVertexColors(material: ShapeScript.Material?) -> Path {
+        guard let color = material?.color, color != .white, !hasColors else {
+            return self
+        }
+        return withColor(color)
     }
 }
 
 extension Polygon {
+    /// Returns the uniform color of all vertices, or nil if they have different colors
+    var uniformVertexColor: Color? {
+        let uniformColor = vertices.first?.color ?? .white
+        return vertices.allSatisfy { $0.color == uniformColor } ? uniformColor : nil
+    }
+
     /// Convert uniform vertex colors to a material instead
-    func fixupColors(material: ShapeScript.Material) -> Polygon {
+    func vertexColorsToMaterial(material: ShapeScript.Material) -> Polygon {
+        var material = self.material as? ShapeScript.Material ?? material
         guard material.texture == nil else {
             return withMaterial(material)
         }
-        var current: Color?
-        for point in vertices {
-            if current == nil {
-                current = point.color
-            } else if point.color != current {
-                var material = material
-                material.albedo = .color(.white)
+        if let uniformVertexColor {
+            if uniformVertexColor == .white {
                 return withMaterial(material)
             }
+            var material = material
+            material.albedo = .color(uniformVertexColor)
+            return withoutVertexColors().withMaterial(material)
         }
-        var material = material
-        material.albedo = (current ?? material.color).map { .color($0) }
-        return mapVertexColors { _ in nil }.withMaterial(material)
+        material.albedo = .color(.white)
+        return withMaterial(material)
     }
 
-    /// Convert material colors to a vertex colors
+    /// Convert material color to vertex colors
     func materialToVertexColors(material: ShapeScript.Material?) -> Polygon {
         guard var material = self.material as? ShapeScript.Material ?? material,
-              let color = material.color
+              let color = material.color, color != .white,
+              !hasVertexColors
         else {
             return self
         }
         material.albedo = .color(.white)
-        return mapVertexColors { $0 * color }.withMaterial(material)
+        return mapVertexColors { _ in color }.withMaterial(material)
     }
 }
 
 extension Mesh {
+    /// Returns the uniform color of all vertices, or nil if they have different colors
+    var uniformVertexColor: Color? {
+        let uniformColor = polygons.first?.uniformVertexColor ?? .white
+        return polygons.allSatisfy { $0.uniformVertexColor == uniformColor } ? uniformColor : nil
+    }
+
     /// Convert uniform vertex colors to a material instead
-    func fixupColors(material: ShapeScript.Material) -> Mesh {
-        .init(polygons.map { $0.fixupColors(material: material) })
+    func vertexColorsToMaterial(material: ShapeScript.Material) -> Mesh {
+        guard material.texture == nil else {
+            return withMaterial(material)
+        }
+        if let uniformVertexColor {
+            if uniformVertexColor == .white {
+                return withMaterial(material)
+            }
+            var material = material
+            material.albedo = .color(uniformVertexColor)
+            return withoutVertexColors().withMaterial(material)
+        }
+        var material = material
+        material.albedo = .color(.white)
+        return withMaterial(material)
     }
 
-    /// Convert material colors to a vertex colors
+    /// Convert material colors to vertex colors
     func materialToVertexColors(material: ShapeScript.Material?) -> Mesh {
         .init(polygons.map { $0.materialToVertexColors(material: material) })
     }
diff --git a/ShapeScript/GeometryCache.swift b/ShapeScript/GeometryCache.swift
@@ -15,6 +15,11 @@ import LRUCache
 public final class GeometryCache {
     private let cache: LRUCache<Key, (mesh: Mesh, associatedData: [Material: Any])>
 
+    /// The number of entries currently stored in the cache
+    public var count: Int { cache.count }
+
+    /// Initialize the cache with a given storage limit
+    /// - Parameter memoryLimit: The maximum amount of data to cache (in bytes)
     public init(memoryLimit: Int = 1_000_000_000) {
         self.cache = LRUCache(totalCostLimit: memoryLimit)
     }
diff --git a/ShapeScript/Interpreter.swift b/ShapeScript/Interpreter.swift
@@ -948,7 +948,7 @@ extension EvaluationContext {
             case let .polygon(p):
                 children.append(.polygon(p
                         .transformed(by: childTransform)
-                        .fixupColors(material: material)))
+                        .vertexColorsToMaterial(material: material)))
             case let .path(path):
                 children.append(.path(path.transformed(by: childTransform)))
             case _ where childTypes.subtypes.contains(.text):
diff --git a/ShapeScript/Scene+SceneKit.swift b/ShapeScript/Scene+SceneKit.swift
@@ -223,8 +223,7 @@ public extension Geometry {
                         width: options.lineWidth,
                         detail: 5
                     ))
-                    let lineColor = path.hasColors ?
-                        Color.white : material.color ?? options.lineColor
+                    let lineColor = path.hasColors ? Color.white : material.color ?? options.lineColor
                     let material = SCNMaterial()
                     material.lightingModel = .constant
                     material.diffuse.contents = OSColor(lineColor)
diff --git a/ShapeScript/StandardLibrary.swift b/ShapeScript/StandardLibrary.swift
@@ -225,7 +225,7 @@ extension Symbols {
         "fill": .block(.builder) { context in
             .mesh(Geometry(type: .fill(context.paths), in: context))
         },
-        "hull": .block(.init(.hull, [:], .union([.point, .path, .mesh]), .mesh)) { context in
+        "hull": .block(.hull) { context in
             let vertices = try context.children.flatMap { child -> [Vertex] in
                 switch child {
                 case let .point(point):
@@ -245,7 +245,7 @@ extension Symbols {
             }
             return .mesh(Geometry(type: .hull(vertices), in: context))
         },
-        "minkowski": .block(.group) { context in
+        "minkowski": .block(.minkowski) { context in
             .mesh(Geometry(type: .minkowski, in: context))
         },
         // mesh
diff --git a/ShapeScript/Types.swift b/ShapeScript/Types.swift
@@ -307,6 +307,8 @@ extension BlockType {
     static let group: Self = .init(.group, [:], .mesh, .mesh)
     static let path: Self = .init(.path, [:], .union([.point, .path]), .path)
     static let pathShape: Self = .init(.pathShape, [:], .void, .path)
+    static let hull: Self = .init(.hull, [:], .union([.point, .path, .mesh]), .mesh)
+    static let minkowski: Self = .init(.group, [:], .mesh, .mesh)
 }
 
 // MARK: Inference
diff --git a/ShapeScriptTests/GeometryTests.swift b/ShapeScriptTests/GeometryTests.swift

Original file line number	Diff line number	Diff line change
`@@ -307,6 +307,8 @@ extension BlockType {`
`307`	`307`	`static let group: Self = .init(.group, [:], .mesh, .mesh)`
`308`	`308`	`static let path: Self = .init(.path, [:], .union([.point, .path]), .path)`
`309`	`309`	`static let pathShape: Self = .init(.pathShape, [:], .void, .path)`
	`310`	`+ static let hull: Self = .init(.hull, [:], .union([.point, .path, .mesh]), .mesh)`
	`311`	`+ static let minkowski: Self = .init(.group, [:], .mesh, .mesh)`
`310`	`312`	`}`
`311`	`313`
`312`	`314`	`// MARK: Inference`