%%% template.tex
%%%
%%% This LaTeX source document can be used as the basis for your technical
%%% paper or abstract. Intentionally stripped of annotation, the parameters
%%% and commands should be adjusted for your particular paper - title, 
%%% author, article DOI, etc.
%%% The accompanying ``template.annotated.tex'' provides copious annotation
%%% for the commands and parameters found in the source document. (The code
%%% is identical in ``template.tex'' and ``template.annotated.tex.'')



\documentclass[conference]{acmsiggraph}

\usepackage{algorithmic}
\usepackage[ruled]{algorithm2e}

\usepackage{array} % for defining a new column type
\usepackage{varwidth} %for the varwidth minipage environment
\usepackage{multirow}
%\usepackage{multicol}

\TOGonlineid{45678}
\TOGvolume{0}
\TOGnumber{0}
\TOGarticleDOI{1111111.2222222}
\TOGprojectURL{}
\TOGvideoURL{}
\TOGdataURL{}
\TOGcodeURL{}


\title{The Image Generalization Visibility Paradigm}

\author{\textit{withheld for double-blind review}}

\keywords{sample-based visibility, continuous visibility, aggressive visibility, exact visibility, visibility in dynamic scenes.}

\begin{document}

\teaser{
\includegraphics[width= 1.0\linewidth]{Fig1/ab}
\caption{\label{fig:1a}
 \textit{\textbf{Top}}: aggressive from-point visibility with quality guarantee: reference image where visible set is computed (left), frame with 17x zoom factor and 0.26\% error rendered from visible set (middle), and frame error visualization (right). \label{fig:1b} \textit{\textbf{Bottom}}: from-segment visibility: view segment (left), incorrect frame rendered from the triangles visible from the view segment endpoints (middle), and correct frame rendered from the visible set computed by our algorithm directly over the entire view segment (right).}
}


\maketitle

\begin{abstract}

We extend the visibility computation capability of conventional images in three ways: (1) by adding sampling locations to sample all triangles fragments, which guarantees that all triangles with a completely visible fragment are found, no matter how small their image footprint; (2) by adding sampling locations based on a visibility subdivision of the image, which completes the set of visible triangles efficiently; (3) and by generalizing the visibility sample at a sampling location from 0D to 1D and to 2D, which supports viewpoint translations and time changes. We have used the paradigm to develop a quality-guaranteed aggressive from-point visibility algorithm, an efficient exact from-point visibility algorithm, a from-segment and a from-rectangle visibility algorithm that are exact under view translation, and an over-time-interval visibility algorithm that is exact for a constant view. We have tested our visibility algorithms on a variety of complex static and dynamic scenes. Our paradigm compares favorably to the prior art approaches of sampling the high dimensional space of visibility parameters with conventional images or with individual rays that are defined by sampling locations placed heuristically.

\end{abstract}

\begin{CRcatlist}
  \CRcat{I.3.7}{Computer Graphics}{Three-Dimensional Graphics and Realism}{Visible line/surface algorithms}.
\end{CRcatlist}

\keywordlist

%% Use this only if you're preparing a technical paper to be published in the 
%% ACM 'Transactions on Graphics' journal.

\TOGlinkslist

%% Required for all content. 

\copyrightspace

\section{Introduction}
For complex scenes, the set of triangles visible from a view region is a small fraction of the total set, and therefore visibility is a powerful tool for reducing scene complexity. Visibility benefits virtually all computer graphics applications, including interactive applications where frame rate is at a premium, applications that require expensive rendering effects such as reflections, soft shadows, or motion blur, and applications where clients running on "thin" platforms have to render complex scenes hosted on remote servers. 

Visibility remains an open research problem despite decades of research. One approach evaluates visibility at a set of image plane sampling locations; the visible set is computed \textit{aggressively}, which means that the set contains \textit{only, but not all} visible triangles. The advantage is efficiency. However, prior sample-based visibility algorithms define sampling locations heuristically, and they do not provide any quality guarantee for the visible set they compute. A second approach performs a continuous visibility analysis of the image, subdividing it into regions where a single triangle is visible. The visibility subdivision provides the exact set that contains \textit{only and all} visible triangles. However, prior continuous visibility algorithms are inefficient as they construct the visibility subdivision from all triangles, with the hidden triangles being unnecessarily added temporarily to the visibility subdivision.



\newcolumntype{M}{>{\centering\arraybackslash} m{2.5cm}}
\begin{figure}[htb]
  \centering
 \includegraphics[width=1.0\linewidth]{NewFig45/1} 
  
  \caption{\label{fig:sphere}
          \textbf{Left}: reference image and image rendered from incomplete set of visible triangles found by reference image. \textbf{Right}:  sampling locations added (crosses) to sample all fragments. }
\end{figure}


We present a novel visibility paradigm based on image generalization, which combines the advantages and avoids the disadvantages of the two approaches described above. The paradigm is based on the observation that a conventional image is a powerful visibility computation tool: an image is computed efficiently using graphics hardware, and every image pixel finds a visible triangle. However, the visible set found by a conventional image is far from complete. First, triangles can have an arbitrarily small image footprint due to a high scene complexity, to a large distance to the eye, or to a grazing viewing angle. In Figure~\ref{fig:sphere} (left), the visible set found by the reference image of the finely tessellated sphere is incomplete, which results in severe artifacts when the set is used to render an image from the same viewpoint but with a slightly different view direction. Increasing the resolution of the reference image is only palliative: the image footprint of a visible triangle can be arbitrarily small, therefore an infinite resolution would be needed to guarantee that all visible triangles are found. Second, an image can rule a triangle as a visible, but it cannot rule a triangle as hidden. Whereas a single sample can be sufficient to verify that a triangle is visible, an infinite number of samples would be needed to verify that a triangle is hidden at all its points. Third, a conventional image finds visible triangles from a viewpoint and not from a view region, missing triangles that become visible as the viewpoint translates. Moreover, a conventional image only computes visibility for a single time point, missing triangles that becomes visible as time changes. We generalize images to remove these shortcomings. Our image generalization paradigm has three elements.

\textit{1. Finding all triangles with a completely visible fragment.} 
A fragment is defined as the convex polygonal intersection between a triangle projection and a pixel. Sampling locations are added to make sure that all fragments are sampled, which guarantees finding all triangles with a completely visible fragment, and which in turn guarantees finding all triangles of a front surface, no matter how small their footprint. For our sphere example, sampling all fragments finds all visible triangles at the cost of exactly one sampling location per fragment (Figure~\ref{fig:sphere}, right). Sampling locations are not added heuristically but rather deterministically, based on the scene geometry and on the pixel grid, to compute efficiently a quality-guaranteed aggressive visible set.

