\fresh{}

\section{Desktop and mobile interactions}\label{sb:interaction}

\subsection{Desktop interaction}

Regarding desktop interaction, we keep the interaction we described in Section~\ref{bi:our-nve}, namely:
\begin{itemize}
    \item W, A, S and D keys to translate the camera;
    \item mouse motions to rotate the camera.
\end{itemize}
A screenshot of this interface is displayed in Figure~\ref{sb:desktop}.

\subsection{Mobile interaction}

\copied{}
Mobile interactions are more complex because the user does not have neither keyboard nor mouse to interact with.
However, there are some other sensors on most mobile devices that can help interaction.
One useful sensor for 3D interaction on mobile devices is definitely the gyroscope.
We use the gyroscope to enable a user to rotate his device to rotate the virtual camera.
We also add the possibility to rotate the camera by using touch controls.
This way, the user is not forced to perform a real-world half-turn to be able to look behind or to keep its device pointing to the sky (which can quickly become tiring) to look up.
These interactions, however, do not allow the user to move the camera: he can rotate it but not translate it.
For this reason, we display a small joystick on the bottom left corner of the screen that mimics the first person video games interactions and allows the user translating the camera:
\begin{itemize}
    \item moving the joystick up makes the camera move forward;
    \item moving the joystick down makes the camera move backwards;
    \item moving the joystick sideways makes the camera move sideways.
\end{itemize}
A screenshot of this interface is displayed in Figure~\ref{sb:mobile}.

\section{Adding bookmarks into DASH NVE framework\label{sb:bookmarks}}

\copied{}
In this section, we explain how to include a new interaction in the system described in the previous chapter.
\fresh{}

\subsection{Interaction --- Visual}

In Chapter~\ref{bi} Section~\ref{bi:3d-bookmarks}, we described two 3D widgets that we used to display bookmarks to users.
One of the conclusions of the user-study, described in Section~\ref{bi:user-study}, was that the impact of the way we display bookmark was not significant.
In this work, we chose a slightly different way of representing bookmarks due to some concerns with our original representations:
\begin{itemize}
    \item viewport bookmarks are simple, but people who are not computer vision scientists are not familiar with this representation;
    \item arrow bookmarks are complex, and need to be regenerated when the camera moves, which can harm the framerate of the rendering.
\end{itemize}
For these reasons, we changed the display to a vertical bar with a 2D sprite of a pictorial representation of an eye.
This 2D sprite is always facing the camera to prevent it from being invisible when the camera would be on the side of it.
Screenshots of user interfaces with bookmarks are available in Figures~\ref{sb:desktop} and~\ref{sb:mobile}.

The size of the sprite changes over time following a sine function to help the user distinguish what is part of the scene and what is extra widgets.
Since our scene is static, a user knows that a changing object is not part of the scene, but part of the UI\@.

The other bookmark parameters remain unchanged since Chapter~\ref{bi}: in order to avoid users to lose context, clicking on a bookmark triggers an automatic, smooth, camera displacement that ends up at the bookmark.
We also display a thumbnail of the bookmark's viewpoint when the mouse hovers a bookmark.
Such thumbnail is displayed in Figure~\ref{sb:desktop}.
Note that since on mobile, there is no mouse and thus no pointer, thumbnails are never downloaded nor displayed.

\begin{figure}[ht]
    \centering
    \includegraphics[width=\textwidth]{assets/system-bookmarks/screenshots/desktop.png}
    \caption{Screenshot of the desktop version, with a bookmark and its thumbnail on the bottom left corner\label{sb:desktop}}
\end{figure}

\begin{figure}[ht]
    \centering
    \includegraphics[width=\textwidth]{assets/system-bookmarks/screenshots/mobile.png}
    \caption{Screenshot of the mobile version, with its joystick on the bottom left corner\label{sb:mobile}}
\end{figure}

\subsection{Segments utility at bookmarked viewpoint\label{sb:utility}}
\copied{}
Introducing bookmarks is a way to make users navigation more predictable.
Indeed, since they are emphasized and, in a way, recommended viewpoints, bookmarks are more likely to be visited by a significant portion of users than any other viewpoint on the scene.
As such, bookmarks can be used as a way to optimize streaming by downloading segments in an optimal, pre-computed order.

More specifically, segment utility as introduced in Section~\ref{d3:utility} is only an approximation of the segment's true contribution to the current viewpoint rendering.
When bookmarks are defined, it is possible to obtain a better measure of segment utility by performing an offline rendering at each bookmark's viewpoint.
% Then, by simply counting the number of pixels that are rendered using each segment, we can rank the segments by order of importance in the rendering.
We define $\mathcal{U}^{*} (s,B_i)$ as being the optimized utility of a segment $s$ in a viewpoint defined at bookmark $B_i$.

