% This is "sig-alternate.tex" V1.9 April 2009
% This file should be compiled with V2.4 of "sig-alternate.cls" April 2009
%
% This example file demonstrates the use of the 'sig-alternate.cls'
% V2.4 LaTeX2e document class file. It is for those submitting
% articles to ACM Conference Proceedings WHO DO NOT WISH TO
% STRICTLY ADHERE TO THE SIGS (PUBS-BOARD-ENDORSED) STYLE.
% The 'sig-alternate.cls' file will produce a similar-looking,
% albeit, 'tighter' paper resulting in, invariably, fewer pages.
%
% ----------------------------------------------------------------------------------------------------------------
% This .tex file (and associated .cls V2.4) produces:
%       1) The Permission Statement
%       2) The Conference (location) Info information
%       3) The Copyright Line with ACM data
%       4) NO page numbers
%
% as against the acm_proc_article-sp.cls file which
% DOES NOT produce 1) thru' 3) above.
%
% Using 'sig-alternate.cls' you have control, however, from within
% the source .tex file, over both the CopyrightYear
% (defaulted to 200X) and the ACM Copyright Data
% (defaulted to X-XXXXX-XX-X/XX/XX).
% e.g.
% \CopyrightYear{2007} will cause 2007 to appear in the copyright line.
% \crdata{0-12345-67-8/90/12} will cause 0-12345-67-8/90/12 to appear in the copyright line.
%
% ---------------------------------------------------------------------------------------------------------------
% This .tex source is an example which *does* use
% the .bib file (from which the .bbl file % is produced).
% REMEMBER HOWEVER: After having produced the .bbl file,
% and prior to final submission, you *NEED* to 'insert'
% your .bbl file into your source .tex file so as to provide
% ONE 'self-contained' source file.
%
% ================= IF YOU HAVE QUESTIONS =======================
% Questions regarding the SIGS styles, SIGS policies and
% procedures, Conferences etc. should be sent to
% Adrienne Griscti (griscti@acm.org)
%
% Technical questions _only_ to
% Gerald Murray (murray@hq.acm.org)
% ===============================================================
%
% For tracking purposes - this is V1.9 - April 2009

\documentclass{sig-alternate}
  \pdfpagewidth=8.5truein
  \pdfpageheight=11truein

\usepackage{pstricks,pst-plot,pst-node,pst-tree}

\begin{document}
%
% --- Author Metadata here ---
\conferenceinfo{SAC'11}{March 21-25, 2011, TaiChung, Taiwan.}
\CopyrightYear{2011} % Allows default copyright year (2002) to be over-ridden - IF NEED BE.
\crdata{978-1-4503-0113-8/11/03}  % Allows default copyright data (X-XXXXX-XX-X/XX/XX) to be over-ridden.
% --- End of Author Metadata ---

\title{Improving 3D Navigation in Multiscale Environments Using Cubemap-based
Techniques}
% \subtitle{[Extended Abstract]
% \titlenote{A full version of this paper is available as
% \textit{Author's Guide to Preparing ACM SIG Proceedings Using
% \LaTeX$2_\epsilon$\ and BibTeX} at
% \texttt{www.acm.org/eaddress.htm}}}
%
% You need the command \numberofauthors to handle the 'placement
% and alignment' of the authors beneath the title.
%
% For aesthetic reasons, we recommend 'three authors at a time'
% i.e. three 'name/affiliation blocks' be placed beneath the title.
%
% NOTE: You are NOT restricted in how many 'rows' of
% "name/affiliations" may appear. We just ask that you restrict
% the number of 'columns' to three.
%
% Because of the available 'opening page real-estate'
% we ask you to refrain from putting more than six authors
% (two rows with three columns) beneath the article title.
% More than six makes the first-page appear very cluttered indeed.
%
% Use the \alignauthor commands to handle the names
% and affiliations for an 'aesthetic maximum' of six authors.
% Add names, affiliations, addresses for
% the seventh etc. author(s) as the argument for the
% \additionalauthors command.
% These 'additional authors' will be output/set for you
% without further effort on your part as the last section in
% the body of your article BEFORE References or any Appendices.

\numberofauthors{2} %  in this sample file, there are a *total*
% of EIGHT authors. SIX appear on the 'first-page' (for formatting
% reasons) and the remaining two appear in the \additionalauthors section.
%
\author{
% You can go ahead and credit any number of authors here,
% e.g. one 'row of three' or two rows (consisting of one row of three
% and a second row of one, two or three).
%
% The command \alignauthor (no curly braces needed) should
% precede each author name, affiliation/snail-mail address and
% e-mail address. Additionally, tag each line of
% affiliation/address with \affaddr, and tag the
% e-mail address with \email.
%
% 1st. author
\alignauthor
Daniel R. Trindade\\
      \affaddr{Tecgraf / Department of Informatics}\\
      \affaddr{Pontifical Catholic University of Rio de Janeiro}\\
      \email{danielrt@tecgraf.puc-rio.br}
% 2nd. author
\alignauthor
Alberto B. Raposo\\
      \affaddr{Tecgraf / Department of Informatics}\\
      \affaddr{Pontifical Catholic University of Rio de Janeiro}\\
      \email{abraposo@tecgraf.puc-rio.br}
}
% Just remember to make sure that the TOTAL number of authors
% is the number that will appear on the first page PLUS the
% number that will appear in the \additionalauthors section.


\maketitle
\begin{abstract}
Navigation in virtual 3D environments, especially those with multiscale
features, is still a problem for many users. In this regard, a good design of
the navigation interfaces is critical to ensure that the users navigate with the
best possible efficiency and comfort. In this paper, we present improvements
made to two well-known interfaces: \emph{fly}, including support to collision
treatment and automatic navigation speed adjustment in relation to scale, and
\emph{examine}, with automatic pivot point. Such techniques are based on the
\emph{cubemap} structure. Usability tests have shown a significant improvement
in the execution of navigation tasks.
\end{abstract}

% A category with the (minimum) three required fields
\category{I.3.6}{Computer Graphics}{Methodology and Techniques}[interaction techniques]
%A category including the fourth, optional field follows...
\category{I.3.7}{Computer Graphics}{Three-Dimensional Graphics and Realism}[virtual reality]

\terms{Image Factors, Experimentation}

\keywords{navigation, multiscale environments, cubemap}

\section{Introduction}
With the arrival of new technologies and the increasing processing power of
computers, larger and richer in detail 3D virtual environments are
becoming more common. Accordingly, several
navigation tools were created to allow users to explore these environments. However, despite the efforts of
researchers, navigation in virtual environments is still problematic for many
people.

%%%%% comentado em 28/10/10
% What in the real world is a natural procedure can lead
% to frustration in virtual ones.

There is a number of reasons for this. 
%For example, when using a navigation tool
%a person can expect a different behavior, either because the
%person lacks knowledge about the functioning of the tool or because the tool was
%not well designed \cite{fitz08}. In the latter case, this can result in tools
%that are difficult to use. 
A frequent problem is related to the type of
environment to be explored. Multiscale virtual environments \cite{perlin93}, for
instance, often require methods to allow the users to navigate through the
different scales of the environment. Multiscale environments are environments
that can provide information in different levels of detail, %. In other words, in
%these environments it is possible to view objects with different scales, 
from a single screw to an oil field spanning dozens of miles.

Our goal is to propose techniques that help users navigate through multiscale
environments. The solutions proposed should satisfy two main
requirements: a) being as automated as possible, demanding minimal intervention
by the user; and b) being independent from the type of model to be viewed, so
that new types of objects can be viewed in the future without the need to
develop new solutions. Moreover, the solutions are intended to work on desktop 
setups, using mouse and keyboard, as this setup is more common to most users 
\cite{santos09}.
%%% citacao sac