\textit{2. Finding all visible triangles.} Sampling all fragments does not guarantee finding all visible triangles since a partially visible fragment might be sampled at a point where the fragment is hidden. Starting from the aggressive visible set, sampling locations are added iteratively to determine the visibility of triangles that are not hidden by the known visible triangles. The algorithm computes and updates a visibility subdivision of the image based on the current set of visible triangles. No hidden triangle is ever added to the visibility subdivision. Because the starting set is almost complete, the visible set converges quickly to the exact set.

\textit{3. Finding all triangles visible at a sampling location.} When the viewpoint translates or when time changes in a dynamic scene, multiple triangles can be visible at a given image plane sampling location. We generalize the visibility sample captured by the sampling location from 0D to 1D, for computing visibility directly from a view segment or over a time interval, and to 2D, for computing visibility directly from a view rectangle. The sampling location does \textit{not} sample the space of visibility parameters exhaustively. The visibility changes are computed directly by solving visibility event equations, which guarantees the quality of the visibility solution, and which provides computation and storage efficiency.

\begin{figure}[htb]
\centering
\includegraphics[width= 1\linewidth]{Fig1/c2}
\caption{ \label{fig:1c}
Over-time-interval visibility in a dynamic scene: frame rendered from the particles visible at the time interval endpoints, with missing particles shown in red (left), and correct frame rendered from the visible particles computed by our algorithm directly over the entire time interval (right).}
\end{figure}

We have used the image generalization paradigm to develop four visibility algorithms. The first one is a quality-guaranteed aggressive from-point visibility algorithm. In Figure~\ref{fig:1a}, the algorithm computes the correct visibility over 99.93\% of the reference image. The aggressive set yields high quality frames even under substantial magnification of the reference image. The few incorrect pixels are at surface boundaries, and never inside visible surfaces, so the frames are virtually indistinguishable from truth. The second algorithm computes exact from-point visibility. The algorithm extends the aggressive set from Figure~\ref{fig:1a} to the exact set in three iterations. 

The third algorithm is an aggressive from-segment visibility algorithm that is exact under view translation. The algorithm computes the visible set directly over the entire view  segment by computing visibility exactly for each sampling location. A sampling location stores a 1D visibility sample that records all triangles visible as the viewpoint translates. When the view translates (and does not rotate or change focal length), the sampling locations do not change, and the visible set is exact. In Figure~\ref{fig:1b}, bottom, rendering an intermediate frame from the triangles visible at the endpoints of the view segment results in severe visibility artifacts, and the correct frame is obtained when using our algorithm. The same algorithm computes visibility over a time interval in a dynamic scene (Figure~\ref{fig:1c}). The fourth algorithm computes visibility directly over a view rectangle, and the algorithm is exact under view translation (Figure~\ref{fig:1d}).

Visibility is computed for a scene by subdividing the viewing volume into box-like cells, and the viewing time into intervals. A conventional image does not compute visibility adequately even for a single viewpoint and a single time point. Approximating from-cell and over-time visibility requires a large number of conventional images to sample the six-dimensional space of visibility parameters (two view direction rotations, three viewpoint translations, and time). Our paradigm increases the visibility computation power of images. Image generalization for exact from-point visibility alone reduces the dimensionality of the parameter space to four by eliminating the two view rotations; over-time-interval visibility eliminates the time parameter; from-rectangle eliminates two translations. From-cell visibility is approximated by aggregating the visible sets for the eight corners, the twelve edges, or the six faces of the cell. The more powerful the underlying image generalization, the more complete the resulting visible set, and the coarser the required subdivision of the viewing volume and time. We also refer the reader to the accompanying video.

\begin{figure}[htb]
\centering
\includegraphics[width= 0.9\linewidth]{Fig1/1d}

\caption{  \label{fig:1d}
From-rectangle visibility: error visualization for a frame rendered from the triangles visible from the view rectangle corners (top), and correct frame rendered from the visible set computed by our algorithm directly over the entire view rectangle (bottom).}
\end{figure}\



\section{Prior Work}

Visibility algorithms are classified based on the visible set they compute. \textit{Conservative visibility algorithms} overestimate visibility, such that no visible triangle is omitted. The benefit is an accurate image, but the number of hidden triangles unnecessarily included in the solution can be substantial ~\cite{ref1,ref2}. \textit{Aggressive visibility algorithms} underestimate the set of visible triangles, which leads to image errors. The goal of aggressive visibility research is to reduce and control the error ~\cite{ref3,ref4}. \textit{Exact visibility algorithms} find only and all visible triangles, which avoids the cost of rendering unnecessary triangles as well as any image error. 

\textit{Aggressive Visibility.} We distinguish between probing visibility by casting individual rays, and by rendering entire images. Algorithms in the first category use heuristics to shoot rays that are likely to find visible triangles, and subsequent sampling is guided by what the initial rays find e.g. ~\cite{ref4,ref5}. The advantage is the flexibility to cast precisely the rays deemed necessary, which limits sampling redundancy. However, it is difficult to place error bounds on the results. Moreover, casting individual rays can only be done efficiently with a hierarchical scene subdivision, which is difficult to extend to dynamic scenes.

Algorithms in the second category leverage the fact that the amortized cost of rays in an image is lower than that of individual rays. Our aggressive visibility algorithms fall in this category. An image only captures samples visible from its viewpoint. One option is to use images from additional viewpoints ~\cite{ref6}, which are highly redundant, or to eliminate redundancy as a pre-process ~\cite{ref9,ref10}. The challenge of these approaches is to decide which images are needed for a sufficient sampling of the visibility parameter space. The usual strategy is to sample uniformly "as densely as possible", and thus the visibility error is not bounded. Multiperspective images capture in a single shot more than what is visible from a single viewpoint through innovation at the camera model level ~\cite{yu2004general,cui2010curved}, but there is no quality guarantee on the visible set they gather.


Specialized visibility algorithms have been developed for many computer graphics contexts. The algorithms are typically aggressive, focusing on finding the visible triangles of highest relevance in the particular context. \textit{The semi-analytical visibility} algorithm ~\cite{ref12}, developed for motion blur, samples the image with lines as opposed to points, an idea from temporal antialiasing ~\cite{ref13}. Visibility is analyzed continuously over time for each line sample. The algorithm is aggressive because the analysis is restricted to lines in the image. Line samples are a brute force approach for improving uniform point sampling. The line parameter adds an expensive second dimension to the 1D motion blur visibility problem. The line sample pattern is fixed, so even after solving the higher-dimension visibility problem, there is still no guarantee for the quality of the solution. We propose deterministic point sampling that guarantees a quality visible set without increasing the visibility problem dimensionality.

