sdog.tex

\chapter{Volume-Preserving SDOG Refinement} \label{chap:sdog}
One of the goals of this thesis is to produce 3D DGGS's with cells of as equal volume as possible.
The first approach we use to achieve this goal is modifying SDOG refinement in order to improve its volume-preserving properties.
While SDOG cells are relatively uniform in size, there is still significant variation that could be reduced.
We chose to use SDOG as a starting point over other options for two main reasons.
First, since SDOG uses a semiregular degenerate refinement, it already satisfies the primary goal of the thesis---that is, support for unbounded ranges of altitude.
Second, the use of spherical coordinates in SDOG refinement allows for efficient coding operations, which we discuss in \cref{chap:coding}.


The content of this chapter is taken from the article "Toward Volume Preserving Spheroid-Degenerated Octree Grid," authored by Benjamin Ulmer and Faramarz Samavati, which appeared in the journal \textit{Geoinformatica}~\cite{ulmer2020toward}.
Slight modifications have been made to maintain consistent terminology with the rest of the thesis, along with a more streamlined presentation of the methodology. Furthermore, the blending method presented in this chapter is different from that in the article.


\section{SDOG Overview} \label{chap:4:sdog}
Before describing our modifications, we first provide a brief explanation of SDOG construction and refinement as initially proposed by Yu and Wu~\cite{yu2009sdog}.
SDOG is an extension of the traditional octree to a spherical, as opposed to Euclidean, volume.
A sphere with twice the radius of the Earth is initially divided into eight equal octants via the equatorial plane and two perpendicular meridian planes.
These octants are taken to be the most coarse cells of the grid and are then refined to create more fine discretizations of the sphere.
\Cref{fig:sdog} shows an SDOG octant after four applications of refinement.


\begin{figure}[t!]
	\centering
	\includegraphics[width=\textwidth]{sdog.pdf}
	\caption[Different views of an SDOG octant]{
		One octant of an SDOG grid after four levels of refinement viewed (a) at an angle, (b) from the front, and (c) from the side.
		Compared to a 3D LLG, cells are more uniform in size and have better compactness.
		Refer to \cref{chap:4:results} for a detailed analysis of the volume and compactness properties of SDOG.
	}
	\label{fig:sdog}
\end{figure}


\begin{figure}[t!]
	\centering
	\includegraphics[width=\textwidth]{sdog-refinement.pdf}
	\caption[Splitting surfaces used in SDOG refinement]{
		Location and extent of splitting surfaces in SDOG refinement for (a) SG cells, (b) LG cells, and (c) NG cells.
		Only NG cells have all three splitting surfaces fully refine the cell into eight children, and make up the majority of cells as the grid becomes increasingly refined.
	}
	\label{fig:sdog-refinement}
\end{figure}


SDOG cells---including octants---are refined using the midpoint of each spherical coordinate: latitude, longitude, and radius.
These midpoints create splitting surfaces used to divide parent cells into smaller children cells, shown in \cref{fig:sdog-refinement}.
As described in \cref{chap:3:semiregDegen}, a semiregular degenerate refinement is used to prevent excessive degeneration in cell size and compactness near the poles and centre of the sphere.
As a result, SDOG cells are grouped into three classes, depending on which singularities they border.


Cells that extend to the centre of the sphere and one of the poles are referred to as Sphere-degenerated Grid (SG) cells (\cref{fig:sdog-refinement}a) and include the original eight octants.
For these cells, the longitudinal splitting surface does not extend beyond the latitudinal one in the direction towards the pole.
Additionally, neither the latitudinal nor longitudinal splitting surfaces extend beyond the radial one in the direction towards the centre of the sphere.
The result of this refinement is four children cells: another SG cell, one Latitude-degenerated Grid (LG) cell, and two Normal Grid (NG) cells.
LG cells (\cref{fig:sdog-refinement}b) are similar to SG ones, except that they only extend to one of the poles and not the centre of the sphere.
Therefore, the longitudinal splitting surface does not extend beyond the latitudinal one in the direction towards the pole.
This refinement results in six children cells: two LG cells and four NG cells.
NG cells (\cref{fig:sdog-refinement}c) extend to neither the pole nor the centre of the sphere and make up the majority of SDOG cells.
These cells are fully refined into eight children NG cells and are the regular case for SDOG refinement.


