\subsection{Hierarchical View Finding}
\label{sec_hierView}
Our essential goal is to find the \emph{good} camera views for the input treelike structure.
This goal naturally leads to the question: what is the metric of camera view goodness for a treelike skeleton structure?
Treelike structures contain geometry information (for example, length, curvature, angle) and morphology information (for example, radius, branching frequency, adjacency).
Therefore, for our purpose, a good camera view should convey these information as much as possible. 
In this section, we present a quantitative metric for camera view goodness in neuron skeleton data and a fast camera view generation method for neuron data.

\subsubsection{Camera view metric}
We quantify the neuron information embedded in the neuron skeleton structures via Mutual Entropy \cite{Feixas2009Unified}.
\begin{equation}
I(v,O) = \sum_{o\in O} {p(o|v) \log \frac{p(o|v)}{p(o)}}
\label{eq:shannon_entropy}
\end{equation}
where $I(v,O)$ represents the information carried by the segment $o$ in the camera view $v$, probability of the occurrence of the corresponding neuron branch, and $\log p$ represents the information carried in this branch. In other words, \ref{eq:shannon_entropy} is to compute the sum of information expressed in the neuron skeleton in a certain camera view. In our method, $p = L_i/L_T$ where $L_i$ is i-th branch, and $L_T$ is the total length of all branches.

Unlike existing works that focused on viewpoint for mesh-based models, the geometry information reflected by skeleton data is quantified in segment length. However, the skeleton is not well-defined if only skeleton segments are recorded. We consider not only the real segments, but also the relative position between nodes and their siblings, the relative position between nodes and their parent's siblings as shown in Figure ~\ref{fig:additional_segmentconnect}.

\begin{figure}
    \centering
    \includegraphics[width=2in]{images/fig_skeleton.png}
    \caption{Mutual entropy in skeleton data. And the result with/without additional connections.}
    \label{fig:additional_segmentconnect}
\end{figure}

\subsubsection{Camera view hierarchy}
Given an arbitrary tree-like struture, geometry and morphology information are expanding through two phases in the visualization: the global view and detailed view.
We present a view hierarchy to include both the information in the best global view and that in a local view for fine structures.
The level of details is determined by the visible subtree level of a specific camera view.
To find the optimal camera view $v_Li$ for the subtree with the level $Li$ in the treelike structure, our objective function is
\begin{equation}
    E = \min_{v_{Li}}I(v_{Li},O_{Li})
\end{equation}
We denote the hierarchical viewpoint set for the tree structure as $$H=\{\{v_{Li}\}|\{v_{L0}\}, \{v_{L1_0}, v_{L1_1}, \cdots, v_{L1_{m1}}\}, \cdots, \{v_{Lh_0},v_{Lh_1},\cdots,v_{Lh_{mh}} \}\}$$
where $m1, m2, \cdots, mh$ represent the subtree amount in each tree level.
In Section \ref{alg:exploration}, a recommended exploration in 3D space will be generated based on this viewpoint set.

\subsection{Skeleton Planar visualization}
One of our main target is to unveal the hidden or invisible geometry information in 


\paragraph{Camera View Generation}


\input{orthographic_projection}

\textbf{Principle planes}
Given a 3D subtree structure $t_{Li_j}$, a primary view plane for this structure is defined as the plane passing the subtree center $C_{Li_j}$ and perpendicular with the direction of $v_{Li_j}$ where $j\in{0,1, \cdots, mi}$.

For each segment, we compute the furcation angle adjustment ratio $r_{furcation}$, within-chain angle adjustment ratio $r_{\theta}$ and length adjustment ratio $r_{length}$. 
The angle definition is shown in Figure \ref{fig:PSO_shaperecovery_angle}. 
\begin{figure}[h]
    \centering
    \includegraphics[width=0.6\linewidth]{images/parameterComparison.pdf}
    \caption{Curve placement with different parameters.}
    \label{fig:PSO_shaperecovery_angle}
\end{figure}

Each angle is bounded in $[0,\pi]$ so that the relative bending shape of each segment will be preserved in the planar embedding. 
We adopted PSO method to solve the skeleton shape recovery because the search space in this optimization problem is non-convex.

our current embedding result is shown in Figure \ref{fig:latest_result}. In our angle optimization method, we search for the optimal parameter combination. 


\begin{algorithm}[h]
\SetAlgoLined
\KwResult{\{$r_{furcation}$\}, \{$r_{\theta}$\}, and \{$r_{length}$\}}
 Init: \{particles\}\;
\While{Best Energy repeated for 20 times}{
    Calculate shape recovery result using each particle's ratio sets \{$r_{furcation}$\}, \{$r_{\theta}$\}, and \{$r_{length}$\} \;
    
    Compute Energy(planar embedding) using each particle's ratio set\;
    Update the best ratio set (of the minimal energy) among all particles\;
    Update the best ratio set (of the minimal energy) within each particle's history\;
    Update particle's ratio set for next loop\;
 }
 \caption{Shape recovery using particle swarm optimization}
 \label{alg:PSO_shaperecovery}
\end{algorithm}

\subsection{Exploration in 3D space}
\label{alg:exploration}
It is inevitable that some spatial information is not fully rendered on the planar embedding while the treelike structure's node length, angle, and curvature information are well-preserved.
To complement the geometry information loss, we generate a camera motion that smoothly connects the hierarchical best views for each subtree in the skeletal structure.
Users explore the raw treelike structure in 3D space in each views that reveal the maximal information.
Furthermore, the tree levels of focus can be specified by users.
Based on Section \ref{sec_hierView}, a series of best views for demonstrating the geometry information in the original tree is generated.
We use a quadratic Bézier curve to connect adjacent views for the structure exploration.