\textit{Exact Visibility.} Early work focuses on from-point visibility for antialiasing. The solution was to compute a visibility partition for each pixel, defined by the triangle fragments visible at each pixel ~\cite{ref15,ref16,ref17}. The solution is inefficient because fragments of hidden triangles are added and then removed from the visibility partitions. Pixel-free from-point visibility algorithms are also inefficient because occluded intersections are computed (e.g. ~\cite{ref18}); typical running times are $O((n + k) \log n)$ or $O(n \log n + k + t)$ for n triangles with $k$ edge intersections and $t$ triangle intersections on the image plane. Output sensitive algorithms are restricted to special input ~\cite{ref19,ref20}. From-point visibility was implemented on the GPU ~\cite{ref21}, but the quadratic running time limits applicability to simple scenes.

Beam tracing ~\cite{ref22} analyzes visibility in 3D by partitioning the 2D space of rays defined by the viewpoint using conical or frustum-like beams. The unsampled gaps between rays are avoided, but beam-triangle intersection is costly. Beam-tracing has recently been used for shadow ~\cite{ref23,ref24} and sound ~\cite{ref25} rendering, using acceleration schemes based on adaptive beam splitting. Our paradigm bypasses the need for beams in from-point visibility: the beam is replaced with the smallest number of rays needed to capture the visible triangles over a solid angle. Moreover, we do not trace multi-dimensional rays but rather evaluate visibility over their sampling domain by projection.

One strategy for from-rectangle visibility is to decompose the 4D non-Euclidean space of lines in the dataset according to visibility criteria. A complete model with $O(n^4)$ complexity and output sensitive construction is yet to be practical ~\cite{ref26}. Another strategy is to compute visibility between pairs of polygons ~\cite{ref27,ref28,ref29}, using constructive solid geometry in the 5D ambient space of the Plucker coordinate representation of lines. The algorithms have high computational complexity and are not output sensitive.

\textit{Conservative Visibility} algorithms are exact algorithms that run on a visibility problem that was conservatively simplified, e.g. through extended projections ~\cite{ref31}, or occluder erosion ~\cite{ref33}. Our aggressive visibility algorithms produce a visible set that is almost complete, so adding to the set all triangles not hidden by the aggressive set yields a good conservative visible set (i.e. with only a small number of hidden triangles). Per-frame occlusion culling improves rendering performance by batch discarding triangles that are hidden in the current output frame ~\cite{ref36}. Triangles are grouped inside containers with simple geometry, the containers are rendered on a partial z-buffer of the output frame obtained from known big blockers, and the triangles of hidden containers are discarded. Occlusion culling methods can also be aggresive by fusing blockers ~\cite{ref35}. Grouping occluded and occluding geometry is heuristic, and it is particularly challenging in the case of dynamic scenes.

\textit{Irregular Framebuffers.} Our paradigm advocates abandoning the uniform sampling of conventional images in favor of adding sampling locations deterministically to guarantee that all visible triangles are found. The benefits of irregular framebuffers have been noted before in contexts that include: pixel-accurate shadow mapping ~\cite{new1}, where the shadow map estimates light visibility precisely at the point samples captured by the output image; point-based rendering ~\cite{new2}, where projected reference image samples are not clamped to the output image pixel grid but rather located precisely within the output image pixel using a pair of offsets; and focus plus context visualization where focus regions are sampled at a higher rate ~\cite{new3}.

\section{From-Point Visibility}

We have developed two from-point visibility algorithms based on our image generalization visibility paradigm: one aggressive, with a quality guarantee, and one exact.

\subsection{Aggressive}

The input to the algorithm is a viewpoint $o$, a conventional pixel grid that defines the reference image where visibility is computed, and a set of triangles. The output is a set of triangles visible from $o$ that is guaranteed to contain all triangles with a fragment that is completely visible from $o$. This includes all triangles of a front surface, no matter their footprint. The algorithm has three steps.

\begin{figure}[htb]
  \centering
  \includegraphics[width = 0.4\linewidth]{Fig5/Fig5}
  \caption{\label{fig:frompoint} Quality-guaranteed aggressive from-point visibility.}
\end{figure}


\textit{Step 1} computes the triangles that are visible at the pixel centers using a conventional rendering pass. In Figure~\ref{fig:frompoint}, the centers of pixels 0-3 are indicated with dots. The conventional image rendered finds triangles $a$ and $c$, but not $b$, even though $b$ is completely visible. 

\textit{Step 2} takes a second pass over the scene triangles adding sampling locations to sample all fragments. A fragment $f$ that does not already contain a sampling location generates a sampling location at its centroid $c_f$, unless the triangle of $f$ is hidden at $c_f$ by the triangle found at step 1. In Figure 5, $a$ generates one and $b$ four sampling locations (crosses); $d$ generates no sampling locations because its fragments in pixels 1 and 2 contain sampling locations that were added for $b$, and because $d$ is hidden by $a$ at the centroid of its fragment in pixel 0. 
 
\textit{Step 3} takes a third pass over the scene to find the triangles visible at each sampling location. Triangle projection proceeds as usual. Rasterization has to take into account that a pixel can have more than one sampling location. This implies that all pixels touched by the projection of a triangle have to be considered, and not just those whose centers are inside the projection. Furthermore, rasterization parameters (e.g. z, edge equation sidedness expressions) have to be evaluated for each sampling location of each pixel.
  
A sampling location is useful only if it reveals that its triangle is visible at that point. If the triangle is not visible at the sampling location, one cannot rule the triangle as hidden, and the sampling location is wasted. Step 1 computes a preliminary set of visible triangles efficiently, then step 2 avoids creating sampling locations that are already known not to be useful based on the preliminary set. If a pixel is completely covered by a visible triangle, the pixel will have only its initial sampling location at its center; the visible triangle is found at step 1, and all candidate sampling locations are discarded by the triangle at step 2. In our experiments, the number of sampling locations was linear in the number of visible fragments. 

\subsection{Exact}


\begin{algorithm}
  \caption{Exact from-point visibility}
\label{algorithm:exact}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{scene $S$, viewpoint $o$, aggressive visible set $V_0$; }
\Output{exact set of visible triangles $V$; }
\begin{algorithmic} [1]
 \STATE \textbf{Construct} initial visibility subdivision $VS$ from $V_0$\;
 \STATE \textbf{Initialize} $V$ = $V_0$, $U$ = $S-V_0$\;
 \WHILE{$U$ is not empty}
     \STATE \textbf{Remove} all sampling locations;
        \FORALL{triangles $t$ in $U$}
        \IF{$t$ is hidden by $VS$} 
        \STATE remove $t$ from $U$;
        \ELSE 
        \STATE add sampling locations for $t$ 
        \ENDIF
        \ENDFOR
        \STATE \textbf{Render} all triangles remaining in $U$;
        \STATE \textbf{Collect} newly found visible triangles $V_i$;
        \STATE \textbf{Update}$VS$ with $V_i$; $U$ = $U-V_i$; $V$ = $V+V_i$;
 \ENDWHILE