In this paper, we improve on two well known navigation
techniques. In the case of the \emph{fly} technique, we added collision support
and automatic speed adjustment in relation to the scale; in the
\emph{examine} technique we added a way to automatically determine the pivot
point. 
%%%%%%%%% comentado em 28/10/10 
% What these techniques have in common is that they are based on a
% structure called \emph{cubemap}, which has the purpose of creating an
% image-based representation of the environment in relation to the observer's
% position \cite{maccrae09}.

This paper is organized as follows. In Section 2 we present related work. The
cubemap concept is presented in Section 3. In Section 4, the navigation
techniques are described, and in Section 5 the results of usability
tests are presented. Section 6 concludes this article.

\section{Related Work}

%Navigation in virtual environments has been the object of study of many
%researchers. The main goal of most of these studies is to propose and analyze
%techniques that facilitate the task of exploring such environments. As an
%example, \cite{ware90} proposed three different navigation tools: \emph{eyeball
%in hand}, \emph{scene in hand}, and \emph{flying vehicle control}. They
%concluded that none of these three techniques by itself is able to fulfill all
%user needs. The same conclusion was reached by \cite{fitz08}, who analyzed the
%behavior of some users of 3D applications and introduced techniques aiming to
%improve the interface of some tools.  Also seeking to propose new interaction
%solutions, \cite{mack90} introduced the \emph{point of interest (POI)}
%technique, in which the user must first choose a destination point and then the
%camera starts to move toward the chosen point, changing its speed in relation to
%the remaining distance. \cite{desney01} proposed a hybrid solution in which the
%\emph{fly} and \emph{examine} tools are combined into a single interaction
%technique.

\emph{Multiscale environments} were first introduced in the works by Perlin and Fox 
\cite{perlin93} and Bederson et al.\cite{bederson94_a}, through the creation of
the \emph{Pad} and \emph{Pad++} interfaces, and have been the focus of study of
many researchers \cite{zhang09,furnas95,furnas98}. Kopper et al. \cite{kopper06} 
presented a system
that allows the user to navigate through the different scales of an environment.
The hierarchy of the scene models is used to define the \emph{levels of scale}.
However, on this approach the user is forced to issue a command to change 
between scales. Moreover, the adjustment of navigation parameters is only made at 
this time. Thus, one can say that the method proposed by Kopper et al. \cite{kopper06} 
is discrete in the sense that the different scale levels are
well defined regarding their form and their location in the hierarchy of the
scene. By contrast, the works presented by Ware and Fleet \cite{ware97} and 
McCrae et al.\cite{maccrae09} make continuous adjustments to the navigation 
parameters, and therefore the virtual
environments do not require a well defined hierarchy of levels of scale.
Ware and Fleet \cite{ware97} proposed adjusting the navigation speed of the \emph{fly} tool by
using the depth information present in the \emph{Z buffer}. To this effect, they
use the smallest value resulting from scanning 15 lines of the \emph{Z buffer}.
McCrae et al. \cite{maccrae09} constructed a representation of the environment called
\emph{cubemap}, which provides information that allows the adjustment of
parameters such as speed and clipping planes, as well as offering collision
support.

To deal with collisions, Baciu et al. \cite{baciu97,baciu98} presented image space based
techniques which consist of projecting the geometry onto an image using graphics
hardware and then checking for interference, usually by analyzing the \emph{Z
buffer}. Calomeni and Celes \cite{calomeni06} proposed the construction of 
a connectivity graph in
preprocessing time. Through this graph, they are able to move the camera in
order to avoid collisions with the environment. This concept was also explored
by Xiao and Hubbold \cite{xiao98}, who used force fields rather than a connectivity graph.
Nonetheless, a preprocessing stage is still required to compute the fields.
McCrae et al. \cite{maccrae09} proposed using a new structure, which they call \emph{cubemap},
to help construct the force map with higher resolution while eliminating the
preprocessing stage altogether.

The techniques introduced in the present paper are also based on the cubemap.
However, the approach taken to construct the cubemap and the navigation
techniques based on it had to be modified in order to fulfill the requirements
of our applications, as will be described in the following sections.


\section{The Cubemap}