\subsection{Hierarchical View Finding}
\label{sec_hierView}
The goal of finding \textit{good} viewpoints naturally requires defining a set of metrics that can measure the preservation of geometric attributes.
For treelike structures, based on existing literature~\cite{Biasotti:2008:SS,Feragen:2010:GST,Feragen:2011:MST}, we have determined the metrics to be length, curvature, and angle, for geometry information; and radius, branching frequency, and adjacency, for morphology information.
To this end, we present an algorithm to quantitatively optimize these metrics to find good camera viewpoints and subsequently, a method for fast camera path generation using these viewpoints.

\subsubsection{Camera view metric}
Feixas et al.~\cite{Feixas2009Unified} formulate the measure of geometric attributes in a camera viewpoint as:
\begin{equation}
I(v,O) = \sum_{o\in O} {p(o|v) \log \frac{p(o|v)}{p(o)}},
\label{eq:shannon_entropy}
\end{equation}
where $I(v,O)$ represents the geometry attributes carried by an object collection $O$ in a camera view $v$, $p(o)$ is the probability that a corresponding object $o \in O$ is visible and conveys information in a scene, and $p(o|v)$ is the probability of an object $o$ being visible in $v$.
Essentially, this equation computes the sum of attribute information expressed for every object in a certain camera view.

While this model is widely used for viewpoint selection in mesh and volume data (see Sec.~\ref{sec:relatedWork_camera}), it does not always yield a satisfactory camera view for treelike skeleton data. 
This is because treelike skeletons have open endings whose geometry information cannot be fully reflected by preserving only its original length ratio. 
To address this limitation, we have introduced a method that not only considers original 3D edges, but also a set of additional \textit{imaginary} edges as shown in~\ref{fig:additional_segmentconnect}~(c), namely, the connection between each node and (i) its siblings, (ii) its grandparent, and (iii) its parent's siblings.
For simplicity, we refer to the skeleton and the imaginary edges as an \emph{enhanced tree}.

For an enhanced tree, we model the geometry attribute of an edge as the ratio between the edge length $l$ and the total length of all edges.
By extension, given a camera view, the projected attributes coming from an edge is the ratio of its projected length over the sum of projected lengths in the enhanced tree.
The effect of views computed using the additional edges is shown in Fig.~\ref{fig:additional_segmentconnect}~(a) and (b).


