[Gzz-commits] manuscripts/AniFont SCRATCH anifont.tex

[Tuomas J. Lukka]

CVSROOT:        /cvsroot/gzz
Module name:    manuscripts
Branch:         
Changes by:     Tuomas J. Lukka <address@hidden>        03/10/27 10:45:20

Modified files:
        AniFont        : SCRATCH anifont.tex 

Log message:
        Sync

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/AniFont/SCRATCH.diff?tr1=1.2&tr2=1.3&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/AniFont/anifont.tex.diff?tr1=1.23&tr2=1.24&r1=text&r2=text

Patches:
Index: manuscripts/AniFont/SCRATCH
diff -u manuscripts/AniFont/SCRATCH:1.2 manuscripts/AniFont/SCRATCH:1.3
--- manuscripts/AniFont/SCRATCH:1.2     Wed Oct 22 05:38:05 2003
+++ manuscripts/AniFont/SCRATCH Mon Oct 27 10:45:19 2003
@@ -66,3 +66,20 @@
   stretch the texture in one direction, squish back by texture coordinates. 
activate
   the aniso filter. Aniso filters planned so that they don't flicker, either.
 
+
+
+Recently, we were looking at increasing the resolution of the page
+textures in our FenPDF system which shows PDF files in a fisheye view, using
+2048x2048 textures for the pages.  
+Hardware anisotropic filtering was
+enabled in order for the fisheye transformation not to blur the textures.  
+The pages were approximately
+letter-size and already scaled vertically nearly to the maximum size,
+but scaled isotropically in the texture.  
+We decided to try to scale both axes to
+the maximum extent, anisotropically, even though we suspected it might
+degrade the image quality.
+
+However, it did not. To our great surprise, the image quality (the
+readability of the text) actually \emph{improved significantly}.
+
Index: manuscripts/AniFont/anifont.tex
diff -u manuscripts/AniFont/anifont.tex:1.23 
manuscripts/AniFont/anifont.tex:1.24
--- manuscripts/AniFont/anifont.tex:1.23        Sat Oct 25 05:43:42 2003
+++ manuscripts/AniFont/anifont.tex     Mon Oct 27 10:45:20 2003
@@ -1,5 +1,6 @@
 \documentclass[twocolumn,10pt]{article}
 \usepackage{graphicx}
+\usepackage{fancybox}
 \usepackage{beton}
 \usepackage{caption2}
 \begin{document}
@@ -48,48 +49,48 @@
 
 \section{Introduction}
 
-Recently, we were looking at increasing the resolution of the page
-textures in our FenPDF system which shows PDF files in a fisheye view, using
-2048x2048 textures for the pages.  
-Hardware anisotropic filtering was
-enabled in order for the fisheye transformation not to blur the textures.  
-The pages were approximately
-letter-size and already scaled vertically nearly to the maximum size,
-but scaled isotropically in the texture.  
-We decided to try to scale both axes to
-the maximum extent, anisotropically, even though we suspected it might
-degrade the image quality.
-
-However, it did not. To our great surprise, the image quality (the
-readability of the text) actually \emph{improved significantly}.
-In this article, we show
-why this is the case and how easy it is to take advantage of this effect.
-
-The rest of the article is organized as follows.
-In Section~\ref{secrelated},  we discuss related work, i.e., texture filtering 
in general.
-In Section~\ref{secsquish}, we show why the stretch-squish method improves
-image quality and its relation to other filtering methods.
-Finally, we conclude. In Appendix A, we show how PFSS diagrams can be generated
-in an elegant fashion by probing the hardware accelerators' true filtering 
behaviour.
-
-
-\section{Background}
-
-\label{secrelated}
+Texture mapping is a ubiquitous computer graphics
+primitive\cite{heckbert86survey,haeberli93texture}
+originally introduced in \cite{catmull74}. 
+In off-line rendering, good algorithms for calculating 
+pixel values by a weighted numerically integral of the texels falling
+inside a pixel have been known for a long time(XXX EWAREF).
+On the other hand, in real-time rendering through 
+hardware-accelerators, it is important that the number of samples can be
+kept constant regardless of the pixel footprint.
 