The purpose of the cubemap, as proposed by McCrae et al. \cite{maccrae09}, is to provide information about the virtual
environment at a given moment. Given a camera position, this structure is constructed from 6
rendering passes, each in a different direction in order to cover the whole
environment. The FOV of the camera is $90^0$, therefore the combination of the 6
resulting frustums yields a cube. At each pass, a shader is used to calculate
the distance from the fragment generated to the camera. The computed distance
values are normalized in relation to the \emph{near} and \emph{far} values, and
stored in the \emph{alpha} channel of the positions related to the fragments.
Rendering is made in 32-bit float images. Such procedure is performed at each frame, or each time the camera position
changes. The image resolution used for rendering does not have to be high, since only an
estimation needs to be obtained.

The cubemap construction process we implemented differs from the one described
by McCrae et al. \cite{maccrae09} in two aspects: 1 - the orientation of the cubemap is the
same as that of the camera (McCrae et al. always used canonical directions);
2 - the \emph{RGB} channels of the images in the cubemap store a unit vector
pointing from the position of the generated fragment to the camera. The first
change was necessary to simplify the obtainment of the distance from the viewer
to the center of the screen, which will be important for the automatic speed
adjustment techniques of \emph{fly} (Section 4.1) and for the automatic
definition of the pivot point in \emph{examine} (Section 4.3). The second change
simplifies the construction of the force map to detect collisions (Section 4.2).

\section{Navigation Techniques}

In this section we will present the three improved navigation techniques.

\subsection{Fly with Automatic Speed Adjustment}
\label{sec:ajuste_vel}

Navigation speed is related to the scale of the environments to be explored.
Larger environments require faster speeds, while the opposite is more convenient
on smaller scales.
%  For instance, the camera speed is expected to be higher when
% navigating from one planet to another, but much lower when navigating from a 
% city to another.

In several applications, the scale of the virtual world does not change much and
is well known, allowing a fixed navigation speed to be used. This is
the case of many games, for instance. Multiscale environments,
however, require a way to estimate the current scale in
order to adjust the navigation speed accordingly.

McCrae et al. \cite{maccrae09} use $minDist$, the minimum distance in the cubemap, as an 
estimation to determine the current scale
the camera is at. Based on that, first we developed a \emph{fly} tool which
could be controlled by the user by pressing the arrow keys of the keyboard to
move the camera while guiding the direction of the motion with the mouse
movements. Navigation speed was adjusted automatically according to equation
\ref{eq:vel_nav}.
\begin{equation} \label{eq:vel_nav}
 V_{nav} = k \ minDist
\end{equation}
where $V_{nav}$ is the adjusted navigation speed and $k$ is a parameter of unit 1/s that
causes an increase or reduction in the acceleration applied to the camera. We
noticed that two situations caused discomfort and disorientation for some users. 
The first situation is when $k$ is too high. In this situation, when users move away 
from the geometry, the camera accelerates too quickly, producing an effect similar to 
teleporting and making users lose their location. The second situation happens for low $k$ 
values, which can considerably increase the time required to reach the intended destination, 
making the navigation tedious. Thus, the value of $k$ should be selected in a way that it 
balances these extreme situations.

In face of the difficulty of determining a value for $k$ that suited all users,
we decided to let the users define it manually, using the scroll button of the
mouse. However, this led to other problems. When navigating very close to an
object, some users increased the $k$ value to move faster but forgot to readjust
it when the camera was distant from the geometry, falling into the case where
$k$ is too high.

The situations described reveal a disadvantage of using only $minDist$ as an
estimation to adjust the speed: when $minDist$ is too low, it works as a break
even when the user wishes to move faster. For instance, when navigating through
a corridor, the user may experience slow navigation due to the closeness of the
walls. %Similarly, a tangential approximation to any object causes the same
%effect. 
Thus, it is convenient to use some other type of estimation.

With that goal in mind, we attempted to use the distance to the central point of
the screen. This seemed reasonable since this point represents momentarily
the location the user wants to reach. Therefore, navigation speed started to be
adjusted using $centerDist$, the distance from the camera to the center of the
screen, rather than $minDist$.

However, the use of $centerDist$ resulted in a strange behavior. The motion of
the camera ceased to be smooth and started to present peaks of speed, giving the
impression that it stopped or accelerated instantly. The reason for this can be
understood by observing the graph in Figure \ref{fig:minCenterCurve}. This graph
shows the behavior of the curves of the $minDist$ and $centerDist$ estimations
for one path followed by the camera in a time interval of around 6 seconds.
\begin{figure}[!h]
\centering
\input{figs/minCenterCurve}
\caption{Graph representing the behavior of the $minDist$ and $centerDist$
curves.}
\label{fig:minCenterCurve}
\end{figure}
It can be seen that the $minDist$ curve is smooth while the $centerDist$
curve is noisier, displaying some peak values that are completely inconsistent
with the general behavior of the curve. This is related to the freedom the
\emph{fly} tool gives to the user, who can turn the camera to any direction at
any time. At a given moment, the central point of the screen may fall on an
object that is distant from the camera. The user then can turn the camera almost
instantly toward a close-by object, leading the value of $centerDist$ to drop
abruptly.  This is reflected in the speed adjustment, creating a steep 
deceleration. % The opposite is also a problem. If, for example, the camera is
%inside an object and the user unwillingly points the camera toward an external
%point, the camera will be subject to a fast acceleration and will be thrown outside the
%object. 
These effects do not happen when $minDist$ is used as estimation because
it is independent from the orientation of the camera.

To avoid the situations caused by the peak values of the $centerDist$ curve, we
smoothened it by applying an \emph{exponential moving average (EMA)}:
\begin{equation}\label{eq:mme}
 EMA_{i} = EMA_{i-1} + A \ ( centerDist_{i} - EMA_{i-1} )  