\subsection{Number of SDOG Cells} \label{chap:4:numCells}
Analyzing the number of cells in the grid at each level of refinement is useful not only for measuring volume-preserving properties---such as quickly calculating the average cell volume---but also for analyzing the grid's behaviour as the level of refinement increases.
This type of analysis is useful in informing decisions about how to modify refinement to improve volume preservation.


With regular refinement, a simple exponential formulation gives the number of cells in the grid at any resolution.
Semiregular degenerate refinement makes this computation more complicated.
Despite this, we can use the above refinement rules to derive recursive definitions for the number of cells in an SDOG grid (or a single octant) at a given level of refinement.
Let $S(k)$, $L(k)$, $N(k)$, and $T(k)$ be the number of SG, LG, NG, and total cells of an SDOG octant at refinement level $k$, respectively.
There is only ever one SG cell in an SDOG octant, so trivially
%
\begin{equation*}
S(k) = 1 \in \mathcal{O}(1).
\end{equation*}
%
We know each LG cell produces two new LG cells, and that the SG cell produces one new LG cell.
From this, we say
%
\begin{equation*}
L(k) = 2L(k-1) + 1 \quad\text{and}\quad L(1) = 1.
\end{equation*}
%
Similarly, each NG cell produces eight new NG cells, each LG cell produces four, and the SG cell produces two.
Thus,
%
\begin{equation*}
N(k) = 8N(k-1) + 4L(k-1) + 2 \quad\text{and}\quad N(1) = 2.
\end{equation*}
%
From here, we note $L(k)$ is a linear non-homogeneous recurrence which can be solved with standard techniques~\cite{bellman1963differential}.
Solving and substituting into $N(k)$, we get another linear non-homogeneous recurrence, which can be solved similarly.
Finally, we get the closed forms
%
\begin{equation*}
L(k) = 2^{k} - 1 \in \mathcal{O}(2^k),
\end{equation*}
%
\begin{equation*}
N(k) = \frac{1}{21} \left( 7 \cdot 2^{k} + 8^{k+1} + 6 \right) - 2^{k} \in \mathcal{O}(8^k), \quad\text{and}
\end{equation*}
%
\begin{equation*}
T(k) = S(k) + L(k) + N(k) = \frac{1}{21} \left( 7 \cdot 2^{k} + 8^{k+1} + 6 \right) \in \mathcal{O}(8^k).
\end{equation*}
%
As far as we are aware, these formulations have not been provided in any of the preexisting literature on SDOG.


\begin{figure}[ht!]
	\centering
	\includegraphics[width=0.6\textwidth]{sph-elements.pdf}
	\caption[Overview of how an SDOG cell is defined by a range of spherical coordinates]{
		An SDOG cell is defined by a range in each spherical coordinate: latitude $\varphi$, longitude $\lambda$, and radius $r$.
		Because of this, volume and surface area are easily derived from the volume and area elements of spherical coordinates.
	}
	\label{fig:sph-elements}
\end{figure}