\end{algorithmic}
\end{algorithm}


We have developed an efficient algorithm that extends the aggressive visible set iteratively to the exact set (Algorithm~\ref{algorithm:exact}). The algorithm first constructs an initial visibility subdivision $VS$ of the image from the aggressive visible set $V_0$ received as input (1). $VS$ has polygonal regions where one or no triangles are visible. The region boundaries are the visible portions of the projected triangle edges.  Figure~\ref{fig:visibilityMap} illustrates the construction of a visibility subdivision. The visible set $V$ is initialized to $V_0$ and all other scene triangles are added to the set of undecided triangles $U$ (2). Then the algorithm iterates until there are no more undecided triangles (3-15). For each iteration, the algorithm first removes the sampling locations generated by the previous iteration (4), and then it processes the undecided triangles (5-11).


\begin{figure}[htb]
  \centering
   \begin{tabular}{>{\centering\arraybackslash}m{1.5cm} >{\centering\arraybackslash}m{1.5cm} >{\centering\arraybackslash}m{1.5cm} >{\centering\arraybackslash}m{1.5cm}}
  \includegraphics[scale=.7]{Fig6/vis1} &
  \includegraphics[scale=.7]{Fig6/vis2} &
  \includegraphics[scale=.7]{Fig6/vis3} &
  \includegraphics[scale=.7]{Fig6/vis4} 
\\(1) & (2) & (3) & (4)  \\

\end{tabular}
  \caption{\label{fig:visibilityMap} Triangle $a$ partially occluding $b$ (1), and visibility subdivision before (2), during (3) and after (4) adding $a$. }
\end{figure}


If an undecided triangle $t$ is hidden by the visibility subdivision, $t$ is removed from further consideration. If $t$ is not hidden in a visibility subdivision region $r$, the algorithm creates sampling locations at the vertices of $t$ that project in $r$, at the vertices of $r$ inside the projection of $t$, and at the intersection points of the edges of $r$ and the projected edges of $t$. In Figure~\ref{fig:add_to_vismap}.1, $t$ is hidden in regions $r_3$ and $r_4$, but not in $r_1$ and $r_2$, and six sampling locations are created.

\begin{figure}[htb]
  \centering
\begin{tabular}{ccc}
  \includegraphics[height = 0.225\linewidth]{Fig7/Classify1a} &
  \includegraphics[height = 0.225\linewidth]{Fig7/Classify2a} &
  \includegraphics[height = 0.225\linewidth]{Fig7/Classify3a} \\
(1) & (2) & (3)
\end{tabular}
  \caption{\label{fig:add_to_vismap} (1) six sampling locations, shown with dots, created for undecided triangle $t$ at first iteration (1), triangles $s$, $u$, and $v$ visible at those sampling locations (2), and eight sampling locations created for $t$ at second iteration (3).}
\end{figure}

After all undecided triangles are processed, the remaining undecided triangles are rendered over the new sampling locations they have generated (12), a step identical to step 3 of the aggressive algorithm. The visible triangles found by the sampling locations are used to update the visibility subdivision, they are removed from the undecided set, and they are added to the visible set (14). 

The algorithm is fast because the initial visible set is almost complete and most remaining triangles are hidden by the initial visibility subdivision. The visibility subdivision is built exclusively from visible triangles. Figure~\ref{fig:add_to_vismap} illustrates an unlikely scenario where a triangle remains undecided after an iteration: all sampling locations created for $t$ are won by other undecided triangles and more sampling locations are needed to decided $t$. In our experiments, the algorithm converged in three iterations or less, for scenes with tens of millions of triangles and with complex occlusion patterns.



\section{From-Segment Visibility}
We have developed an algorithm that computes visibility from a view segment directly. The input to the algorithm is a scene modeled with triangles, a view, and a view segment. The output is an aggressive approximation of the set of triangles visible from points on the view segment, with the following quality guarantees:

1.	The visible set contains all triangles $t$ that have a fragment $f$ at a pixel $p$ that is completely visible from any viewpoint on the segment from where $f$ exists (i.e. the projection of $t$ touches $p$). Like before, this guarantees that all triangles of a front surface are captured, no matter how small their footprint.

2.	The visible set contains all triangles visible at the pixel centers as the view translates from one segment endpoint to the other. This makes the algorithm exact under view translation. As the view translates along the view segment, the visible set produces correct frames from any intermediate viewpoint.

The algorithm has two stages. In the first stage, sampling locations are added to sample all triangle fragments. This is done like before by computing the image footprint of the triangle, by computing its fragments, and by adding a sampling location at the centroid of a fragment that does not already contain one. The only difference is that now the footprint of the triangle is the union of all triangle projections as the view translates.  We use a fast, tight, and conservative approximation of the triangle footprint as the convex hull of the six extremal vertex projections. In Figure~\ref{fig:segment} the projection of the triangle moves from $a_0b_0c_0$ to $a_1b_1c_1$,  and the convex hull $a_0b_0c_0a_1b_1c_1$ has six fragments, each with one sampling location.

\begin{figure}[htb]
  \centering
  \includegraphics[width = 0.5\linewidth]{Fig101/Fig101Visio_2}
  \caption{\label{fig:segment}Triangle footprint as the view translates. }
\end{figure}

The second stage uses the third element of our visibility paradigm to find all triangles that are visible at each sampling location, as the view translates. The translation along the view segment defines a one-parameter visibility change. The visibility sample of a sampling location is generalized from 0D to 1D to store a list of visibility intervals that define which triangle is visible at the sampling location and for which view sub-segment. The algorithm for the second stage takes a pass over the scene triangles. For each triangle $t$, the footprint of $t$ is approximated as described at stage 1, and then the visibility sample is updated for each sampling location inside the triangle footprint.

\begin{figure}[htb]
  \centering
  \includegraphics[width = 0.7\linewidth]{Fig71/Fig71_v2}
  \caption{\label{fig:d_interval} \textbf{Left}: triangles $d$ and $e$ move over a sampling location (cross). \textbf{Right}: visibility intervals at the sampling location. }
\end{figure}