+Trilinear (mipmap) filtering\cite{williams83pyramidal}
+was designed to avoid temporal and spatial aliasing while only requiring 8 
+texture samples per pixel. 
+For 3D rendering, the most well-known problem of
+trilinear filtering is that it blurs the texture the pixel footprint in 
texture space
+is far from square, i.e., in \emph{anisotropic} situations
+(squished more in one direction than in another).
+This has led to the development of several anisotropic filtering 
algorithms(REFS feline texram talisman spaf ffp...)
+that usually work through some type of
+\emph{footprint assembly}, i.e. assembling a better approximation
+to the pixel footprint in texture space from normal mipmap samples or by using
+trilinear \emph{probes}.
+
+While summed-area tables(XXX CROWREF) can often provide
+better rendering quality, their hardware implementation is not easy, as 
discussed in 
+(XXX ref to fast footprint/... discussing this), so today trilinear rendering, 
supplemented
+with some form of anisotropic filtering
+is the \emph{de facto} standard in hardware accelerators, supplemented by
+support for full-screen super- or multisampling. 
 
-\def\snapsize{2.5cm}
+\def\snapsize{2.4cm}
 \def\snapshot#1{\raisebox{-2cm}{\includegraphics[totalheight=\snapsize]{#1}}}
 
-\def\colwidth{2.3cm}
+\def\colwidth{2.4cm}
 
 \begin{figure*}
 
\begin{tabular}{p{1.5cm}|p{\colwidth}p{\colwidth}p{\colwidth}p{\colwidth}p{\colwidth}}
 Coordinate mapping&Nearest neighbour&Trilinear&Trilinear+ Anisotropic&FSAA 
4xSS&Vertex-based 4xSS \\
 \hline\\
 Iso& 
-\snapshot{snapsps/aniso-gffx-tbl-iso-nearest.ps}   &
-\snapshot{snapsps/aniso-gffx-tbl-iso-trilinear.ps}   &
+\snapshot{snapsps/aniso-gffx-tbl-iso-nearest.ps}   &%
+\hbox{\hskip-4pt\doublebox{\snapshot{snapsps/aniso-gffx-tbl-iso-trilinear.ps}}}
   &
 \snapshot{snapsps/aniso-gffx-tbl-iso-aniso.ps}   &
 \snapshot{snapsps/aniso-gf4go-tbl-iso-fsaa.ps}   &
 \snapshot{snapsps/aniso-gffx-tbl-iso-super4.ps}   \\
@@ -97,14 +98,14 @@
 %
 Aniso&
 \snapshot{snapsps/aniso-gffx-tbl-aniso-nearest.ps}   &
-\snapshot{snapsps/aniso-gffx-tbl-aniso-trilinear.ps}   &
-\snapshot{snapsps/aniso-gffx-tbl-aniso-aniso.ps}   &
+\snapshot{snapsps/aniso-gffx-tbl-aniso-trilinear.ps}   &%
+\hbox{\hskip-4pt\doublebox{\snapshot{snapsps/aniso-gffx-tbl-aniso-aniso.ps}}}  
 &
 \snapshot{snapsps/aniso-gf4go-tbl-aniso-fsaa.ps}   &
 \snapshot{snapsps/aniso-gffx-tbl-aniso-super4.ps}   \\
 %
 \end{tabular}
 \caption{
-\label{figbitrilinear}
+\label{figallpfss}
 PFSS (Pixel Footprint in Screen Space) diagrams generated on a Geforce4Go 
(FSAA 4xSS) 
 and a Geforce FX 5600 (all others), showing
 different types of filtering as they actually occur on the hardware 
@@ -114,64 +115,96 @@
 In the lower row, the texture is mapped quite anisotropically and the 
 blurring effect of trilinear filtering is obvious - the footprint
 is much larger in the vertical direction than it should be.
+The two highlighted diagrams are the ones relevant to understanding 
stretch-squish.
 }
 \end{figure*}
 
-% \subsection{The texture mapping primitive}
-
-Texture mapping is a ubiquitous ... \cite{heckbert86survey,haeberli93texture}
-originally introduced by Catmull\cite{catmull74}.
-
-In off-line rendering, off
 
