---
title: "SurfaceMesh: 3D Surface Meshes Based on CGAL"
author: "Daniel Wollschläger (<wollschlaeger@uni-mainz.de>)"
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)
```