In Figure~\ref{fig:d_interval}, left, two triangle projections $e$ and $d$ move over a sampling location as the viewpoint translates along the view segment. The translation is linear with parameter $t$. The graph (right) shows the depths $z$ from the viewpoint to the triangles, at the sampling location, as the viewpoint translates. The visibility intervals stored are shown on the abscissa. Initially the visibility sample of the sampling location is empty. After $d$ is processed, there is one visibility interval $[t_0, t_s]$ for $d$. After $e$ is processed, there are three visibility intervals: $[t_0, t_q]$ for $d$, $[t_q, t_r]$ for $e$, and $[t_r, t_s]$ for $d$.

Visibility changes at a sampling location when a moving projected triangle edge crosses the sampling location. Given two triangle vertices $a$ and $b$ and a sampling location $s$ with image plane coordinates $(u_s, v_s)$, we derive the condition that the projection of triangle edge $ab$ contains $s$. The coordinates $(u_a, v_a)$ of the projection of $a$ are computed by writing $a$ as a 3D point on the ray through $(u_a, v_a)$ at $w$ from viewpoint $v_0$:
\begin{eqnarray}
\label{eq1}
a=v_0+M\begin{bmatrix}u_a\\v_b\\1\end{bmatrix}w,\begin{bmatrix}u_a\\v_b\\1\end{bmatrix}w=M^{-1}(a-v_0)\\
u_a=\frac{m_0\cdot (a-v_0)}{m_2\cdot (a-v_0)},v_a=\frac{m_1\cdot (a-v_0)}{m_2\cdot (a-v_0)}
\end{eqnarray}

where $M$ is the camera matrix, and the rows of $M^{-1}$ are $m_i$. $s$ is on the projection of $ab$ if:
\begin{equation}
\label{eq2}
\frac{u_s-u_a}{u_s-u_b}=\frac{v_s-v_a}{v_s-v_b}
\end{equation}

\label{eq3}
By plugging in $u_a$ and $v_a$ from Eq.~\ref{eq1} into Eq.~\ref{eq3}, we obtain:
\begin{equation}
\label{eq3}
\frac{(u_sm_2-m_0) (a-v_0)}{(u_sm_2-m_0) (b-v_0)}=
\frac{(v_sm_2-m_1) (a-v_0)}{(v_sm_2-m_1)(b-v_0)}
\end{equation}

We target all possible view directions by running all visibility algorithms for each of the six faces of a cube map aligned with the world coordinate system. Consequently $M$ is constant. Since $m_i$, $v_s$, $u_s$, $a$ and $b$ are constant, and since $v_0$ is linear in $t$, Eq.~\ref{eq3} is quadratic in $t$. Eq.~\ref{eq3} is solved for each of the three edges of the triangle, the solutions in $[t_0, t_1]$ are kept and sorted to define the visibility intervals of the current triangle, and the visibility intervals are z-buffered with the previous visibility intervals at the sampling location. The depth $z$ from $v_0$ to the intersection of a triangle $abc$ and camera ray $r_s$ through $s$ is given by:
\begin{equation}
\label{eq4}
z=\frac{(a-v_0)\cdot n}{r_s \cdot n},n=(b-a)\times(c-a)
\end{equation}

Since $a$, $b$, $c$, $n$, and $r_s$ are constant, and since $v_0$ is linear in $t$, $z$ is linear in $t$. For scenes where triangles do not intersect, z-buffering two overlapping visibility intervals is simply done by evaluating the two depth functions at a $t$ inside the overlap. When triangles could intersect, the possible intersection between two triangles is found by solving the quadratic equation that results from setting their $z$'s (Eq.~\ref{eq4}) to be equal at the sampling location. The algorithm is exact per sampling location, where visibility is analyzed continuously over the view segment. Since the pixel centers are part of the sampling locations, the visible set contains all triangles visible at pixel centers as the view translates. View rotations and focal length changes modify the sampling locations defined by the view rays, therefore the algorithm is exact only under view translation.

\section{Over-Time-Interval Visibility}

The from-segment visibility algorithm can be used to compute the triangles visible over a time interval in a dynamic scene. The input is a dynamic scene modeled with triangles whose vertices move linearly over a time interval $[t_0, t_1]$, and a view $V$. The output is the set of triangles visible at the pixels of $V$ at any time in $[t_0, t_1]$. The visible set is exact for view $V$. 

Eq.~\ref{eq3} used to compute the visibility events remains a quadratic in $t$, as now vertices $a$, $b$, and $c$ are linear in $t$ and $v_0$ is constant. Eq.~\ref{eq4}  used to z-buffer the overlapping visibility intervals of two triangles is now a cubic in $t$ over a quadratic in $t$, as $n$ is quadratic in $t$. For applications where moving triangles do not intersect, such as for the finite element analysis (FEA) and the smoothed particle hydrodynamics (SPH) simulation applications used as examples in this paper, the depth functions are trivially evaluated to arbitrate between the two triangles. When triangles intersect, depth function equality results in an order five equation in $t$, which would have to be solved numerically.

The visible set is exact for the given view $V$ because visibility is computed exactly for each sampling location, including the pixel centers of $V$. Visibility at a sampling location is computed continuously over the time interval by solving visibility event equations. The algorithm computes not only what triangles are visible at each sampling location for $[t_0, t_1]$, but also what triangle is visible when, which provides perfect occlusion culling for any t in $[t_0, t_1]$.

\section{From-Rectangle Visibility}
We have used all three elements of our visibility paradigm to develop an algorithm for computing visibility directly over a view rectangle. The input to the algorithm is a scene modeled with triangles, a view, and a view rectangle. The output is an aggressive set of triangles visible from the view rectangle. The visible set provides the same guarantees as before: the set contains all triangles that have a completely visible fragment, and the algorithm is exact under view translation. The algorithm has two stages, similarly to the from-segment algorithm (Section 4).

In stage 1, sampling locations are added to a conventional image to ensure that all triangle fragments are sampled. The triangle footprint is approximated with the convex hull of the twelve extremal projections of the triangle vertices (i.e. one for each of the four corners of the view rectangle, for each of three vertices).

In stage 2 visibility is computed exactly for each sampling location with another pass over the scene triangles. For each triangle, the footprint is approximated as described for stage one, and the visibility samples of the sampling locations covered by the footprint are updated. The viewpoint translation inside the view rectangle is described with two parameters $v$ and $t$. Like before, visibility changes when a projected triangle edge crosses the sampling location. These visibility events are defined by lines in the 2D visibility parameter space $(v, t)$. The three edges of a triangle define three visibility event lines, which define a triangle in $(v, t)$. The triangle projection moving with two degrees of freedom in the image plane corresponds to a (static) triangle in the $(v, t)$ plane. This can also be thought of as an orthographic projection of the scene triangle with the set of parallel rays obtained by translating the sampling location ray with two degrees of freedom. We solve visibility exactly for each sampling location, by running our exact from-point visibility algorithm (Section 3.2) in the $(v, t)$ plane.

