Skip to content

Commit df3b175

Browse files
nicklockwoodnicklockwood
committed
Add minkowski command
1 parent 6b27f3f commit df3b175

File tree

8 files changed

+57
-22
lines changed

8 files changed

+57
-22
lines changed

‎ShapeScript/Geometry.swift‎

Lines changed: 23 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -58,7 +58,7 @@ public final class Geometry: Hashable {
5858
case .cone, .cylinder, .sphere, .cube, .lathe, .loft, .path, .mesh, .camera, .light,
5959
.intersection, .difference, .stencil:
6060
return false
61-
case .union, .xor, .extrude, .fill, .hull:
61+
case .union, .xor, .extrude, .fill, .hull, .minkowski:
6262
return mesh == nil
6363
}
6464
}
@@ -185,13 +185,11 @@ public final class Geometry: Hashable {
185185
default:
186186
assert(children.isEmpty)
187187
}
188-
case .hull:
189-
break // TODO: what needs to be done here?
190188
case .cone, .cylinder, .sphere, .cube, .loft, .path, .camera, .light:
191189
assert(children.isEmpty)
192190
case let .mesh(mesh):
193191
material = mesh.polygons.first?.material as? Material ?? material
194-
case .union, .xor, .difference, .intersection, .stencil:
192+
case .union, .xor, .difference, .intersection, .stencil, .hull, .minkowski:
195193
material = children.first?.material ?? .default
196194
case .group:
197195
if debug {
@@ -233,7 +231,7 @@ public final class Geometry: Hashable {
233231
// Must be set after cache key is generated
234232
self.isOpaque = isOpaque
235233

236-
// Compute bounds
234+
// Compute the overestimated, non-transformed bounds
237235
switch type {
238236
case .difference, .stencil:
239237
self.bounds = children.first.map {
@@ -253,7 +251,13 @@ public final class Geometry: Hashable {
253251
self.bounds = type.bounds.union(Bounds(children.map {
254252
$0.bounds.transformed(by: $0.transform)
255253
}))
256-
case .cone, .cube, .cylinder, .sphere, .path, .mesh:
254+
case .minkowski:
255+
var bounds = Bounds(min: .zero, max: .zero)
256+
for child in children {
257+
bounds.formMinkowskiSum(with: child.bounds.transformed(by: child.transform))
258+
}
259+
self.bounds = bounds
260+
case .cone, .cylinder, .sphere, .cube, .mesh, .path:
257261
self.bounds = type.bounds
258262
case .camera, .light:
259263
self.bounds = .empty
@@ -466,15 +470,13 @@ private extension Geometry {
466470
switch type {
467471
case .extrude([], _), .lathe([], _), .fill([]):
468472
mesh = nil
469-
case .hull:
470-
mesh = nil
471473
case .group, .path, .mesh,
472474
.cone, .cylinder, .sphere, .cube,
473475
.extrude, .lathe, .loft, .fill:
474476
assert(type.isLeafGeometry) // Leaves
475477
case .stencil, .difference:
476478
mesh = children.first?.merged(callback)
477-
case .union, .xor, .intersection, .camera, .light:
479+
case .union, .xor, .intersection, .hull, .minkowski, .camera, .light:
478480
mesh = nil
479481
}
480482
return callback()
@@ -529,6 +531,11 @@ private extension Geometry {
529531
let m = Mesh.convexHull(of: vertices, material: Material.default, isCancelled: isCancelled)
530532
let meshes = ([m] + childMeshes(callback)).map { $0.materialToVertexColors(material: material) }
531533
mesh = .convexHull(of: meshes, isCancelled: isCancelled).fixupColors(material: material)
534+
case .minkowski:
535+
let meshes = childMeshes(callback).map { $0.materialToVertexColors(material: material) }
536+
mesh = Mesh.minkowskiSum(of: meshes, isCancelled: isCancelled)
537+
.fixupColors(material: material)
538+
.makeWatertight()
532539
case let .fill(paths):
533540
mesh = Mesh.fill(paths.map { $0.closed() }, isCancelled: isCancelled).makeWatertight()
534541
case .union, .lathe, .extrude:
@@ -704,7 +711,7 @@ public extension Geometry {
704711
case .camera, .light, .path:
705712
return false
706713
case .cone, .cylinder, .sphere, .cube,
707-
.extrude, .lathe, .loft, .fill, .hull,
714+
.extrude, .lathe, .loft, .fill, .hull, .minkowski,
708715
.union, .difference, .intersection, .xor, .stencil,
709716
.group, .mesh:
710717
return true
@@ -718,7 +725,7 @@ public extension Geometry {
718725
case .camera, .light:
719726
return 0
720727
case .cone, .cylinder, .sphere, .cube,
721-
.extrude, .lathe, .loft, .fill, .hull,
728+
.extrude, .lathe, .loft, .fill, .hull, .minkowski,
722729
.union, .difference, .intersection, .xor, .stencil,
723730
.path, .mesh:
724731
return 1
@@ -731,7 +738,7 @@ public extension Geometry {
731738
.extrude, .lathe, .fill, .loft,
732739
.mesh, .path, .camera, .light:
733740
return 0 // TODO: should paths/points be treated as children?
734-
case .union, .xor, .difference, .intersection, .stencil, .group, .hull:
741+
case .union, .xor, .difference, .intersection, .stencil, .group, .hull, .minkowski:
735742
return children.count
736743
}
737744
}
@@ -790,6 +797,10 @@ public extension Geometry {
790797
bounds.formUnion(child.exactBounds(with: child.transform * transform, callback))
791798
}
792799
return bounds
800+
case .minkowski:
801+
return children.reduce(.empty) {
802+
$0.minkowskiSum(with: $1.exactBounds(with: $1.transform * transform, callback))
803+
}
793804
case let .path(path):
794805
return path.transformed(by: transform).bounds
795806
case let .fill(paths), let .loft(paths):

‎ShapeScript/GeometryType.swift‎

Lines changed: 6 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -66,6 +66,7 @@ public enum GeometryType: Hashable {
6666
case loft([Path])
6767
case fill([Path])
6868
case hull([Vertex])
69+
case minkowski
6970
// csg
7071
case union
7172
case difference
@@ -83,7 +84,7 @@ public enum GeometryType: Hashable {
8384
public extension GeometryType {
8485
var isEmpty: Bool {
8586
switch self {
86-
case .union, .xor, .difference, .intersection, .stencil, .group, .camera, .light:
87+
case .union, .xor, .difference, .intersection, .stencil, .group, .minkowski, .camera, .light:
8788
return true
8889
case .cone, .cylinder, .sphere, .cube:
8990
return false
@@ -101,10 +102,10 @@ public extension GeometryType {
101102
}
102103
}
103104

104-
/// Returns exact bounds, not including the effect of child shapes
105+
/// Returns exact bounds, not including the effect of transform or child shapes
105106
var bounds: Bounds {
106107
switch self {
107-
case .union, .xor, .difference, .intersection, .stencil, .group, .camera, .light:
108+
case .union, .xor, .difference, .intersection, .stencil, .group, .minkowski, .camera, .light:
108109
return .empty
109110
case .cube:
110111
return .init(min: .init(-0.5, -0.5, -0.5), max: .init(0.5, 0.5, 0.5))
@@ -163,15 +164,15 @@ extension GeometryType {
163164
case .cone, .cylinder, .sphere, .cube, .loft, .path, .mesh, .fill,
164165
.group, .camera, .light:
165166
return true
166-
case .hull, .union, .xor, .difference, .intersection, .stencil:
167+
case .hull, .minkowski, .union, .xor, .difference, .intersection, .stencil:
167168
return false
168169
}
169170
}
170171

171172
/// Returns representative points needed to generate exact bounds
172173
var representativePoints: [Vector] {
173174
switch self {
174-
case .union, .xor, .difference, .intersection, .stencil, .group, .camera, .light:
175+
case .minkowski, .union, .xor, .difference, .intersection, .stencil, .group, .camera, .light:
175176
return []
176177
case .cube:
177178
return [

‎ShapeScript/StandardLibrary.swift‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -245,6 +245,9 @@ extension [String: Symbol] {
245245
}
246246
return .mesh(Geometry(type: .hull(vertices), in: context))
247247
},
248+
"minkowski": .block(.group) { context in
249+
.mesh(Geometry(type: .minkowski, in: context))
250+
},
248251
// mesh
249252
"mesh": .block(.init(.mesh, [:], .polygon, .mesh)) { context in
250253
let polygons = context.children.compactMap { $0.value as? Polygon }

‎ShapeScript/Types.swift‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -523,7 +523,7 @@ extension Value {
523523
switch geometry.type {
524524
case let .path(path):
525525
return .path(path.transformed(by: geometry.transform))
526-
case .cone, .cylinder, .sphere, .cube, .extrude, .lathe, .loft, .fill, .hull,
526+
case .cone, .cylinder, .sphere, .cube, .extrude, .lathe, .loft, .fill, .hull, .minkowski,
527527
.union, .difference, .intersection, .xor, .stencil, .group, .mesh, .camera, .light:
528528
return nil
529529
}

‎ShapeScript/Value+Logging.swift‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -252,6 +252,7 @@ extension GeometryType: Loggable {
252252
case .loft: return "loft"
253253
case .fill: return "fill"
254254
case .hull: return "hull"
255+
case .minkowski: return "minkowski"
255256
case .union: return "union"
256257
case .difference: return "difference"
257258
case .intersection: return "intersection"

‎ShapeScript/Values.swift‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -157,8 +157,8 @@ extension Value {
157157
case .cylinder: return "cylinder"
158158
case .sphere: return "sphere"
159159
case .cube: return "cube"
160-
case .group, .extrude, .lathe, .loft, .fill, .hull, .union,
161-
.difference, .intersection, .xor, .stencil, .mesh:
160+
case .group, .extrude, .lathe, .loft, .fill, .hull, .minkowski, .union, .difference,
161+
.intersection, .xor, .stencil, .mesh:
162162
return "mesh"
163163
case .camera: return "camera"
164164
case .light: return "light"

‎ShapeScriptTests/StandardLibraryTests.swift‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -954,6 +954,25 @@ class StandardLibraryTests: XCTestCase {
954954
XCTAssertEqual(geometry.mesh?.bounds, Mesh.cube().bounds)
955955
}
956956

957+
// MARK: Minkowski sum
958+
959+
func testMinkowskiSumOfCubes() throws {
960+
let program = try parse("""
961+
minkowski {
962+
cube
963+
cube { size 0.5 }
964+
}
965+
""")
966+
let delegate = TestDelegate()
967+
let context = EvaluationContext(source: program.source, delegate: delegate)
968+
XCTAssertNoThrow(try program.evaluate(in: context))
969+
let geometry = try XCTUnwrap(context.children.first?.value as? Geometry)
970+
let expected = Mesh.cube(size: 1.5)
971+
XCTAssertEqual(geometry.bounds, expected.bounds)
972+
_ = geometry.build { true }
973+
XCTAssertEqual(geometry.mesh?.bounds, expected.bounds)
974+
}
975+
957976
// MARK: Functions
958977

959978
func testDot() {

‎Viewer/Mac/Document.swift‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -471,7 +471,7 @@ private extension Geometry {
471471
var isSelectable: Bool {
472472
switch type {
473473
case .cone, .cylinder, .sphere, .cube, .mesh,
474-
.extrude, .lathe, .loft, .fill, .hull,
474+
.extrude, .lathe, .loft, .fill, .hull, .minkowski,
475475
.union, .difference, .intersection, .xor, .stencil,
476476
.path:
477477
return true
@@ -488,7 +488,7 @@ private extension Geometry {
488488
.extrude, .lathe, .loft, .fill,
489489
.path, .camera, .light:
490490
return false
491-
case .hull, .union, .difference, .intersection, .xor, .stencil:
491+
case .hull, .minkowski, .union, .difference, .intersection, .xor, .stencil:
492492
return childDebug
493493
}
494494
}

0 commit comments

Comments
 (0)