\end{equation}
In equation \ref{eq:mme}, $EMA_{i}$ is the smoothed value of $centerDist_{i}$ at
instant $i$, $EMA_{i-1}$ is the value smoothed at instant $i-1$, and $A$ is a
constant that influences how smooth the new curve will be and how quickly this
curve will converge to the $centerDist$ values. The smaller $A$ is, the smoother
the curve will be and the higher the time needed for such convergence to take
place. The maximum value of $A = 1$ is equivalent to the original curve. Figure
\ref{fig:mme} shows the results of smoothening an interval of the $centerDist$
curve (represented by the darker line) for three different values of $A$.
\begin{figure}[!h]
\centering
\input{figs/mme}
\caption{Effect of applying the EMA to a curve.}
\label{fig:mme}
\end{figure}
By smoothening the $centerDist$ curve, we can use it to adjust the speed. 

But one last problem remained: when the camera was close to a geometry but
pointed to a location at a great distance, the navigation speed tended to
increase, albeit smoothly, until it converged to $centerDist$ again. In some
situations this can be undesirable from the user's point of view, such as when
the camera is inside an object but the user wishes to view its outer parts. In
this case, the user has to navigate out of the object and then point the camera
toward this object. During the procedure of navigating out of the object, the
camera might point to a location far away from the object for a time span
long enough to increase the speed too much. This is because the scale perception
provided by $minDist$ is no longer present. In such cases, $minDist$ acts as a
break, preventing the camera from moving far away too quickly.

To solve this final issue, values of $centerDist$ higher than $n~\times~minDist$ were discarded. 
This way, $minDist$ serves as a criterion to decide when a $centerDist$ value should or not be
considered inconsistent.

This solution reflects a hybrid use of the $minDist$ and $centerDist$
estimations: while $centerDist$ ensures that speed adjustment is closer to what
the user intends, $minDist$ acts as a break in cases when the speed would be too
high. The result is an increased comfort for the user when using this tool, as will be demonstrated by the usability tests.

\subsection{Collision Detection and Treatment} \label{sec:colision_detection}

Not allowing the camera to cut through objects in a virtual environment can
be crucial in some situations \cite{rocha08}. 
% citacao sac

%In immersive environments, for example, colliding
%with an object can halt the immersion and leave the user disoriented. Another
%situation is when a visualization involves a stereoscopy effect; in this case, a
%collision with an object in the scene can cause physical discomfort to the
%user's eyes. 
McCrae et al. \cite{maccrae09} used information from the distance cube to obtain a collision
factor that causes the camera to smoothly dodge the
closest objects. The idea is that each point in the cubemap located at a
distance smaller than a given radius $r$ produces a repulsion factor given by:
\begin{equation}\label{eq:colision_force}
 F(x,y,i) = w(dist(x,y,i)) \ norm(pos(x,y,i) - camPos)
\end{equation}
\begin{equation}\label{eq:penal_factor}
 w(d) = e^{\frac{(r - d)^2}{\sigma^2}}
\end{equation}
where $F(x,y,i)$ is the repulsion factor produced by point $p$ referring to
position $(x,y)$ of image $i$ of the cubemap. Value $dist(x,y,i)$ is the
distance from $p$ to the camera. The term $pos(x,y,i)$ is the position of $p$ in
world space, and $camPos$ is the camera position. Function $norm(v)$ indicates
the normalized vector of $v$. In equation \ref{eq:penal_factor}, $\sigma$ is a
parameter that indicates the smoothness of the collision factor. The higher
$\sigma$ is, the smoother will be the calculated factor. Considering a spherical
region with radius $r$ and centered on the camera position, equation
\ref{eq:penal_factor} results in determining a collision penalty that grows
exponentially from the moment when point $p$ enters this region.

The repulsion factors referring to equation \ref{eq:colision_force} are computed
for each position in the cubemap where $d < r$ and then are combined into a single
factor: 
% if the distance stored in the
% current position is smaller than $r$, then the corresponding point is inside the
% collision region, and a penalty is calculated for it according to equations
% \ref{eq:colision_force} and \ref{eq:penal_factor}. After doing this for all
% points, the results are combined into a single factor, given by the following
% equation:
\begin{equation}\label{eq:f_colisao}
 F_{collision} = \dfrac{1}{6 \ cubeRes^2} \sum_{x,y,i} F(x,y,i)
\end{equation}
where $cubeRes$ is the resolution of the distance cube.

When we applied the factor given by equation \ref{eq:f_colisao} to the camera,
the \emph{fly} tool behaved as described in the previous section: as the camera
moves, $F_{collision}$ ensured that it smoothly deviate the objects that crossed
its path. The behavior obtained is similar to the assisted navigation described
previously \cite{xiao98,calomeni06}, whereby the user can navigate through the
environment without worrying about choosing a collision-free path as the
system is in charge of this task. It is a different approach from the one used
by McCrae et al. \cite{maccrae09}, who employ $F_{collision}$ combined with the POI technique,
a more restrictive solution which does not give the user total control over
the camera when navigation is being performed.

\subsection{Examine with Automatic Pivot Point}

The \emph{examine} tool allows any object or location in the scene to be
inspected. Basically, its functioning corresponds to rotating the camera around
a point, called \emph{pivot point}. In our test application, drag movements
using the left mouse button made the camera rotate around the pivot  point,
which can be chosen by the user. Dragging vertically or horizontally with the
right mouse button caused the camera to zoom in or zoom out, respectively. When
the scroll mouse button is present, it can also be used for zoom operations.

The location of the pivot point is crucial for the proper functioning of the
\emph{examine} tool. If it is not specified correctly, the camera can display
behaviors which, from the user's point of view, would seem confusing. Figure
\ref{fig:centro_rotacao} illustrates two of these cases.
\begin{figure}[htb]
  \centering
  \includegraphics[scale=0.35]{figs/examine}\\
  \caption{Problems related to the pivot point: (i) pivot point located outside
the field of vision; (ii) pivot point mapped beyond the object.
}
  \label{fig:centro_rotacao}