\subsection{Geometry of SDOG Cells} \label{chap:4:geom}
In order to measure the volume preservation properties of SDOG and its modifications, it is necessary to be able to measure the volume of individual cells in the grid.
Referring to \cref{fig:sph-elements}, an SDOG cell represents a range of each spherical coordinate (latitude $\varphi$, longitude $\lambda$, and radius $r$); therefore, calculating the volume of an individual cell is a straightforward task.
Note that we use the geographic convention for spherical coordinates in this thesis.
Let the subscripts $\mathrm{max}$ and $\mathrm{min}$ denote the maximum and minimum of a given spherical coordinate for an SDOG cell; then, the volume is \cite{yu2009sdog}
%
\begin{equation} \label{eq:volume}
\frac{1}{3} \left( \lambda_\mathrm{max} - \lambda_\mathrm{min} \right) \left(r_\mathrm{max}^{\,3} - r_\mathrm{min}^{\,3} \right) \left(\sin\varphi_\mathrm{max} - \sin\varphi_\mathrm{min} \right).
\end{equation}


In addition to the volume of a cell, surface area is another useful property to be able to measure.
Combined with the volume of cells, this allows us to measure the compactness of cells, which we use in \cref{chap:4:results} to help evaluate the consequences of our modifications.
From the fact that SDOG cells are refined using spherical coordinates, each face of a cell is a section of a simple geometric shape.
Faces created by radial splitting surfaces are spherical, with surface area given by
%
\begin{equation*}
r^{\,2} \left( \lambda_\mathrm{max} - \lambda_\mathrm{min} \right) \left( \sin\varphi_\mathrm{max} - \sin\varphi_\mathrm{min} \right).
\end{equation*}
%
Faces created by longitudinal splitting surfaces are the difference of two circular sectors, and have an area of
%
\begin{equation*}
\frac{1}{2} \left( \varphi_\mathrm{max} - \varphi_\mathrm{min} \right) \left( r_\mathrm{max}^{\,2} - r_\mathrm{min}^{\,2} \right).
\end{equation*}
%
Finally, faces created by latitudinal splitting surfaces lie on a cone, with a surface area of
%
\begin{equation*}
\frac{1}{2} \cos\varphi \left( \lambda_\mathrm{max} - \lambda_\mathrm{min} \right) \left( r_\mathrm{max}^{\,2} - r_\mathrm{min}^{\,2} \right).
\end{equation*}


\section{Modified SDOG Refinement} \label{chap:4:modified}
The main goal of this work is to modify SDOG in such a way as to improve volume preservation while minimizing the impact on other desired properties of the grid.
As a baseline, the distribution of cell volumes in a conventional SDOG grid is visualized in \cref{fig:sdog-volume}; the largest cell has approximately 8.9 times the volume of the smallest cell.
In conventional SDOG refinement, the location of the different splitting surfaces is always at the midpoint of the respective spherical coordinate; we question if this should be the case.
For an octree in Euclidean space, such midpoint refinement is desirable, as it generates children cells of identical size and shape.
In spherical space, however, this property does not transfer.
Using midpoints to refine cells makes for a simple refinement scheme, but it makes no guarantees about the shape or size of the resulting child cells.


\begin{figure}[ht!]
	\centering
	\includegraphics[width=0.85\textwidth]{sdog-volume.pdf}
	\caption[Visualization of cell volumes in SDOG]{
		Cell volumes in an octant after four applications of conventional SDOG refinement
	}
	\label{fig:sdog-volume}
\end{figure}


\begin{figure}[ht!]
	\centering
	\includegraphics[width=0.55\textwidth]{sdog-functions.pdf}
	\caption[How functions determine the location of SDOG splitting surfaces]{
		Each SDGO cell represents a range in each spherical coordinate; each splitting surface's location is expressed as a function of the maximum and minimum of the respective range.
		Here, we show only an NG cell; however, the same applies to SG and LG cells.
		The functions $f$, $g$, and $h$ serve as placeholders for any valid function that results in the output being strictly between the two inputs.
	}
	\label{fig:functions}
\end{figure}