\fresh{}
In order to know the optimized utility of a segment, we developed Algorithm~\ref{sb:algo-optimal-order}, that sorts segments according to their optimized utility.
It takes as input the considered viewpoint, the ground truth from this viewpoint and the set of segments to sort.
It starts with an empty model, individually tries adding each segment from the set of candidates, and computes the PSNR between the corresponding render and the ground truth render.
We can thus determine which segment brings the highest $\Delta\text{PSNR} / s$, $s$ being the size of the segment in bytes.
Once the best segment is found, it is registered, and a new iteration begins.
That way, it is able to generate an order of segments sorted by $\Delta\text{PSNR} / s$.
This order is then saved as a JSON file that a client can download in order to know which segments contribute the most to a certain viewpoint.

\begin{algorithm}[th]
    \SetKwInOut{Input}{input}
    \SetKwInOut{Output}{output}

    \SetKwData{BookmarkViewpoint}{bookmark\_viewpoint}
    \SetKwData{OptimalOrder}{optimal\_order}
    \SetKwData{TotalModel}{total\_model}
    \SetKwData{EmptyModel}{empty\_model}
    \SetKwData{I}{i}
    \SetKwData{BestSegment}{best\_segment}
    \SetKwData{BestPsnr}{best\_delta\_psnr}
    \SetKwData{PreviousPsnr}{previous\_psnr}
    \SetKwData{None}{none}
    \SetKwData{CurrentModel}{current\_model}
    \SetKwData{EmptyRender}{empty\_render}
    \SetKwData{CurrentRender}{current\_render}
    \SetKwData{GroundTruthRender}{ground\_truth\_render}
    \SetKwData{CurrentPsnr}{current\_psnr}
    \SetKwData{CurrentDeltaPsnr}{current\_delta\_psnr}
    \SetKwData{Segment}{segment}
    \SetKwData{Candidates}{candidates}
    \SetKwFunction{Render}{render}
    \SetKwFunction{Psnr}{psnr}

    \Input{The bookmark viewpoint, the ground truth render at this viewpoint, the candidate segments}
    \Output{The optimal order of the segments}

    \OptimalOrder\leftarrow{} []\;
    \EmptyRender\leftarrow\Render{\EmptyModel,\BookmarkViewpoint}\;
    \PreviousPsnr\leftarrow\Psnr{\EmptyRender,\GroundTruthRender}\;

    \TotalModel\leftarrow\EmptyModel\;

    \For{\I\in0\ldots200}{%

        \BestSegment\leftarrow\None\;
        \BestPsnr\leftarrow0\;

        \For{\Segment\in\Candidates}{%

            \CurrentModel\leftarrow\TotalModel\cup\Segment\;
            \CurrentRender\leftarrow\Render{\CurrentModel,\BookmarkViewpoint}\;
            \CurrentPsnr\leftarrow\Psnr{\CurrentRender,\GroundTruthRender}\;
            \CurrentDeltaPsnr\leftarrow\CurrentPsnr$-$\PreviousPsnr\;

            \If{\CurrentDeltaPsnr$>$\BestPsnr}{%
                \BestSegment\leftarrow\Segment\;
                \BestPsnr\leftarrow\CurrentDeltaPsnr\;
            }
        }
        \OptimalOrder\leftarrow\OptimalOrder+\BestSegment\;
        \TotalModel\leftarrow\TotalModel\cup\BestSegment\;
    }
    \caption{Computation of the optimal order of segments from a bookmark\label{sb:algo-optimal-order}}
\end{algorithm}

Sorting all the segments from the model would be an excessively time consuming computation.
To speed up this algorithm, we only sort the 200 first best segments, and we choose these segments among a filtered set of candidates.
To find those candidates, we reuse the ideas developed in Chapter~\ref{bi}.
We render the ``pixel to geometry segment'' and ``pixel to texture'' maps, as shown in Figure~\ref{sb:bookmarks-utility}.
These renderings allow us to know what geometry segment and what texture correspond to each pixel, and filter out useless candidates.

\begin{figure}[th]
    \centering
    \includegraphics[width=0.32\columnwidth]{assets/system-bookmarks/bookmark/ground-truth.png}
    \includegraphics[width=0.32\columnwidth]{assets/system-bookmarks/bookmark/geometry.png}
    \includegraphics[width=0.32\columnwidth]{assets/system-bookmarks/bookmark/texture.png}
    \caption{A bookmarked viewpoint (left), a pixel to geometry segment map (center), and a pixel to texture map (right)\label{sb:bookmarks-utility}}
\end{figure}

Figure~\ref{sb:precomputation} shows how this precomputation improves the quality of rendering.
Each curve represents the PSNR one can obtain by downloading a certain amount of data, and they show that, for the same amount of data downloaded, the optimized order reaches a higher PSNR than the greedy order, which means that its utility metric is more accurate.
This curve is averaged on all the 9 bookmarks of the scene: we decided the locations of the bookmarks and each bookmark faces an interesting object in the scene.