\end{figure}
In case (i), the pivot point (referred to as \emph{pivot} in the image) is
located outside the user's field of vision, too distant from the object to be
inspected. When the \emph{examine} tool is used, a rotation (from camera 
position 1 to 2) is made around the
pivot which is mathematically correct. For the user, however, this operation
leads to a completely unexpected motion. This problem is worse when the pivot is
located at a great distance from the model: the greater the distance, the higher
the angular speed of the camera and, as a consequence, the bigger will be the
error perceived by the user. Informal observations showed that this situation
occurred rather often in our test application. In the case of (ii), the pivot is
within the viewing angle of the camera but is located outside the object of
interest. As can be seen in the image, $pivot$ is beyond the model, and the
rotation around it has the effect of a pan operation.

Analyzing these situations, it can be concluded that they are basically caused
by one reason: the pivot point is not located at a point corresponding to the 
object to be examined. %The correct functioning of the \emph{examine} tool depends 
%on not allowing this situation to happen, therefore it is important to identify 
%when it takes place.

Usually, 3D visualization applications that make use of the \emph{examine} tool
include a button (or any other interface item) that, when selected, allows a new
pivot point to be chosen. We observed that some people, even more
experienced users, at some point forgot to select an adequate pivot point before
starting to rotate around the object of interest.%This happens because, after a
%certain time using the application, users stop focusing on details of the
%interface and, naturally, transfer all of their attention to the virtual
%environment. 
This occurred especially when some users switched from the
\emph{fly} to the \emph{examine} tool, as they attempted to rotate the camera
around the object located in front of them before readjusting the pivot point.
And, even when the users did not forget to perform this last operation, they
reported feeling upset with the fact that they had to do it explicitly.

The solution we found for this was to automatically determine a pivot point at
the moment the \emph{examine} tool is activated. Using the point corresponding
to
the center of the screen as the new $pivot$, it is possible to establish a
behavior that seems natural from the user's point of view. All the user needs to
do is point the camera to the object of interest and then select the
\emph{examine} tool. It is reasonable to expect this to happen, as in most cases
the users only decide to examine an object once it is in front of them. However,
the object might not necessarily be located exactly in the direction of the
center of the screen; in fact, the pivot point could be mapped to an object
behind the one the user wishes to examine. In this case, the user would
experience the effect of a pan operation, as shown in (ii) in Figure
\ref{fig:centro_rotacao}. Another possibility is that the central point of the
screen does not correspond to any valid point in the geometry, and thus
determining $pivot$ is impossible. 

To avoid these problems, the smallest distance present on the front face of the
distance cube, $minFront$, is used. When the central point is not valid, $pivot$
is adjusted to the point that is $minFront$ away from the camera. This way, the
angular speed of the rotation of the \emph{examine} tool will be coherent with
the scale in which the camera is located, preventing it from making excessively
quick movements.

The $minFront$ estimation is also used when the pivot point is mapped to a
distant point located behind the object. In this case, $minFront$ can act as a
restriction in the sense of identifying and correcting situations that could
lead to an odd camera behavior. The idea is not to allow $pivot$ to be adjusted
to a point whose distance is greater than $k \times minFront$. This solution
does not solve the problem definitively, but reduces its effects adequately.

\section{User Tests}

The techniques presented in the previous section have as their main goal
on assisting the users in the task of exploring virtual environments. From the
user's point of view, this should result in a more comfortable navigation
experience and less prone to errors.

To verify this, usability tests were carried out with two groups of users, 
%one with 5 individuals and the other with 7 individuals, 
with the purpose of gathering their opinions about the solutions developed. 
%These tests were planned and conducted based on the orientations provided by \cite{tullis08}.

\begin{figure*}[ht]
  \centering
  \includegraphics[width=15.5cm,height=3.5cm]{figs/siviep1}\\
  \caption{SiVIEP: visualization of an oil enterprise. In the first image, a
complete oil field can be seen. Then the camera reaches the scale of a platform.
Finally, the interior of the platform can be navigated.}
  \label{fig:cenario_teste}
\end{figure*}

\subsection{Test Environment}

The tests were performed using the SiVIEP viewer, a project under development
by TecGraf in cooperation with Petrobras. SiVIEP supports a comprehensive
visualization of several types of models comprising an oil exploration and
production enterprise. For example, it is possible to load from oil platforms to
wells and reservoirs in a single scene (Figure \ref{fig:cenario_teste}). The main
characteristic of the virtual environments resulting from this
integration is that they are multiscale.

\subsection{User Profiles}

Twelve people were selected to carry out the tests. They were divided in two
groups: \emph{advanced users}, with experience in the use of 3D visualization
and 3D modeling applications who use this type of software at least once in a
month; and \emph{non-advanced users}, with little experience with 3D
visualization applications, except for some electronic games, and who do not use
3D visualization applications frequently.

From the 12 individuals, 7 were allocated in the first group and 5 in the second
group. All of them had the following characteristics in common: they were
between 20 and 30 years old, were males, and did not have any previous contact
with the application used in the tests. The individuals in the advanced group of 
users are herein called PA1 to PA7, while the test users in the
non-advanced group are identified as PN1 to PN5.

\subsection{Procedures Adopted}

Each person was first asked to read and sign a consent agreement to confirm
their commitment to taking the test. They were then given an overview of
SiVIEP, seeing a presentation of the application and its functionalities. The
test consisted basically in asking the subjects to use two different versions of
SiVIEP:
\begin{itemize}
 \item \emph{Automated}: this version supports the solutions discussed in the
preceding sections. The user does not have to worry about speed adjustment,
collisions are prevented automatically, and the explicit use of the pivot-point
tool is not necessary.
 \item \emph{Manual}: this version does not include any of the improved
techniques previously mentioned. The speed in the \emph{fly} tool must be
adjusted manually with the mouse scroll button, the user must be careful to
not collide with the models, and the pivot-point tool has to be used always
before beginning to inspect an object with the \emph{examine} tool.
\end{itemize}
Before each person started to use one of the versions, some instructions were
given about the functioning of the navigation tools in that version. In the
manual version, for instance, the users were asked to avoid crossing through the
models in the scene and instructed on how to make manual speed adjustments and
to operate the pivot-point tool. %In the case of the automated version, the
%users were informed that they did not have to worry about these aspects.

