\fresh{}
\section{3D Streaming\label{sote:3d-streaming}}

In this thesis, our objective is to stream 3D scenes.
Even though 3D streaming is not the most researched field, special attention has been brought to 3D content compression, in particular progressive compression which is a premise for 3D streaming.
In the next sections, we review the 3D streaming related work, from 3D compression and structuring to 3D interaction.

\subsection{Compression and structuring}

According to \citep{maglo20153d}, mesh compression can be divided in four categories:
\begin{itemize}
    \item single-rate mesh compression, seeking to reduce the size of a mesh;
    \item progressive mesh compression, encoding meshes in many levels of resolution that can be downloaded and rendered one after the other;
    \item random accessible mesh compression, where parts of the models can be decoded in any order;
    \item mesh sequence compression, compressing mesh animations.
\end{itemize}

Since our objective is to stream 3D static scenes, single-rate mesh and mesh sequence compressions are less interesting for us.
This section thus focuses on progressive meshes and random accessible mesh compression.

Progressive meshes were introduced in~\citep{progressive-meshes} and allow a progressive transmission of a mesh by sending a low resolution mesh first, called \emph{base mesh}, and then transmitting detail information that a client can use to increase the resolution.
To do so, an algorithm, called \emph{decimation algorithm}, starts from the original full resolution mesh and iteratively removes vertices and faces by merging vertices through the so called \emph{edge collapse} operation (Figure~\ref{sote:progressive-scheme}).

\begin{figure}[ht]
    \centering
    \begin{tikzpicture}[scale=2]
        \node (Top1) at (0.5, 1) {};
        \node (A) at (0, 0.8)    {};
        \node (B) at (1, 0.9)    {};
        \node (C) at (1.2, 0)    {};
        \node (D) at (0.9, -0.8) {};
        \node (E) at (0.2, -0.9) {};
        \node (F) at (-0.2, 0)   {};
        \node (G) at (0.5, 0.5)  {};
        \node (H) at (0.6, -0.5) {};
        \node (Bottom1) at (0.5, -1) {};

        \node (Top2) at (3.5, 1)  {};
        \node (A2) at (3, 0.8)    {};
        \node (B2) at (4, 0.9)    {};
        \node (C2) at (4.2, 0)    {};
        \node (D2) at (3.9, -0.8) {};
        \node (E2) at (3.2, -0.9) {};
        \node (F2) at (2.8, 0)    {};
        \node (G2) at (3.55, 0)   {};
        \node (Bottom2) at (3.5, -1) {};

        \draw (A.center) -- (B.center) -- (C.center) -- (D.center) -- (E.center) -- (F.center) -- (A.center);
        \draw (A.center) -- (G.center);
        \draw (B.center) -- (G.center);
        \draw (C.center) -- (G.center);
        \draw (F.center) -- (G.center);
        \draw (C.center) -- (H.center);
        \draw (F.center) -- (H.center);
        \draw (E.center) -- (H.center);
        \draw (D.center) -- (H.center);
        \draw[color=red, line width=1mm] (G.center) -- (H.center);

        \draw (A2.center) -- (B2.center) -- (C2.center) -- (D2.center) -- (E2.center) -- (F2.center) -- (A2.center);
        \draw (A2.center) -- (G2.center);
        \draw (B2.center) -- (G2.center);
        \draw (C2.center) -- (G2.center);
        \draw (F2.center) -- (G2.center);
        \draw (E2.center) -- (G2.center);
        \draw (D2.center) -- (G2.center);
        \node at (G2) [circle,fill=red,inner sep=2pt]{};

        \draw[-{Latex[length=3mm]}] (Top1) to [out=30, in=150] (Top2);
        \draw[-{Latex[length=3mm]}] (Bottom2) to [out=-150, in=-30] (Bottom1);

        \node at (2,  1.75) {Edge collapse};
        \node at (2, -1.75) {Vertex split};


    \end{tikzpicture}
    \caption{Vertex split and edge collapse\label{sote:progressive-scheme}}
\end{figure}

Every time two vertices are merged, a vertex and two faces are removed from the original mesh, decreasing the resolution of the model.
After content preparation, the mesh consists in a base mesh and a sequence of partially ordered edge split operations.
Thus, a client can start by downloading the base mesh, display it to the user, and keep downloading refinement operations (vertex splits) and display details as time goes by.
This process reduces the time a user has to wait before seeing something, thus increases the quality of experience.

\begin{figure}[ht]
    \centering
    \includegraphics[width=\textwidth]{assets/state-of-the-art/3d-streaming/progressivemesh.png}
    \caption{Four levels of resolution of a mesh~\citep{progressive-meshes}}
\end{figure}