\label{fig:2D}
The table in Figure~\ref{fig:2D} (left) shows two triangle projections that move over a sampling location $s$ as the viewpoint translates over a view rectangle. The 3D graph (right) shows the depth $z$ at the sampling location as a planar function of the two translations, for each triangle. The $(v, t)$ plane (bottom of graph) shows the 2D visibility sample stored at the sampling location. 

\begin{figure}[htb]
  \centering
  \includegraphics[width = 1\linewidth]{Fig81/Fig81}
  \caption{\label{fig:2D}. Left: two triangles projections moving over sampling location $s$ as the view translates over a view rectangle $[v_0, v_1] \times [t_0, t_1]$. Right: $z$ planes of the two triangles as they move over the sampling location, and 2D visibility sample in the $(v, t)$ plane.}
\end{figure}

\section{Spherical Particles as Visibility Primitives}
We have described our visibility algorithms for scenes modeled with triangles. The algorithms support any geometric primitive that can be tessellated. We have extended our from-point, from-segment, and over-time-interval visibility algorithms to support spherical particles directly, without the cost of increasing the number of primitives through tessellation. The extension has to solve three problems: (1) deciding whether a particle covers a sampling location, which is done in 3D by checking whether the distance $d$ from the particle center to the sampling location ray is less than or equal to the particle radius $r$; (2) finding the visibility parameter values (translation or time) when a visibility event occurs, which is done by solving a quadratic equation that results from setting $d$ equal to $r$, and (3) finding the centroid of a particle "fragment", which is the projection of the particle center if the projection is inside the pixel, or else the average of the intersection points between the pixel frame and the particle projection. 

\section{Results and Discussion}
We have tested our visibility algorithms on a variety of scenes: \textit{Manhattan} (4.0Mtris, Figure~\ref{fig:1d}), \textit{Grass} (55Mtris, Figure~\ref{fig:1a}), \textit{Forest} (47Mtris, Figure~\ref{fig:1b}), \textit{Isosurface} (500Mtris, Figure~\ref{fig:102}), \textit{Water} (2.1M spherical particles over 80 states, Figure~\ref{fig:1c}), \textit{Impact} (2Mtris over 134 states,  Figure~\ref{fig:102}), \textit{Fusion} (500K spherical particles over 100 states, Figure~\ref{fig:102}). We organize the presentation and discussion of our results in four subsections: quality, efficiency, comparison to prior art methods, and limitations.

\begin{figure}[htb]
\centering
\includegraphics[width= 1\linewidth]{Fig102/fig102}
\caption{  \label{fig:102}
\normalfont{Isosurface, Impact}, \textit{and}  Fusion \textit{scenes}.}
\end{figure}

\subsection{Quality}


\newcolumntype{M}{>{\centering\arraybackslash} m{1.0cm}}
\newcolumntype{N}{>{\centering\arraybackslash} m{0.7cm}}
\newcolumntype{O}{>{\centering\arraybackslash} m{0.9cm}}
\newcolumntype{P}{>{\raggedright\arraybackslash} m{2.1cm} @{}}


\textit{From-point visibility.} The quality of the visibility solution computed by our aggressive from-point visibility algorithm is summarized in the top three rows of Table~\ref{table:1}. Visibility completeness (row 1) is defined as the percentage of image area for which visibility is fully resolved by the aggressive set. Let $S^*$ and $S$ be the visibility subdivisions of the image induced by the aggressive and exact sets. Then visibility completeness is computed as the sum of the areas of the regions in $S$ for which $S^*$ provides the correct visible triangle. As seen from the table, the aggressive visible set all but completes the visibility subdivision of the image.

\begin{table}[ht]
\caption{\label{table:1}
Quality and efficiency of from-point visibility algorithms.}
\small
\hfill{}
\begin{tabular}[c]{>{\bfseries}P|M|N|N|O|N }
\hline
\hline
        
~ & {\textbf{Manhattan}} & {\textbf{Grass}} & {\textbf{Forest}} & {\textbf{Isosurface}} & {\textbf{Water}} \\ \hline
1. Completeness & 99.9\% & 99.9\%  & 98.1\% & 99.7\%  & N/A \\  \hline
2. Frame err. (avg)&      0.03\% & 0.11\%  & 2.11\% & 0.27\% & 0.09\%\\ \hline
3. Frame err. (max)& 0.08\% & 0.20\% & 3.0\% & 0.61\% & 0.13\%  \\ \hline
4. S.L. / pix (avg) & 1.6  & 5.7 & 24  & 209 & 2.0\\ \hline
5. S.L. / pix (max) & 57  & 1,490 & 1,245 & 1,670 & 27\\ \hline
6. Time A [s] & 31  &  31  & 347   & 8,008 & 8.1 \\ \hline \hline
7. Iterations & 2 & 3 & 3 & 3 & N/A  \\ \hline
8. Time E [s]& 5.8 & 22 & 1,078 &  146 & N/A \\\hline
     
\hline
\end{tabular}
\hfill{}
\end{table}

%Table might need to be full page width
%Caption: Table 1: Quality and efficiency of from-point visibility algorithms.
%Columns: Row number, Manhattan downtown and midtown, Grass low and high, Forest, Impact outside and inside, Water, Fusion. Under each column reference an appropriate figure from the paper.
%Rows: Visibility correctness, Avg. pixel error, Max. pixel error
%double line
%Rows: Avg S.L. / pix, Max S.L. / pix, Time
%double line
%Rows: Iterations, Time

We have also estimated the quality of the algorithm by measuring the average and maximum per frame percentages of incorrect pixels over typical paths with thousands of frames. Both the reference image and the output frames have a resolution of $1,280 \times 720$. The errors are small, even though the paths include zooming in. The maximum zoom-in factors for the \textit{Manhattan}, \textit{Grass}, and \textit{Forest} paths were $7\times$, $17\times$, and $10\times$. The errors only occur in between surfaces, which makes them less noticeable.

The exact from-point visibility algorithm supports rendering correct frames with any view direction and any zoom factor. We have developed a robust implementation of the algorithm based on a perturbation technique that evaluates control logic predicates correctly and without special handling of individual types of degeneracies ~\cite{SM13}. We start by perturbing the triangle vertex coordinates by an amount that is negligible in terms of visibility solution but sufficient to avoid degeneracies (i.e. $10^{-8}\%$ of the diameter of the scene). We evaluate predicates with floating point interval arithmetic, which provides an interval that contains the true value of the predicate. The sign of the predicate is determined unless the interval contains zero. We resolve such ambiguous cases by increasing the precision of the interval arithmetic, and thus shrinking the interval, until zero is excluded. The extended precision arithmetic is implemented with the MPFR library~\cite{FL07}. Although it is costly, ambiguity is rare due to perturbation, so the overall efficiency is high.