\begin{figure}[th]
    \centering
    \begin{tikzpicture}
        \begin{axis}[
                xlabel=Data downloaded (in B),
                ylabel=PSNR,
                no markers,
                cycle list name=mystyle,
                width=\tikzwidth,
                height=\tikzheight,
                legend pos=south east,
                xmin=0,
            ]

            \addplot table [x=x, y=y]{assets/system-bookmarks/precomputation/greedy.dat};
            \addlegendentry{\scriptsize Default order $\mathcal{U}$}
            \addplot table [x=x, y=y]{assets/system-bookmarks/precomputation/precomputed.dat};
            \addlegendentry{\scriptsize Proposed order $\mathcal{U}^*$}

        \end{axis}
    \end{tikzpicture}
    \caption{Impact of using the precomputed information of bookmarks to select segments to download\label{sb:precomputation}}
\end{figure}


\subsection{MPD modification}

\copied{}

We now present how to include bookmarks information in the Media Presentation Description (MPD) file.
Bookmarks are fully defined by a position, a direction, and the additional content needed to properly render and use a bookmark in a system consists in two files: a thumbnail of the point of view at the bookmark, along with the JSON file giving the optimal segment order for this viewpoint.
For this reason, for each bookmark, we create a separate adaptation set in the MPD\@.
The bookmarked viewpoint information is stored as a supplemental property.
Bookmarks adaptation set only contain one representation, composed of two segments: the thumbnail used as a preview for the desktop interface and the JSON file.

\begin{figure}[th]
    \lstinputlisting[%
        language=XML,
        caption={MPD description of a geometry adaptation set, and a texture adaptation set.},
        label=sb:bookmark-as,
        emph={%
            MPD,
            Period,
            AdaptationSet,
            Representation,
            BaseURL,
            SegmentBase,
            Initialization,
            Role,
            SupplementalProperty,
            SegmentList,
            SegmentURL,
            Viewpoint
        }
    ]{assets/system-bookmarks/bookmark-as.xml}
\end{figure}

An example of a bookmark adaptation set is depicted on Listing~\ref{sb:bookmark-as}.
The three first values in the supplemental property are the camera position coordinates, and the three last values are the target point coordinates.

\subsection{Loader modifications}

We build on the loader introduced in Algorithm~\ref{d3:next-segment} to implement a client adaptation logic.
We include a bookmark adaptation logic such that (i) when a bookmark is hovered for the first time, the corresponding images (see Listing~\ref{sb:bookmark-as}) are downloaded, and (ii) when a bookmark is clicked, we switch from utility $\mathcal{U}$ to optimized utility $\mathcal{U}^*$ to determine which segments to download next.

\begin{algorithm}[th]
    \SetKwInOut{Input}{input}
    \SetKwInOut{Output}{output}
    \Input{Current index $i$, time $t_i$, viewpoint $v(t_i)$, buffer of already downloaded  \texttt{segments} $\mathcal{B}_i$, MPD}
    \Output{Next segment $s^{*}_i$ to request, updated buffer $\mathcal{B}_{i+1}$}
    \SetAlgoLined%
    {- Estimate the bandwidth $\widehat{BW_i}$ and RTT $\widehat{\tau_i}$ \;}

    {-  Among all \texttt{segments} that are not already downloaded $s \in \mathcal{S} \backslash \mathcal{B}_i$, % \;}
   % {-
    keep the ones inside the upcoming viewing frustums $\mathcal{FC}=\mathbb{FC}(\widehat{v}(t_i)), t\in [t_i, t_i+\chi]$  thanks to a viewpoint predictor $t_i \rightarrow \hat{v}(t_i)$, a temporal horizon $\chi$ and a frustum culling operator $\mathbb{FC}$ \;}


    {- Optimize a criterion  $\Omega$ based on $\mathcal{U}$ values and well chosen viewpoint $v(t_i)$ to select the next segment to query }
   {\begin{equation*}
   s^{*}_i= \argmax{s \in \mathcal{S} \backslash \mathcal{B}_i \cap \mathcal{FC}}  \Omega_{\theta_i} \Big(\mathcal{U}(s,v(t_i))\Big) \label{sb:eq1}
   \end{equation*} \\
   given parameters $\theta_i$ that gathers both online parameters $(i,t_i,v(t_i),\widehat{BW_i}, \widehat{\tau_i}, \mathcal{B}_i)$ and offline metadata;}

    {- Update the buffer $\mathcal{B}_{i+1}$  for the next decision: $s^{*}_i$ and lowest \texttt{representations} of $s^{*}_i$ are considered downloaded\;}
     {- \Return{segment  $s^{*}_i$, buffer $\mathcal{B}_{i+1}$}\;}

    {\caption{Algorithm to identify the next segment to query\label{sb:next-segment}}}
\end{algorithm}

\todo[inline]{to be modified to include bookmarks}