The test environment for both versions consisted of a scene containing two oil
extraction platforms, A and B, a certain distance apart from each other. The
camera was initially placed in a position where both platforms could be seen.
The users were asked to navigate to platform A using the \emph{fly} tool. Once
there, they had to explore the internal areas of the platform in order to select
any three objects to be inspected with the \emph{examine} tool. Finally, the
users were asked to navigate from platform A to platform B.

After using each version, the users were asked to answer a questionary aimed at gathering their impressions about the tools used. This questionary
consisted of the following statements: %, here identified as S1, S2, S3, S4 and S5:
\begin{itemize}
 \item S1: \emph{I did not have any difficulty with the speed adjustment of the
fly tool.}
 \item S2: \emph{I was able to perform the tasks without colliding with the
environment.}
 \item S3: \emph{I did not have any difficulty with the pivot-point tool.}
 \item S4: \emph{I did not feel disoriented at any moment when navigating
in the virtual environment.}
 \item S5: \emph{I felt comfortable using the navigation tools.}
\end{itemize}
Below each of these statements there was a scale of ten numbers, from 1 to 10, 1
meaning that the user disagrees completely with the statement and 10 meaning
that the user fully agrees with it. At the end of the form there was a blank
space where the users could textually describe their general impressions and
justify the grades given.

After both versions had been used, the users were asked to fill out a final
survey consisting of two written questions: %, identified as Q1 and Q2:
\begin{itemize}
 \item Q1: \emph{Which of the two approaches did you prefer: the automated
navigation techniques or the manual techniques? Why?}
 \item Q2: \emph{With regard to the approach you preferred, in your opinion
could something be improved? If affirmative, what is it and why would it need to
be improved?}
\end{itemize}

%Question Q1 was considered one of the most important in the test due to its
%conclusive nature. In this question, the person was encouraged to think about
%both versions and establish a mental comparison between the two experiences. 

Lastly, the order in which the versions were presented to each user was not the
same. The first person to take the test used the manual version first, and then
the automated one. The second took the test in the opposite order. This pattern
was followed until the last user. This measure was taken with the purpose of
minimizing the learning effect of using the first version over the second.

\subsection{Results}

\subsubsection{Non-Advanced Group}

Tables \ref{tab:results3} and \ref{tab:results4} show the results obtained after
the application of the tests to the group of non-advanced users. They include
the grades given by each individual to the 5 statements presented in the
previous section. Table \ref{tab:results3} provides the grades referring to the
use of the manual version, while Table \ref{tab:results4} contains the grades
given to the automated version. The final column in each table shows the average
grade for each statement. For a better view of the general results, these
averages are presented side by side in Figure \ref{fig:teste_usuario1}. The
confidence interval used in the generation of this graph was 90 \%.

\begin{table}[!htb]
\centering
\begin{tabular}[c]{|c|c c c c c|c|}
\hline
 & \scriptsize PN1 & \scriptsize PN2 & \scriptsize PN3 & \scriptsize PN4 & \scriptsize PN5 & \scriptsize Avg \\
\hline
\scriptsize S1     & \scriptsize 7   & \scriptsize 8   & \scriptsize 10  & \scriptsize 9   & \scriptsize 5   & \scriptsize 7.8 \\
\hline
\scriptsize S2          & \scriptsize 6   & \scriptsize 5   & \scriptsize 7   & \scriptsize 7   & \scriptsize 2   & \scriptsize 5.4 \\
\hline
\scriptsize S3          & \scriptsize 6   & \scriptsize 9   & \scriptsize 8   & \scriptsize 7   & \scriptsize 3   & \scriptsize 6.6 \\
\hline
\scriptsize S4          & \scriptsize 4   & \scriptsize 8   & \scriptsize 7   & \scriptsize 9   & \scriptsize 1   & \scriptsize 5.8 \\
\hline
\scriptsize S5          & \scriptsize 5   & \scriptsize 8   & \scriptsize 9   & \scriptsize 10  & \scriptsize 4   & \scriptsize 7.2 \\
\hline
\end{tabular}
\caption{Results of the usability test for the manual version (group of
non-advanced users).}
\label{tab:results3}
\end{table}

\begin{table}[!htb]
\centering
\begin{tabular}[c]{|c|c c c c c|c|}
\hline
 & \scriptsize PN1 & \scriptsize PN2 & \scriptsize PN3 & \scriptsize PN4 & \scriptsize PN5 & \scriptsize Avg \\
\hline
\scriptsize S1          & \scriptsize 9   & \scriptsize 10  & \scriptsize 10  & \scriptsize 10  & \scriptsize 9   & \scriptsize 9.6 \\
\hline
\scriptsize S2          & \scriptsize 10  & \scriptsize 10  & \scriptsize 10  & \scriptsize 10  & \scriptsize 10  & \scriptsize 10.0  \\
\hline
\scriptsize S3          & \scriptsize 10  & \scriptsize 8   & \scriptsize 10  & \scriptsize 10  & \scriptsize 10  & \scriptsize 9.6 \\
\hline
\scriptsize S4          & \scriptsize 10  & \scriptsize 10  & \scriptsize 9   & \scriptsize 10  & \scriptsize 10  & \scriptsize 9.8 \\
\hline
\scriptsize S5          & \scriptsize 10  & \scriptsize 9   & \scriptsize 10  & \scriptsize 10  & \scriptsize 10  & \scriptsize 9.8 \\
\hline
\end{tabular}
\caption{Results of the usability test for the automated version (group of
non-advanced users).}
\label{tab:results4}
\end{table}

\begin{figure}[htb!]
  \centering
  \includegraphics[width=6.8cm,height=3.2cm]{figs/teste_usuario_iniciante}\\
  \caption{Comparative results between the manual and the automated version
(non-advanced users.)}
  \label{fig:teste_usuario1}