\textit{1D visibility.} We solve from-segment visibility and over-time-interval visibility with an algorithm that computes 1D visibility samples directly over the entire visibility parameter domain (i.e. translation or time). The algorithm computes visibility exactly for each sampling location, by z-buffering visibility intervals. The resulting visible set is therefore exact when the sampling locations do not change, as is the case when the view translates along the segment for from-segment visibility, or when the view does not change for over-time-interval visibility. Table~\ref{table:2} gives the error if instead of using our 1D visibility algorithm one approximates the visible set by unioning the two visible sets computed for the endpoints of the visibility parameter domain (i.e. view segment or time interval). The error is given as the average and maximum percentage of incorrect pixels per frame over a sequence of 1,000 frames uniformly sampling the visibility parameter domain.

\newcolumntype{M}{>{\centering\arraybackslash} m{0.5cm}}
\newcolumntype{N}{>{\centering\arraybackslash} m{0.8cm}}
\newcolumntype{C}{>{\centering\arraybackslash} m{1.0cm}}

\begin{table}[h]
\center
\caption{\label{table:2}
Incorrect pixels when using union of endpoint visible sets. Our 1D visibility algorithm is exact in these cases.}
\small
\hfill{}
\begin{tabular}{M|M|M|C|N|M|M|}
\cline{2-7}
       & \multicolumn{3}{c|}{\textbf{From segment endpoints}     }                              & \multicolumn{3}{c|}{\textbf{From time interval endpoints}    }                          \\ \cline{2-7}
                           & \textbf{Forest} & \textbf{Grass} & \textbf{Manhattan} & \textbf{Impact} & \textbf{Water} & \textbf{Fusion} \\  \hline
\multicolumn{1}{|c|}{\textbf{Avg.}} &        26\%    &    46\%       &          2.5\%       &  0.093\%         &     0.17\%     &       0.66\%     \\ \hline
\multicolumn{1}{|c|}{\textbf{Max.}} &        34\%   &    50\%        &            5.2\%     &    0.34\%           &   0.35\%      &        0.91\%        \\ \hline
\end{tabular}
\end{table}


The from-segment algorithm supports any segment length. The longer the segment, the bigger the benefit of the algorithm compared to simply computing visibility at the segment endpoints, but also the less efficient the algorithm becomes as discussed below. The over-time-interval algorithm is run for time intervals that are short enough for the motion of triangle vertices to be approximately linear over the interval. The scenes used here were animated by numerical simulation codes that define these intervals implicitly in between simulation states.



\textit{From-rectangle visibility.} Table~\ref{table:3} reports the quality of the visible set computed by our from-rectangle visibility algorithm. The scene is $Manhattan$ and the output resolution is $1,280 \times 720$. The algorithm is compared to running the exact from-point algorithm from the corners of the view rectangle and unioning the resulting four visible sets. The error is given as the average and maximum number of incorrect pixels over two paths of 10,000 frames each, which sample the view rectangle. For the first path the view only translates, and for the second path the view translates and rotates. The view-rectangle algorithm is exact under view translation and it has substantially smaller errors than the four-corners algorithm when the view also rotates.

\begin{table}[h]
\center
\small
\caption{\label{table:3}
Quality of from-rectangle visibility algorithm.}
\begin{tabular}{c|c|c|c|c|}
\cline{2-5}
                                             & \multicolumn{2}{c|}{\textbf{From-rectangle}} & \multicolumn{2}{c|}{\textbf{From rectangle corners}} \\ \cline{2-5} 
                                             & Avg.             & Max.             & Avg.             & Max.             \\ \hline
\multicolumn{1}{|c|}{\textbf{Tanslation only}}        & 0             & 0                & 202              & 362              \\ \hline
\multicolumn{1}{|c|}{\textbf{Translation + rotation}} & 0.01             & 1                & 274              & 948              \\ \hline
\end{tabular}
\end{table}


\subsection{Efficiency}

The efficiency of our aggressive from-point visibility algorithm is summarized in rows 4-6 of Table~\ref{table:1}. The number of sampling locations per pixel (rows 4-5) depends on the average image footprint of the triangles, and on the presence of large blockers, and therefore it is small for scenes like $Manhattan$ and large for scenes like $Isosurface$. The running times (row 6) were measured for a \textit{serial} implementation on a 3.16GHz X5460 Intel workstation, and are all below 6min except for \textit{Isosurface} where the average number of sampling locations per pixel is 209.

The efficiency of our exact from-point visibility algorithm is summarized in rows 7-8 of Table~\ref{table:1}. The algorithm converges in at most three iterations (row 7), even for the \textit{Grass} and \textit{Forest} scenes which have tens of millions of triangles and complex occlusion patterns. The sampling locations generated based on the visibility subdivision (Figure~\ref{fig:add_to_vismap}) are very likely to resolve the visibility of an undecided triangle $t$ by verifying that $t$ is visible or by finding the triangle that occludes $t$. The running time (Time E, row 8) does not include the time for computing the starting aggressive visible set (Time A), and it was measured for a parallel implementation executed on 32 2.27GHz X7560 Intel cores. The algorithm is parallelized by subdividing the $1,280 \times 720$ reference image into  $16 \times 16$ tiles, and by assigning the tiles to cores in round robin fashion.

The running times of our from-segment and our over-time-interval visibility algorithms are given in Table~\ref{table:4}. For the over-time-interval algorithm the times given are the sum of all times over all intervals (i.e. 134, 80, and 100 intervals for the \textit{Impact}, \textit{Water}, and \textit{Fusion} scenes). The times were measured for a parallel implementation that tiles the reference image, run on 4 3.16GHz X5460 Intel cores. Interval z-buffering uses a binary search tree and has an $O(n\log n)$ running time for a sampling location with $n$ intervals.



\begin{table}[h]
\center

\caption{\label{table:4}Running times in minutes for our 1D visibility algorithm.}
\small
\hfill{}
\begin{tabular}{M|M|M|C|N|M|M|}
\cline{2-7}
      & \multicolumn{3}{c|}{\textbf{From-segment}}                                   & \multicolumn{3}{c|}{\textbf{Over-time-interval}}                              \\ \cline{2-7} 
                           & \textbf{Forest} & \textbf{Grass} & \textbf{Manhattan} & \textbf{Impact} & \textbf{Water} & \textbf{Fusion} \\ \hline
