--- title: "SurfaceMesh: 3D Surface Meshes Based on CGAL" author: "Daniel Wollschläger ()" date: "`r format(Sys.time(), '%B %d, %Y')`" output: rmarkdown::html_vignette: fig_height: 5 fig_width: 5 toc: true html_document: df_print: paged toc: true pdf_document: fig_height: 5 fig_width: 5 toc: true vignette: > %\VignetteIndexEntry{SurfaceMesh} %\VignetteDepends{SurfaceMesh} %\VignetteKeywords{SurfaceMesh} %\VignettePackage{SurfaceMesh} %\VignetteEngine{knitr::rmarkdown} --- ```{r setup, echo=FALSE, results="asis"} source("setup.R") setupKnitr(autoprint=TRUE) set.seed(123) rgl_webshot_org <- Sys.setenv("RGL_USE_WEBSHOT"=FALSE) ``` # Introduction `SurfaceMesh` is an R package that supports processing of 3D surface meshes using as backend the C++ library for computational geometry [`CGAL`](https://www.cgal.org/) via R package [`RcppCGAL`](https://cran.r-project.org/package=RcppCGAL). Features include: * Read in and write mesh files in common formats (STL, PLY, OBJ, OFF) * Conversion to / from class `mesh3d` from package [`rgl`](https://cran.r-project.org/package=rgl), also compatible with package [`Rvcg`](https://cran.r-project.org/package=Rvcg) * Mesh repair * Boolean mesh operations on bounded volumes * Remeshing * Subdivision * Surface reconstruction * (Oriented) bounding box, bounding sphere, bounding ellipse * Convex hull * Distance from points to mesh * Centroid (center of mass) * Surface area * Volume * Vertex normals * Randomly sampling points on a mesh The package also calculates surface distance and volume-overlap based similarity metrics for a given pair of 3D surface meshes (see [dkfz metrics reloaded](https://metrics-reloaded.dkfz.de/metric-library)): * (Quantile) Hausdorff distance * Average symmetric surface distance * Surface RMSE * JSC (IoU) * DSC # Background This package includes code adapted from packages [`Boov`](https://github.com/stla/Boov/), [`cgalMeshes`](https://github.com/stla/cgalMeshes/), and [`SurfaceReconstruction`](https://github.com/stla/SurfaceReconstruction/), developed and copyright by [Stéphane Laurent](https://laustep.github.io/stlahblog/). Currently, only a subset of the functionality of these packages is provided in `SurfaceMesh`. A fork / adaptation of packages [`Boov`](https://github.com/stla/Boov/), [`cgalMeshes`](https://github.com/stla/cgalMeshes/), and [`SurfaceReconstruction`](https://github.com/stla/SurfaceReconstruction/) was carried out as upstream changes to CGAL introduced incompatibilities, and the packages were archived from [CRAN](https://cran.r-project.org/). The design was chosen such that mesh data resides in R space. This means that for each mesh operation, data is first transferred to the C++ side (using `Rcpp`), converted to a CGAL surface mesh, processed with CGAL functions, and then transferred back to R. The package does not maintain a pointer to a C++ data structure to keep the mesh data there - unlike packages such as [`terra`](https://cran.r-project.org/package=terra) or [`cgalMeshes`](https://github.com/stla/cgalMeshes/). This approach carries a performance penalty, but from an R perspective, it is more straightforward. In particular, there are no serialization issues (saving meshes). Furthermore, memory management is easier. # Create Surface Meshes See `vignette("SurfaceMesh_Examples")` for meshes included in this package as examples. ## Read Mesh / Polygon Soup Files ```{r} f_mesh <- system.file("extdata", "dataCorner.off", package="SurfaceMesh") mesh <- makeMesh(f_mesh, verbose=FALSE) mesh_rgl <- toRGL(mesh) view3d(85, -65, zoom=0.8) shade3d(mesh_rgl, col="wheat2") ``` ## Create Surface Mesh Based on `mesh3d` Object ```{r} dataTubularKnot mesh <- makeMesh(dataTubularKnot) mesh ``` ## Triangulate ```{r} mesh <- makeMesh(dataSeptuaginta, triangulate=FALSE, verbose=FALSE) mesh_rgl <- toRGL(mesh) isTriangle(mesh) mesh_tri <- triangulateMesh(mesh) mesh_tri_rgl <- toRGL(mesh_tri) mfrow3d(1, 2) view3d(0, 30, zoom=0.8) wire3d(mesh_rgl) next3d() view3d(0, 30, zoom=0.8) wire3d(mesh_tri_rgl) ``` ## Vertex normals Calculate vertex normals when creating a mesh. ```{r} mesh <- makeMesh(dataToroHelix, normals=TRUE) mesh ``` Calculate vertex normals for existing mesh. ```{r} mesh <- makeMesh(dataToroHelix, normals=FALSE) mesh_vn <- addVertexNormals(mesh) mfrow3d(1, 2) view3d(0, 30, zoom=0.8) shade3d(toRGL(mesh), col="tomato") next3d() view3d(0, 30, zoom=0.8) shade3d(toRGL(mesh_vn), col="turquoise4") ``` Extract vertex normals. ```{r} mesh <- makeMeshValid(dataSphere, normals=TRUE) vn <- getVertexNormals(mesh) head(vn) ``` Set vertex normals to given matrix. ```{r} ## random unit normal vectors mesh <- makeMesh(dataPentaPrism, triangulate=TRUE, normals=FALSE) nVerts <- nrow(mesh[["vertices"]]) nrmls0 <- matrix(runif(nVerts*3), ncol=3) lens <- sqrt(rowSums(nrmls0^2)) nrmls <- diag(1/lens) %*% nrmls0 ## set vertex normals mesh_vn <- setVertexNormals(mesh, nrmls) head(mesh_vn[["normals"]]) head(nrmls) ``` # Mesh Characteristics ## Check Mesh Status ```{r} mesh <- makeMeshValid(dataTorus) isValid(mesh) hasGarbage(mesh) isTriangle(mesh) isQuad(mesh) doesBoundVolume(mesh) isClosed(mesh) doesSelfIntersect(mesh) ``` ## Check and Change Mesh Orientation ```{r} mesh_rgl <- meshIsoCuboid(c(-1, -2, -3), c(1, 2, 3)) mesh <- makeMeshValid(mesh_rgl) mesh_rfo <- reverseFaceOrientations(mesh) isOutwardOriented(mesh) isOutwardOriented(mesh_rfo) ``` Two tetraeders, one with positive orientation, one with negative orientation. ```{r} vertices <- rbind( c(0, 0, 0), c(2, 2, 0), c(2, 0, 2), c(0, 2, 2), c(3, 3, 3), c(5, 5, 3), c(5, 3, 5), c(3, 5, 5)) faces <- rbind( c(3, 2, 1), c(3, 4, 2), c(1, 2, 4), c(4, 3, 1), c(5, 6, 7), c(6, 8, 7), c(8, 6, 5), c(5, 7, 8)) mesh <- makeMesh(vertices, faces=faces) mesh_bv <- orientToBoundVolume(mesh) doesBoundVolume(mesh) doesBoundVolume(mesh_bv) ``` ## Measurements ### Centroid (Center of Mass) ```{r} mesh <- makeMesh(dataPentaPrism, triangulate=TRUE) getCentroid(mesh) ``` ### Surface Area ```{r} mesh <- makeMesh(dataTruncIcosahedron, triangulate=TRUE) getArea(mesh) ``` ### Volume ```{r} mesh <- makeMesh(dataSeptuaginta, triangulate=TRUE) getVolume(mesh) ``` ### Average Spacing ```{r} mesh <- makeMesh(dataToroHelix, triangulate=TRUE) getAverageSpacing(mesh[["vertices"]], nNeighbors=12L) ``` # Mesh Repair See [`CGAL` mesh repair](https://doc.cgal.org/latest/PMP_Mesh_repair/) ## Fill Boundary Holes Note: Hole is easier to see in interactive version shown with `example(fillBoundaryHoles)`. ```{r} f_mesh <- system.file("extdata", "dataCornerHole.off", package="SurfaceMesh") mesh <- makeMesh(f_mesh, triangulate=TRUE, verbose=TRUE) mesh_rgl <- toRGL(mesh) mesh_fill <- fillBoundaryHoles(mesh, verbose=TRUE) mesh_fill_rgl <- toRGL(mesh_fill) mfrow3d(1, 2) view3d(70, 25, zoom=0.8) shade3d(mesh_rgl, col="orangered") next3d() view3d(70, 25, zoom=0.8) shade3d(mesh_fill_rgl, col="violetred") ``` ## Remove Self-Intersections TODO: Use a mesh with self-intersections. ```{r} mesh <- makeMesh(dataPentaPrism, triangulate=TRUE) mesh_nsi <- removeSelfIntersections(mesh) getVolume(mesh_nsi) ``` ## Randomly Sample Points on a Mesh ```{r} mesh <- makeMesh(dataPentaPrism, triangulate=TRUE) ptsOnMesh <- samplePoints(mesh, ptsOnFaces=2L) head(ptsOnMesh) ``` # Boolean Mesh Operations on Bounded Volumes See [`CGAL` Boolean operations](https://doc.cgal.org/latest/PMP_Boolean_operations/) ## Union ```{r} # mesh one: a cube mesh1_rgl <- cube3d() # (from the rgl package) mesh2_rgl <- translate3d(cube3d(), 1, 1, 1) mesh_u <- boolUnion(list(mesh1_rgl, mesh2_rgl)) mesh_u_rgl <- toRGL(mesh_u) shade3d(mesh_u_rgl, color="red") ``` ## Difference ```{r} mesh1_rgl <- cube3d() # (from the rgl package) mesh2_rgl <- translate3d(cube3d(), 1, 1, 0) mesh_d <- boolDifference(mesh1_rgl, mesh2_rgl) mesh_d_rgl <- toRGL(mesh_d) shade3d(mesh1_rgl, color="yellow", alpha=0.2) shade3d(mesh2_rgl, color="cyan", alpha=0.2) shade3d(mesh_d_rgl, color="red") ``` ## Intersection ```{r} mesh1 <- makeMesh(dataTruncIcosahedron, triangulate=TRUE) mesh1_rgl <- toRGL(mesh1) mesh2_rgl <- translate3d(cube3d(), 2, 0, 0) mesh2 <- makeMesh(mesh2_rgl, triangulate=TRUE) mesh_i <- boolIntersection(list(mesh1, mesh2)) mesh_i_rgl <- toRGL(mesh_i) shade3d(mesh1_rgl, color="yellow", alpha=0.2) shade3d(mesh2_rgl, color="cyan", alpha=0.2) shade3d(mesh_i_rgl, color="red") ``` # Remeshing See [`CGAL` remeshing](https://doc.cgal.org/latest/PMP_Remeshing/) ## Approximated centroidal Voronoi diagram remeshing ```{r} mesh <- makeMeshValid(dataOloid) mesh_rgl <- toRGL(mesh) mesh_d <- remeshACVD(mesh, method="uniform_iso_qem", nVerts=100L) mesh_d_rgl <- toRGL(mesh_d) mfrow3d(1, 2) view3d(0, 30, zoom=0.8) wire3d(mesh_rgl) next3d() view3d(0, 30, zoom=0.8) wire3d(mesh_d_rgl) ``` ## Surface Delaunay ```{r} mesh <- makeMesh(dataPentaPrism, triangulate=TRUE) mesh_rgl <- toRGL(mesh) mesh_d <- remeshDelaunay(mesh, edgeSize=0.2, facetDist=0.2, protectConstraints=TRUE) mesh_d_rgl <- toRGL(mesh_d) mfrow3d(1, 2) view3d(0, 30, zoom=0.8) wire3d(mesh_rgl) next3d() view3d(0, 30, zoom=0.8) wire3d(mesh_d_rgl) ``` ## Isotropic ```{r} mesh <- makeMesh(dataTruncIcosahedron, triangulate=TRUE) mesh_rgl <- toRGL(mesh) mesh_i <- remeshIsotropic(mesh, targetEdgeLen=0.7) mesh_i_rgl <- toRGL(mesh_i) mfrow3d(1, 2) view3d(0, 0, zoom=0.7) wire3d(mesh_rgl) next3d() view3d(0, 0, zoom=0.7) wire3d(mesh_i_rgl) ``` ## Triangulated Surface Mesh Simplification ```{r} mesh <- makeMesh(dataHopfTorus, triangulate=TRUE) mesh_rgl <- toRGL(mesh) mesh_s <- remeshSimplify(mesh, method="LT-R", stopUeRatio=0.1) mesh_s_rgl <- toRGL(mesh_s) mfrow3d(1, 2) view3d(0, 0, zoom=0.7) wire3d(mesh_rgl) next3d() view3d(0, 0, zoom=0.7) wire3d(mesh_s_rgl) ``` ## Smoothing ### Smooth Shape ```{r} mesh <- dataHeart1 mesh_rgl <- toRGL(mesh) mesh_s <- remeshSmoothShape(mesh, nIter=5L, time=1) mesh_s_rgl <- toRGL(mesh_s) mfrow3d(1, 2) view3d(0, -90, zoom=0.7) shade3d(mesh_rgl, col="forestgreen") next3d() view3d(0, -90, zoom=0.7) shade3d(mesh_s_rgl, col="darkolivegreen4") ``` ### Angle Smoothing ```{r} mesh <- makeMesh(dataSeptuaginta, triangulate=TRUE) mesh_rgl <- toRGL(mesh) mesh_s <- remeshSmoothAngle(mesh, nIter=5L) mesh_s_rgl <- toRGL(mesh_s) mfrow3d(1, 2) view3d(45, -45, zoom=0.7) shade3d(mesh_rgl, col="darkviolet") next3d() view3d(45, -45, zoom=0.7) shade3d(mesh_s_rgl, col="gray") ``` Note that CGAL `angle_and_area_smoothing()` supports smoothing by area optimization as well. However, this feature requires the external [Ceres library](https://github.com/ceres-solver/ceres-solver) and is thus currently not enabled here. ### Tangential Relaxation ```{r} mesh <- makeMesh(dataSeptuaginta, triangulate=TRUE) mesh_rgl <- toRGL(mesh) mesh_s <- remeshSmoothTangentRelax(mesh, nIter=5L) mesh_s_rgl <- toRGL(mesh_s) mfrow3d(1, 2) view3d(45, -45, zoom=0.7) shade3d(mesh_rgl, col="gray") next3d() view3d(45, -45, zoom=0.7) shade3d(mesh_s_rgl, col="royalblue3") ``` # Subdivision See [`CGAL subdivision`](https://doc.cgal.org/latest/Subdivision_method_3/) ## Catmull-Clark ```{r} mesh <- makeMesh(dataPentaPrism, triangulate=TRUE) mesh_rgl <- toRGL(mesh) mesh_cc <- subdivide(mesh, method="CC", nIter=2L) mesh_cc_rgl <- toRGL(mesh_cc) mfrow3d(1, 2) view3d(0, 30, zoom=0.8) wire3d(mesh_rgl) next3d() view3d(0, 30, zoom=0.8) wire3d(mesh_cc_rgl) ``` ## Doo-Sabin ```{r} mesh <- makeMesh(dataSeptuaginta, triangulate=TRUE) mesh_rgl <- toRGL(mesh) mesh_ds <- subdivide(mesh, method="DS", nIter=1L) mesh_ds_rgl <- toRGL(mesh_ds) mfrow3d(1, 2) view3d(0, 30, zoom=0.8) wire3d(mesh_rgl) next3d() view3d(0, 30, zoom=0.8) wire3d(mesh_ds_rgl) ``` ## Loop ```{r} mesh <- makeMesh(dataSeptuaginta, triangulate=TRUE) mesh_rgl <- toRGL(mesh) mesh_l <- subdivide(mesh, method="Loop", nIter=1L) mesh_l_rgl <- toRGL(mesh_l) mfrow3d(1, 2) view3d(0, 30, zoom=0.8) wire3d(mesh_rgl) next3d() view3d(0, 30, zoom=0.8) wire3d(mesh_l_rgl) ``` ## Sqrt3 ```{r} mesh <- makeMesh(dataPentaPrism, triangulate=TRUE) mesh_rgl <- toRGL(mesh) mesh_s3 <- subdivide(mesh, method="Sqrt3", nIter=2L) mesh_s3_rgl <- toRGL(mesh_s3) mfrow3d(1, 2) view3d(0, 30, zoom=0.8) wire3d(mesh_rgl) next3d() view3d(0, 30, zoom=0.8) wire3d(mesh_s3_rgl) ``` # Surface Reconstruction ## Removing outliers from point cloud ```{r} ptsBefore <- matrix(rnorm(120L, mean=0, sd=1), ncol=3L) getAverageSpacing(ptsBefore, nNeighbors=6L) ## contaminate idx <- sample(seq_len(nrow(ptsBefore)), 4L, replace=FALSE) ptsBefore[idx, ] <- matrix(rnorm(12L, mean=10, sd=1), ncol=3L) ptsAfter <- removeOutliers(ptsBefore, nNeighbors=6L) dim(ptsBefore) dim(ptsAfter) ``` ## AFS See [`CGAL` AFS](https://doc.cgal.org/latest/Advancing_front_surface_reconstruction/) ```{r} mesh <- dataHeart1 mesh_rgl <- toRGL(mesh) mesh_afs <- reconstructAFS(mesh[["vertices"]], nNeighbors=30) mesh_afs_rgl <- toRGL(mesh_afs) mfrow3d(1, 2) view3d(0, -90, zoom=0.7) shade3d(mesh_rgl, col="mediumorchid4") next3d() view3d(0, -90, zoom=0.7) shade3d(mesh_afs_rgl, col="maroon2") ``` ## SSS See [`CGAL` SSS](https://doc.cgal.org/latest/Scale_space_reconstruction_3/) ```{r} mesh <- dataHeart1 mesh_rgl <- toRGL(mesh) mesh_sss <- reconstructSSS(mesh[["vertices"]], nScaleIter =2L, forceManifold=TRUE, nNeighbors =12L) mesh_sss_rgl <- toRGL(mesh_sss) mfrow3d(1, 2) view3d(0, -90, zoom=0.7) shade3d(mesh_rgl, col="yellowgreen") next3d() view3d(0, -90, zoom=0.7) shade3d(mesh_sss_rgl, col="rosybrown4") ``` ## Poisson See [`CGAL` SSS](https://doc.cgal.org/latest/Poisson_surface_reconstruction_3/) ```{r} mesh <- makeMesh(dataSeptuaginta) mesh_rgl <- toRGL(mesh) mesh_psr <- reconstructPoisson(mesh[["vertices"]], normalsFun=getNormalsFun(6L), smAngle=20, smRadius=1, smDistance=20) mesh_psr_rgl <- toRGL(mesh_psr) mfrow3d(1, 2) shade3d(mesh_rgl, col="gray") next3d() shade3d(mesh_psr_rgl, col="gray") ``` ## Alpha Wrapping See [`CGAL` Alpha Wrapping](https://doc.cgal.org/latest/Alpha_wrap_3/) ```{r} mesh <- dataHeart1 mesh_rgl <- toRGL(mesh) mesh_aw <- alphaWrap(mesh, alphaRel =10, offsetRel=300) mesh_aw_rgl <- toRGL(mesh_aw) mfrow3d(1, 2) view3d(0, -90, zoom=0.7) shade3d(mesh_rgl, col="olivedrab3") next3d() view3d(0, -90, zoom=0.7) shade3d(mesh_aw_rgl, col="mediumseagreen") ``` # Bounding Shapes ## Axis-parallel Bounding Box ```{r} mesh1 <- makeMesh(dataTubularKnot) mesh1_rgl <- toRGL(mesh1) bb1 <- getBoundingBox(mesh1[["vertices"]]) bb1_rgl <- toRGL(bb1) view3d(10, 25, zoom=0.9) shade3d(mesh1_rgl, color="mediumaquamarine") wire3d(bb1_rgl) ``` ## Optimal (Oriented) Bounding Box Based on matrix of points ```{r} mesh2 <- dataHeart1 mesh2_rgl <- toRGL(mesh2) bb2 <- getBoundingBox(mesh2[["vertices"]], oriented=TRUE) bb2_rgl <- toRGL(bb2) shade3d(mesh2_rgl, color="peachpuff") wire3d(bb2_rgl) ``` ## Bounding Sphere Based on `mesh3d` object ```{r} bs_rgl <- getBoundingSphere(dataToroHelix, out="rgl") shade3d(dataToroHelix, color="plum2") wire3d(bs_rgl) ``` ## Bounding Ellipse ```{r} mesh <- dataHeart1 mesh_rgl <- toRGL(mesh) bell_rgl <- getBoundingEll(mesh, out="rgl", eps=0.01) shade3d(mesh_rgl, color="lightgreen") wire3d(bell_rgl) ``` ## Convex Hull ```{r} mesh <- makeMesh(dataToroHelix) mesh_rgl <- toRGL(mesh) hull <- getConvexHull(mesh[["vertices"]]) hull_rgl <- toRGL(hull) mfrow3d(1, 2) view3d(15, 45, zoom=0.8) wire3d(mesh_rgl) next3d() view3d(15, 45, zoom=0.8) wire3d(hull_rgl) ``` # Distace and Agreement Measures ## Euclidean Distance from Points to a Mesh ```{r} mesh <- makeMesh(dataPentaPrism, triangulate=TRUE) points <- matrix(2*runif(3*4), ncol=3) getDistance(mesh, points) ``` ## Distance Between the Two Respective Centers of Mass (DCOM) ```{r} getDCOM(dataHeart1, dataHeart2) ``` ## Surface Distance Between two Meshes ### Hausdorff Distance See [`CGAL` Hausdorff distance](https://doc.cgal.org/latest/Polygon_mesh_processing/index.html#PMPDistance), [dkfz metrics reloaded: HD](https://metrics-reloaded.dkfz.de/metric-library/hd) Approximate ```{r} getHausdorff(dataHeart1, dataHeart2, symmetric=TRUE) ``` Bounded error ```{r} getHausdorff(dataHeart1, dataHeart2, symmetric=TRUE, errBound=0.01) ``` Quantile (e.g., 'HD95'), see [dkfz metrics reloaded: xHD](https://metrics-reloaded.dkfz.de/metric-library/xhd) ```{r} getHausdorff(dataHeart1, dataHeart2, symmetric=TRUE, p=0.95) ``` ### Average symmetric surface distance (ASSD) and Root Mean Squared Error (RMSE) See [dkfz metrics reloaded: ASSD](https://metrics-reloaded.dkfz.de/metric-library/assd) ```{r} sd_heart <- getSurfaceDist(dataHeart1, dataHeart2, p=0.95, ptsOnFaces=100L) sd_heart[["ASSD"]] sd_heart[["RMSE"]] ``` ## Volume-Overlap Based Similarity Measures * [dkfz metrics reloaded: Jaccard Similarity Coefficient](https://metrics-reloaded.dkfz.de/metric-library/intersection_over_union) (JSC, aka 'Intersection over Union', IoU) * [dkfz metrics reloaded: Dice Similarity Coefficient](https://metrics-reloaded.dkfz.de/metric-library/dsc) (DSC) ```{r} mesh1_rgl <- cube3d() # (from the rgl package) mesh2_rgl <- translate3d(cube3d(), 1, 1, 1) jsc_dsc <- getJSCDSC(mesh1_rgl, mesh2_rgl) jsc_dsc[["JSC"]] jsc_dsc[["DSC"]] ``` ```{r echo=FALSE, results="asis"} Sys.setenv("RGL_USE_WEBSHOT"=rgl_webshot_org) ```