-- off-line rendering: EWA XXXREF
-
-% \subsection{Mipmapping: bi- and trilinear filtering}
-
-On the other hand, in real-time rendering through 
-hardware-accelerators, it is important that the number of samples can be
-kept constant regardless of the pixel footprint.
-
-- Trilinear/bilinear (mipmap) filtering was designed to avoid temporal and 
spatial aliasing\cite{williams83pyramidal}
-
-For 3D rendering, the most well-known problem of
-trilinear filtering is that it blurs the texture the pixel footprint in 
texture space
-is far from round, i.e., in \emph{anisotropic} situation
-(squished more in one direction than in another).
-However, even in isotropic situations trilinear filtering
-can blur sharp edges (text) too much.
-
-- for sharp edges / small features, even under orthogonal transformations, 
trilinear bad:
-sampling at too low a resolution for much of the time!
-
-
-    - LOD bias sharpening causes spatial and temporal aliasing (flickering)
-
-
-% \subsection{Anisotropic texture filtering}
+In this article, we consider texture filtering in the overlooked,
+isotropic or nearly isotropic case. Even in the isotropic case, trilinear
+can blur small features that appear in, e.g., text.
+We discovered accidentally that stretching an image anisotropically
+when placing it into a texture and squishing it back when rendering
+using texture coordinates, all the while enabling anisotropic filtering,
+yields a considerably better image quality for text. 
+
+In looking to understand why the stretch-squish method works,
+we found pixel footprint in screen space (PFSS) diagrams 
+extremely useful, contrary to the usual practice in the
+texture filtering literature to 
+visualize the pixel footprint is exclusively in the texture space.
+Our PFSS diagrams show a highly magnified pixel (e.g. 100 pixels in side)
+and the contributions (assuming box filtering for the mipmap levels)
+from the texels mapped to the surrounding area by a color.
+Figure~\ref{figallpfss} shows 
+several PFSS (pixel footprint in screen space) diagrams of several filtering
+methods in both isotropic and anisotropic mappings, measured on actual graphics
+hardware. 
+
+In the following Sections, 
+we first discuss known methods for improving isotropic or near-isotropic
+hardware-accelerated texture filtering.
+In Section~\ref{secsquish}, we show why the stretch-squish method improves
+image quality and its relation to the other methods.
+Finally, we conclude. 
+In Appendix A, we show how PFSS diagrams can be generated
+elegantly by probing the hardware accelerators' true filtering behaviour.
 
-- basic anisotropic solution: more samples from the mipmaps than the 8 used for
-  trilinear - better approximation of EWA. Modern graphics cards support up to 
XXX samples
-  XXX Feline texram talisman
 
-\section{Related work: Improving hardware-rendered image quality}
 
-- Unextended OpenGL aniso: article on using lod bias etc to get 
it\cite{olano01vertexbasedaniso}
+\label{secrelated}
 
-- lod BIAS
 
-- supersampling: FSAA / as above; however, most cards focus on multisampling, 
not supersampling - 
-  no help for textures
+\section{Related work}
 
-- custom supersampling in the same way as in \cite{olano01vertexbasedaniso}, 
or using multitexture.
-  Vertex and fragment -based.
+In this Section, we discuss the known methods to improve the quality of
+hardware-accelerated texture filtering in isotropic situations.
 
-- Mipmap adjustment (see advanced OpenGL course notes)
+For sharp edges or small features under isotropic or nearly isotropic 
transformations,
+trilinear filtering is far from optimal: it samples at a too low resolution
+(too large pixel footprint, see Fig.~\ref{figallpfss}) much of the time, 
+and is also sensitive to subpixel translations (see 
Fig.~\ref{figstretchsquishwhyworks}).
+
+The best solution would be to use a well-founded reconstruction
+filter, such as EWA (XXX Heckbert) or other filters (Wolberg REF), but these 
use a varying
+number of samples from textures and cannot be easily implemented on current 
hardware..
+Summed-area tables\cite{crow84summedareatables} could be a great improvement 
but,
+while they can be implemented using fragment programs on some of the current 
hardware,
+are rather slow in such an implementation.
+
+A conventional way to obtain blurring or sharpening
+blurring artifacts is to use a
+LOD bias to sample from a lower mipmap level; however,
+this causes significant spatial and temporal aliasing (flickering).
+
+The most common way in computer graphics to avoid aliasing artifacts
+is to use supersampling. Indeed, most graphics cards today support
+some form of full-screen supersampling or multisampling. However,
+multisampling (which does not supersample textures, only polygon coverage) 
+seems to be the more popular alternative. If full-screen supersampling
+is present, it does increase texture filtering quality significantly; see 
Fig.~\ref{figallpfss}.
+
+It is also possible to adapt the approach given in 
\cite{olano01vertexbasedaniso}
+for anisotropic filtering using unextended OpenGL to supersampling by 
+However, this approach does significantly restrict the OpenGL texture 
environment
+and blend modes available unless the hardware supports a sufficient number of 
texture
+accesses to accomplish the complete texturing operation in one pass (e.g., 4 
for 2x2 supersampling).
+Also, the vertex-based implementation requires computation of the derivatives 
of the texture coordinates
+for each vertex, which may require considerable changes to code when applying 
this
+method to code that has been using the usual filtering primitives of the 
hardware.
+In systems supporting the calculation of derivatives on the fragment level
+(via, e.g., the OpenGL extensions \verb+GL_NV_fragment_program+ and 
\verb+GL_ARB_fragment_shader+)
+the supersampling can be implemented entirely in the fragment program, with no 
changes
+to the vertex code, albeit with further performance degradation.
+
+The Advanced OpenGL course notes(XXX REF) suggest ``generating the mipmap 
levels carefully, e.g.  XXX''.
+This appears to be largely unexplored territory and seems to be, in any case, 
orthogonal
+to the improvements in the actual filtering methods.
 