By allowing the location of the splitting surfaces to vary, we can modify the shape and size of child cells and---as a result---affect the volume preservation, compactness, and other properties of the grid.
Let $c_{s}$ be the location of the splitting surface, where $c$ is one of $\left\lbrace \varphi, \lambda, r \right\rbrace$ (\cref{fig:functions}).
One way to express the location of the splitting surfaces used for refinement is as a convex combination of maximum and minimum values:
%
\begin{equation*}
c_{s} = \alpha c_\mathrm{max} + \left( 1-\alpha \right) c_\mathrm{min}, \quad \alpha \in \left( 0, 1 \right).
\end{equation*}
%
Conventional SDOG used midpoints (i.e. $\alpha = 1/2$) for each spherical coordinate during refinement, regardless of cell type.
While a convex combination is the most straightforward, any function of the maximum and minimum such that the result is strictly between the two is a valid method for determining the location of the splitting surfaces.
Thus, the location of splitting surfaces is modified by changing this function, either by using a different value of $\alpha$ or by using a different function altogether.
Furthermore, the function used can be different for each cell type and spherical coordinate.


A useful function for improving volume preservation is one that results in one of the new ranges having a specific percentage of the volume of the original range.
Each spherical coordinate has a different effect on volume; therefore, this function is different for each.
We start with the radial splitting surface.
Referring to \cref{eq:volume}, let $p \in (0,1)$ be the percentage we wish for the lower range to have.
Then,
%
\begin{equation*}
p \left( r_\mathrm{max}^{\,3} - r_\mathrm{min}^{\,3} \right) = r_{s}^{\,3} - r_\mathrm{min}^{\,3}
\end{equation*}
%
\begin{equation*}
p r_\mathrm{max}^{\,3} - p r_\mathrm{min}^{\,3} = r_{s}^{\,3} - r_\mathrm{min}^{\,3}
\end{equation*}
%
\begin{equation*}
r_{s}^{\,3} = p r_\mathrm{max}^{\,3} + r_\mathrm{min}^{\,3} - p r_\mathrm{min}^{\,3}
\end{equation*}
%
\begin{equation*}
r_{s}^{\,3} = p r_\mathrm{max}^{\,3} + \left( 1 - p \right) r_\mathrm{min}^{\,3}
\end{equation*}
%
\begin{equation} \label{eq:radVol}
r_{s} = \sqrt[3]{ p r_\mathrm{max}^{\,3} + \left( 1 - p \right) r_\mathrm{min}^{\,3} }.
\end{equation}
%
The derivations for the latitudinal and longitudinal splitting surfaces follow the same, with results
%
\begin{equation} \label{eq:latVol}
\varphi_{s} = \arcsin \left( p \sin\varphi_\mathrm{max} + \left( 1 - p \right) \sin\varphi_\mathrm{min} \right) \quad\text{and}
\end{equation}
%
\begin{equation} \label{eq:longVol}
\lambda_{s} = p \lambda_\mathrm{max} + \left( 1 - p \right) \lambda_\mathrm{min}.
\end{equation}


The question then becomes which splitting surfaces should be modified, and in which ways, in order to improve the volume preservation of the grid.
We first look at which splitting surfaces should \textit{not} be modified.
From \cref{eq:longVol}, it is clear a longitudinal splitting surface at the midpoint will always split a cell exactly in half, and therefore they should not be changed.


\begin{figure}[ht!]
	\centering
	\includegraphics[width=0.675\textwidth]{sdog-shells.pdf}
	\caption[Spherical shells that result from SDOG refinement]{
		Spherical shells created by the radial splitting surfaces of SG cells.
		At $k$ levels of refinement there are $k$ shells and one inner SG cell.
		These shells are similar and should have volume proportional to the number of cells they contain.
	}
	\label{fig:sdog-shells}
\end{figure}