\end{figure}

We applied a two-tailed paired t-test to compare the average of the results for
both versions. We obtained $t(4) = -6.43, p = 0.001$, which allows us to affirm
that this group preferred the automated version of the navigation. When using
the manual version, users complained especially about the difficulty to control
the camera speed in order not to collide with the environment. One of the users,
for instance, reported that ``the program is somewhat abrupt, which makes its
use difficult for someone who is not used to or does not have enough dexterity
for 3D games and software''. The lack of collision treatment caused situations
in which some people felt lost. When these situations occurred, 2 of the 5 users
mentioned that they would like to quit the task.

The written answers confirm the statistic results. For question $Q1$,
all users
in this group replied that they preferred the automated version rather than the
manual one. In the justifications, most users mentioned that the techniques
provided by the automated version made navigation simpler, less prone to errors,
and easier to control. As for question $Q2$, none of these users considered that
any improvement was necessary to their preferred version.

\subsubsection{Advanced Group}

Tables \ref{tab:results5} and \ref{tab:results6} show the results obtained after
the application of the tests to the group of advanced users. The results are
presented in the same format as those in the previous section. Figure
\ref{fig:teste_usuario2} also shows a comparison between the grades given to the
manual version and those given to the automated version. The confidence interval
was 90 \%.

\begin{table}[!htb]
\centering
\begin{tabular}[c]{|c|c c c c c c c|c|}
\hline
 & \scriptsize PA1 & \scriptsize PA2 & \scriptsize PA3 & \scriptsize PA4 & \scriptsize PA5 & \scriptsize PA6 & \scriptsize PA7 & \scriptsize Avg \\
\hline
\scriptsize S1          & \scriptsize 10  & \scriptsize 9   & \scriptsize 7   & \scriptsize 7   & \scriptsize 10  & \scriptsize 9   & \scriptsize 9   & \scriptsize 8.7 \\
\hline
\scriptsize S2          & \scriptsize 3   & \scriptsize 7   & \scriptsize 7   & \scriptsize 7   & \scriptsize 10  & \scriptsize 8   & \scriptsize 7   & \scriptsize 7.0 \\
\hline
\scriptsize S3          & \scriptsize 7   & \scriptsize 8   & \scriptsize 10  & \scriptsize 3   & \scriptsize 5   & \scriptsize 5   & \scriptsize 7   & \scriptsize 6.4 \\
\hline
\scriptsize S4          & \scriptsize 3   & \scriptsize 9   & \scriptsize 6   & \scriptsize 5   & \scriptsize 10  & \scriptsize 6   & \scriptsize 8   & \scriptsize 6.7 \\
\hline
\scriptsize S5          & \scriptsize 6   & \scriptsize 8   & \scriptsize 8   & \scriptsize 8   & \scriptsize 10  & \scriptsize 8   & \scriptsize 7   & \scriptsize 7.8 \\
\hline
\end{tabular}
\caption{Results of the usability test for the manual version (group of advanced
users).}
\label{tab:results5}
\end{table}

\begin{table}[!htb]
\centering
\begin{tabular}[c]{|c|c c c c c c c|c|}
\hline
 & \scriptsize PA1 & \scriptsize PA2 & \scriptsize PA3 & \scriptsize PA4 & \scriptsize PA5 & \scriptsize PA6 & \scriptsize PA7 & \scriptsize Avg \\
\hline
\scriptsize S1          & \scriptsize 7  & \scriptsize 5  & \scriptsize 10 & \scriptsize 5  & \scriptsize 9  & \scriptsize 9  & \scriptsize 9  & \scriptsize 7.7 \\
\hline
\scriptsize S2          & \scriptsize 10 & \scriptsize 9  & \scriptsize 9  & \scriptsize 10 & \scriptsize 10 & \scriptsize 9  & \scriptsize 10  & \scriptsize 9.6 \\
\hline
\scriptsize S3          & \scriptsize 10 & \scriptsize 6  & \scriptsize 6  & \scriptsize 10 & \scriptsize 10 & \scriptsize 9  & \scriptsize 10  & \scriptsize 8.7 \\
\hline
\scriptsize S4          & \scriptsize 6  & \scriptsize 9  & \scriptsize 7  & \scriptsize 10 & \scriptsize 10 & \scriptsize 8  & \scriptsize 9  & \scriptsize 8.4 \\
\hline
\scriptsize S5          & \scriptsize 10 & \scriptsize 6  & \scriptsize 9  & \scriptsize 9  & \scriptsize 10 & \scriptsize 9  & \scriptsize 9  & \scriptsize 8.9 \\
\hline
\end{tabular}
\caption{Results of the usability test for the automated version (group of
advanced users).}
\label{tab:results6}
\end{table}

\begin{figure}[htb!]
  \centering
  \includegraphics[width=6.8cm,height=3.2cm]{figs/teste_usuario_avancados}\\
  \caption{Comparative results between the manual and the automated version
(advanced users.)}
  \label{fig:teste_usuario2}
\end{figure}

We applied a two-tailed paired t-test to compare the average of the results for
both versions. We obtained $t(4) = -2.1, p = 0.09$, which does not allow us to
affirm that this group preferred the automated version of the navigation.
Nevertheless, as can be observed, the automated version received higher grades
in all statements with the exception of S1, which sought to evaluate the
automatic speed adjustment of the \emph{fly} tool. Analyzing the justifications
to the grades and the general comments made by each of these users revealed some
interesting points.

Almost all advanced users who gave a lower grade to the automatic speed
adjustment reported that, when getting very close to an object, the camera would
become too slow and it would take a while until they were able to move away from
the object again. These users felt impatient about this situation, and this
feeling was made worse by the fact that no control option was provided to allow
them to \emph{momentarily} increase the speed. Nonetheless, the same users noted
that the automatic adjustment was good because it allowed them to be less
concerned with the controls and helped them avoid some errors, which is in
agreement with the general comments made by the non-advanced users. In summary,
the advanced users wished they were offered some sort of control which allowed
them to make a more ``customized'' adjustment at certain moments, while at the
same time including automatic speed adjustment.