-\section{Why does stretch and squish improve image quality?}
+\section{Stretch and squish improves image quality}
 
 
-\begin{figure}[t!]
+\begin{figure}[thb!]
 \centering
 \begin{tabular}{c|c}
 Trilinear  & Stretch-squish 2x\\
@@ -194,14 +227,29 @@
 }
 \end{figure}
 
-The quality of trilinear filtering result depends strongly on subpixel 
position,
-as shown in Fig.~\ref{figstretchsquishwhyworks}. The anisotropic filter 
provides
-a better 
+We were surprised to find that stretching an image in a texture and
+squishing it with texture coordinates while enabling anisotropic filtering
+improved image quality. The first intuition is that this should \emph{reduce}
+image quality, just as scaling an image and subsequently shrinking it should.
+However, this is not the case here: the isotropic and anisotropic texture 
filters
+are different, and it happens to be that \emph{in screen space}, anisotropic 
filtering
+of an anisotropic texture is always better than the isotropic filtering of
+an isotropic texture. This is shown in detail in 
Fig.~\ref{figstretchsquishwhyworks}.
+The trilinear filter footpring size depends strongly on subpixel position and 
+can be quite large compared to the actual pixel, causing blurring.
+When using the anisotropic filter, the footprint is remains significantly 
smaller
+in one direction regardless of subpixel shifting --- in the other direction,
+it is similar.
 
 - analogous to supersampling
 
 
-- downside: if transformed nonorthogonally, blurs easier since the "aniso 
power" is already used
+- downsides: 
+
+    - if transformed anisotropically, blurs easier in one direction
+      since some of the "aniso power" is already used
+
+    - only better in one direction, can't be easily directly generalized
 
 
 \def\fontexamplesize{8cm}
@@ -217,26 +265,10 @@
 }
 \end{figure*}
 
-- comparison:
 
-    - trilinear (upside: one texunit, fast, downside: blurry)
 
-    - aniso, different levels (upside: one texunit, quite fast, downside: only 
better in one direction)
 
-    - virtual supersampling, different levels (downsides: uses more texunits!, 
upsides: allows improvement in both directions)
 
-    - real supersampling (downsides: not supported on all boards, slows down 
EVERYTHING)
-
-    - combinations aniso + vss? A pretty nice one might be 2x2 using 2 
texunits and 2-degree aniso... However, only 
-      NV GF FX supports that, nothing else. Others can only bias the lod so 
have to use supersampling 1 or 2x2
-
-    - texture mipmap level "careful" making - as mentioned in Advanced OpenGL 
SIGGRAPH course notes:
-      aniso is orthogonal
-
-
-- benefit / cost ratio analysis: how much slower than trilinear and
-  how must faster than real supersampling -- does aniso filter provide
-  ``optimal'' quality / cost ratio?
 
 
 
@@ -252,7 +284,10 @@
 Stretch-squish 2x   & NV1X+  & Better      & ---         & almost trivial & 
1.5---2 \\
 4x FSAA supersampling & NV1X\footnote{Not available on NVIDIA Linux drivers 
44.96 on NV25 or NV31, only on NV1X}  & Good        & ---         & trivial     
   & 4\footnote{With FSAA, the entire scene slows down, not just the polygon to 
be improved} \\
 Vertex-based supersampling &
