# Electron collision studies on the CH${}_{2}^{+}$ molecular ion

K. Chakrabarti1<EMAIL_ADDRESS>J. Zs Mezei2,3<EMAIL_ADDRESS>I. F.
Schneider3<EMAIL_ADDRESS>J. Tennyson3,4<EMAIL_ADDRESS>1Department of Mathematics, Scottish Church College, 700006 Kolkata, India
2HUN-REN Institute for Nuclear Research (ATOMKI), H-4001 Debrecen, Hungary
3LOMC-UMR6294, CNRS, Université Le Havre Normandie, 76600 Le Havre, France
4Department of Physics and Astronomy, University College London, WC1E 6BT
London, UK

###### Abstract

Calculations are performed for electron collision with the methylene molecular
ion CH${}_{2}^{+}$ in its bent equilibrium geometry, with the goal to obtain
cross sections for electron impact excitation and dissociation. The polyatomic
version of the UK molecular R-matrix codes was used to perform an initial
configuration-interaction calculation on the doublet and quartet states of the
CH${}_{2}^{+}$ ion. Subsequently, scattering calculations are performed to
obtain electron impact electronic excitation and dissociation cross sections
and, additionally, the bound states of the CH2 molecule and Feshbach
resonances in the $e$-CH${}_{2}^{+}$ system.

###### pacs:

33.80. -b, 42.50. Hz

††preprint: APS/123-QED

##  I Introduction

Many low temperature plasma environments have hydrocarbon molecular ions as
important constituents. Collision of electrons with molecules and their ions
in these environments are important processes that play a fundamental role in
initiating chemistry, particle balance and transport. For example, although
the present tendency in the magnetically controlled International
Thermonuclear Fusion Reactor type fusion devices is to coat the reactor walls
with beryllium or tungsten, hydrocarbon ions, in particular the methylene ion
CH${}_{2}^{+}$, are found in the edge and divertor plasmas of fusion devices
which operate with graphite as plasma facing material McLean05 . Another
important context is that of the dusty plasmas, the CH2 and CH${}_{2}^{+}$
being species involved in the chain of reactions resulting in the growths of
the nano and micro-particles. In these situations, the cross sections for
different electron induced process are necessary to model the plasma flow (see
for example Reiter10 ), in particular electron impact dissociation and
dissociative ionisation:

$e+\mathrm{CH_{2}^{+}}\rightarrow\left\\{\begin{array}[]{ll}\mathrm{C^{+}}+\mathrm{H_{2}}+e\\\
\mathrm{CH^{+}}+\mathrm{H}+e\end{array}\right.$ (1)
$e+\mathrm{CH_{2}^{+}}\rightarrow\left\\{\begin{array}[]{lll}e\;+\;\mathrm{CH^{+}}+\mathrm{H^{+}}+e\\\
e\;+\;\mathrm{C^{+}}+\mathrm{H^{+}}+\mathrm{H}+e\\\
e\;+\;\mathrm{C^{+}}+\mathrm{H{{}_{2}}^{+}}+e\\\
e\;+\;\mathrm{C^{+}}+\mathrm{H^{+}}+\mathrm{H^{+}}+2e\end{array}\right.$ (2)

These processes, leading to the destruction of the CH${}_{2}^{+}$ ions and to
the C atom production Janev02a ; Janev02b , are highly significant for
understanding the carbon redeposition.

In the interstellar medium (ISM), CH${}_{2}^{+}$ ions are synthesised in gas
phase by collision of C+ ions with hydrogen Wak10  and through hydrogen
abstraction by CH+. On the other hand, CH${}_{2}^{+}$ ions can be removed by
reactions such as (1), (2) and by dissociative recombination (DR),

$e+\mathrm{CH_{2}^{+}}\rightarrow\left\\{\begin{array}[]{lll}\mathrm{C+H_{2}}\\\
\mathrm{CH+H}\\\ \mathrm{C+H+H}\end{array}\right.$ (3)

which is known to proceed via Feshbach resonances Larson98 .

There is a considerable literature on CH${}_{y}^{+}$ hydrocarbon ions, and
CH${}_{2}^{+}$ ions in particular, in the context of synthesis of hydrocarbons
in the ISM Dishoeck96 ; Dishoeck06 ; Wak10 ; Puglisi18 ; IdB19 . Significant
work on CH${}_{y}^{+}$ hydrocarbon ions have also been done relevant to
plasmas for fusion Janev02a ; Janev02b ; Vane07 ; Lecointre09 ; Reiter10 .
These works mainly focus on different electron impact cross sections relevant
for plasma modeling.

Molecular structure calculations on CH${}_{2}^{+}$ have been reported by
several authors JT83 ; TP91 ; KJB94 ; Li15 ; Guo18 ; Ma21 . TP91  obtained
bending potential energy curves (PEC) and vertical excitation energies of
CH${}_{2}^{+}$ for its bent $C_{2v}$ and its linear $D_{\infty h}$
configurations. Accurate global potential energy surfaces (PES) were reported
by Guo18  and Li15 . Apart from these, there are also many spectroscopic
studies on the rovibrational states of CH${}_{2}^{+}$ Ross92 ; Bunker01 ;
Jensen02 ; Will03 ; Wang13 .

In a number of earlier studies Chakrabarti17 ; Chakrabarti18 ; Chakrabarti19a
; Chakrabarti20  we have studied electron collision with the CH molecule and
its positive ion CH+ in considerable detail. In these works, we not only
computed cross sections for different electronic processes, but also
identified many new neutral valence states of CH that are relevant for the DR.
The present article aims to continue and extend our work to more complex
hydrocarbon ions.

##  II R-matrix Calculations

###  II.1 R-matrix method

The R-matrix method, described in detail by Tennyson10  and Burke11 , and its
implementation in the polyatomic version of the UK molecular R-matrix codes
(UKRmol) jt518  is used in the present work. The method employs a division of
space into an inner region, a sphere of radius $a$ (chosen to be 10 a0 in this
work) called the $R$-matrix sphere whose purpose is to include within it all
short range interactions, and an outer region exterior to this sphere which
contains all the long range interactions. This division allows the treatment
of the short range and, the more complicated, long range interactions
separately using different techniques Tennyson10 .

In the inner region, the wave function of the target (here CH${}_{2}^{+}$) and
a single continuum electron, together having $N+1$ electrons, is taken as

$\displaystyle\Psi_{k}$ $\displaystyle=$ $\displaystyle{\cal
A}\sum_{i,j}a_{i,j,k}\Phi_{i}(1,\ldots,N)F_{i,j}(N+1)+$ (4) $\displaystyle+$
$\displaystyle\sum_{i}b_{i,k}\chi_{i}(1,\ldots,N+1)\;,$

where $\mathcal{A}$ is an antisymmetrisation operator, $\Phi_{i}(1,\ldots,N)$
is the wave function of the $N$ electron target and $F_{i,j}(N+1)$ are
continuum orbitals. The functions $\chi_{i}(1,\ldots,N+1)$ in the last term
are square integrable functions, called $L^{2}$ functions, are constructed by
allowing the projectile electron to enter the target complete active space
(CAS) and are included to take into account electron correlations and
polarization of the target in presence of the projectile electrons. The
coefficients $a_{i,j,k}$ and $b_{i,k}$ are obtained by diagonalizing the inner
region Hamiltonian.

The inner region wave function $\Psi_{k}$ is then used with appropriate
boundary conditions to obtain scattering information, the details of which are
given in the following subsections.

###  II.2 Target calculations

We used the cc-pVTZ Gaussian basis sets BPP19  centered on the C and H atoms
to represent the target orbitals. These not only gave reasonably good target
vertical excitation energies but also allows the inner region calculation to
remain manageable with respect to computational resources.

The X ${}^{2}A_{1}$ ground state of CH${}_{2}^{+}$ is known to be bent in C2v
symmetry and has the electronic configuration
$(1a_{1})^{2}(2a_{1})^{2}(1b_{2})^{2}(3a_{1})^{1}$ Pople87 ; Graber93 . In
this work all calculations are reported at the equilibrium C-H bond length
2.066 a0 and the H-C-H bond angle 140.1∘ taken from TP91 , which are very
close to those obtained by more sophisticated coupled cluster calculations
using large basis sets NRB02 . An initial Hartree-Fock (HF) calculation was
first performed on the X ${}^{2}A_{1}$ ground state of CH${}_{2}^{+}$. The HF
orbitals were then used in a configuration interaction (CI) calculation.

We considered two target models. In both models we kept two electrons frozen
in the $1a_{1}$ orbitals while the remaining five electrons were distributed
in the CAS. In the first model (M1), the complete active space was defined by
$(1a_{1}-6a_{1},1b_{1}-4b_{1},1b_{2}-4b_{2})$, while in the second (M2) the
CAS was chosen to be bigger with an additional 1$a_{2}$ orbital, namely
$(1a_{1}-8a_{1},1b_{1}-5b_{1},1b_{2}-5b_{2},1a_{2})$. Table 1 shows the
comparison of the vertical excitation energies (VEE) form the X ${}^{2}A_{1}$
ground state of CH${}_{2}^{+}$ to the first $12$ low lying excited states.
Although the second model M2 appears to produce VEEs slightly in better
agreement with the theoretical results of TP91  and Osmann99 , calculations
with this model required much longer time compared to the model M1. We
therefore chose the model M1 for subsequent calculations as it was
computationally more efficient.

From Table 1, we see that apart from the VEE of the 4 ${}^{2}A_{1}$ state,
which appears too high compared to TP91 , all other vertical excitation
energies obtained by the target model M1 are in reasonably good agreement with
the results of TP91  and Osmann99 . Moreover, our dipole moment for the
CH${}_{2}^{+}$ ground state with model M1 is 0.701 D which compares perfectly
with the value 0.701 D obtained by NRB02  using coupled cluster calculation.
The model M1 therefore provides a good description of the target for
subsequent scattering calculations.

Table 1:  Comparison of the vertical excitation energies (in eV) from the X
${}^{2}A_{1}$ ground state to 12 low lying excited states of CH${}_{2}^{+}$
for different target models. The target models used are the following:
M1: $(1a_{1})^{2}(1a_{1}-6a_{1},1b_{1}-4b_{1},1b_{2}-4b_{2})^{5}$
M2: $(1a_{1})^{2}(1a_{1}-8a_{1},1b_{1}-5b_{1},1b_{2}-5b_{2},1a_{2})^{5}$

Target state | M1 | M2 | Theorya | Theoryb
---|---|---|---|---
X ${}^{2}A_{1}$ | 0c | 0d | 0e | 0
1 ${}^{2}B_{1}$ | 0.92 | 0.81 | 0.84 | 0.83
1 ${}^{4}A_{2}$ | 5.24 | 5.07 |  |
1 ${}^{2}A_{2}$ | 6.93 | 6.81 | 6.81 | 6.92
1 ${}^{2}B_{2}$ | 7.46 | 7.36 | 7.60 | 7.8
2 ${}^{2}A_{2}$ | 7.88 | 7.60 | 7.25 | 7.26
1 ${}^{4}B_{1}$ | 9.73 | 9.58 |  |
2 ${}^{2}B_{2}$ | 9.48 | 9.17 | 9.25 | 9.6
2 ${}^{2}A_{1}$ | 11.17 | 10.50 | 10.44 | 11.1
3 ${}^{2}A_{1}$ | 13.52 | 13.04 | 12.81 |
2 ${}^{2}B_{1}$ | 13.47 | 13.21 | 13.14 | 13.9
4 ${}^{2}A_{1}$ | 14.89 | 14.76 | 13.40 |
3 ${}^{2}B_{2}$ | 13.22 | 13.23 | 13.53 |

aTP91
bOsmann99
cAbsolute energy -38.61306904 Hartree
dAbsolute energy -38.63754516 Hartree
eAbsolute energy -38.705744 Hartree

###  II.3 Scattering calculations

For the scattering calculations, we used
$8~{}a_{1},6~{}b_{1},6~{}b_{2}\textrm{ and }2~{}a_{2}$ target orbitals
allowing $2$ virtual orbitals for each symmetry. Since the target
CH${}_{2}^{+}$ is a positive ion, the continuum functions were represented by
Coulomb functions which were obtained as a solution of the radial Coulomb
equation for an isotropic Coulomb potential, and the solutions with $l\leq 4$,
and energy eigenvalue $\leq 5$ Ryd were retained in the calculation. The
Coulomb functions were then fitted to GTOs using the procedure outlined in
Faure02 .

The target and continuum orbitals must all be orthogonal to each other. To
ensure the orthogonality, the target and continuum orbitals were first
individually Schmidt orthogonalized and finally the full set of target and
continuum orbitals were symmetric orthogonalized, retaining only those
orbitals for which the eigenvalue of their overlap matrix was less than a
deletion threshold, chosen here to be $5\times 10^{-5}$. The deletion
threshold depends on the R-matrix radius and was adjusted to ensure that there
was no linear dependence.

An R-matrix was built at the boundary of the inner and outer region from the
inner region solutions (Eq.(4)). The $R$-matrix were then propagated to an
asymptotic distance $R_{asy}=70\,$a0 in a potential which included the Coulomb
potential and the dipole and quadrupole potentials of the target, where they
were then matched to asymptotic functions obtained from a Gailitis expansion
Noble84 . This matching procedure yields the $K$-matrix from which all
scattering observables can be obtained. A different route, however, is
followed for obtaining bound states, as is outlined below.

For bound states, the R-matrix and wave functions were propagated using Runge-
Kutta-Nystrom method Zhang11  to an asymptotic distance $R_{asy}=50\,$a0 in a
potential which included the Coulomb potential and the dipole and quadrupole
potentials of target, and were matched to exponentially decreasing asymptotic
functions Noble84 . A searching algorithm Sarpal91  over a non-linear quantum
defect based grid Rabadan96  was then used to find the bound states as roots
of a determinant $\mathcal{B}(E)$ dependent on the energy. The details of the
method are omitted and can be found in Sarpal91 .

Table 2:  Comparison of the vertical excitation energies (in eV) from the
ground X ${}^{3}B_{1}$ state of CH2 to some of its low lying excited states.

CH2 state | This work | CIa | Romeltb | Yamaguchic
---|---|---|---|---
X ${}^{3}B_{1}$ | 0.0d | 0.0e | 0.0f | 0.0
1 ${}^{1}A_{1}$ | 1.16 | 0.995 | 1.14 |
${}^{1}B_{1}$ | 1.74 | 1.86 | 1.63 |
2 ${}^{1}A_{1}$ | 3.24 | 3.31 | 3.38 |
${}^{3}A_{1}$ | 6.21 | 7.67 | 6.37 |
${}^{3}B_{2}$ | 7.35 | 8.05 | 7.59 | 7.86
${}^{1}B_{2}$ | 7.25 | 9.25 | 7.63 | 7.75
${}^{3}A_{2}$ | 7.63 | 7.47 | 7.57 | 7.23
${}^{1}A_{2}$ | 8.33 | 8.39 | 8.46 |

aCI calculation done at CH2 equilibrium (C-H bond length 2.0314 a0 and H-C-H
bond angle 133.8∘) using
$(1a_{1})^{2}~{}(2a_{1}-6a_{1},1b_{1}-4b_{1},1b_{2}-4b_{2})^{6}$ CAS-CI model.
bRomelt81
cYama97
d,e,f Absolute energies of the ground states are respectively $-38.985233^{d}$
Hartree, $-38.966950^{e}$ Hartree and $-39.06034^{f}$ Hartree.

##  III Results

All scattering calculations in this work were performed at a single geometry,
namely the equilibrium geometry of the CH${}_{2}^{+}$ target ion, for bound
states of the CH2 molecule, Feshbach resonances in the $e+$CH${}_{2}^{+}$
system and cross sections for elastic scattering and electronic excitations.
An 11 state scattering model including three ${}^{2}A_{1},\textrm{ three
}^{2}B_{1},\textrm{ three }^{2}B_{1}$ and two ${}^{2}A_{2}$ target states in
the close coupling expansion Eq. (4) were used for the singlet
$e+$CH${}_{2}^{+}$ scattering close-coupling expansion, while a 15 state model
which included the same 11 doublet states as in the singlet state model,
together with the lowest each of the ${}^{4}A_{1},^{4}B_{1},^{4}B_{2}$, and
${}^{4}A_{2}$ states was used in Eq. (4) for triplet symmetry close-coupling
expansion. As will be shown below, this procedure provides a reliable
scattering model which was tested by calculating the bound states of CH2.

Figure 1: Eigenphase sums for the overall $e+$ CH${{}_{2}}^{+}$ symmetries
${}^{1}A_{1}$ and ${}^{3}B_{1}$.

###  III.1 Bound states

Table 2 shows the vertical excitation energies for the bound states of CH2
form its X ${}^{3}B_{1}$ ground state to few of its low lying excited states.
For a comparison, we also did a quantum chemistry-style CI calculation on CH2
at its equilibrium geometry (C-H bond length 2.0314 a0 and H-C-H bond angle
133.8∘) using a $(1a_{1})^{2}~{}(2-6a_{1},1-4b_{1},1-4b_{2})^{6}$ CAS-CI
model. The vertical excitation energies are then compared with the multi
reference double excitation (MRD-CI) calculation of Romelt81  and the coupled
cluster results of Yama97 . Form Table 2, it is clear that the vertical
excitation energies obtained by the R-matrix method are in very good agreement
with all others. The fact that the calculated bound state energies are
consistent and accurate enough indicates that our scattering model is
reasonably good.

Figure 2: Cross sections for electronic excitation form the $X~{}^{2}A_{1}$
ground state to the first four excited states of doublet symmetry as given in
Table 1 and indicated in each panel.

###  III.2 Resonances at equilibrium

For resonance calculation, the R-matrix was propagated to 70 a0. Resonances
were detected by the characteristic change in sign of the second derivative of
the eigenphase sum $\delta(E)$ given by

$\delta(E)=\sum_{i}\arctan(K_{ii}),$ (5)

where $K_{ii}$ are the diagonal elements of the $K$ matrix. They were then
fitted to a Breit-Wigner profile Tennyson84  with an energy grid 0.005 eV to
obtain the resonance energy $E$ and width $\Gamma$.

Table 3: Resonance positions and widths (in Ryd) and effective quantum numbers at the CH${}_{2}^{+}$ equilibrium for states of ${}^{3}B_{1}$ and ${}^{1}A_{1}$ symmetry of the $e$-CH${}_{2}^{+}$ system below the first two CH${}_{2}^{+}$ excited states. Numbers within brackets indicate power of 10. Position | Width | $\nu$ | Position | Width | $\nu$
---|---|---|---|---|---
${}^{3}B_{1}$ symmetry |  |  |  |  |
Below $1~{}^{2}B_{1}$ state | Below $~{}^{4}A_{2}$ state
0.3558(-02) | 0.2400(-04) | 3.9466 | 0.1925 | 0.1075(-01) | 2.2792
0.4870(-02) | 0.5833(-04) | 3.9875 | 0.2678 | 0.3334(-03) | 2.9201
0.1567(-01) | 0.4765(-04) | 4.3815 | 0.2872 | 0.2789(-02) | 3.1980
0.1718(-01) | 0.6172(-04) | 4.4465 | 0.3034 | 0.1910(-03) | 3.5000
0.2685(-01) | 0.1503(-04) | 4.9440 | 0.3197 | 0.2426(-03) | 3.9143
${}^{1}A_{1}$ symmetry |  |  |  |  |
Below $1~{}^{2}B_{1}$ state | Below $1~{}^{2}A_{2}$ state
0.2034(-01) | 0.2198(-03) | 4.5925 | 0.3582 | 0.9116(-02) | 2.5716
0.3582(-01) | 0.1225(-03) | 5.5953 | 0.3907 | 0.2355(-02) | 2.9015
0.4478(-01) | 0.7510(-04) | 6.5969 | 0.4323 | 0.1280(-02) | 3.6009
0.5043(-01) | 0.4929(-04) | 7.5979 | 0.4424 | 0.2339(-02) | 3.8615
0.5423(-01) | 0.3407(-04) | 8.5985 | 0.4492 | 0.3074(-02) | 4.0762

Figure 1 shows the plot of two typical eigenphase sums for ${}^{1}A_{1}$ and
${}^{3}B_{1}$ symmetries. Characteristic of electron collision with ions, the
figure shows numerous resonances some of which are tabulated in Table 3
according to their parent state. As seen from the table, many of the
resonances appear to be in Rydberg series which can be identified by their
effective quantum numbers. The relatively small gap between the ground and
first excited electronic state means that the resonances start with relatively
high effective quantum numbers, $\nu\approx 4$, and then closely space.

A full set of fits to the resonances covering all overall scattering
symmetries is given in the supplementary material.

###  III.3 Electron impact excitation

Our calculated cross sections for electron impact excitation of CH${}_{2}^{+}$
from the ground state to four of its lowest doublet states are shown in Figure
2. As in the elastic cross section, the excitation cross sections show highly
resonant behaviour due to temporary captures into resonant states.
Particularly, the X ${}^{2}A_{1}\rightarrow~{}1~{}^{2}B_{1}$ excitation cross
section shows evidence of a large resonance near threshold. Referring to
Figure 1, this is likely due to the large ${}^{3}B_{1}$ resonance near 1 eV as
seen from the plot of the ${}^{3}B_{1}$ eigenphase sum. Generally, the
excitation cross sections decrease with increasing incident energy and the
cross sections from the higher lying excited states are much smaller.

Figure 3: Cross section for the electron impact dissociation of the
CH${}_{2}^{+}$ ion. Thin curve: present R-matrix results (see text). Thick
(red) curve: present result after smoothing with a Gaussian function. Green
circles with error bars: experimental results for C+ ion production Vane07 .
Blue circles with error bars: experimental results for CH+ ion production
Vane07 . Dashed curve: experimental results for C+ and CH+ ion production
summed after suitable fitting (see text).

###  III.4 Electron impact dissociation

Experimental cross sections for electron impact dissociation were obtained by
Vane07  for the production of CH+ and C+ fragments. Although model
calculations exist for the electron impact dissociation of CH${}_{2}^{+}$ ions
(see for example Reiter10 ), to the best of our knowledge, the 2007
experiments have never been described by any ab initio calculation.

The dissociation of CH${}_{2}^{+}$ into the lowest dissociation channels,
namely $e+$ CH+ \+ H and $e+$ C+ \+ H2, proceed via direct dissociative
excitation and have thresholds 6.08 eV and 5.62 eV respectively Vane07 . In
deriving the dissociation cross section, we assumed that electronic
excitations to all states above the respective dissociation thresholds lead to
dissociation. In our calculation, we have included the states 1 ${}^{2}B_{1}$,
1 ${}^{2}B_{2}$, 1 ${}^{2}A_{2}$, and the 2 ${}^{2}A_{2}$ excited states all
of which lie close to one another at the CH${}_{2}^{+}$ equilibrium. Moreover,
except the 1 ${}^{2}B_{1}$ state, which has both valence and Rydberg
character, all the other three are of valence character at equilibrium (see
for example TP91 ) and hence are likely to dissociate to the e+C++H2 (5.62 eV)
or the e+CH++H (6.08 eV) dissociation limits, which are the most relevant in
the energy range considered. Since the dissociation channels cannot be
separated in our calculations, our cross section in Figure 3 represents a sum
over these channels. For better comparison, we have also shown our cross
sections after smoothing by using a Gaussian function. The experimental data
from Vane07  are available for each of the dissociation channels mentioned
above. The energy grid of the experimental cross sections for these two
dissociation channels, however, are neither same nor uniform. Therefore, to
sum the experimental data, we first spline interpolated each set over the same
and uniform energy grid. This allowed us to sum the cross section for the
experimental data. In Figure 3, this sum is shown as the dashed line and it
agree fairly well with our computed cross section. In particular, the peak
near 8 eV agrees quite well with the spline interpolated summed experimental
curve. However, we note that since the experimental data is non uniformly
spaced, the interpolated curve may not often reflect the actual trend. For
example, we suspect the agreement of the interpolated curve with our
calculation would have been much better between 11 eV - 15 eV had there been
more experimental points available in this region. Similarly, below 6 eV the
interpolated experimental curve, appears to diverge for our Gaussian fitted
curve. This is a result of the fitting procedure, the interpolated
experimental curve actually follows the trend of our raw cross section curve.

##  IV Conclusion

As mentioned in the introduction, CH${}_{2}^{+}$ is a very important
constituent in low temperature plasma environments. However, despite its
importance, electron collisions studies on CH${}_{2}^{+}$ have been rare. In
fact, we could not find any ab initio calculation for the cross sections
included in the present work. The only cross section result available, seems
to be the total ionisation cross section of CH${}_{2}^{+}$ calculated within
the Binary-Encounter-Bethe (BEB) model by Irikura02 .

In this work, we have presented a reliable set of cross sections for the
electronic excitation, and electron impact dissociation of the CH${}_{2}^{+}$
ion. In fact, none of these cross sections have ever been reported before by
any ab initio calculation. Additionally, we have also calculated and have
given the position and width for some of the Feshbach resonances in the
e-CH${}_{2}^{+}$ system. These Feshbach resonances, as is well known, are the
routes to dissociative recombination of the CH${}_{2}^{+}$ ion. However, its
treatment requires a more comprehensive calculation of the resonance energies,
widths and the potential energy surfaces of the CH${}_{2}^{+}$ states. This is
the subject of an ongoing project.

## Acknowledgements

The authors acknowledge support from Fédération de Recherche Fusion par
Confinement Magétique (CNRS, CEA and Eurofusion), La Région Normandie, FEDER
and LabEx EMC3 via the projects PTOLEMEE, Bioengine, the Institute for Energy,
Propulsion and Environment (FR-IEPE),and ERASMUS-plus conventions between
Université Le Havre Normandie and University College London. We are indebted
to Agence Nationale de la Recherche (ANR) via the project MONA, Centre
National de la Recherche Scientifique via the Programme National ’Physique et
Chimie du Milieu Interstellaire’ (PCMI). JZsM thanks the financial support of
the National Research, Development and Innovation Fund of Hungary (NKFIH),
under the K18 and FK19 funding schemes with project no. K128621 and FK132989.
JZsM and IFS are grateful for the support of the
NKFIH–2019-2.1.11-TÉT-2020-00100 and Campus France-Programme Hubert
Curien–BALATON–46909PM projects.

## Data availability

Upon a reasonable request, the data supporting this article will be provided
by the corresponding author.

## References

  * (1) McLean A G, Elder J D, Stangeby P C, Allen S L, Boedo J A, Brooks N H, Fenstermacher M E, Groth M, Lisgo S, Nagy A, Rudakov D L, Wampler W R, Watkins J G, West W P, and Whyte D G 2005 J. Nucl. Materials 337-339, 124–128.
  * (2) Reiter D and Janev R K 2010 Contrib. Plasma Phys. 50, 986.
  * (3) Janev R K and Reiter D 2002a Phys. Plasmas 9, 4071.
  * (4) Janev R K and Reiter D 2002b Collision Processes of Hydrocarbon Species in Hydrogen Plasmas: I. The Methane Family (Available from: Forschungszentrum-Jülich, Jülich, Germany).
  * (5) Wakelam V, Smith I W M, Herbst E, Troe J, Geppert W, Linnartz H, K. Öberg, Roueff E, Agúndez M, Pernot P, Cuppen H M, Loison J C, and Talbi D 2010 Space Sci. Rev. 156, 13.
  * (6) Larson Å, Padellec A L, Semaniak J, Strömholm C, Larsson M, Rośen S, Peverall R, Danared H, Djuric N, Dunn G H, and Datz S 1998 The Astrophysical Journal 505, 459.
  * (7) IdBarkach T, Chabot M, Béroff K, Negra S D, Lesrel J, Geslin F, Padellec A L, Mahajan T, and Díaz-Tendero S 2019 Astron. Astrophys. 628, A75.
  * (8) Puglisi A, Miteva T, andJ Paul Mosnier E T K, Bizau J M, Cubaynes D, Sisourat N, and Carniato S 2018 Phys. Chem. Chem. Phys. 20, 4415.
  * (9) van Dishoeck E F, Beaerda R A, and van Hemert M C 1996 Astron. Astrophys. 307, 645.
  * (10) van Dishoeck E F, Jonkheid E F, and van Hemert M C 2006 Faraday Discuss. 133, 231.
  * (11) Lecointre J, Belic D S, Jureta J J, Janev R K, and Defrance P 2009 Euro. Phys. J D 55, 569.
  * (12) Vane C R, Bahati E M, Bannister M E, and Thomas R D 2007 Phys. Rev. A 75, 052715.
  * (13) Guo L, Ma H, Zhang L, Song Y, and Li Y 2018 Rsc. Adv. 8, 13635.
  * (14) Ma H, Zhang C, Song Y, Ma F, and Li Y 2021 J. Phys. Chem. A 125, 5490
  * (15) Kraemer W P, Jensen P, and Bunker P R 1994 Can. J. Phys. 72, 871.
  * (16) Li Y Q, Zhang P Y, and Han K L 2015 J. Chem. Phys. 142, 124302.
  * (17) Tennyson J and Sutcliffe B T 1983 J. Mol. Spectrosc. 101, 71.
  * (18) Theodorakopoulos G and Petsalakis I D 1991 J. Molec. Struct. (THEOCHEM) 230, 205.
  * (19) Bunker P R, Chan M C, Kraemer W P and Jensen P 2001 Chem. Phys. Lett. 341, 358.
  * (20) Jensen P, Wesolowski S S, Brinkmann N R, Richardson N A, Yamaguchi Y, Schaefer H F, and Bunker P R 2002 J. Mol. Spectrosc. 211, 254.
  * (21) Rösslein M, Gabrys C M, Jagod K F, and Oka T 1992 J. Mol. Spectrosc. 153, 738.
  * (22) Wang H, Neese C F, Morong C P, Kleshcheva M, and Oka T 2013 J. Phys. Chem. 117, 9908.
  * (23) Willitsch S and Merkt F 2003 J. Chem. Phys. 118, 2235.
  * (24) Chakrabarti K, Dora A, Ghosh R, Choudhury B S, and Tennyson J 2017 J. Phys. B: At. Mol. Opt. Phys. 50, 175202.
  * (25) Chakrabarti K, Ghosh R, and Choudhury B S 2019 J. Phys. B: At. Mol. Opt. Phys. 52, 105205.
  * (26) Chakrabarti K, Mezei J Z, Motapon O, Faure A, Dulieu O, Hassouni K, and Schneider I F 2018 J. Phys. B: At. Mol. Opt. Phys. 51, 104002.
  * (27) Ghosh R, Chakrabarti K, and Choudhury B S 2020 Plasma Sources Sci. Technol. 29, 095016.
  * (28) Tennyson J 2010 Phys. Rep. 491, 29–76.
  * (29) Burke P G 2011 R-Matrix Theory of Atomic Collisions Springer-Verlag:Heidelberg.
  * (30) Carr J M, Galiatsatos P G, Gorfinkiel J D, Harvey A G, Lysaght M A, Madden D, Mašín Z, Plummer M, Tennyson J, and Varambhia H N 2012 Euro. Phys. J. D 66, 58.
  * (31) Pritchard B P, Altarawy D, Didier B, Gibson T D, and Windus T L 2019 J. Chem. Inf. Model. 59, 4814.
  * (32) Graber T, Kanter E P, Vager Z, and Zajfman Z 1993 J. Chem. Phys. 98, 7725.
  * (33) Pople J A and Curtiss L A 1987 J. Phys. Chem 91, 155.
  * (34) Brinkmann N R, Richardson N A, Wesolowski S S, Yamaguchi Y, and Schaefer III H F 2002 Chem. Phys. Lett. 352, 505.
  * (35) Osmann G, Bunker P R, Kraemer W P and Jensen P 1999 Chem. Phys. Lett. 309, 299.
  * (36) Faure A, Gorfinkiel J D, Morgan L A, and Tennyson J 2002 Comput. Phys. Commun. 144, 224.
  * (37) Römelt J and Peyerimhoff D 1981 Chem. Phys. 54, 147.
  * (38) Yamaguchi Y and Shaeffer III H F 1997 J. Chem. Phys. 106, 1819.
  * (39) Noble C J and Nesbet R K 1984 Comput. Phys. Commun. 33, 399.
  * (40) Zhang R, Baluja K L, Franz J, and Tennyson J 2011 J. Phys. B: At. Mol. Opt. Phys. 44, 035203.
  * (41) Sarpal B K, Branchett S E, Tennyson J, and Morgan L A 1991 J. Phys. B: At. Mol. Opt. Phys. 24, 3685–99.
  * (42) Rabadán I and Tennyson J 1996 J. Phys. B: At. Mol. Opt. Phys. 29, 3747–61.
  * (43) Tennyson J and Noble C J 1984 Comput. Phys. Commun. 33, 421.
  * (44) Irikura K K, Kim Y K, and Ali M A 2002 J. Res. Natl. Inst. Stand. Technol. 107, 63.


# Growing Trees and Amoebas’ Replications

Vladimir Gurvich National Research University Higher School of Economics,
<EMAIL_ADDRESS>Matjaž Krnc FAMNIT and IAM, University of
Primorska<EMAIL_ADDRESS>Mikhail Vyalyi National Research University
Higher School of Economics; Moscow Institute of Physics and Technology;
Federal Research Center “Computer Science and Control” of the Russian Academy
of Science<EMAIL_ADDRESS>
###### Abstract

An amoeba is a tree with a number assigned to each vertex. We describe a
natural process of growing trees from a given amoeba and discuss conditions
for such a process to be finite.

##  1 Introduction

We describe a process of growing trees from an amoeba, which is a tree $H$
with a number assigned to each vertex. In a simplified language, this number
$m(v)$ tells how many extra edges we will require around a $v\in V(H)$. Given
a tree $T$ we look at a fixed copy $H^{\prime}$ of $H$ within $T$, and look
whether every $v\in V(H^{\prime})$ is incident with at least $m(v)$ edges
within $E(T)\setminus E(H^{\prime})$. If not, we attach the corresponding
number of pendent edges to $v$, increasing the size of $T$. A particularly
interesting question is whether such growth process can stop or go on forever.
This has relations to several known models:

#### String and graph generation models

are intensively studied in theoretical computer science, formal language
theory, and mathematical biology. There are many models of this sort: cellular
automata, rewriting systems, graph grammars etc. [13, 6, 10, 12]. In
particular, our model resembles graph relabelling systems with forbidden
contexts [12]. Most of graph generation models use labelling of graphs. In
contrast, we propose a simple rule of tree growth that governed by the
structure of subtrees and does not use labels on vertices and/or edges. The
resulting process is interesting from graph-theoretical point of view and
possibly might impact the area of graph generation models.

#### Galton-Watson process

is a foundational concept in the realm of probability theory, specifically in
the study of family trees and the dynamics of progeny within populations [7].
Introduced by Francis Galton and Henry Watson [3, 7], this stochastic process
serves as a mathematical model to examine the transmission of traits,
characteristics, or lineage through successive generations of families [7,
11]. The key idea revolves around the probability distribution of offspring
within a family, where individuals independently give rise to a random number
of descendants [7]. This model has proven particularly valuable in fields such
as genetics and demography [3], providing insights into the likelihood of
lineage continuation or extinction [7]. The Galton-Watson process remains an
essential tool for understanding the unpredictable nature of family structures
and the variability in the number of progeny across generations [11].

In contrast to the probabilistic nature of the Galton-Watson process, our
process represents a deterministic analog with a distinct feature—its
replication criteria are not dictated by a random probability distribution.
Instead, the expansion is orchestrated by the existence of a precisely chosen
subgraph within the existing tree, acting as a deterministic trigger for the
generation of additional leaves or progeny. This deterministic analog
introduces a structured and controlled element to the reproductive dynamics,
offering a unique perspective on how specific configurations within a family
lineage can influence and determine the proliferation of descendants. This
departure from stochastic randomness to a deterministic criterion opens up new
avenues for exploring the interplay between structure and growth of trees,
providing a nuanced understanding of the factors that contribute to the
perpetuation or divergence of lineages.

#### Avoidable paths

were studied in [9, 2, 1]. This concept was generalized further to the case of
arbitrary two-rooted graphs in [8] where the so-called _inherent graphs_ were
introduced. Verifying inherence is a difficult task. For example, it is not
known whether the path $P_{3}$ with edges $st$ and $tv$ is inherent provided
$s$, $t$ are the roots. Interestingly, this problem is related to the cops and
robbers game [5]. The paper [8] presents necessary conditions for inherence in
terms of a _pendant extension_ process, which extends a two-rooted graph by
pendant edges.

The process of growing trees from an amoeba generalizes the pendant extension
process. It might be useful for further generalizations of avoidability.

This paper is structured as follows. In the beginning of Section 2 we
introduce the main concepts of the paper, such as _amoeba_ , its _extension_ ,
_growth_ , _mortality_ and _confinement_. In Section 2.1 we relate mortality
and confinement conditions while in Section 2.2 we discuss relations between
the symmetries of the underlying graphs and the amoeba mortality. In Section 3
we focus on the mortality conditions for amoebas growing in a simplest way,
namely, by attaching pendant edges. We identify degree conditions which are
necessary for any such amoeba to be immortal in Section 3.1, while in Section
3.2 we describe the immortal amoebas whose underlying graph is a caterpillar.
We conclude the paper by Section 4, in which we propose some conjectures as
well as directions for future work.

##  2 Amoebas

An _ordinary amoeba_ 111This name was recently given to a different class of
graphs [4]. We think that these two classes can not be confused. $A=(T,m)$ is
defined as a pair consisting of a tree $T$, together with the _root function_
$m:V(T)\to\mathbb{N}$ mapping every vertex $v$ of $T$ to a non-negative
integer $m(v)$ called _multiplicity_ of $v$.

A vertex from $A$ of positive multiplicity is called a root of $A$.
Furthermore define $k(A)=\sum_{v\in V(H)}m(v)$.

If not stated otherwise, the amoebas discussed in this paper will always be
ordinary.

An _$\ell$ -extension of amoeba_ $(H,m)$ is a graph $G$ obtained from $H$ by
applying to each vertex $v$ the following procedure: take $m(v)$ disjoint
paths $P_{\ell+1}$ and identify one endpoint of each with $v$. The paths are
called _extension paths_.

A _copy of amoeba_ $(H,m)$ in a graph $G$ is an amoeba
$(H^{\prime},m^{\prime})$ where $H^{\prime}\leq G$, and $H\cong H^{\prime}$
such that the functions $m,m^{\prime}$ coincide under the corresponding
isomorphism. When no fear of ambiguity, we denote amoeba and its copy by the
same notation.

Let $A$ be a copy of an amoeba in a tree $G$. Then a _$\ell$ -growth_
$G^{\prime}$ of $A$ in $G$ is a tree containing both $G$ and an
$\ell$-extension of $A$ and having the minimal possible number of edges.

If, for a copy $A$ of an amoeba in graph $G$, all growths of $A$ in $G$
coincide with $G$, then the copy is called _dead_. Otherwise, the copy is
called _alive_.

Note that a copy of an amoeba may have non-isomorphic growths, see example in
Fig. 1.

Figure 1: Non-isomorhic 3-growths of the same copy of amoeba. The copy is
shadowed in grey, the new edge is dashed

For an amoeba $A=(H,m)$, a $\ell$-_growth sequence_ of $A$ starting at a tree
$T$ is a sequence of trees $T_{0},T_{1},\dots$ such that $T_{0}=T$ and
$T_{i+1}$ is a growth of a copy of $A$ in $T_{i}$, and $T_{i+1}\neq T_{i}$.

For an amoeba $A=(H,m)$, a $\ell$-_generation sequence_ of $A$ is a maximal
$\ell$-growth sequence starting at $H$.

If $\ell$ is clear from the context it will be omitted in notation for
extensions, growths, generation sequences etc.

Let $\ell$ be the extension parameter and $A$ be an amoeba. It is _immortal_
if it admits an infinite generation sequence, otherwise it is _mortal_. Amoeba
$A$ is _strongly immortal_ if all its generation sequences are infinite.
Amoeba $A$ is _partially immortal_ if it admits an infinite growth sequence.

A tree $T$ is _confining_ for an amoeba $A=(H,m)$ if it admits a copy of $A$
and all copies of $A$ in $T$ are dead.

An amoeba is _totally confined_ if for each tree $T$ containing a copy of $A$
there exists a confining tree $T^{\prime}$ containing a copy of $T$.

######  Remark 1.

Confining trees can be replaced by confining graphs. Totally confined amoebas
can be defined in this more general setting too.

######  Remark 2.

In [8], general two-rooted graphs are considered in the extension process.
Since attaching paths to a graph does not change its set of cycles, this
process is finite for non-trees. As we mainly study mortality, we restrict our
attention to the case of trees.

###  2.1 Initial observations

Note that a copy of an amoeba may have non-isomorphic growths, which make
things complicated. So, we start from study of this effect to show that it
appears for small amoebas (with respect to $\ell$) and in early members of
growth sequences. An example in Fig. 1 can not be seen in generation
sequences, as we will prove. It is caused by the minimality condition.

Let $T^{\prime}$ be an $\ell$-growth of a alive copy of an amoeba $A=(H,m)$ in
a tree $T$, and let $A^{\prime}$ be the corresponding extension of $A$
contained in $T^{\prime}$, and $P$ be a path $v_{0},v_{1},\dots,v_{\ell}$ of
the extension starting at a vertex $v_{0}$ such that
$\\{v_{\ell-1},v_{\ell}\\}\notin E(G)$. Take a connected component of the
forest $T^{\prime}-H$ containing $v_{1}$. It is a tree $T^{\prime\prime}$
rooted at $v_{1}$, which is called an _area_ of $P$. Due to the minimality
condition, the depth of $T^{\prime\prime}$ (the maximal length of a path from
the root to a leaf) is $\ell-1$. Moreover, $v_{1},\dots,v_{\ell}$ is a unique
path of length $\ell-1$ from the root $v_{1}$. Note that other edges in
$T^{\prime}$ are the edges of the original tree $T$. In this way we come to
the following conlusion.

######  Proposition 1.

An intersection of an area of an extension path and the original graph is a
tree of depth at most $\ell-1$.

Given a tree $T$ and its subtree $T^{\prime}$, there is a partial order on
$V(T)\setminus V(T^{\prime})$ defined as follows: $u\leq^{T^{\prime}}v$ if $u$
belongs to the path from $v$ to $T^{\prime}$. For each $v\in V(T)\setminus
V(T^{\prime})$ the set $\\{u:v\leq^{T^{\prime}}u\\}$ induces a tree
${\mathcal{I}}_{v}^{T^{\prime}}$ rooted at $v$. We omit the mentioning of
$T^{\prime}$ in the exponent when it is clear from context.

######  Lemma 2.

Let $T_{0},T_{1},\dots,T_{k}$ be an $\ell$-growth sequence for an amoeba
$A=(H,m)$ and $v\in V(T_{k})\setminus V(T_{0})$ such that
${\mathcal{I}}_{v}^{T_{0}}$ has the depth at most $\ell-1$. If for some vertex
$u$ in ${\mathcal{I}}_{v}^{T_{0}}$ there are two different paths $P$ and
$P^{\prime}$ of equal lengths from $u$ to a leaf, then

$\text{{diam}}(H)\leq 2\ell-4\ \text{and}\ \text{{diam}}(T_{0})\leq 2\ell-6.$

###### Proof.

W.l.o.g. we can assume that $P$ and $P^{\prime}$ have no common edges. Indeed,
otherwise we can change the vertex $u$ by the last common vertex of $P$ and
$P^{\prime}$. Choose the maximal $i$ such that at least one edge of $P\cup
P^{\prime}$ is not in $T_{i}$. W.l.o.g. we can assume that $e=(u_{0},u_{1})$
is the last edge of $P$ and $e$ is not in $T_{i}$. It means that $e$ is added
in a growth in $T_{i}$ of a copy $A=(H,m)$ of the amoeba. So an extension of
$A$ contains an extension path from a root $r$ of $A$ to $u_{1}$. We claim
that $u$ is not on the path from $r$ to $u_{1}$ that has no common edges with
$P^{\prime}$. Indeed, otherwise $P^{\prime}$ does not intersect $H$ and the
extension path can be changed to the path containing $P^{\prime}$,
contradicting the minimality condition, see Fig. 2(a). Also, $r$ is not on
$P$. Indeed, otherwise the extension should add more edges, since the length
of the whole path $P$ is less than $\ell$, see Fig. 2(b).

|
---|---
(a) | (b) $a<\ell$
|
(c) | (d)
Figure 2: Four ways of extension

In contrast, the next two options are possible and mutually exclusive:

  * vertices $u$, $u_{1}$, $r$ are end-points of paths starting at a vertex $w$, Fig. 2(c);

  * the path from $r$ to $u_{1}$ has a common edge with $P^{\prime}$, see Fig. 2(d).

In both cases $A$ is contained in the subtree rooted at $r$ since the path
from $r$ to $u_{1}$ has no common edges with $A$. This subtree is inside
${\mathcal{I}}^{T_{0}}_{u}$ so its depth is at most $\ell-2$, which implies
that the diameter of $H$ is at most $2\ell-4$. Also, any path starting at $r$
and containing $w$ and $u$ should has the length at most $\ell-1$, by the
minimality condition. Since $T_{i}$ contains $T_{0}$ and the path from $r$ to
$T_{0}$ has at least 3 edges, the diameter of $T_{0}$ is at most $2\ell-6$. ∎

Lemma 2 puts restrictions on extensions using ‘new’ edges only. Ambiguous
$\ell$-growths are possible in generation sequences even if $H$ has the
diameter at least $2\ell-6$. See example in Fig. 3.

|
---|---
|
Figure 3: An amoeba admitting ambiguous $3$-extensions in a generation
sequence

It is open if these three versions of immortality are equivalent.

Figure 4: An immortal amoeba with one root with respect to $2$-extensions.
Next step uses the left lower $P_{5}$ for extensions. Repetitions of the
process continue forever.

It is clear that the last tree in any generation sequence is confining. So
mortality implies the existence of confining tree. We do not know whether the
opposite is true. We are able to prove the opposite for the values of the
extension parameter $\ell\in\\{1,2\\}$.

######  Lemma 3.

For extension parameter $\ell\in\\{1,2\\}$, an amoeba is mortal if and only if
there exists a confining tree for it.

###### Proof.

In one direction it is obvious.

In other direction: take a confining tree and a copy of the amoeba. Start a
generation sequence from this copy. Note that $1$\- and $2$-growths of a copy
of the amoeba in any tree are isomorphic since in a rooted tree of depth $\leq
1$ all leaves belong to the same orbit of automorphisms of the tree. It
implies that at each step of extension new edges can be chosen from the
confining tree. Therefore the sequence is finite. ∎

######  Remark 3.

In general case, strong immortality implies immortality but the converse is
open. For the extension parameterr $\ell\in\\{1,2\\}$ the converse follows
from Lemma 3. If an amoeba is not strongly immortal then the last tree of its
finite generation sequence is a confining tree for the amoeba. Thus any its
generation sequence is finite.

In the proof of the next theorem we will use the notion of full $t$-ary tree
of depth $\ell$. To this end we denote by $T^{t,\ell}$ a tree where every node
on depth less than $\ell$ has $t$ children while every node on depth $\ell$ is
a leaf.

######  Theorem 4.

An amoeba is not partially immortal if and only if it is totally confined,
regardless of its extension parameter.

###### Proof.

Let $\ell$ be the extension parameter.

In one direction it is easy. Suppose an amoeba is not partially immortal. Take
a tree $T$ and any $\ell$-growth sequence $T=T_{0},\dots,T_{k}$ starting at
$T$. It is finite and the last tree $T_{k}$ in the sequence confines the
amoeba and contains $T$.

For the other direction, take a tree $T_{0}$ and a totally confined amoeba
$A=(H,m)$. Let $\delta=\max_{v\in V(H)}\big{(}d(v)+m(v)\big{)}$,
$d=\mathop{\mathrm{diam}}(T_{0})$. Choose a confining tree $T$ that contains a
full $\delta$-ary tree $T^{\delta,3\ell+2d}$ of sufficiently large depth, say,
$3\ell+2d$. Choose a copy of $T_{0}$ containing the center of
$T^{\delta,3\ell+2d}$. Start $\ell$-growth sequence $T_{0},T_{1},\dots$ from
this particular copy. If $\mathop{\mathrm{diam}}(T_{i})\leq 2\ell-6$ then any
copy of $A$ in it is at distance at most $2\ell-6$ from the center of
$T^{\delta,3\ell+2d}$. Thus any growth of $T_{i}$ can be embedded to $T$. If
an $\ell$-growth of $T_{i}$ uses edges of $T_{0}$, then the corresponding copy
of $A$ is at distance at most $2d$ from the center of $T^{\delta,3\ell+2d}$.
Thus, again, the growth can be embedded to $T$. If an $\ell$-growth of $T_{i}$
does not use edges of $T_{0}$ and $\mathop{\mathrm{diam}}(T_{i})>2\ell-6$,
then Lemma 2 implies that all such growths are isomorphic. So we apply the
same arguments as in the proof of Lemma 3 and conclude that $T_{i+1}$ can be
embedded in $T$. Therefore the sequence is finite. ∎

######  Conjecture 1.

Let $\ell$ be the extension parameter, let $A=(H,m)$ be an amoeba. If
$\Delta(H)>k(A)+2$ then $A$ is totally confined.

###  2.2 Orbit lemma

Fix an amoeba $A=(H,s_{1},\dots,s_{k})$. For a vertex $v\in V(H)$, we define
the _orbit_ of $v$, denoted by $\mathop{\mathrm{Orb}}(v)$, as the set of
vertices $w\in V(H)$ such that there exists an automorphism of $H$ mapping $v$
to $w$. The _completion_ $[A]$ of amoeba $A$ is defined as

$[A]=(H,m^{\prime}),\qquad
m^{\prime}(v)=\max_{w\in\mathop{\mathrm{Orb}}(v)}m(w).$

We call a pair of amoebas $A=(H,m)$ and $A^{\prime}=(H,m^{\prime})$
_equivalent_ (to each other) if $[A]=[A^{\prime}]$. Using this notation one
can easily obtain the following claim.

######  Lemma 5.

Let $\ell$ be the extension parameter and $A=(H,m)$ be an amoeba. If
$\ell\in\\{1,2\\}$ then $A$ is immortal if and only if its completion is.

For other values of $\ell$, an amoeba is partially immortal if and only if its
completion is.

###### Proof.

We start from the case $\ell\in\\{1,2\\}$. Suppose that the completion
$A^{\prime}$ of $A$ is mortal, that is, it admits a confining tree
$T^{\prime}$. It remains to observe that $T^{\prime}$ confines also $A$, so
$A$ is mortal by Lemma 3.

Now suppose by contradiction that $A$ is mortal and
$A^{\prime}=(H,m^{\prime})$ is not. Lemma 3 implies that there exists a
confining tree $T$ of $A$. Since $T$ does not confine $A^{\prime}$ there
exists a simplicial copy of $A^{\prime}$ in $T$, that is, for some vertex
$v\in V(H)$ it holds

$d_{T}(v)-d_{H}(v)\leq m^{\prime}(v).$

Since $m^{\prime}(v)=\max_{w\in\mathop{\mathrm{Orb}}(v)}m(w)$, there is a
vertex $w\in\mathop{\mathrm{Orb}}(v)$ such that $m(w)=m^{\prime}(v)$. Since
$v$ and $w$ are in the same orbit of $H$, there exists a copy of $A$ such that

$d_{T}(v)-d_{H}(v)\leq m(v),$

which contradicts the choice of $T$.

For $\ell>2$, similar arguments show that an amoeba is partially immortal if
and only if its completion is. The only difference is to use Theorem 4 instead
of Lemma 3. ∎

##  3 Case of $1$-extensions

Understanding the mortality of general amoebas seems to be very difficult. In
this section we focus on the mortality conditions for amoebas which grow in
the simplest of ways – by attaching pendant edges. In our notation such amoeba
growth corresponds to the case of $1$-extensions. In [8] authors show that for
the case $k(A)=2$, any immortal amoeba is necessarily subcubic. The following
subsection generalizes those results to the case of arbitrary $k(A)$.

###  3.1 Degree conditions

For the rest of this subsection fix an immortal amoeba $A=(H,m)$. Let
$(d(v),m(v))$, $v\in H$, be the sequence of vertex degrees and multiplicities
of the roots in $H$. We also define

$\tilde{d}(v)=d(v)+m(v)\qquad\text{and}\qquad m=\max_{v\in V(H)}\tilde{d}(v).$

Fix a $1$-generation sequence $G_{0},G_{1},\dots$. The immediate corollary of
minimality of $\ell$-generation is the following claim.

######  Claim 6.

If a vertex $v$ of $G_{i}$ is a root of a copy of the amoeba to be extended
and $d_{G_{i+1}}(v)>d_{G_{i}}(v)$ then $d_{G_{i}}(v)<\tilde{d}(v)$.

###### Proof.

If $d_{G_{i}}(v)\geq\tilde{d}(v)$ then an extension uses existing edges
incident to $v$ due to minimality condition. ∎

######  Corollary 7.

$d_{G_{i}}(v)\leq m$ for all $i$ and $v\in V(G_{i})$.

######  Corollary 8.

For all $i$ and sufficiently large $j$, vertices of a copy extending at step
$j$ do not intersect $V(G_{i})$.

These facts put restrictions on degrees of vertices in $H$. Recall that we add
pendant edges. So, initially a degree of a new vertex $v$ is 1. Then it can be
increased by extension of a copy having a root at $v$. Thus
$\min_{v:m(v)>0}d(v)=1$.

To catch the process of degree increasing, we introduce an auxiliary directed
graph $D$. The vertices of $D$ are positive integers up to $m$. A pair $(x,y)$
is an edge in $D$ if $y=d(v)+m(v)$ and $d(v)+m(v)>x\geq d(v)$ for some $v\in
V(H)$.

Let $q$ be the maximal integer reachable from 1 in $D$. By definition of $q$,
the inequality $q\leq m$ holds. For an immortal amoeba $m=d(v^{*})+m(v^{*})$
should be reachable because the degree $d(v^{*})$ should appear in some new
vertex (i.e. a vertex from $V(G_{i})\setminus V(G_{0})$) and all copies
containing this vertex at some moment have enough space for the extension.
This implies the following theorem.

######  Theorem 9.

Let $A=(H,m)$ be an immortal amoeba. Then

  1. 1.

$q=m$;

  2. 2.

$d_{H}(v)\leq m$ for all $v\in V(H)$.

######  Claim 10.

$m\leq 1+k$.

###### Proof.

Let $x_{1},x_{2},\dots,x_{t}$ be a directed path in $D$. By definition of $D$,
$x_{i}=d(v_{i})+m(v_{i})$ and $x_{i-1}\geq d(v_{i})$, for $i>1$. Then

$\displaystyle x_{1}\leq 1;$ $\displaystyle x_{2}=d(v_{2})+m(v_{2})\leq
1+m(v_{2});$ $\displaystyle\dots$ $\displaystyle x_{t}\leq
1+\sum_{j=2}^{t}m(v_{j})\leq 1+\sum_{v\in V(H)}m(v)=1+k.$

The last inequality follows from the fact that each $x_{j}$ can appear along
the path only once. ∎

######  Corollary 11.

Let $A=(H,m)$ be amoeba. If $\Delta(H)>1+k$, then $A$ is mortal.

######  Corollary 12.

Let $A=(H,m)$ be an immortal amoeba such that $k=1$. Then $\Delta(H)\leq 2$.

###  3.2 Mortality criteria for caterpillars

In this subsection a $1$-extension of a given amoeba will be referred to
simply as _extension_. Furthermore, throughout this section we assume that the
multiplicity function $m$ takes values $0$ and $1$ only. A _caterpillar_
$C(d_{1},d_{2},\dots,d_{\ell})$ is a tree constructed as follows. We start
with a _central path_ $P_{\ell}=(p_{1},\dots,p_{\ell})$, and afterwards, for
each $i\in\\{1,\dots,\ell\\}$, we add $d_{i}$ pendant vertices to $p_{i}$. In
addition, we require $d_{1}=d_{\ell}=0$. A caterpillar is said to be symmetric
if $d_{i}=d_{\ell-i+1}$, for all $i$. The family of amoebas $(H,m)$ where $H$
is a caterpillar and $m$ respects the above mentioned properties is denoted by
$\mathcal{A}$. In this section we characterize immortal amoebas from
$\mathcal{A}$.

######  Observation 13.

Let $H$ be a caterpillar with central path $P\subseteq V(H)$, and let
$A=(H,m)$ be an amoeba such that $\operatorname{supp}(m)\subseteq P$. An
extension of $A$ gives rise to a caterpillar.

Figure 5: A caterpillar $(C(0,2,2,3,0),m)$ and its extension $C(0,0,2,3,4,0)$.

###### Proof.

It is enough to observe that the central path of the obtained graph
corresponds to $P$, possibly with additional vertex on either endpoint of $P$
(also see fig. 5). ∎

We now give necessary and sufficient condition for an amoeba from
$\mathcal{A}$ to be shifted ”to the right”. But first we need some
definitions.

######  Definition 1 (of slow integer sequences).

Let $S=(d_{1},d_{2},\dots)$ be an integer sequence. We say that $S$ is

  * •

_slowly decreasing_ , if $d_{i}-d_{i-1}\geq-1$ for all $d_{i},d_{i-1}$;

  * •

_slowly increasing_ , if $d_{i}-d_{i-1}\leq 1$ for all $d_{i},d_{i-1}$;

  * •

_slow_ if it is either slowly increasing or slowly decreasing.

######  Definition 2 (of slow amoebas).

For an integer sequence $S$ let $(p_{1},\dots,p_{\ell})$ be the central path
of $C(S)$ and $(C(S),m)$ be an amoeba from $\mathcal{A}$. The amoeba
$(C(S),m)$ is said to be

  * •

_slowly decreasing_ if $S$ is slowly decreasing and the roots are placed at
$p_{i}$ whenever $d_{i}-d_{i-1}=-1$, and also in $p_{\ell}$;

  * •

_slowly increasing_ if $S$ is slowly decreasing and the roots are placed at
$p_{i-1}$ whenever $d_{i}-d_{i-1}=1$, and also in $p_{1}$;

  * •

_slow_ if it is either slowly increasing or slowly decreasing.

######  Theorem 14.

An amoeba $A\in\mathcal{A}$ is immortal if and only if $[A]$ is slow.

###### Proof.

Let $S=(d_{1},d_{2},\dots)$ be the degree sequence of the central path of
$[A]$. To prove the ‘if direction’ assume wlog that $[A]$ is slowly
decreasing. We define a sequence of graphs $\mathcal{G}=(G_{1},G_{2},\dots)$,
starting with $G_{1}=C(S)$. (Informally speaking, $\mathcal{G}$ is a sequence
of ”right shifts” of $[A]$.) Every member of this sequence is a caterpillar
graph, hence, the vertex notation (vertices $p_{1},\dots$) is well defined.

Within $G_{i}$ define a set of vertices $\mathcal{C}_{i}\subseteq V(G)$ as
$\mathcal{C}_{i}=\\{p_{i},\dots,p_{i+|S|}\\}$.

If $G_{i}$ admits a copy $H$ of $C(S)$ containing $\mathcal{C}_{i}$ then
$G_{i+1}$ is obtained from $G_{i}$ by extending $H$.

Due to Lemma 3 of the ‘if direction’ of the statement it is enough to prove
that $\mathcal{G}$ is infinite. Assume for contradiction that $\mathcal{G}$
has (a finite) length $k$. By definition $G_{1}=C(S)$ contains
$\mathcal{C}_{1}$, hence, $k\geq 2$.

Furthermore, $G_{k}$ does not admit a copy of $C(S)$ containing
$\mathcal{C}_{k}$. In other words, either

  1. (i)

there is an $i$ such that $d_{G_{k}}(p_{k+i})<d_{i}+2$ with $i<|S|$, or

  2. (ii)

$d_{G_{k}}(p_{k+i})<d_{i}+1$ with $i=|S|$.

Note that (ii) implies $d_{G_{k}}(p_{k+|S|})=0$ which is impossible. Let us
fix an $i$ satisfying (i).

By construction, there exists a copy $H$ of $C(S)$ in $G_{k-1}$ containing
$\mathcal{C}_{k-1}$ whose extension gives rise to $G_{k}$. By (i) we have
$d_{i}-d_{i-1}<0$, furthermore $d_{i}-d_{i-1}=-1$ since $S$ is slowly
decreasing. However, due to the extension of $[A]=(H,m^{\prime})$ in
$G_{k-1}$, we are guaranteed that $m^{\prime}(p_{k+i})>0$, and hence
$d_{G_{k}}(p_{k+i})-2\geq d_{i}$, which is a contradiction.

To prove the ‘only if direction’ of the claim assume that $[A]=(H,m^{\prime})$
is neither slowly increasing nor slowly decreasing. This can be due to one of
the following reasons. There exist:

  1. 1.

$i$ and $j$ such that $d_{i}-d_{i-1}<-1$ while $d_{j}-d_{j-1}>1$;

  2. 2.

$i$ and $j$ such that $d_{i}-d_{i-1}<-1$, and $d_{j}-d_{j-1}=1$ while
$p_{j-1}$ is not a root;

  3. 3.

$i$ and $j$ such that $d_{i}-d_{i-1}=-1$, and $d_{j}-d_{j-1}>1$ while $p_{i}$
is not a root;

  4. 4.

$i$ and $j$ such that $d_{i}-d_{i-1}=-1$ and $d_{j}-d_{j-1}=1$, while neither
$p_{i}$ nor $p_{j-1}$ are roots.

Consider the central path $(p_{1},\dots,p_{\ell})$ in an arbitrary copy of
$[A]$ in $G_{1}$. In all four above cases the following claim holds:

######  Lemma 15.

For all copies of $[A]$ in $G_{2}$, the sets $\\{p_{2},\dots,p_{\ell-1}\\}$
coincide.

###### Proof.

Indeed, any path of length $\ell-1$ in $G_{2}$ contains a pendant vertex
either from $V(G_{2})\setminus V(G_{1})$ or from $G_{1}$, and in the latter
case it is adjacent to either $p_{2}$ or $p_{\ell-1}$. In fact, the former
case of this alternative is possible only if the amoeba is slow. Otherwise,
one of the cases listed above holds. ∎

Denote by $(p^{\prime}_{1},\dots,p^{\prime}_{\ell})$ the vertices of $G_{2}$
which correspond to $(p_{1},\dots,p_{\ell})$ of $A$. By Lemma 15, for
$1<i\leq\ell$, we have that either

$p^{\prime}_{i}=p_{i-1},\text{ or}\quad p^{\prime}_{i}=p_{i},\text{ or}\quad
p^{\prime}_{i}=p_{\ell-i+1},\text{ or}\quad p^{\prime}_{i}=p_{\ell-i}.$

In all four cases, we obtain a contradiction with the vertex degrees’
conditions in $G_{2}$.

To finish the proof, take a copy $A^{\prime}$ of $[A]$ in $G_{2}$ such that
its central path contains a pendant vertex $v$ from $G_{1}$ adjacent to
$p_{\ell-1}$; the case when it is adjacent to $p_{2}$ is proved similarly. To
have enough room for $A^{\prime}$ to grow, we add one pendant edge to $v$
only. Notice that no new copies of $[A]$ appear, thus, $[A]$ is mortal, and
due to Lemma 5, so is $A$. ∎

##  4 Directions for future work

As announced in Section 2, we conjecture that the three notions of immortality
are equivalent.

######  Conjecture 2.

The following properties of an amoeba $A$ are equivalent:

  * •

$A$ is immortal.

  * •

$A$ is strongly immortal.

  * •

$A$ is partially immortal.

Deciding mortality looks hard (undecidable); perhaps one can model a general
Turing machine by amoebas. For this purpose a more general notion of an amoeba
colony might be useful. An amoeba colony is a set of ordinary amoebas
$\mathcal{C}=\\{A_{1},\dots,A_{n}\\}$. An _$\ell$ -growth_ $G^{\prime}$ of
$\mathcal{C}$ in $G$ is an $\ell$-growth of some $A_{i}\in\mathcal{C}$. The
remaining definitions are the same as for the case of ordinary amoebas. So, in
construction of $\ell$-growth sequence for an amoeba colony, one can choose an
alive amoeba to be extended. It gives more freedom and we conjecture that such
a process can simulate a universal computation.

######  Conjecture 3.

The following algorithmic problem is undecidable.

Input: an integer $\ell$, a tree $T$ and an amoeba colony $\mathcal{C}$.

Question: is there an infinite growth sequence for $\mathcal{C}$ starting from
$T$?

The following generalizations might be of independent interest.

A more general type of an extension of an amoeba is to attach to each vertex a
specified tree. A general-type amoeba is $(T,\pi)$, where $\pi$ is a _root
function_ from $V(T)$ to rooted trees (the empty tree is allowed). All other
definitions are naturally extended to the case of general-type amoebas.

A general-type amoeba is called _absolutely mortal_ if it is mortal for any
root function $\pi$. Characterization of absolutely mortal amoebas is an
interesting open question in this area.

Another way of generalization is to substitute trees by arbitrary graphs,
possibly disconnected. We know a little about this general problem. But it
also seems to be interesting.

As already mentioned in Remark 1, we can extend the definition of confining
trees to general graphs. This would naturally generalize the concept of
totally confined amoebas. From our previous results [8] it follows that there
exist amoebas which do not admit confining trees but can be confined by a
general graph. For various amoebas, the confining graphs are cages: Petersen
graph, Heawood graph, McGee graph, Tutte–Coxeter graph. The confinement of
general amoebas might lead to interesting results about cages and other graphs
having rich structure.

#### Acknowledgements.

Authors are grateful to Prof. Martin Milanič for valuable discussions and
observations.

This research was partially prepared within the framework of the HSE
University Basic Research Program. This work is supported in part by the
Slovenian Research Agency (research program P1-0383 and research projects
N1-0160, N1-0209, J1-3003, J1-4008 and J5-4596).

## References

  * [1] Jesse Beisegel, Maria Chudnovsky, Vladimir Gurvich, Martin Milanič, and Mary Servatius.  Avoidable vertices and edges in graphs: Existence, characterization, and applications.  Discrete Appl. Math., 309:285–300, 2022.
  * [2] Marthe Bonamy, Oscar Defrain, Meike Hatzel, and Jocelyn Thiebaut.  Avoidable paths in graphs.  Electron. J. Combin., 27(4):Paper No. 4.46, 9, 2020.
  * [3] F. Thomas Bruss.  Galton-Watson processes and their role as building blocks for branching processes, 2021.
  * [4] Yair Caro, Adriana Hansberg, and Amanda Montejano.  Graphs isomorphisms under edge-replacements and the family of amoebas.  Electron. J. Comb., 30(3), 2023.
  * [5] Maria Chudnovsky, Irena Penev, Alex Scott, and Nicolas Trotignon.  Substitution and $\chi$-boundedness.  J. Combin. Theory Ser. B, 103(5):567–586, 2013.
  * [6] Nachum Dershowitz and Jean-Pierre Jouannaud.  Rewrite systems.  In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics, pages 243–320. Elsevier and MIT Press, 1990.
  * [7] Moez Draief and Laurent Massoulié.  Galton–Watson branching processes, page 7–18.  London Mathematical Society Lecture Note Series. Cambridge University Press, 2009.
  * [8] Vladimir Gurvich, Matjaž Krnc, Martin Milanič, and Mikhail Vyalyi.  Avoidability beyond paths, 2023.  arXiv:2208.12803v2.
  * [9] Vladimir Gurvich, Matjaž Krnc, Martin Milanič, and Mikhail Vyalyi.  Shifting paths to avoidable ones.  J. Graph Theory, 100(1):69–83, 2022.
  * [10] Aristid Lindenmayer.  Mathematical models for cellular interactions in development I. Filaments with one-sided inputs.  Journal of Theoretical Biology, 18(3):280–299, 1968.
  * [11] K. V. Mitov and N. M. Yanev.  Critical Galton–Watson processes by decreasing state-dependent immigration.  Journal of Applied Probability, 21(1):22–39, 1984.
  * [12] Grzegorz Rozenberg, editor.  Handbook of Graph Grammars and Computing by Graph Transformations, Vol. 1-3.  World Scientific, 1997.
  * [13] Stephen Wolfram.  A New Kind of Science.  Wolfram Media, May 2002.


# RTSDF: Real-time Signed Distance Fields for Soft Shadow Approximation in
Games

Yu Wei Tan  , Nicholas Chua, Clarence Koh and Anand Bhojan
School of Computing, National University of Singapore, Singapore
{yuwei, nicholaschuayunzhi<EMAIL_ADDRESS><EMAIL_ADDRESS>
https://orcid.org/0000-0002-7972-2828 https://orcid.org/0000-0001-8105-1739

###### Abstract

Signed distance fields (SDFs) are a form of surface representation widely used
in computer graphics, having applications in rendering, collision detection
and modelling. In interactive media such as games, high-resolution SDFs are
commonly produced offline and subsequently loaded into the application,
representing rigid meshes only. This work develops a novel technique that
combines jump flooding and ray tracing to generate approximate SDFs in real-
time. Our approach can produce relatively accurate scene representation for
rendering soft shadows while maintaining interactive frame rates. We extend
our previous work with details on the design and implementation as well as
visual quality and performance evaluation of the technique.

##  1 INTRODUCTION

Signed distance fields (SDFs) are scalar fields that store the shortest
distance between a point in space to a model. Their sign indicates if that
point is inside or outside the bounds of said model. In interactive media,
models are most commonly represented by triangle meshes. SDFs are typically
generated offline through ray tracing and scan conversion etc., limiting their
use to rigid meshes. While existing real-time GPU-based methods can update
SDFs per frame, they are unable to handle high resolutions efficiently.

We present a novel SDF method that integrates jump flooding and ray tracing to
generate an approximate real-time SDF (RTSDF) of reasonably high quality for a
fixed small scene. Additionally, we evaluate the technique by applying it to
raymarched soft shadow approximation, offering trade-offs between speed and
quality for real-time application requirements. This paper extends our
previous work (Tan et al.,, 2020) with a detailed analysis of the design,
implementation and evaluation of the technique.

##  2 DESIGN

As shown in Figure 1, jump flooding produces a fast approximation of the SDF
which allows for real-time calculation. Conversely, ray tracing gives a more
accurate scene representation as it queries the hardware-generated triangle
mesh and slowly converges. Hence, we propose a real-time SDF that combines the
speed of jump flooding with the precision of ray tracing. We first perform an
initial jump flooding which creates an SDF of the voxelized scene. Next, we
use the voxelized SDF as a mask to decide where to attempt ray tracing on the
triangle mesh for more accurate scene representation. Naturally, we choose
locations closer to surfaces to ray trace and fall back on the distances
generated by jump flooding in empty regions. Our technique is built on
NVIDIA’s Falcor library (Benty et al.,, 2020) which provides an abstraction
over the graphics API for our implementation.

(a) Jump flooded SDF (b) Ray-traced SDF

Figure 1: Soft shadows from SDF raymarching.

###  2.1 Ray Tracing

The basic implementation of an SDF is a uniform grid where the discrete points
in the scalar field are stored as a 3D texture (Wright,, 2015). Uniform grids
are easy to implement and allow us to perform hardware interpolation of
neighbouring points, making sampling efficient. A brute force approach to
generate uniform SDF is ray sampling (Wright,, 2015).

For each discrete point in the distance field, we shoot rays in random
directions to query the distance to the closest mesh. To calculate the
direction, we randomly generate a point on the surface of a sphere with a
uniform distribution (Weisstein,, 2019). The minimum distance traced for each
point is stored in the red channel of a $400\times 200\times 400$ 3D texture.
Rays traced in future frames will overwrite the value if the newer value is
smaller. To determine the sign, we first check if it is a front or back face
hit via the dot product of the ray direction and normal of the primitive
intersected. We then accumulate the number of front and back face hits in the
green and blue channels of the texture. Finally, we set the sign to negative
if the majority of hits are back face hits (Wright,, 2015).

###  2.2 Jump Flooding

The jump flooding algorithm (JFA) (Rong and Tan,, 2006) which can be run on
parallel on the GPU allows us to generate an approximate SDF in real-time. We
first initialize a 3D SDF texture where each texel represents a 3D point or a
grid point. JFA gives us information about the closest seed at any point in
space. Setting every point on each triangle in the mesh as a seed, we can
obtain the closest distance to a surface for our distance field. To determine
if a grid point contains a triangle efficiently, we voxelize the scene with
voxel resolution equal to our final distance field. After voxelization, we
simply check if a grid point contains a model voxel to determine if it is a
seed.

We now have a 3D texture containing grid points that are either empty or are
seeds. Without loss of generality, we assume that the dimensions of the 3D
texture are equal (i.e. 3D cube) and that its length $n$ is a power of 2. For
each grid point, we query a constant number of neighbouring grid points a
predefined offset away. For each query, if the queried grid point is a seed or
contains seed information, we check if that seed is closer to its currently
stored seed and update its seed information if so. We start with an offset of
length $\frac{n}{2}$ and halve it for each subsequent iteration until it
reaches 1 for our final iteration.

With current GPUs that can write to 3D textures, we adapt the 2D JFA algorithm
(Rong and Tan,, 2006) for 3D space. During a single iteration, we run the
querying in parallel, allowing us to use the GPU to accelerate the
calculations. However, the algorithm produces an unsigned distance field. To
determine the sign, we subtract a small $\beta$ from the distance field,
causing surface points to be of negative value and effectively thickening the
surface. The surfaces generated are also hollow as they contain positive
values in their interior. With jump flooding, we can generate an approximate
SDF in real-time for a decently large resolution of $256^{3}$ at 30ms and
$128^{3}$ at 2.34ms.

###  2.3 Ray Mask

We obtain a rough approximation of the SDF or _coarse_ SDF via jump flooding
to locate regions in the scene to apply ray tracing. In raymarching, regions
far from the surface act as a way to accelerate the process but closer regions
require a more accurate surface representation. Hence, we can detect regions
closer to surfaces based on a distance $d$ from the _coarse_ SDF and only ray
trace in these regions at a higher resolution for better surface
representation. Essentially, the _coarse_ SDF is a ray mask that determines
which areas in the SDF should be ray-traced to generate a _fine_ SDF as shown
in Figure 2. $d$ can be used to trade-off performance for accuracy where a
larger $d$ results in more rays traced as texels further from surfaces would
be within $d$ distance from a surface point.

(a) _Coarse_ SDF (b) _Fine_ SDF

Figure 2: Slice of SDF.

Unlike adaptively sampled fields which increase the resolution at regions with
finer details, we limit the number of levels of detail to two as generation of
hierarchical SDF is difficult to parallelize (Liu and Kim,, 2014).
Additionally, real-time traversal of the SDF may require multiple texture
lookups to sample until the leaf node despite saving space with a sparse voxel
texture (Aaltonen,, 2018).

With the combination of the techniques, we turn a blocky representation of the
scene into a more refined triangle mesh representation without ray tracing
every texel in the SDF as shown in Figure 3. Additionally, we can resolve
issues identified in the jump flooding of voxelization of thin surfaces. As
seen in Figure 4, while the _coarse_ SDF gets a disconnected representation of
the plant, we fill in the holes through refinement with the ray trace pass.

(a) _Coarse_ SDF (b) _Fine_ SDF

Figure 3: Precision.

(a) _Coarse_ SDF (b) _Fine_ SDF

Figure 4: Holes.

###  2.4 Raymarching

While SDFs are surface representations, they only provide proximity
information without a direction. To perform ray casting on an SDF, we can find
the intersection with raymarching. The SDF value shows the safest possible
distance we can move along the ray without missing any potential
intersections. Hence, given a ray origin and direction, we can query the SDF
at safe points along the ray and terminate if the distance field returns a
value less than or equal to 0, signalling that we have reached a surface
point.

This raymarching algorithm, also known as sphere tracing (Hart,, 1996), does
not account for no intersection and could potentially iterate indefinitely in
practice. A simple solution would be to terminate if the raymarched distance
exceeds the bounds of the queried scene. More commonly, we can set a maximum
number of iterations to perform and return no intersection if the limit is
reached, ensuring consistent execution time for interactive rendering.
Additionally, as the raymarch count approaches $\infty$, we are marching
closer to a surface but will never reach it, potentially making the algorithm
run indefinitely. Hence, we could terminate the algorithm if the closest
distance to a surface is lower than some $\epsilon$.

SDFs are used to calculate dynamic occlusion in rendering like for area light
shadow approximation as in Wright, (2015). Considering direct illumination of
the area light source alone, we can reform the rendering equation as explained
in Dutré et al., (2004). Wright, (2015) uses raymarching of SDFs to
approximate the visibility term for the entire area light source.

With ray tracing, we can only get the intersection point with the surface.
However, we can also know the closest it got to intersecting an object with
raymarching. To get this information with ray tracing, we need to shoot
multiple rays within a cone which is more accurate but too inefficient for
real-time.

###  2.5 Correcting Artifacts

####  2.5.1 Ghosting

While the _fine_ SDF generated is comparable to full ray sampling, it uses
temporal accumulation to converge to the final distance field. Consequently,
when a moving object is introduced in the scene, its surface ghosts as shown
in Figure 5 because the area it leaves is not invalidated as the closest
distance.

Figure 5: Ghosting of circular-moving teapot.

(a) $128^{3}$ _coarse_ SDF input (b) $x$ = 1 (c) $x$ = 5 (d) $x$ = 10

Figure 6: _Fine_ SDF result.

As such, each texel in the SDF must be recalculated every frame. However, to
get stable results, the number of rays $x$ shot per frame must be
substantially high. Otherwise, it will result in noisy SDF as shown in Figure
6 due to random sampling - in each frame, there is a chance we might not hit
the closest surface. Conversely, the value of $x$ is restricted by the
computational cost of ray tracing. As a compromise, we spread our effective
rays shot over multiple frames with temporal accumulation of the SDF but apply
a decay factor to the distance field in the previous frame to minimize
ghosting as shown in Equation 1.

$f_{t}=\begin{cases}\min(\alpha\cdot f_{t-1}+(1-\alpha)\cdot
c_{t},r_{t}),&\text{for }c_{t}\leq d\\\ c_{t},&\text{for }c_{t}>d\end{cases}$
(1)

Let $f_{t}$, $c_{t}$ and $r_{t}$ be the _fine_ SDF, _coarse_ SDF and the
shortest distance generated from ray sampling respectively at frame $t$.
$\alpha$ refers to the decay factor for the previous frame. Note that we
eliminate any form of ghosting for $c_{t}>d$ as we use $c_{t}$, the jump
flooded SDF that is newly calculated every frame. To perform jump flooding
every frame, the _coarse_ SDF is set to $128^{3}$ while the _fine_ SDF is at a
resolution of $256^{3}$. Our testing found an $\alpha$ of 0.95 and $d$ of 0.1
provides a good qualitative result which minimizes ghosting of moving
surfaces.

####  2.5.2 Banding

Banding artifacts come from the low resolution of the SDF for real-time
optimization. They appear along the penumbra of shadows, causing alternating
regions of high and low occlusion as shown in Figure 7.

(a) Before triangulation (b) After triangulation (c) After triangulation and
max. step size

Figure 7: Banding from low resolution SDF.

We reduce some of the banding by approximating the occlusion according to
Aaltonen, (2018). From Figure 8, given two raymarch samples $D$ and $D_{-1}$,
we can triangulate to calculate an approximation of the SDF at $E$ which would
have contributed to a higher occlusion than both samples.

Figure 8: Approximation of occlusion with triangulation. Source: Aaltonen,
(2018).

To ensure that neighbouring pixels have similar raymarch samples, we also
restrict the maximum step size of our raymarching to 0.05 to remove the
banding. However, a consequence would be an increase in texture samples (128
in this case) required to calculate occlusion so we are looking into finding a
better compromise. Nonetheless, we achieve a smooth penumbra for now, as
expected of a soft shadow.

Lastly, due to the fixed step size, there is also an obvious pattern when
shadows are parallel to the light direction. We remove this sampling artifact
by jittering the offset of the ray so that we move our ray sample slightly
along the light direction. We then apply a temporal anti-aliasing (TAA)
(Karis,, 2014) pass to remove any noise in the final image for a smooth
gradient as shown in Figure 9.

(a) Before TAA (b) After TAA

Figure 9: Banding from fixed step size.

####  2.5.3 Holes

Holes in our SDFs are observable from the shadow of objects with thin surfaces
like in Figure 10 due to the low resolution of the SDF. Increasing the
resolution to 500 $\times$ 500 $\times$ 500 only reduces the size of the holes
but does not eliminate them, and results in a poor rendering performance of
70ms. Consequently, we add a bias of 0.01 to our SDF to thicken surfaces. With
this change, we compromise the accuracy of the surface representation for
cleaner shadows.

(a) Low resolution (b) High resolution

Figure 10: Holes in SDF. Figure 11: Holes in umbra.

Another artifact comes from the $\epsilon$ of our raymarching technique.
$\epsilon$ must be minimally one voxel size to avoid self-occlusion. However,
the ray steps through thin surfaces entirely due to the large $\epsilon$
arising from our low-resolution distance field, appearing as holes in the
shadow umbra as shown in Figure 11. A solution is to combine our soft shadow
technique with a classic hard shadow approach like Cascaded Shadow Maps (CSM)
(Engel,, 2006) which can achieve the shadow umbra.

##  3 RESULTS

We test our RTSDF technique by generating raymarched soft shadows and
comparing them with the shadows produced by shadow mapping and ground truth
distributed ray tracing (Cook et al.,, 1984). Our shadow map implementation
makes use of the CSM and Exponential Variance Shadow Maps (EVSM) (Lauritzen
and McCool,, 2008) filtering sample provided by Falcor. We perform our
evaluation on The Modern Living Room (Wig42,, 2014) with dynamic objects and
TAA.

###  3.1 Performance

The measurements here are taken with the Falcor profiling tool on an Intel
Core i7-8700K CPU at 16GB RAM with an NVIDIA GeForce RTX 2080 Ti GPU.

####  3.1.1 Comparison with Shadow Mapping

We evaluate the performance of RTSDF with one directional light as shown in
Table 1. Without extensive optimizations on the Falcor API and Direct3D level,
we are already achieving relatively interactive frame rates and pass
durations. In comparison, shadow mapping has a frame rate of 241 fps, but it
is expected that our method is slower because of our additional SDF generation
and raymarching processes. We are also using additional abstractions and
wrappers provided by Wyman, (2018) for ease of implementation.

Table 1: RTSDF pass durations (ms) and frame rate. Passes | Processor | Duration
---|---|---
| CPU | 0.29
G-Buffer | GPU | 1.05
| CPU | 0.63
Voxelization (V) | GPU | 0.93
| CPU | 0.06
Jump Flood (JF) | GPU | 2.09
| CPU | 1.05
Ray Trace (RT) | GPU | 4.60
| CPU | 0.11
Deferred Lighting (DL) | GPU | 1.28
| CPU | 7.42
Others | GPU | 0.27
| CPU | 9.56
Total Duration | GPU | 10.22
Frame Rate | 97

####  3.1.2 SDF Resolution

We compare the increasing size of our SDF and record the GPU timings for the
SDF generation passes and final deferred lighting computation on three lights
at different resolutions specified in Table 2.

Table 2: Resolution for different SDF sizes. Resolution |  _Coarse_ SDF |  _Fine_ SDF
---|---|---
Small (S) | $64^{3}$ | $128^{3}$
Medium (M) | $128^{3}$ | $256^{3}$
Large (L) | $256^{3}$ | $512^{3}$

As seen in Table 3, the duration of jump flooding becomes much higher with
increasing SDF resolution, as there are more dispatch calls when executing the
compute shader as well as reduced GPU cache locality when reading and writing
to a much larger 3D texture. Jump flooding for $256^{3}$ _coarse_ SDF costs
21.89ms which results in a frame rate of lower than 60 frames per second.
Consequently, we note that with current optimizations applied to jump
flooding, we are limited to $128^{3}$ resolution. Nonetheless, with a lower
_fine_ SDF resolution of $256^{3}$, we can afford to shoot more rays per texel
which improves the stability of the distance field generated.

Table 3: GPU timings of passes (ms). Size | $x$ | 0 | 1 | 5 | 10
---|---|---|---|---|---
| S | 0.49 | 0.49 | 0.49 | 0.49
| M | 0.49 | 0.49 | 0.49 | 0.49
V | L | 1.12 | 1.12 | 1.12 | 1.12
| S | 0.28 | 0.28 | 0.28 | 0.28
| M | 2.37 | 2.37 | 2.37 | 2.37
JF | L | 21.89 | 21.89 | 21.89 | 21.89
| S | 0.14 | 0.16 | 0.71 | 1.41
| M | 0.55 | 1.41 | 4.51 | 8.36
RT | L | 3.98 | 9.12 | 26.56 | 48.32
| S | 3.17 | 3.17 | 3.17 | 3.17
| M | 3.17 | 3.17 | 3.17 | 3.17
DL | L | 7.32 | 7.32 | 7.32 | 7.32

However, at $64^{3}$, the jump flooding is unable to capture some surfaces of
thin objects as seen in Figure 12 where the plant’s shadow is disjointed and
incomplete. Increasing the ray count gives little noticeable improvement as
the ray mask is too small.

(a) S (b) M (c) L

Figure 12: Thin object shadows.

####  3.1.3 Ray Mask Size

We measure the effect of distance $d$ which determines the size of the ray
mask in Table 4. Here, $d$ = $\infty$ corresponds to the case where every
texel in the _fine_ SDF is ray-traced. As shown in Figure 13, there are
noticeable holes in the SDF for $d$ = 0.05 as the low resolution of the
_coarse_ SDF makes it difficult to voxelize thin surfaces. Increasing $d$ to
0.1 fills up the missing holes as we use a more aggressive ray mask which can
detect the thin surfaces. However, there is less qualitative difference from
$d$ = 0.1 to $d$ = 0.5. Weighing it against the decrease in performance, it
appears that $d$ = 0.1 is most suitable for the shot.

Table 4: Size M SDF GPU timings (ms). $x$ $d$ | 0.01 | 0.05 | 0.1 | 0.5 | $\infty$
---|---|---|---|---|---
1 | 0.8 | 1.28 | 1.63 | 3.12 | 4.08
5 | 1.43 | 3.17 | 4.82 | 11.71 | 16.15
10 | 2.18 | 5.41 | 8.36 | 22.25 | 30.69
15 | 3.17 | 7.7 | 12.42 | 32.7 | 46.0

(a) $d$ = 0.05 (b) $d$ = 0.1 (c) $d$ = 0.5

Figure 13: Thin surfaces.

###  3.2 Graphics Quality

We compare the smoothness of the soft shadow penumbra generated with our
approach against shadow mapping as well as the ground truth as shown in Figure
14 with one directional light. RTSDF generates a plausible penumbra while the
penumbra from shadow mapping is hardly visible. For shadow mapping, a 15px
$\times$ 15px kernel was used to generate soft shadows by blurring with EVSM
filtering. It could be the case that the shadow map resolution is too low in
the foreground for better quality penumbra. We manage to recreate the details
of the penumbra more clearly such that it is closer to the distributed ray
tracing reference. Our penumbra appears to be larger than the ground truth as
a result of adding the small bias in Section 2.5.3 to prevent holes in thin
surfaces.

(a) Shadow Map (b) RTSDF (c) Distributed RT

Figure 14: Penumbra.

###  3.3 Limitations

Due to a small amount of ghosting of the SDF, our rays shot towards the light
source may intersect with the ghosted surface representation of the object.
This results in incorrectly occluded areas such as the top of the teapot in
Figure 15. For static regions, this artifact would not be present.

Figure 15: Self intersection of moving teapot.

Though not a focus of the paper, a key thing to note is also the accuracy of
the shadows. Our soft shadow algorithm widens the penumbra and does not
accurately calculate umbra as shown in Figure 16. On the left, for the ground
truth, we shoot multiple visibility rays towards the area light source and
hence have an occlusion factor of more than 0. However, for the SDF
raymarching estimation, we raymarch a single ray towards the centre of the
light source and record an occlusion factor of 0. Consequently, this technique
is referred to as penumbra widening shadows by Aaltonen, (2018).

Figure 16: Reference (left) vs penumbra estimation (right).

This becomes noticeable as we increase the radius of our area light source,
and accompanied by the increased thickness of the surface representation
causes our shadows to substantially thicken and darken. More research could be
done to investigate potential ways to calculate the shadow umbra given an SDF
to achieve less noisy results than a ray trace counterpart. For example, as
shown in Figure 17, we could perform random sampling towards the light and
weight the occlusion factor based on the distance to the closest object along
the ray towards the light.

(a) RTSDF (b) Ray Trace (1 per frame) (c) Distributed Ray Trace (d) SDF-
Simulated Umbra

Figure 17: Umbra.

###  3.4 Future Work

####  3.4.1 SDF

Currently, the setup is fine-tuned for a small simple scene. However, it gets
more complex when accounting for larger scenes. Having a single SDF for the
entire scene is not feasible due to the memory and computation requirements to
get a good resolution per $m^{3}$ of the scene. A potential strategy would be
to have a clip map explained by Panteleev, (2014), with multiple resolutions
based on the camera’s position and view direction. In regions outside of the
camera’s view frustum, a lower resolution SDF can be calculated which would
reduce the cost of rendering. Furthermore, these regions could potentially use
only jump flooding instead of adding ray tracing.

As of the date of submission, the acceleration structures generated by the GPU
drivers which support the DirectX Raytracing API are not accessible in code.
They are bounding volume hierarchies that are used for ray tracing and the API
exposed only allows for ray tracing queries. As noted by Quilez, (2019),
proximity information can be queried from the acceleration structures and
potentially be used for rendering effects. These structures could also help
aid better reconstruction of the SDF.

####  3.4.2 Soft Shadows

Currently, we apply TAA to reduce noise in the image as shown in Figure 18.
However, noise is not eliminated. We could adopt ideas from existing
techniques such as spatiotemporal variance-guided filtering (Schied et al.,,
2017) which uses screen space blurs and temporal accumulation to remove noise
from path tracing samples. With more intelligent filtering of the final
result, we could potentially get away with a larger raymarch step introduced
to remove banding artifacts and improve performance.

(a) Before TAA (b) After TAA

Figure 18: Noise.

Raymarching is an expensive operation given the required number of samples per
pixel. We could also optimize this by combining our soft shadows with a shadow
map pass where we decide to raymarch only if not in shadow.

While not explored, we note that since we have an SDF approximation of the
scene, there is the potential of representing translucent surfaces to generate
translucent soft shadows. The main initial difficulty would be identifying the
surface intersected when raymarching a distance field. We could potentially
store surface information in the distance field and perform optimization by
using lookup tables.

##  4 CONCLUSION

We developed a novel technique that combines jump flooding and ray tracing to
generate SDFs in real-time with plausible results for soft shadowing and
exposed values that trade-off between performance and quality of the SDF
generated which would be useful when targeting hardware of different
specifications. Our approach can handle scenes with dynamic objects and
produce penumbra that is smoother than shadow mapping but cleaner than
distributed ray tracing.

## ACKNOWLEDGEMENTS

We thank Wyman, (2018) for the Falcor scene file of The Modern Living Room (CC
BY). This work is supported by the Singapore Ministry of Education Academic
Research grant T1 251RES1812, “Dynamic Hybrid Real-time Rendering with
Hardware Accelerated Ray-tracing and Rasterization for Interactive
Applications”.

## REFERENCES

  * Aaltonen, (2018) Aaltonen, S. (2018).  Advanced graphics techniques tutorial: Gpu-based clay simulation and ray-tracing tech in ’claybook’.
  * Benty et al., (2020) Benty, N., Yao, K.-H., Clarberg, P., Chen, L., Kallweit, S., Foley, T., Oakes, M., Lavelle, C., and Wyman, C. (2020).  The Falcor rendering framework.
  * Cook et al., (1984) Cook, R. L., Porter, T., and Carpenter, L. (1984).  Distributed ray tracing.  SIGGRAPH Comput. Graph., 18(3):137–145.
  * Dutré et al., (2004) Dutré, P., Jensen, H. W., Arvo, J., Bala, K., Bekaert, P., Marschner, S., and Pharr, M. (2004).  State of the art in monte carlo global illumination.  In ACM SIGGRAPH 2004 Course Notes, SIGGRAPH ’04, page 5–es, New York, NY, USA. Association for Computing Machinery.
  * Engel, (2006) Engel, W. (2006).  Cascaded shadow maps.  pages 197–206.
  * Hart, (1996) Hart, J. (1996).  Sphere tracing: A geometric method for the antialiased ray tracing of implicit surfaces.  The Visual Computer, 12:527–545.
  * Karis, (2014) Karis, B. (2014).  High quality temporal supersampling.
  * Lauritzen and McCool, (2008) Lauritzen, A. and McCool, M. (2008).  Layered variance shadow maps.  In Proceedings of Graphics Interface 2008, GI ’08, page 139–146, CAN. Canadian Information Processing Society.
  * Liu and Kim, (2014) Liu, F. and Kim, Y. J. (2014).  Exact and adaptive signed distance fields computation for rigid and deformable models on gpus.  IEEE Transactions on Visualization and Computer Graphics, 20(5):714–725.
  * Panteleev, (2014) Panteleev, A. (2014).  Practical real-time voxel-based global illumination for current gpus.  GTC 2014.
  * Quilez, (2019) Quilez, I. (2019).  Sdf bounding volumes - 2019.
  * Rong and Tan, (2006) Rong, G. and Tan, T.-S. (2006).  Jump flooding in gpu with applications to voronoi diagram and distance transform.  In Proceedings of the 2006 Symposium on Interactive 3D Graphics and Games, I3D ’06, page 109–116, New York, NY, USA. Association for Computing Machinery.
  * Schied et al., (2017) Schied, C., Kaplanyan, A., Wyman, C., Patney, A., Chaitanya, C. R. A., Burgess, J., Liu, S., Dachsbacher, C., Lefohn, A., and Salvi, M. (2017).  Spatiotemporal variance-guided filtering: Real-time reconstruction for path-traced global illumination.  In Proceedings of High Performance Graphics, HPG ’17, New York, NY, USA. Association for Computing Machinery.
  * Tan et al., (2020) Tan, Y. W., Chua, N., Koh, C., and Bhojan, A. (2020).  RTSDF: Generating Signed Distance Fields in Real Time for Soft Shadow Rendering.  In Lee, S.-h., Zollmann, S., Okabe, M., and Wuensche, B., editors, Pacific Graphics Short Papers, Posters, and Work-in-Progress Papers. The Eurographics Association.
  * Weisstein, (2019) Weisstein, E. W. (2019).  Sphere point picking.
  * Wig42, (2014) Wig42 (2014).  The modern living room.
  * Wright, (2015) Wright, D. (2015).  Advances in real-time rendering in games: Part ii: Dynamic occlusion with signed distance fields.
  * Wyman, (2018) Wyman, C. (2018).  Introduction to directx raytracing.  In ACM SIGGRAPH 2018 Courses, SIGGRAPH ’18.