These methods have been vastly researched \citep{bayazit20093,mamou2010shape}, but very few of these methods can handle meshes with attributes, such as texture coordinates.

\citep{streaming-compressed-webgl} develop a dedicated progressive compression algorithm based on iterative decimation, for efficient decoding, in order to be usable on web clients.
With the same objective, \citep{pop-buffer} proposes pop buffer, a progressive compression method based on quantization that allows efficient decoding.

Following this, many approaches use multi triangulation, which creates mesh fragments at different levels of resolution and encodes the dependencies between fragments in a directed acyclic graph.
In \citep{batched-multi-triangulation}, the authors propose Nexus: a GPU optimized version of multi triangulation that pushes its performances to make real time rendering possible.
It is notably used in 3DHOP (3D Heritage Online Presenter, \citep{3dhop}), a framework to easily build web interfaces to present 3D models to users in the context of cultural heritage.

Each of these approaches define its own compression and coding for a single mesh.
However, users are frequently interested in scenes that contain many meshes, and the need to structure content emerged.

To answer those issues, the Khronos group proposed a generic format called glTF (GL Transmission Format,~\citep{gltf}) to handle all types of 3D content representations: point clouds, meshes, animated model, etc.\
glTF is based on a JSON file, which encodes the structure of a scene of 3D objects.
It contains a scene graph with cameras, meshes, buffers, materials, textures, animations an skinning information.
Although relevant for compression, transmission and in particular streaming, this standard does not yet consider view-dependent streaming which is required for large scene remote visualisation and that we address in our work.

% Zampoglou

\citep{zampoglou} is the first paper that proposes to use DASH to stream 3D content.
In their work, the authors describe a system that allows users to access 3D content at multiple resolutions.
They organize the content, following DASH terminology, into periods, adaptation sets, representations.
Their first adaptation set codes the tree structure of the scene graph.
Each further adaptation set contains both geometry and texture information and is available at different resolutions defined in a corresponding representation.
To avoid requests that would take too long and thus introduce latency, the representations are split into segments.
The authors discuss the optimal number of polygons that should be stored in a single segment.
On the one hand, using segments containing very few faces will induce many HTTP requests from the client, and will lead to poor streaming efficiency.
On the other hand, if segments contain too many faces, the time to load the segment will be long and the system loses adaptability.
Their approach works well for several objects, but does not handle view-dependent streaming, which is desirable in the use case of large NVEs\@.

\subsection{Viewpoint dependency}

3D streaming means that content is downloaded while the user is interacting with the 3D object.
In terms of quality of experience, it is desirable that the downloaded content is visible to the user.
This means that the progressive compression must allow a decoder to choose what it needs to decode, and to guess what it needs to decode from the users point of view.
This is typically called \emph{random accessible mesh compression}.
\citep{maglo2013pomar} is such an example of random accessible progressive mesh compression.
\citep{cheng2008receiver} proposes a receiver driven way of achieving viewpoint dependency with progressive mesh: the client starts by downloading the base mesh, and then is able to estimate the importance of vertex splits and choose which ones to download.
Doing so reduces drastically the server computational load, since it only has to send data, and improves the scalability of this framework.

In the case of streaming a large 3D scene, viewpoint dependent streaming is a must-have: a user will only be seeing one small portion of the scene at each time, and a system that does not adapt its streaming to the user's point of view is bound to have poor quality of experience.

A simple way to implement viewpoint dependency is to access the content near the user's camera.
This approach, implemented in Second Life and several other NVEs (e.g.,~\citep{peer-texture-streaming}), only depends on the location of the avatar, not on its viewing direction.
It exploits spatial locality and works well for any continuous movement of the user, including turning.
Once the set of objects that are likely to be accessed by the user is determined, the next question is in what order should these objects be retrieved.
A simple approach is to retrieve the objects based on distance: the spatial distance from the user's virtual location and rotational distance from the user's view.

More recently, Google integrated Google Earth 3D module into Google Maps.
Users are now able to go to Google Maps, and click the 3D button which shifts the camera from the top-down view.
Even though there are no associated publications, it seems that the interface does view dependent streaming: low resolution from the center of the point of view gets downloaded right away, and then, data farther away or higher resolution data gets downloaded since it appears in a second time.
The choice of the nearby can be based based on an a priori, discretized, partitioned version of the environment; for example, \citep{3d-tiles} developed 3D Tiles, is a specification for visualizing massive 3D geospatial data developed by Cesium and built on top of glTF\@.
Their main goal is to display 3D objects on top of regular maps.

\begin{figure}[ht]
    \centering
    \includegraphics[width=0.8\textwidth]{assets/state-of-the-art/3d-streaming/3dtiles.png}
    \caption{Screenshot of 3D Tiles interface~\citep{3d-tiles}}