% Another factor that contributed to the higher grades given to the manual version
% in S1 was the manner in which the tests were conducted. Before the users began
% the test with the manual version, they were asked to avoid cutting through
% (colliding with) objects in the scene. This led them to be very cautious in
% relation to speed adjustment, thus avoiding possible difficulties they could
% face when using the manual version, which resulted in higher grades for this
% version. However, this had a negative impact on the comfort experienced by the
% users: in order to avoid colliding with the models, they were forced to stop
% often and readjust the navigation speed.

The greatest contributions of the automated version were related to statements
S2 and S3, which aimed at evaluating the efficacy of collision treatment and
automatic pivot point, respectively. %These two techniques were the ones that
%received most positive remarks in the general comments. 
The users could easily
notice the effects provided by these techniques and were very satisfied with
their results. Some users expressly stated that, thank to these techniques, they
did not make certain errors and were able to focus less on interface issues.
Finally, the grades given by the users in the advanced group to statements S4
and S5 demonstrate that they felt more comfortable and experienced less moments
of disorientation while using the automated version.
%, as was the case with the non-advanced users.

Regarding the final survey answered by the users, 6 out of the 7 advanced users
stated in Q1 that they preferred the automated version rather than the manual
one. Only user PA2 preferred the latter. In the justification, this user
mentioned the problem with the automatic speed adjustment and the lack of
feedback to the user about the location of the pivot point when using automatic
adjustment.

Finally, in question Q2, which asks for suggestions about what could be improved
in the preferred version, all of them asked for some kind of control that allows
them to momentarily increase the speed. This leads us to assume that advanced
users have a greater tendency to prefer solutions that make the tools simple to
use but that are not completely automated. The opposite might be said of
non-advanced users: due to their lack of experience, they prefer approaches that
minimize the need to adjust the parameters of the navigation tools.

\section{Conclusions}

This work presented some techniques to assist and facilitate the task of
navigating 3D virtual environments. They were based on the construction and
maintenance of a data structure called \emph{cubemap} 
\cite{maccrae09}. Improvements were proposed for the \emph{examine} tool, with
the addition of a way to automatically determine the pivot point, and for the
\emph{fly} tool, in which collision support and automatic speed adjustment in
relation to the scale were implemented.

To verify the efficacy of the solutions proposed, usability tests were
performed. The results allow us to conclude that the techniques presented
here improve the navigation experience of the users. From the 12 subjects of the
usability tests, 11 preferred the version of the application that included the
techniques proposed. In particular, the automatic adjustment of the pivot point
in the \emph{examine} tool and the collision support implemented in the
\emph{fly} tool had a significant positive impact in user experience.

Navigation in 3D environments still presents issues and is plenty of challenges.
Multiscale environments, which are becoming more common, bring further problems
to be solved in terms of navigation. We believe the techniques showed in this
work contribute toward providing solutions to some of the problems identified
regarding navigation in these environments. 

%ACKNOWLEDGMENTS are optional
\section{Acknowledgments}
% This section is optional; it is a location for you
% to acknowledge grants, funding, editing assistance and
% what have you.  In the present case, for example, the
% authors would like to thank Gerald Murray of ACM for
% his help in codifying this \textit{Author's Guide}
% and the \textbf{.cls} and \textbf{.tex} files that it describes.
The authors thank Petrobras for this research support and for the software
used in this research (SiVIEP). D. Trindade thanks CAPES and A. Raposo, 
FAPERJ (\#E-26/102.273/2009) for the individual support granted to this research.

%
% The following two commands are all you need in the
% initial runs of your .tex file to
% produce the bibliography for the citations in your paper.
\bibliographystyle{abbrv}
\bibliography{template}  % sigproc.bib is the name of the Bibliography in this case
% You must have a proper ".bib" file
%  and remember to run:
% latex bibtex latex latex
% to resolve all references
%
% ACM needs 'a single self-contained file'!
%
%APPENDICES are optional
%\balancecolumns
% \appendix
%Appendix A
% \section{Headings in Appendices}
% The rules about hierarchical headings discussed above for
% the body of the article are different in the appendices.
% In the \textbf{appendix} environment, the command
% \textbf{section} is used to
% indicate the start of each Appendix, with alphabetic order
% designation (i.e. the first is A, the second B, etc.) and
% a title (if you include one).  So, if you need
% hierarchical structure
% \textit{within} an Appendix, start with \textbf{subsection} as the
% highest level. Here is an outline of the body of this
% document in Appendix-appropriate form:
% \subsection{Introduction}
% \subsection{The Body of the Paper}
% \subsubsection{Type Changes and  Special Characters}
% \subsubsection{Math Equations}
% \paragraph{Inline (In-text) Equations}
% \paragraph{Display Equations}
% \subsubsection{Citations}
% \subsubsection{Tables}
% \subsubsection{Figures}
% \subsubsection{Theorem-like Constructs}
% \subsubsection*{A Caveat for the \TeX\ Expert}
% \subsection{Conclusions}
% \subsection{Acknowledgments}
% \subsection{Additional Authors}
% This section is inserted by \LaTeX; you do not insert it.
% You just add the names and information in the
% \texttt{{\char'134}additionalauthors} command at the start
% of the document.
% \subsection{References}
% Generated by bibtex from your ~.bib file.  Run latex,
% then bibtex, then latex twice (to resolve references)
% to create the ~.bbl file.  Insert that ~.bbl file into
% the .tex source file and comment out
% the command \texttt{{\char'134}thebibliography}.
% % This next section command marks the start of
% % Appendix B, and does not continue the present hierarchy
% \section{More Help for the Hardy}
% The sig-alternate.cls file itself is chock-full of succinct
% and helpful comments.  If you consider yourself a moderately
% experienced to expert user of \LaTeX, you may find reading
% it useful but please remember not to change it.
% %\balancecolumns % GM June 2007
% % That's all folks!
\end{document}