Less trivially, the radial splitting surface for SG cells should also remain at the midpoint.
Referring to \cref{fig:sdog-shells}, we see that the radial splitting surfaces for SG cells separate the grid into spherical shells.
Shell $n$ has a volume proportional to
%
\begin{equation*}
\alpha^{3n} - \alpha^{3 \left( n + 1 \right)},
\end{equation*}
%
so the ratio of the volumes of shell $n+1$ and $n$ is
%
\begin{equation} \label{eq:shellVolume}
\frac{ \alpha^{3 \left(n + 1 \right)} - \alpha^{3\left( n + 2 \right)} }{ \alpha^{3n} - \alpha^{3 \left( n + 1 \right)} } = \frac{ \alpha^{3} \alpha^{3n} \left( 1 - \alpha^{3} \right) }{ \alpha^{3n} \left( 1 - \alpha^{3} \right) } = \alpha^{3}.
\end{equation}
%
From the self similar nature of SDOG refinement, we know that the cells in shell $n$ are simply the cells of shell $n+1$ refined once.
We also know that, in the limit, an SDOG grid at one level higher of refinement will have eight times as many cells as the previous resolution ($\lim_{k \to \infty} T(k+1) / T(k)  = 8 $).
Therefore, in order for cells in the grid to be close to equal volume, it must be that shell $n+1$ has one eighth the volume of shell $n$---since it will have one eighth the number of cells---which occurs when $\alpha = 1 / 2$.


We are left with five possible splitting surfaces to be modified: the radial splitting surface for LG and NG cells, and the latitudinal splitting surface for SG, LG, and NG cells.
Below, we determine the ideal placement for each of these surfaces to maximize volume preservation between cells.
We then propose other possible splitting surface combinations to balance the tradeoff between volume preservation and cell compactness.


\subsection{Ideal Splitting Surfaces for Volume Preservation} \label{chap:4:ideal}
Ideal splitting surfaces to maximize volume preservation are achieved using \cref{eq:radVol,eq:latVol}; all that is required is to determine the ideal value of $p$ for the different splitting surfaces and cell types.
We start with the radial splitting surfaces for LG and NG cells and the latitudinal one for NG cells, as these surfaces behave the same as regular refinement.
Specifically, these splitting surfaces result in the same number and type of cells on both sides, a property that also holds for their children.
We call these the regular splitting surfaces.
Therefore, we require that the volume on each side of the regular splitting surfaces be equal, or in other words, we set $p = 1/2$ for these splitting surfaces.


\begin{figure}[t!]
	\centering
	\includegraphics[width=0.9859\textwidth]{sdog-zones.pdf}
	\caption[Spherical zones that result from SDOG refinement]{
		Spherical zones created by the latitudinal splitting surfaces of SG and LG cells.
		At $k$ levels of refinement, there are $k$ zones and one upper stack of LG cells in the outermost shell.
		Each successively smaller shell has one fewer zone than the previous until reaching the innermost SG cell.
		Zones in the same shell are not exactly similar, but are regular grid regions and should have volume proportional to the number of cells they contain.
	}
	\label{fig:sdog-zones}
\end{figure}


Determining the ideal latitudinal splitting surfaces for SG and LG cells is more involved.
First, notice that these two latitudinal splitting surfaces have a similar effect as the radial splitting surface for SG cells.
Referring to \cref{fig:sdog-zones}, we see that these splitting surfaces further divide the spherical shells into spherical zones.
Additionally, each zone is comprised entirely of NG cells.
From this, we conclude that zone $n$ has precisely four times as many cells as zone $n+1$, and thus, should have four times the volume as well.
Using this information, we find the value for $p$.
First, we note zone $n$ has a volume equal to $\left( 1 - p \right)^{n} p$ that of the initial octant.
Then, setting the ratio between zone $n+1$ and $n$ to be equal to $1/4$ gives us $p = 3/4$, which we use directly in \cref{eq:latVol} to find the appropriate splitting surface locations.


\begin{figure}[htp!]
	\centering
	\includegraphics[width=0.85\textwidth]{vol-volume.pdf}
	\caption[Visualization of cell volumes in the volume modification]{
		Results of the volume method after four applications of refinement.
		All NG cells have exactly the same volume, with the LG and SG cells having a lower volume.
		Notice how the resulting NG cells are stretched and squashed in order to ensure they all have equal volume.
	}
	\label{fig:modified-volume}