\end{figure}

\subsection{Geometry and textures}

As discussed in Chapter~\ref{f:3d}, most 3D scenes consists in two main types of data: geometry and textures.
When addressing 3D streaming, one must handle the concurrency between geometry and textures, and a system needs to solve this compromise.

Balancing between streaming of geometry and texture data is addressed by~\citep{batex3},~\citep{visual-quality-assessment}, and~\citep{mesh-texture-multiplexing}.
Their approaches combine the distortion caused by having lower resolution meshes and textures into a single view independent metric.
\citep{progressive-compression-textured-meshes} also deals with the geometry / texture compromise.
This work designs a cost driven framework for 3D data compression, both in terms of geometry and textures.
This framework generates an atlas for textures that enables efficient compression and multiresolution scheme.
All four works considered a single, manifold textured mesh model with progressive meshes, and are not applicable in our work since we deal with large scenes with autointersections and T vertices.

Regarding texture streaming, \citep{simon2019streaming} propose a way to stream a set of textures by encoding the textures into a video.
Each texture is segmented into tiles of a fixed size.
Those tiles are then ordered to minimise dissimilarities between consecutive tiles, and encoded as a video.
By benefiting from the video compression techniques, they are able to reach a better rate-distortion ratio than webp, which is the new standard for texture transmission, and jpeg.
However, the geometry / texture compromise is not the point of that paper.

% \copied{}
% \subsection{Prefetching in NVE}
% The general prefetching problem can be described as follows: what are the data most likely to be accessed by the user in the near future, and in what order do we download the data?
%

%
% Other approaches consider the movement of the user and attempt to predict where the user will move to in the future.
% \citep{motion-prediction} and~\citep{walkthrough-ve} predict the direction of movement from the user's mouse input pattern.
% The predicted mouse movement direction is then mapped to the navigation path in the NVE\@.
% Objects that fall in the predicted path are then prefetched.
% CyberWalk~\citep{cyberwalk} uses an exponentially weighted moving average of past movement vectors, adjusted with the residual of prediction, to predict the next location of the user.
%
% \citep{prefetching-walkthrough-latency} cluster the navigation paths of users and use them to predict the future navigation paths.
% Objects that fall within the predicted navigation path are prefetched.
% All these approaches work well for a navigation path that is continuous --- once the user clicks on a bookmark and jumps to a new location, the path is no longer continuous and the prediction becomes wrong.
%
% Moving beyond ordering objects to prefetch based on distance only,~\citep{caching-prefetching-dve} propose to predict the user's interest in an object as well.
% Objects within AoI are then retrieved in decreasing order of predicted interest value to the user.
%
% % \cite{learning-user-access-patterns} investigates how to render large-scale 3-D scenes on a thin client.
% % Efficient scene prefetching to provide timely data with a limited cache is one of the most critical issues for remote 3-D data scheduling in networked virtual environment applications.
% % Existing prefetching schemes predict the future positions of each individual user based on user traces.
% % In this paper, we investigate scene content sequences accessed by various users instead of user viewpoint traces and propose a user access pattern-based 3-D scene prefetching scheme.
% % We make a relationship graph-based clustering to partition history user access sequences into several clusters and choose representative sequences from among these clusters as user access patterns.
% % Then, these user access patterns are prioritized by their popularity and users' personal preference.
% % Based on these access patterns, the proposed prefetching scheme predicts the scene contents that will most likely be visited in the future and delivers them to the client in advance.
%
% \citep{remote-rendering-streaming} investigate remote image-based rendering (IBR) as the most suitable  solution for rendering complex 3D scenes on mobile devices,  where the server renders the 3D scene and streams the rendered images to the client.
% However, sending a large  number of images is inefficient due to the possible limitations  of wireless connections.
% They propose a  prefetching scheme at the server side that predicts client  movements and hence prefetches the corresponding images.
%
% Prefetching techniques easing 3D data streaming and real-time rendering for remote walkthroughs are considered in~\citep{prefetching-remote-walkthroughs}.
% Culling methods, that don't possess frame to frame coherence, can successfully be combined with remote scene databases, if the prefetching algorithm is adapted accordingly.
% We present a quantitative transmission policy, that takes the limited bandwidth of the network and the limited memory available at the client computer into account.
%
% Also in the context remote visualization,~\citep{cache-remote-visualization} study caching and prefetching and  optimize configurations of remote visualization architectures.
% They aim at minimizing the fetch time in a remote visualization system and defend a practical infrastructure software to adaptively optimize the caching architecture of such systems under varying conditions (e.g.\ when network ressources vary).
%