-                        NV2X+ & Good       & ---         & significant    & 
4---6 \\
+                        NV2X+\footnote{With a limited selection of
+                                      texture environment and blending modes, 
can be used as a multi-pass approach on any implementation 
+                                      supporting LOD biasing, however with a 
significantly larger performance drop due to multiple passes
+                                      and blending..} & Good       & ---       
  & significant    & 4---6 \\
 Fragment-based supersampling & 
                         NV3X+ & Good       & ---         & trivial        & 
10---20 \\
 \hline
@@ -270,6 +305,10 @@
 - In this article, we argue that isotropic situations should be explicitly 
avoided
   in 2D orthogonal rendering - better quality with aniso
 
+- at least, almost never should only a part of a texture be used for an image
+  to allow the image to be isotropically scaled
+
+- one more tool
 
 - described how hardware implementations of anisotropic filtering can be probed
   for better understanding
@@ -288,12 +327,9 @@
 - this is a REALLY SIMPLE way to get a SOMEWHAT better quality. For dramatic 
improvements,
   real supersampling is needed
 
-Seveeral aspects we did not touch
-
-- basic model of filtering - well-known (e.g. advanced opengl course notes): 
-  should darken / sharpen the mipmap levels in combination
-
-- LCD-text
+- combinations aniso + vss? A pretty nice one might be 2x2 using 2 texunits 
and 2-degree aniso... However, only 
+  NV GF FX supports that, nothing else. Others can only bias the lod so have 
to use supersampling 1 or 2x2
+  XXX Try fragment-based like that!
 
 
 
@@ -323,6 +359,8 @@
 
 This seems to be a well-known technique that has not so far been published
 anywhere
+A similar technique appears to be used more commonly used for probing hardware
+antialiasing patterns, 
 
 
 - Graphics companies unfortunately do not provide ...
@@ -346,25 +384,15 @@
   the same results (in some drivers, this is not the case - 3dcenter about nv 
51.XX series
   DirectX),
   Driver isn't using a different set of samples for large and small triangles, 
-  e.g. NV patent describing using lower mipmap level!
   pixel translation invariance, in screen space.
 
-- define separate texture $T_{(k),x,y}$ for each texel of each
-  mipmap level, with exactly one light
-  texel at the point $(x,y)$ of that mipmap level, all other texels and mipmap 
levels middle gray
-  (we define level $(n)$ to be the 1x1 texture, ${n-1}$ to be the 2x2 texture 
etc.
-  Non-square mipmap hierarchies are a simple generalization)
-    
-    - gray so we see also if there are negative weights in the filter!
-
-- select the texture coordinates for a single-pixel quad for which you want
-  to see contributions.
-  In reality, only a triangle gets used so these should be linearly obtained
-  from three coordinates but it's still easier for a human to understand these
-  as quads... 
+- gray so we see also if there are negative weights in the filter!
 
-- For each mipmap level texel, render a one-pixel quad,
-  with the same texture coordinates and 
+- select the texture matrix to map the single-pixel texture quad ...
+
+- For each texel on each mipmap level, render a one-pixel quad,
+  with the same texture coordinates and ... 
+  render only for the lowest level and use box filtering? Roundoff errors
 
 - Resulting image gives contribution from each texel on a mipmap level
   to the final image, PROVIDED ASSUMPTIONS HOLD.
@@ -374,18 +402,20 @@
 
 - utility in our free software OpenGL libvob system
 
+- FSAA does not blur samples from neighbouring pixels
 
+    - if it does, render larger quads further apart.
+      and use CopyTexSubImage instead of CopyTexImage
 
-A similar technique appears to be used more commonly used for probing hardware
-antialiasing patterns, (XXX should we?). 
 
 - assumptions about the contents of the mipmap levels
 
-    - aniso filter might compute trilinear samples using only one level, etc.
-    
     - for analysis, the contribution of one texel could be represented
       as the contribution of four texels on a higher mimap level as per
-      the assumption of generating the mipmap levels in the usual way
+      the assumption of generating the mipmap levels using a box filter.
+      If this assumption does not hold, it's possible to visualize the
+      mipmap levels separately (on the other hand, the different mipmap
+      level samples are easy to distinguish from the final image, so ...)
 
 
 \begin{enumerate}
@@ -423,8 +453,8 @@
 
 \end{enumerate}
 
-Note that only the display list \texttt{quad} need to be changed
-for probing different texture-to-screen mappings or, even more easily,
-one can simply change the texture-matrix while using a static quad.
+Note that only the texture matrix and texture filter parameters
+for texture 1 need to be changed
+for probing different texture-to-screen mappings 
 
 \end{document}