\end{figure}


\Cref{fig:modified-volume} shows the resulting grid from this method of calculating splitting surfaces, which we refer to as the \textit{volume} method.
In this grid, all NG cells at the same level of refinement have equal volume; this dramatically improves the volume preservation.
Only cells that extend to one of the singularities---SG and LG cells---will have a smaller volume than the other cells in the grid, by a factor of approximately 2.6 and 1.5, respectively.


\subsection{Balanced Splitting Surfaces} \label{chap:4:balanced}
While the above refinement method significantly improves volume preservation in the grid, this gain does not come without consequence.
Cells are stretched and squashed to achieve this volume preservation, which reduces cell compactness and may be an undesirable effect depending on the application.
In order to address this issue, we use different splitting surfaces to achieve a better balance between volume preservation and cell compactness.


\begin{figure}[htp!]
	\centering
	\includegraphics[width=0.85\textwidth]{lat-volume.pdf}
	\caption[Visualization of cell volumes in the latitude modification]{
		Results of the latitude method after four applications of refinement.
		Since only latitude splitting surface for SG and LG cells have been modified, the results are similar to that of conventional SDOG.
	}
	\label{fig:latitude-volume}
\end{figure}


Looking at \cref{fig:modified-volume}, we see that the regular splitting surfaces are responsible for the majority of the reduction in cell compactness.
Our first balanced scheme then is to leave these splitting surfaces at the midpoints and only modify the latitudinal splitting surfaces for SG and LG cells.
\Cref{fig:latitude-volume} shows the results of this method, which we refer to as the \textit{latitude} method.
Comparing this grid to conventional SDOG (refer back to \cref{fig:sdog-volume}), the two are nearly identical, with only slight variation in the placement of latitude splitting surfaces.
Thus, this method offers only a slight improvement with regards to volume preservation, while also only slightly sacrificing cell compactness.


\begin{figure}[tp!]
	\centering
	\includegraphics[width=0.85\textwidth]{bal-volume.pdf}
	\caption[Visualization of cell volumes in the balanced modification]{
		Results of the balanced method after four applications of refinement.
		NG cells are still stretched and squashed in order to better preserve volume; however, the effect is less pronounced than in the volume method.
	}
	\label{fig:balanced-volume}
\end{figure}


In order to achieve varying tradeoffs between compactness and volume preservation, modifying the regular splitting surfaces is necessary.
\Cref{eq:radVol,eq:latVol} give ideal placements for volume preservation as compared to the conventional midpoint functions which result in better compactness.
Therefore, using different functions that blend between these two extremes allows for a more balanced tradeoff.
There are endless possibilities for these functions; however, as will be required for coding in \cref{chap:mapping}, they should be easily invertible.
That is, given a splitting surface, we need to be able to determine the parameter $d$ between given maximum and minimum values that results in said splitting surface.
To calculate splitting surfaces during refinement, $d = 1/2$.
For the radial splitting surfaces, we propose the function
%
\begin{equation} \label{eq:radBlend}
r_{s} = \sqrt[t]{ d r_\mathrm{max}^{\,t} + \left( 1 - d \right) r_\mathrm{min}^{\,t} },
\end{equation}
%
where $1 \leq t \leq 3$ blends between compactness at $t = 1$ (equivalent to midpoint) and volume preservation at $t=3$ (equivalent to \cref{eq:radVol}).
For the latitudinal splitting surfaces, we propose
%
\begin{equation} \label{eq:latBlend}
\varphi_{s} = h \arcsin \left( d \sin \left( \frac{1}{h} \varphi_\mathrm{max} \right) + \left( 1 - d \right) \sin \left( \frac{1}{h} \varphi_\mathrm{min} \right) \right),
\end{equation}
%
where $1 \leq h \leq \infty$ blends between volume preservation at $h = 1$ (equivalent to \cref{eq:latVol}) and compactness as $h \rightarrow \infty$ (equivalent to midpoint).
We found values of $t = 2$ and $h = 1.45$ to offer a relatively balanced tradeoff between the two properties, with the resulting grid shown in \cref{fig:balanced-volume}.
We refer to this method as the \textit{balanced} one.