\begin{figure}
    \centering
    \includegraphics[width=\linewidth,keepaspectratio]{images/Figure2.pdf}
    \caption{Global best view generated using (a) the method in ~\cite{Takahashi:2005:FDA} and (b) our model. 
   
    The red arrows show that our \textit{enhanced} tree edges, represented by the dashed lines in (c), result in a more accurate projection of each node's relative placement. The green, red, and blue dashed lines represent three types of imaginary edges for node F.}
    \label{fig:additional_segmentconnect}
\end{figure}

\subsubsection{Camera view hierarchy}
\label{sec:viewhierarchy}
We present a camera view hierarchy algorithm that facilitates shape understanding by presenting level-of-detail~(LoD) information using a computed best global view and a series of local view for fine structures.
For each LoD hierarchy, our method determines the best camera position $v_h \in \mathbb{R}^3$.
To this end, we formulate a hierarchical view finding optimization such that the camera viewpoint candidates lie on a spherical surface.
The radius of this spherical search space is proportional to the subtree expansion radius with its center positioned at the weighted center of all subtree nodes, $c^{T}$.
The distance $D$ between the camera and the tree center is defined as $D =\beta R^{T}$, where $R^{T}$ is the radius of the principal view with a weight factor $\beta$.
Based on our experiments, we suggest $\beta$ to be 1.5.
Furthermore, the camera look-at direction is the ray from the camera center to $c^{T}$ and the up direction perpendicular to the look-at direction.
Thus, to find the optimal camera viewpoint $v_{h}$ for a subtree, $T_{h}$, in the hierarchy level $h$ of the tree, we define the following objective function:
\begin{equation}
   
        v_h = \argmin_{v_h} E_v \quad \textrm{\textit{,}} \quad E_v = I(v_{h},T_{h})
   
\end{equation}
The hierarchical viewpoint set, $H$, for a tree structure is denoted as $H=\{\{v_{h}\}|\{v_{h=0}\}\cup\{v_{h=1}\}\cup \cdots \cup\{v_{h=m} \}\}$,
where $1, 2, \cdots, m$ represent the hierarchy levels.
The number of hierarchical viewpoints in each tree level is equal to the subtree number in that level.

\subsection{Skeleton Planar Embedding}
To maintain the 3D geometry of a structure in a single planar view, we first determine a method to best preserve its edge lengths and the node angles.
To achieve this, we design a scheme for projecting the nodes onto a principal plane using our viewpoint selection method described in Sec.~\ref{sec:viewhierarchy}.

\subsubsection{Node angle}
\input{orthographic_projection}
\label{sec:node_angle}

We categorize two sets of node connectivity that determine the target angles for planar embedding: chain and branching.
A chain condition is the set of nodes in a segment where each node has a single child. 
A branching condition is when a node has multiple children.
Given a subtree with a root node that has multiple children, a chain representing a branch of the subtree is collected starting from the root along each node that has a single child, as shown in Fig.~\ref{fig:projection}~(a).
A branching set contains a node, its parent and children, as show in Fig.~\ref{fig:projection}~(b).
To calculate target angles, we first project the relevant set of nodes onto a principal plane and then compute, for each node, the angle formed between its projected node-parent-grandparent edges, in a counterclockwise order.
Given a set of nodes, the principal plane is the plane passing through the subtree center and perpendicular to the look-at direction of the optimal camera view calculated using the method introduced in Sec.~\ref{sec_hierView}.


\subsubsection{Embedding optimization}
Using the target angles and edge length, we formulate the planar embedding problem as a UV coordinate optimization procedure. 
In other words, we aim to find a position for each node on a planar view that minimizes loss in target angles and edge lengths.
However, to ascertain geometry preservation of the tree structure, we cannot directly apply a constant minimization factor to all edges and nodes.
For instance, applying a certain shrinking factor to a longer edge can account for a heavier loss in geometry than an edge with a smaller length.
To address this, we minimize the percentage loss of edge length and node angle, denoted as  $r_{l}$ and $r_{a}$ respectively, in the candidate 2D embedding.
Given $r_l$ and $r_a$, an edge length $l_e = (1+r_l)l$, and a node angle $\theta_{e}$ is
\begin{equation}
    {\theta_{e} =
    \begin{cases}
    \theta + (\pi - \theta)r_a & \text{if $\theta \leq \pi$ and $r_a \geq 0 $ } \\
    (1+r_a)\theta & \text{if $\theta \leq \pi$ and $r_a < 0 $ } \\
    \theta - (\theta - \pi)r_a & \text{if $\theta > \pi$ and $r_a \geq 0 $ } \\
    \theta - (2\pi - \theta)r_a & \text{if $\theta > \pi$ and $r_a < 0 $ }
    \end{cases}
    }
    \label{eq:embedding_angle}
\end{equation}
where $\theta$ is the target node angle calculated in Sec.~\ref{sec:node_angle}.
We constrain $r_l\in(0, 2.0]$ and $r_a \in [-1.0, 1.0]$ in the following optimization step.
Fig.~\ref{fig:curve_differentparams}~(a) shows an example of the $\theta_{e}$ based on different $r_a$ when $\theta \in (\pi, 2\pi)$.
By applying Eq.~\ref{eq:embedding_angle}, the relative bending direction of the nodes will be maintained although the angle value may be changed, as shown in Fig~\ref{fig:curve_differentparams}~(b). 

We optimize a single $r_{l}$ and $r_{a}$ for each segment using:
\begin{equation}
    \begin{split}
        R^{*}_{li},R^{*}_{ai} &= \argmin_{R_{li},R_{ai}} E_p \\
        E_p &= \sum_{i}^{M}{w_l\cdot r_{li}^2 + w_a\cdot r_{ai}^2 + w_X\cdot X(r_{li}, r_{ai})}
     \label{eq:embedding_Energy}
    \end{split}
\end{equation}
where $w_l$ and $w_a$ are the weights for the length and angle loss ratio, respectively, $M$ is the total segment amount, $w_X$ is the penalty weight for intersecting edges, and $X(r_{li}, r_{ai})$ are the corresponding length and angle responsible for the intersection  in the current placement. 
We report our parameter values in Sec.~\ref{sec:eval}.
The resulting node placement of a simple tree structure with different $r_{l}$ and $r_{a}$ settings are shown in Fig.~\ref{fig:curve_differentparams}~(b). 

\begin{figure}
    \centering
    \includegraphics[width=0.8\linewidth]{images/parameter_change_v3.pdf}
    \caption{(a) An example of the impact of $r_a$ on $\theta_{e}$ with the node $C$'s target angle $\theta$ ($\angle ABC_T$ in counterclockwise order) as an reflex angle. If $r_a > 0$, node $C$ is positioned at the range between $BD$ and $BC_T$, e.g., $C_1$. If $r_a=0$, node $C$ is at $C_t$. If $r_a < 0$, $C$ is positioned at the range between $BC_T$ and $BA$, e.g., $C_2$ or $C_3$. Thanks to our constrain, $C$ will not be on the $C_T$'s opposite side against the dash line. (b) Segment shapes with different parameters. The top left structure is the original skeleton. The top row shows the changed shape with varying length ratio $r_l$ (left to right: 0.0, 0.2 and 0.5, respectively) and a constant $r_a$ ($r_a=0$). The bottom row shows the result of varying $r_a$ (left to right: -0.02, 0.2 and 0.5, respectively) and $r_l=0$.
} 
    \label{fig:curve_differentparams}
\end{figure}

Since the search space for this optimization is not convex nor differentiable, we apply PSO ~\cite{Kennedy:1995:PSO} to find a local optimal embedding solution. 
PSO is a robust approach that controls parameters without depending on a search space gradient.
In our algorithm, the skeleton placement is determined by the combination of the $\{r_{l}\}$ and $\{r_{a}\}$  ratios, denoted as $R_{l}$ and $R_{a}$ respectively.
Specifically, each swarm particle $P_i$ represents a candidate solution for the placement. 
$R_{l}$ and $R_{a}$ are initialized randomly.
The energy $E_p$ of this embedding is calculated using Eq. \ref{eq:embedding_Energy} that quantifies the goodness of a candidate nodes placement.
A lower energy corresponds to less geometry loss and fewer intersections.
In each iteration, a particle is updated based on its moving velocity $U_i$, current ratio set $\{R_{li}, R_{ai}\}$, historically best ratio set $P_{ig}$, and the ever best particle $P_g$ amongst all particles. This is formulated as: 
\begin{equation}
    P_i^{c+1} = \omega_g \cdot (P_g^{c} - P_i^{c}) + \omega_p \cdot (P_{gi}^{c} - P_i^{c}) + \omega_{inert} \cdot (U_i^{c} + \gamma^{c}) + P_i^{c}
    \label{eq:particle_update}
\end{equation}
where $\omega_g$, $\omega_p$, $\omega_{inert}$ represent the effect of the global best ratio set, the best ratio set within the particle history, and the inertial velocity of the particle itself in the searching space, respectively, $c$ refers to the iteration count, and $\gamma$ is a randomized velocity value to increase the search diversity and accelerate convergence. 
$U_i^c$ is calculated as the difference of the corresponding ratios between the $(c)$th and $(c-1)th$ iteration.
The optimization is terminated when the geometry loss is zero or when the maximal loop limit is reached.
Algorithm \ref{alg:PSO_shaperecovery} provides a pseudocode of our method.

To encourage non-intersecting node placement candidates and to accelerate the optimization convergence, we propose setting $w_X$ to have a value much larger than the other weights.
In evaluating our experiments, we determined this weight to be 1.5 times the sum of the maximal edge length loss and the maximal angle loss. 
Since both the possible maximal angle and edge length loss equals the total number of edges in the tree, a node placement with a single edge crossing will have a higher energy than a placement without any edge crossing, in our implementation.
Moreover, to ensure at least one non-intersecting solution, we additionally generate a radial layout of the tree, using the method in \cite{marino2015planar}, and calculate its $\{R_{l}, R_{a}\}$ as Particle 1's initial values, $\{ Q_l, Q_a \}$.
Thus, in contrast to a general PSO solution, our method guarantees a final non-intersecting placement, no worse than the radial layout.


\begin{algorithm}[ht]
\LinesNumbered
\KwResult \text{Optimal ratio set} $\{R^{*}_{l}, R^{*}_{a}\}$ \text{ denoted as } $P_g$;\\
\KwIn {\text{Randomize} ${R_{l}, R_a, U_i}$ \text{ for each } $P_i$;\\
$P_0 \leftarrow \{r_{lm}=0, r_{am}=0\}, P_1\leftarrow \{Q_{l}, Q_{a}\}$;\\
$P_g \leftarrow P_0, P_{ig} \leftarrow P_i, E_{pi}\leftarrow\infty, c \leftarrow 1, c_{max}\leftarrow 100$}
\While{$E_{p}>0$ \text{ and } $c\leq c_{max}$}{
    \text{For each } $P_i$: \\
    ~~~\text{Generate node placement based on its } $R_l, R_a$ ;\\
    ~~~\text{Update }$E_{pi}$ \text{ using } ${E_p(P_i)}$ \text{ defined in Equation ~\ref{eq:embedding_Energy}};\\
    ~~~$P_{ig}=\min \{ P_{i0}, P_{i1},\cdots, P_{ic}\}$;\\
    End for;\\
    $P_g=\argmin_{P_i}{E_p(P_i)}$;\\
    For each $P_i$:\\
    ~~~ $\{R_l, R_a\}$ \text{ is updated using Equation~\ref{eq:particle_update}};\\
    End for;\\
    $c=c+1$;
 }
\caption{Planar Embedding Using PSO}
\label{alg:PSO_shaperecovery}
\end{algorithm}

\begin{figure*}[ht]
    \centering
    \includegraphics[width=\textwidth,keepaspectratio]{images/exploration_2.pdf}
    \caption{The original structure in 3D space and four screen shots of our automatically generated 3D exploration views. The exploration starts with the best global view and then moves along a smooth B\'ezier path for each subtree's best local view. Screenshots of selected camera views are shown in the insets. We also generate a small camera motion to enhance parallax, as demonstrated using the two insets in the bottom right corner. A video of the exploration is available as supplementary material.}
    \label{fig:exploration}
\end{figure*}


\subsection{Interaction}
\label{sec:interaction}
Researchers have varying preferences with regards to the strictness in geometry attributes preservation.  
For example, a neuroscientist may want to investigate the distance between endpoints of a traced neuron skeleton and as a result, may want to maximize the weight of length preservation. 
Likewise, an anatomist may prefer increasing the weight of angle preservation to observe curvatures along an anatomy. 
To facilitate this, our technique supports the ability to interactively adjust the length and angle weights. 

Furthermore, our implementation also supports the interactive refining or adjustment of the planar embedding result. 
Specifically, a user can specify any curve or curve segment and rotate it around an anchor node. 
Following the manual adjustment, our method checks to remove any newly introduced intersections.  
An example of this user adjustment is shown in Figure \ref{fig:user_interaction}.
It is worth noting here that the optimization post manual intervention considers the ratios of the user-adjusted segment to be fixed and only recalculates the angle and length ratios of other segments.

\begin{figure}
    \centering
    \includegraphics[width=\linewidth,keepaspectratio]{images/click_adjust_v2.pdf}
    \caption{Interactive branch adjustment.  (a) The original embedding result.  (b) The user has repositioned a branch, causing an intersection that is indicated by the red arrow.  (c) The updated embedding result, with the intersection removed.}
    \label{fig:user_interaction}
\end{figure}


\subsection{Exploration in 3D space}
\label{alg:exploration}
It is inevitable to lose some 3D information when reducing the dimensionality from  3D to a planar embedding.
Particularly, information such as the relative position between subtrees and the expansion in 3D space may not be maintained in a 2D view.
To fully uncover the geometry information carried in a 3D structure, our method generates an exploration path based on the hierarchical view set $H$ in Sec.~\ref{sec_hierView}.
To support the effective investigation of geometry information inherent in a 3D structure, we introduce a technique to generate an exploration path based on the hierarchical view set $H$, discussed in Sec.~\ref{sec_hierView}.

This exploration path is composed of multiple groups of camera motion sequences.
Each group includes two motion sequences: a transition from between consecutive principal views and a camera dolly motion to stimulate parallax.
The camera positions in the transition clip is generated using a quadratic B\'ezier curve connecting one principal view to the next 
and the camera orientation is interpolated using a smooth transition between the two views.
For the dolly motion, the camera is always looking at the center of the subtree and moving along an arc of $90\degree$.
Fig.~\ref{fig:exploration} demonstrates an example of the camera path.
Moreover, please refer to our supplementary video for further examples.




\iffalse
\begin{equation}
    r_{l} = \frac{\Delta{l}}{l} \quad \textrm{,} \quad r_{a} = \frac{\Delta{\phi}}{\phi}  
\end{equation}    
\fi
\subsection{Vascular analysis}
\par
\textbf{Vascular analysis. }Though 3D rendering already provides a better view than na\"ively scrolling through slices of the CT scan, its visualization efficiency depends on the user's ability to seamlessly manipulate camera views within the application to study the entire structure and simultaneously make a mental note of features such as radii and abnormalities.
In contrast, using a planar visualization as in Fig.~\ref{fig:teaser}(c), the user is able to visualize all of the blood vessels and compare their geometric attribute (i.e., radius) within a single view. 
Moreover, at an application level, we have shown that our camera view technique can be used to generate viewpoints that results in minimal visual occlusion and maximizes the spatial understanding of the structure. 

\par
\textbf{Neurite analysis. }
Connectomics~\cite{TheHumanConnectome} is an emerging field for techniques that study complex neural connection maps.
By mapping the brain connectivity, neuroscientists will be able to analyze how the human brain functions and its degradation process as a result of cognitive decline or disease~\cite{ghahremani2021neuroconstruct}.
A common challenge in this domain is the immensity of volume data. 
Recent works~\cite{mohammed2017abstractocyte,al2014neurolines} have introduced methods to alternatively represent dense neuronal structures as abstracted diagrams, albeit in a linear graph-like arrangement.
Though schematic diagrams help study connections and topological layouts, an examination of the shape of the structure is required to understand morphological changes during degeneration. 
Moreover, given the density of information within a microscopy volume and the intricate neurite morphology, neuroscientists independently observe regions of the brain and make general visual observations using population analysis.  
Our embedding and visualization method can allow for effective analysis of fragmentation and thinning patterns within a neuron by juxtaposing the \textit{healthy} and \textit{diseased} neurites, as shown in Fig~\ref{fig:juxtapose}~(e), instead of separately visualizing them in 3D.







\section*{ACKNOWLEDGMENTS}       
\section*{Acknowledgements}
This project was supported in part by NSF grants CNS1650499, OAC1919752, ICER1940302, and IIS2107224.
Bronchial CT scans courtesy of the EXACT'09 study, lower limb vessels courtesy of OsiriX, upper aorta courtesy of the Visible Korean Human Project, and cranial vessels courtesy of VolVis.



\subsection{Geometry Information Loss}
We provide a quantitative and qualitative evaluation of our planar embedding results and camera path generation.
Moreover, we compare our results with the skeleton embedding method in \cite{marino2015planar}.
\subsubsection{Quantitative analysis}
\label{sec:quantitative}
Table~\ref{tab:length_and_angle_loss} reports the geometry loss analysis using two metrics.

\textbf{Metric 1. Projected angle and length:} 
We evaluate the loss $L_l$ and $L_a$ by comparing our embedding with the target edge lengths and wth the target node angles, respectively:
$$L_l = \sum_{i}^{N-1}\frac{|l_i-l_{ei}|}{l_{i}} \quad \text{,} \quad L_a = \sum_{i}^{N}\frac{|\theta_{i} - \theta_{ei}|}{\theta_{i}} $$
where $N$ is the number of nodes.

\textbf{Metric 2. Angle and Length in 3D space:} 
Since the ultimate goal of planar embedding is to preserve the 3D geometry information, we also compute the edge length and angle loss compared to the original 3D structure.
In the original structure, each node angle is the acute angle between the edge and its parent edge.
The edge length and angle loss for the root node is 0.
We show that our technique can maintain the segment length well and the overall angle loss is small.

\begin{figure*}[t!]
\includegraphics[width=\textwidth,keepaspectratio]{images/comparison_joe_v3.pdf}
  \caption{Preservation of local morphology in our work compared to a global-view based technique \cite{marino2015planar}.  (a) Different camera views of the structure, which may result in intersection and distortion of other branches, therefore making it difficult to find a global view that best captures the morphology of all branches.  (b) Embedding result from \cite{marino2015planar} that uses the global projection, resulting in misleading distortions highlighted using the teal-colored branch AC.  (c) Embedding using our method, which more accurately captures the local branching morphology.}
	\label{fig:comparison}

 \end{figure*}
 

\subsubsection{Qualitative Analysis}

As mentioned in Section~\ref{Sec:related_works_planar}, we consider~\cite{marino2015planar, won2012uncluttered} as methods closest to our work and ~\cite{marino2015planar} as the state-of-the-art.
The algorithm in these methods greatly depend on an appropriate input view, thus requiring users to manipulate 3D camera for an optimal input view. 
This is a challenging task that has motivated our work to require no user-defined input view.
Furthermore, the embedding from these method only demonstrate limited geometry information in the original 3D skeleton.
Fig.~\ref{fig:results} shows that our method outperforms ~\cite{marino2015planar} regarding visualizing segment shapes, especially when the input structure expands in all three dimensions in space, e.g., the bronchial airways, the cranial blood vessels, and the dense neuron fibers in olfactory neurites.

Fig.~\ref{fig:comparison} shows how a single global view can lead to misleading distortions.
Specifically for complex treelike objects where branching structures have varying principal axes, reducing the image space dimensionality can project the structure in a way that can distort its local morphology. 
The central structure in Fig.~\ref{fig:comparison}~(a) is a global projection of cranial blood vessels used in \cite{marino2015planar} to generate a planar embedding, and the corresponding insets show alternate projections from different 3D camera viewpoints.
This global view gives a perception that the branch AC has a \textit{curled} morphology. However, by observing the same branch from different viewpoints it can be seen that the AC has a much smaller curvature.
In comparison, since our embedding result uses local projection views to maintain local morphology and spatial relation with neighboring nodes, we see that the embedded segment AC in our result, shown in Figure~\ref{fig:comparison}~(c), does not have the misleading distortion. 



\subsection{Expert Feedback}
We presented our technique to five experts (A1, A2, A3, A4, A5) from different research domains to comprehensively evaluate our method. 
Among the experts, A1 was a scientist in scientific visualization studying brain connectomics, A2 was a graduate student pursuing Doctor of Medicine who worked on medical visual analytics, A3 was a neuroscientist focusing on microscopy biology data including neurons, A4 was a doctor in nutritional science who heavily uses hierarchical visualization tools to organize datasets and conducts data mining, and A5 was a scientist in single cell genomics, studying the evolutionary trajectories of plant cells.

Each expert participated in this evaluation separately. 
They were presented with the planar embedding of interested datasets, the interactive embedding GUI, and the automatic exploration in 3D space, followed by an interview to collect their feedback.
A1 observed the neocortical axon structure and the bronchial airways; A2 observed the lower limb vessels, the upper aorta vessels, the olfactory neuron fibers, and the neocortical axon structure; A3 examined the neocortical axon structure; A4 observed the bronchial airways and the olfactory neuron fibers; and A5 studied one hippocampal neuron model and the olfactory neuron fibers.

The interview started with a description of treelike structure visualization.
Next, the experts were asked three profile questions: ``Do you have any experience of studying treelike structures datasets?"; ``When studying your data, what are your focused attributes?"; and ``Can you give a score (on a scale of 1 as no expertise, to 5 as authoritative understanding and experience) to rate your expertise on general data visualization and data visualization with treelike structures, respectively?".
Experts' self ratings for the first and third questions are (5, 4, 5, 3, 4) and (4, 3, 5, 2, 2), respectively.
For 3D navigation, experts chose the hierarchical views and navigated themselves using a GUI slider to control the speed.
We then asked ``What features are helpful for your research?" and ``What can be improved to better assist your research?".
Additionally, participants was asked to rate the overall practicality of our method and the two major functions, i.e., planar embedding with interactive edit, and suggested 3D exploration path.
\iffalse
The details of the scores are plotted in Fig.~\ref{fig:expert_score} 
\begin{figure}
    \centering
    \includegraphics[width=\linewidth]{images/evaluation/expertscore_plot.png}
    \caption{The expert score on each component of our technique and the overall method. Rating levels include 1 to 5, corresponding to ``strongly dislike'', ``slightly dislike'', ``neutral'', ``slightly like'', and ``strongly like'' respectively}
    \label{fig:expert_score}
\end{figure}
\fi
A1, A2, A3, and A4 rated the overall method and the embedding as 4. A5 rated the overall method as 5.
For the itemized score, A1 rated the navigation as 5 and the others rated it as 4.

The feedback from the experts were positive.
All experts appreciated the skeleton embedding with segment shape preservation.
According to A2, in vascular studies, it is important to reveal the vessel's branching pattern and connections since they are unique for each person.
A3 noted that ``This technique can be very useful in studying neuron sample's structure".
A5 highly rated the planar embedding because ``the method can be very useful for studying plant root system".
A1, A2, A4, and A5 favored the camera dolly motion around each hierarchical view in the path.
A1 said, ``This is helpful for understanding the neural connections coming from different areas in the brain''.
A2 preferred our LoD function for 3D treelike structure.
Both A1 and A3 emphasized that they would like to use the 3D exploration and 2D embedding visualization together because the combined modes can invoke different insights.
A5 commented that this effective visualization tool simplifies the study of complex root structures.
Regarding what can be improved, A1 commented that the sub-structures in 3D navigation view should be dynamically highlighted in the 2D embedding to enhance structural understanding.
A2 suggested to tune the distance between the camera and the center of the data and to adjust the visualized width of the segment in the skeleton structure for aesthetic purposes.
A4 suggested indicating the existing manual edits on the embedding to help researchers be aware of the accumulated changes.
\input{limitation}





\subsection{Discussion and Limitations}
Our planar embedding method preserves segment length, angles, and high level shape, especially revealing detailed node angles that are easily overlooked by people in global view observation.
Fig.~\ref{fig:aorta_explain} demonstrates an example of this. Although the blue curve in the upper aorta vessel structure appears to be quite straight in a global view, we can observe bending when zoomed into the subtree.
However, since our method avoids intersection, some large bending angles may be introduced during optimization, when a curve's expansion conflicts with other curves.
For example, we notice a bending near the of the blue curve in Fig.~\ref{fig:results}.
This is caused by the conflict between the expansion scope of the blue curve during the green curve's placement below it.

While we optimize an exhaustive list, more attributes that preserve treelike structures need to be explored.
For instance, relative position between different segment pairs may be a useful geometry attribute in some research domains. Since each segment is projected onto the principal plane which is determined by the hierarchical view, the relative location of segments on a projection of an arbitrary view is not always consistent with the view of the principal plane.

\begin{figure}
\centering
\includegraphics[width=\linewidth]{images/evaluation/aorta_explain1.pdf}
\caption{Local shape preservation and an example of avoiding intersections. Left: details of the node angles are shown by zooming in. The cube below each subfigure shows the relative transformation between each view. Right: in the blue curve, the bending near the end is caused by the potential conflict with the green curve below. Our method adjusts the expansion scope of the blue curve based on the target of optimizing the sum of the geometry loss. }
\label{fig:aorta_explain}
\end{figure}

\subsubsection{Parameter analysis}
The combination of $w_l$ and $w_a$ reflects the importance of length and angle preservation.
With a fixed $w_a$, increasing $w_l$ yields a smaller edge length loss.
Similarly, fixed $w_l$ and increasing $w_a$ results in a smaller angle loss.
Fig.~\ref{fig:rarl} demonstrates geometry losses for $w_l$ and $w_a$ combinations, using Metric 1 on Hippocampal Neurons 1.

The parameter adjustment allows the users to assign varying $w_l$ and $w_a$ for different nodes based on their specific visualization needs.
For instance, to impose strict length preservation closer to the root node, the nodes with the shorter depth can be assigned a higher $w_l$ than other nodes in the tree.


\begin{figure}
\centering
\includegraphics[width=\linewidth]{images/parameterTune.pdf}
\caption{The relationship between the embedding's geometry loss and the parameters $w_l$, $w_a$ in the optimization. Left: $w_a=2.0$. Right:$w_l=2.0$}
\label{fig:rarl}
\end{figure}

\subsubsection{Limitations}
The PSO time complexity is $O{(N^2)}$. The performance bottleneck is the segment intersection checking task in each loop. This intersection checking is composed of a coarse and fine intersection checking. The coarse check facilitates faster computation when the nodes are sparsely placed. As shown in Table~\ref{tab:timecost}, when optimizing the planar embedding for structures with dense nodes, our time cost is more expensive than the method in~\cite{marino2015planar}. 

One failure case is caused by extremely large radii of the tree segments. Since our embedding preserves the edge radius, the intersection checking stage filter out the conditions when wide edges overlap with each other. Therefore, it is guaranteed that when applying the surface mesh onto the skeleton, no occlusion will be introduced. 
In the cases with extremely large radius there may not even be a valid radial layout embedding, thus resulting in no solutions for the planar embedding.

\section{Introduction}\label{sec:introduction}}
\input{introduction_v3}


\section{Related Work}
\label{sec:related}
\input{related_work}

\section{Algorithm}
\label{sec:alg}
\input{algorithm_v2}

\section{Results}
\label{sec:results}
\input{results}

\section{Evaluation and Discussion}
\label{sec:eval}
\input{evaluation_and_discussion}

\subsubsection{Applications}
\label{sec:application}
\input{application}

\section{Conclusion and Future Work}
\label{sec:conclusion}
\input{conclusion}

\ifCLASSOPTIONcaptionsoff
  \newpage
\fi



\bibliographystyle{abbrv-doi}



\subsection{Planar Visualization Techniques}
\input{related_work_planar_visualization}

\subsection{Camera Viewpoint Selection}
\label{sec:relatedWork_camera}
Given a scene content, a view is determined by the configuration of the camera.
Through a good viewpoint, fundamental data can be perceived and significant objects can be recognized.
Since viewpoint selection is a broad research topic, we focus on the relevant works adopting low level attributes of the view content and the viewpoint selection metrics.
Bonaventura et al.~\cite{Bonaventura:2018:SVS} have summarized the pioneering viewpoint selection methods for polygonal data.
Kamada and Kawai have proposed a basic rule for finding a good view, maximizing the projected lines on each object~\cite{Kamada:1988:SMC}.
Inspired by information entropy theory~\cite{feixas1999information,I2002information}, many works have designed  methods that formulate the problem in entropy space. Arbel et al.~\cite{Arbel:1999:VSN} measure object recognition in a monochrome view, which studied the view selection problem based on Shannon entropy maps.
V\'{a}zquez et al.~\cite{vazquez2001viewpoint} have further modeled view selection as an object visibility maximization problem by transforming view finding into a visibility probability space.
The attributes used are the projected area of each unit in the mesh-based objects.  
Stoev et al.~\cite{Stoev:2002:CSA} have designed a method for automatic camera positioning in time, considering projected area and scene depth.
Podolak et al.~\cite{Podolak:2006:PRS} automatically choose a good viewpoint by minimizing the visible object symmetry.

View selection methods have also been investigated for volume data~\cite{Takahashi:2005:FDA}. 
Bordoloi et al.~\cite{bordoloi2005view} have developed a viewpoint selection method for static volume visualization and their method provides a set of representative views for the volume that partition the view space into several subsets based on view similarity.
For dynamic volumes, Ji et al.~\cite{Ji:2006:DVS} have formulated a utility function that combines voxel opacity, color, and curvature information.
For terrain data visualization, Stove and Straber ~\cite{Stoev:2002:CSA} have proposed considering maximum depth, in addition to projected area.
Focusing on the camera views inside blood vessel models, Meuschke et al.~\cite{Meuschke:2017:AVS} have developed an automatic viewpoint selection technique for exploring simulated aneurysm data. Based on their technique, Apilla et al.~\cite{Apilla:2021:AAA} have presented a camera path generation method to explore the model through optimal viewpoints showing the interesting regions during the cardiac cycle.
Recently, methods for viewpoint generation are being developed that take perceptual factors into consideration~\cite{ono1988dynamic,Secord:2011:PMV,PH:2019:RSS}.
Secord et al.~\cite{Secord:2011:PMV} have proposed a perceptual model that combines attributes, projected model, and silhouette length of the polygonal objects to predict the users' preferences to the viewpoint of a variety of objects.

Our method shares some similarity with Bordoloi et al.~\cite{bordoloi2005view} as it locates the best views to maximize the visible geometry attributes reflected on the skeletal data.
However, we generate a series of hierarchical views that discover the details in the treelike structure based on subtree levels.







\subsection{Planar Visualization}
The most simplistic visualization of an embedded structure is to render its projected skeleton as lines, similar to the rendered results in Fig.~\ref{fig:comparison}.  
Such a rendering provides a broad overview of the global and local morphology of a structure and can provide clear indications of specified locations along the skeleton.

A pseudo-surface rendering based on the radii values can be used to generate a 3D appearance of the embedded structure and also present a surface on which attributes can be mapped to color. Fig.~\ref{fig:teaser} shows such a surface rendering of segmented blood vessels from a CT scan. The color map\footnote{The diverging color map for three classes was designed using ColorBrewer~\cite{harrower2003colorbrewer} with the `color blind safe' and `print friendly' options.}, from a shade of blue to yellow to red, represents the gradient of the radii difference of a segment with respect to the average radius of the entire structure, in order of increasing segment radius value.  

A planar visualization for studying corresponding structural changes within a structure is possible by juxtaposing the projected structures in a single view.  We demonstrate this idea in Fig~\ref{fig:juxtapose} using an isolated \textit{healthy} olfactory neuron from a dense brain microscopy volume and its corresponding \textit{diseased} state predicted using~\cite{boorboor2021neuregenerate}.
A planar embedding of the neuron's skeleton data (Fig.~\ref{fig:juxtapose}~(d)) is first constructed using our method.
Next, using a viewpoint perpendicular to the central axis of the skeleton, we render a bounded view volume using~\cite{boorboor2018visualization} and project it onto a single view along the embedding result. 
Finally, we juxtapose the two embedded volumes in a single view with an offset for clarity, as shownin Fig.~\ref{fig:juxtapose}~(e).

\subsection{Camera Navigation Path}
Exploring information in 3D space is the most natural way to fully investigate a 3D object.
With this motivation, our technique generates a camera path with dynamic focus on the different subtrees in the skeleton for users to automatically explore the data in 3D space.
Fig~\ref{fig:exploration} demonstrates this concept for investigating a hippocampel neuron.
This camera path follows a top-down approach, starting with the best global view of the structure and then hierarchically navigating each subtree.
A spherical dolly motion around each subtree stimulates visual parallax to aid in understanding the geometry information along the view direction and a smooth transition between the two views gives the user a perception of the spatial relationship between different parts in the structure.
We refer the reader to our supplementary video for a more elaborate demonstration.


\input{tab_timecost}

\subsection{Performance}
Time and Memory.
\input{tab_timecost}


\subsection{User study}

\Peggynote{

To evaluate the effectiveness of our embedding and exploration result, we conduct a user study on multiple datasets.
Dataset we are using include Hippocampal neuron1, Bronchial airways, and Cranial blood vessels.
To test various structure complexity, the three datasets are chosed based on their node numbers.
Functions:
\begin{itemize}
    \item Let users freely explore the Dataset A for 2 minutes. Alternative: Then show them exploration suggested by our method. After the exploration, show them two segments (one is original, one is in modified shape ) and ask them "Which one do you think is a segment in the original dataset?"
    \item Global view comparison: given Dataset A, starting with a random view, let the user freely explore the dataset for 2 minutes, then let them decide which view is the best view. Alternative: after 2 minute's exploration, show the global best view generated using our method and then show them with a randomly picked view. ``Which view is more representative in terms of showing geometry information of the dataset?''
\end{itemize}

Each subject has two trials.

\begin{figure}[h]
    \centering
    \includegraphics[width=1.\linewidth]{user_study.PNG}
    \caption{User Study Pipeline.}
    \label{fig:userstudy}
\end{figure}

}