\multicolumn{1}{|c|}{\textbf{Time}} &        34    &   120       &         20       &  34         &     12      &     75      \\ \hline
\end{tabular}
\end{table}


The running time of our from-rectangle visibility algorithm was 23h for the \textit{Manhattan} scene for a parallel implementation that tiles the reference image, run on 20 2.53GHz E5649 Intel cores.


\subsection{Comparison to Prior Art Methods}

We compare the visibility computation capability of our image generalization paradigm to two prior art approaches.

The first prior art approach is the use of conventional images to aggregate an approximate visibility solution by uniformly sampling the high-dimensional space of visibility parameters. We compared our from-point visibility algorithms to computing visibility with a conventional image of ultra-high resolution, i.e. $ 32 \times 1,280 \times  32 \times 720$. This corresponds to a $32 \times 32$ uniform supersampling of the reference image used by our visibility algorithms. Even at the prohibitive cost of 1,024 samples per pixel, the conventional image fails to find all visible triangles: the average pixel errors for the cases used in Table~\ref{table:1} are 0.015\%, 0.0078\%, 0.11\%, 0.25\%, and 0.0001\%. Our exact from-point visibility algorithm produces correct frames. For the \textit{Manhattan} scene our aggressive algorithm yields a 0.03\% frame error with 1.6 sampling locations per pixel, compared to the 0.015\% error for the high resolution image with 1,024 sampling locations per pixel.

We compared our 1D visibility algorithm to sampling the visibility parameter domain, i.e. the view segment or the time interval. Even when the domain is sampled densely, the quality of the aggregate visibility solution is low. For example, for the \textit{Forest} (Table~\ref{table:3}), aggregating the visibility solution from 40 points on the view segment reduces the average error only to 4.9\%, whereas our algorithm yields error-free frames. Similarly, we have compared our from-rectangle visibility algorithm to aggregating visibility from $50 \times 50$ conventional images supersampled by a factor of $32 \times 32$, rendered from viewpoints that sample the view rectangle uniformly. Again, the extensive uniform sampling of the visibility parameter domain failed to find all visible triangles (average and maximum frame errors of 2.5 and 41 pixels). Our algorithms do not search for the visible triangles blindly, through uniform sampling of the visibility parameter domain, but they rather find the visible triangles directly, by computing the visibility parameter values where visibility changes occur, through visibility event equations.

The second prior art approach to which we compare our image generalization paradigm for visibility is \textit{adaptive global visibility sampling} (AGVS) ~\cite{ref5}, which relies on individual rays to sample the space of visibility parameters heuristically. Table 5 gives the average and maximum frame errors obtained for a path with 10,000 frames through a box-like view cell in the \textit{Manhattan} scene. Our paradigm performs substantially better even when we only compute visibility at the eight corners of the view cell. The errors are further reduced when our more powerful visibility algorithms are used for the edges and the faces of the view cell.

\begin{table}[h]
\center
\small
\caption{\label{table:5} Incorrect pixels per frame for prior and our approach.}
\begin{tabular}{c|c|c|c|c|}
\cline{2-5}
                           & \multirow{2}{*}{\textbf{AGVS}} & \multicolumn{3}{c|}{\textbf{Image Generalization paradigm}} \\ \cline{3-5} 
                           &                       & \textbf{ 8 corners  }        & \textbf{ 12 edges  }        & \textbf{ 6 faces }         \\ \hline
\multicolumn{1}{|c|}{\textbf{Avg.}} & 435                   & 21               & 4.9            & 0.56           \\ \hline
\multicolumn{1}{|c|}{\textbf{Max.}} & 3,198                  & 210              & 124            & 21             \\ \hline
\end{tabular}
\end{table}


\subsection{Limitations}

The current implementation of our aggressive from-point visibility algorithm has a running time quadratic in the number of sampling locations per pixel, as a new sampling location is created only after checking that none of the existing sampling locations is inside the current fragment. This is acceptable when the average number of sampling locations is small, but can become a bottleneck for scenes where the average triangle image footprint is small (e.g. \textit{Isosurface}). In all our experiments the resolution of the reference image where visibility was computed was always the same as the resolution of the output image. Choosing a reference image resolution commensurate with the average triangle footprint will control the average number of sampling locations per pixel. Another option is to subdivide pixels hierarchically, e.g. with a quadtree, to find the sampling locations inside a fragment in logarithmic time.

Our over-time-interval visibility algorithm relies on the assumption that triangle vertices move with a constant velocity vector over the time interval, which reduces the complexity of the visibility event equations. The assumption requires subdividing time into multiple intervals and running the visibility algorithm for each interval. Generalizing our from-rectangle visibility algorithm to a from-segment \textit{and} over-time-interval algorithm is non-trivial. When one visibility parameter is translation and the other one is time, the visibility event loci are not lines anymore, but rather curves, and the visibility subdivision becomes not polygonal.

Our algorithms rely on sampling locations to eliminate two visibility parameters. For example, from-rectangle visibility is reduced to solving a from-point visibility problem at each sampling location. However, this comes at the cost of redundancy--the same triangle is found as visible by many sampling locations. The bigger the span of the visibility parameter domain (e.g. view segment, time interval, view rectangle), the higher the redundancy.

\section{Conclusions and Future Work}

We have described a novel approach to visibility based on image generalization. The image is enhanced with sampling locations defined by scene geometry. A small number of sampling locations are sufficient to reveal most visible triangles. Our approach couples a sample-based and a continuous visibility analysis of the image plane to complete the visible set efficiently, in a remarkably small number of iterations. 1D and 2D visibility domains are handled directly, by solving visibility event equations, which reveals visibility changes without trial and error.

So far we have used our visibility algorithms to precompute visibility for complex scenes off-line. One direction of future work is to accelerate our visibility algorithms to support applications where visibility has to be computed in real time, such as antialiasing of minified geometry, motion blur, or soft shadow rendering. One option is to leverage the programmability of current graphics hardware (e.g. through CUDA); another option is to devise hardware extensions that bring native support to rendering over framebuffers with a variable number of sampling locations per pixel, and with more complex sampling locations (e.g. a list of intervals, a 2D map).

A second direction of future work is to use the image generalization paradigm to develop more general visibility algorithms. For example, an exact from-rectangle visibility algorithm, which also provides exact from-box visibility when applied to the six faces of the box, requires the construction of a two-parameter dynamic visibility subdivision of the image; a quality-guaranteed aggressive from-rectangle \textit{and} over-time-interval visibility algorithm requires 3D visibility samples, which could be implemented by voxelizing the translation by translation by time visibility parameter volume.

%\section*{Acknowledgements}

%To Robert, for all the bagels.

\bibliographystyle{acmsiggraph}
\small
\bibliography{bib}
\end{document}