\section{Results} \label{chap:4:results}
There are several potential methods for evaluating the volume-preserving properties of a 3D DGGS.
When first proposed by Yu and Wu, they used the ratio between cells of the largest and smallest volume to evaluate the volume-preserving properties of SDOG~\cite{yu2009sdog}.
This volume ratio is a useful measure for determining the worst-case difference in the volume of cells; however, it does not give any information about the distribution of said volumes.
For example, a grid with all cells except one having equal volume and a grid where every cell has a distinct volume could have the same volume ratio.
To get a complete understanding of volume preservation, we should also examine statistics that measure distribution.
For this purpose, we use the coefficient of variation (CV), which is simply the ratio between the standard deviation (SD) and the mean.
We use the CV over the SD as it a dimensionless quantity.


In modifying the refinement for volume preservation, it is also important to evaluate the impact these changes have on other properties of the grid.
Specifically, we should measure the effect our changes have on the compactness of cells.
To measure this, we use the notion of sphericity, which quantifies how closely the shape of an object approximates a sphere~\cite{wadell1935volume}.
Sphericity is defined as the ratio between the surface area of a sphere with the same volume as the object and the surface area of the object itself.
Therefore, a perfect sphere will have a sphericity of one, and any other object will have sphericity strictly less than one.
Formally, given an object $\omega$ and a sphere $s$ such that $\operatorname{vol}(s) = \operatorname{vol}(\omega)$, the sphericity of $\omega$, $\Psi$, is given by $\operatorname{area}(s) / \operatorname{area}(\omega)$.
Equivalently,
%
\begin{equation*}
\Psi = \frac{\pi^{\frac{1}{3}}\left( 6\operatorname{vol}(\omega) \right)^{\frac{2}{3}}}{\operatorname{area}(\omega)}.
\end{equation*}
%
Since the sphere is the most compact shape, lower values of sphericity corespond to lower compactness.
The sphericity of several common geometric shapes is provided in \cref{tab:sphericity}.
We use the mean and SD of sphericity for all cells in the grid to evaluate compactness globally.


\begin{table}[ht!]
	\centering
	\caption[Sphericity of common geometric shapes]{
		Sphericity of common geometric shapes
	}
	\begin{tabular}{@{} c c c c c c @{}}
		\toprule
		           & Sphere & Hemisphere & Cube  & Spherical Octant (SG Cell) & Regular Tetrahedron \\ \midrule
		Sphericity & 1      & 0.840      & 0.806 & 0.8                        & 0.671               \\ \bottomrule
	\end{tabular}
	\label{tab:sphericity}
\end{table}


\begin{figure}[p!]
	\centering
	\includegraphics[width=0.8\textwidth]{volume-ratio.pdf}
	\caption[Graph of volume ratio for the different grids]{
		Volume ratio for the different grids at increasing levels of refinement.
		Note that for the volume method, the volume ratio does not change with refinement level.
	}
	\label{fig:vr}
\end{figure}


\begin{figure}[p!]
	\centering
	\includegraphics[width=0.8\textwidth]{cv-volume.pdf}
	\caption[Graph of CV of volume for the different grids]{
		CV of volume for the different grids at increasing levels of refinement
	}
	\label{fig:cv}
\end{figure}


