--- title: "An example of the Minkowski addition" author: "Stéphane Laurent" date: '2022-06-11' tags: geometry, R, rgl, graphics, C++, Rcpp rbloggers: yes output: md_document: variant: markdown preserve_yaml: true html_document: highlight: kate keep_md: no highlighter: pandoc-solarized --- Now the **MeshesOperations** package can construct the [Minkowski sum](https://www.wikiwand.com/en/Minkowski_addition) of two polyhedra, thanks to the C++ library **CGAL** and the R package **RcppCGAL**. Let's see an example: the Minkowski sum of Leonardo da Vinci's 72-sided sphere and a truncated icosahedron. Here are these two polyhedra: ![](./figures/LeonardoAndTruncIco.png) The mesh of the truncated icosahedron is provided by the **MeshesOperations** package. Here are the (rounded) vertices and the faces of da Vinci's 72-sided sphere: ```r vertices <- rbind( c( 1.61352, -0.43234, 1.18620), c( 1.18118, -1.18118, 1.18620), c( 0.43234, -1.61352, 1.18620), c(-0.43234, -1.61352, 1.18620), c(-1.18118, -1.18118, 1.18620), c(-1.61352, -0.43234, 1.18620), c(-1.61352, 0.43234, 1.18620), c(-1.18118, 1.18118, 1.18620), c(-0.43234, 1.61352, 1.18620), c( 0.43234, 1.61352, 1.18620), c( 1.18118, 1.18118, 1.18620), c( 1.61352, 0.43234, 1.18620), c( 1.61352, -0.43234, -1.18620), c( 1.61352, 0.43234, -1.18620), c( 1.18118, 1.18118, -1.18620), c( 0.43234, 1.61352, -1.18620), c(-0.43234, 1.61352, -1.18620), c(-1.18118, 1.18118, -1.18620), c(-1.61352, 0.43234, -1.18620), c(-1.61352, -0.43234, -1.18620), c(-1.18118, -1.18118, -1.18620), c(-0.43234, -1.61352, -1.18620), c( 0.43234, -1.61352, -1.18620), c( 1.18118, -1.18118, -1.18620), c( 2.01020, 0.53863, 0.00000), c( 1.47157, 1.47157, 0.00000), c( 0.53863, 2.01020, 0.00000), c(-0.53863, 2.01020, 0.00000), c(-1.47157, 1.47157, 0.00000), c(-2.01020, 0.53863, 0.00000), c(-2.01020, -0.53863, 0.00000), c(-1.47157, -1.47157, 0.00000), c(-0.53863, -2.01020, 0.00000), c( 0.53863, -2.01020, 0.00000), c( 1.47157, -1.47157, 0.00000), c( 2.01020, -0.53863, 0.00000), c( 0.89068, 0.23866, 1.77777), c( 0.89068, -0.23866, 1.77777), c( 0.65202, -0.65202, 1.77777), c( 0.23866, -0.89068, 1.77777), c(-0.23866, -0.89068, 1.77777), c(-0.65202, -0.65202, 1.77777), c(-0.89068, -0.23866, 1.77777), c(-0.89068, 0.23866, 1.77777), c(-0.65202, 0.65202, 1.77777), c(-0.23866, 0.89068, 1.77777), c( 0.23866, 0.89068, 1.77777), c( 0.65202, 0.65202, 1.77777), c( 0.65202, -0.65202, -1.77777), c( 0.89068, -0.23866, -1.77777), c( 0.89068, 0.23866, -1.77777), c( 0.65202, 0.65202, -1.77777), c( 0.23866, 0.89068, -1.77777), c(-0.23866, 0.89068, -1.77777), c(-0.65202, 0.65202, -1.77777), c(-0.89068, 0.23866, -1.77777), c(-0.89068, -0.23866, -1.77777), c(-0.65202, -0.65202, -1.77777), c(-0.23866, -0.89068, -1.77777), c( 0.23866, -0.89068, -1.77777), c( 0.00000, 0.00000, 2.04922), c( 0.00000, 0.00000, -2.04922) ) triangles <- lapply(list( c(36, 60, 47), c(37, 60, 36), c(38, 60, 37), c(39, 60, 38), c(40, 60, 39), c(41, 60, 40), c(42, 60, 41), c(43, 60, 42), c(44, 60, 43), c(45, 60, 44), c(46, 60, 45), c(47, 60, 46), c(48, 61, 59), c(49, 61, 48), c(50, 61, 49), c(51, 61, 50), c(52, 61, 51), c(53, 61, 52), c(54, 61, 53), c(55, 61, 54), c(56, 61, 55), c(57, 61, 56), c(58, 61, 57), c(59, 61, 58) ), function(x) x + 1) quads <- lapply(list( c( 0, 11, 24, 35), c(10, 25, 24, 11), c( 9, 26, 25, 10), c( 8, 27, 26, 9), c( 7, 28, 27, 8), c( 6, 29, 28, 7), c( 5, 30, 29, 6), c( 4, 31, 30, 5), c( 3, 32, 31, 4), c( 2, 33, 32, 3), c( 1, 34, 33, 2), c( 0, 35, 34, 1), c(12, 35, 24, 13), c(13, 24, 25, 14), c(14, 25, 26, 15), c(15, 26, 27, 16), c(16, 27, 28, 17), c(17, 28, 29, 18), c(18, 29, 30, 19), c(19, 30, 31, 20), c(20, 31, 32, 21), c(21, 32, 33, 22), c(22, 33, 34, 23), c(12, 23, 34, 35), c( 0, 37, 36, 11), c( 0, 1, 38, 37), c( 1, 2, 39, 38), c( 2, 3, 40, 39), c( 3, 4, 41, 40), c( 4, 5, 42, 41), c( 5, 6, 43, 42), c( 6, 7, 44, 43), c( 7, 8, 45, 44), c( 8, 9, 46, 45), c( 9, 10, 47, 46), c(10, 11, 36, 47), c(12, 49, 48, 23), c(12, 13, 50, 49), c(13, 14, 51, 50), c(14, 15, 52, 51), c(15, 16, 53, 52), c(16, 17, 54, 53), c(17, 18, 55, 54), c(18, 19, 56, 55), c(19, 20, 57, 56), c(20, 21, 58, 57), c(21, 22, 59, 58), c(22, 23, 48, 59) ), function(x) x + 1) faces <- c(triangles, quads) Leonardo <- list(vertices = vertices, faces = faces) ``` In order to produce the above plot with **rgl**, I triangulated the two meshes. Actually this is not necessary for the Leonardo mesh, since **rgl** allows meshes with triangles and quads. This is necessary for the mesh of the truncated icosahedron, because it has some faces with more than four sides. To triangulate a mesh with **MeshesOperations**, I recommend to use the option `numbersType = "lazyExact"`: ```r library(MeshesOperations) tLeonardo <- Mesh( mesh = Leonardo, triangulate = TRUE, numbersType = "lazyExact" ) tmesh <- Mesh( mesh = truncatedIcosahedron, triangulate = TRUE, numbersType = "lazyExact" ) ``` Now, here is the code which generates the picture shown before: ```r library(rgl) open3d(windowRect = c(50, 50, 850, 450)) mfrow3d(1L, 2L) view3d(30, 30, zoom = 0.7) shade3d(toRGL(tLeonardo), color = "navy") plotEdges( tLeonardo[["vertices"]], tLeonardo[["exteriorEdges"]], color = "gold", tubesRadius = 0.06, spheresRadius = 0.08 ) next3d() view3d(30, 30, zoom = 0.7) shade3d(toRGL(tmesh), color = "navy") plotEdges( tmesh[["vertices"]], tmesh[["exteriorEdges"]], color = "gold", tubesRadius = 0.06, spheresRadius = 0.08 ) ``` Now let's see the Minkowski sum of these two polyhedra: ```r MinkMesh <- MinkowskiSum(Leonardo, truncatedIcosahedron) open3d(windowRect = c(50, 50, 562, 562), zoom = 0.8) shade3d(toRGL(MinkMesh), color="navy") plotEdges( MinkMesh[["vertices"]], MinkMesh[["exteriorEdges"]], color = "gold", tubesRadius = 0.06, spheresRadius = 0.08 ) ``` ![](./figures/DaVinciPlusTruncIco.gif) Beautiful. The generation of the Minkowski sum is fast for this example. But it can be very slow for meshes with numerous vertices.