\begin{table}[p!]
	\centering
	\caption[Convergence values of measures for the different grids]{
		Convergence value of each measure for the different grids
	}
	\begin{tabular}{@{} c c c c c @{}}
		\toprule
		                 & SDOG    & Latitude & Balanced & Volume     \\ \midrule
		Volume Ratio     & 8.88    & 7.99     & 4.470    & 2.63       \\
		CV of Volume     & 0.412   & 0.399    & 0.201    & $\approx$0 \\
		Mean Sphericity  & 0.799   & 0.797    & 0.786    & 0.768      \\
		SD of Sphericity & 0.00639 & 0.00626  & 0.0147   & 0.0271     \\ \bottomrule
	\end{tabular}
	\label{tab:results}
\end{table}


\begin{figure}[p!]
	\centering
	\includegraphics[width=0.8\textwidth]{mean-sph.pdf}
	\caption[Graph of mean sphericity for the different grids]{
		Mean sphericity for the different grids at increasing levels of refinement
	}
	\label{fig:sph}
\end{figure}


\begin{figure}[p!]
	\centering
	\includegraphics[width=0.8\textwidth]{sd-sph.pdf}
	\caption[Graph of SD of sphericity for the different grids]{
		Standard deviation of sphericity for the different grids at increasing levels of refinement
	}
	\label{fig:sd-sph}
\end{figure}


\begin{table}[p!]
	\centering
	\caption[Convergence values of max and min sphericity for the different grids]{
		Convergence value of max and min sphericity for the different grids
	}
	\begin{tabular}{@{} c c c c c @{}}
		\toprule
		               & SDOG   & Latitude & Balanced & Volume \\ \midrule
		Max sphericity & 0.806  & 0.806    & 0.806    & 0.806  \\
		Min sphericity & 0.754  & 0.765    & 0.730    & 0.672  \\
		Difference     & 0.0520 & 0.0406   & 0.0761   & 0.134  \\ \bottomrule
	\end{tabular}
	\label{tab:results-sph}
\end{table}


As a baseline, we have calculated the value of these measures at each refinement level from one to fifteen for conventional SDOG.
We then repeated this for the three modifications discussed in this chapter: the volume method, the latitude method, and the balanced method.
The results for each grid are displayed in \cref{fig:vr,fig:cv,fig:sph,fig:sd-sph} showing the volume ratio, CV of volume, mean sphericity, and SD of sphericity, respectively.
\Cref{tab:results} summarizes these charts with the convergence value of each property for the four different grids.
We also give convergence values for the maximum and minimum sphericity---and their difference---for each grid in \cref{tab:results-sph}.
It is important to note that for volume ratio and CV of volume, lower values are better, but for sphericity, a higher value is better.


The latitude method has a better volume ratio than conventional SDOG for all levels of refinement except the first and fourth, and a lower CV of volume for all levels of refinement after the second.
However, the mean sphericity of cells in this method is slightly reduced as compared to conventional SDOG.
The variation in sphericity is nearly identical between these two refinement methods, with the latitude one having a minuscule reduction.


As expected, with all NG cells having equal volume, the volume method significantly improves the volume ratio and the CV of volume for all refinement levels but the first.
As the level of refinement gets large, the CV of volume quickly approaches zero since the number of NG cells grows faster than the number of LG and SG cells in the grid.
The cost of this improved volume preservation is a much larger reduction in the sphericity of cells and an increase in the variation of sphericity, which is also to be expected.


By construction, the balanced method has measures in between that of conventional SDOG and the volume method.
The CV of volume, mean sphericity, and SD of sphericity are all near the respective halfway points, whereas the volume ratio still ends up being a significant improvement over conventional SDOG.

\section{Summary}
By modifying the location of splitting surfaces used in SDOG refinement, we have improved the volume preservation properties in the resulting grids.
Our modifications improve volume preservation as measured by two different metrics at the cost of reducing the compactness of cells.
Two blending functions---each defined on a single parameter---enable different balances between volume preservation and compactness.
When used for maximum volume preservation, our method results in all non-degenerate cells in the grid having exactly equal volume.