[Gzz-commits] gzz/Documentation/Manuscripts gzigzag.bib Irreg...

[Tuomas J. Lukka]

CVSROOT:        /cvsroot/gzz
Module name:    gzz
Changes by:     Tuomas J. Lukka <address@hidden>        02/11/30 10:26:52

Modified files:
        Documentation/Manuscripts: gzigzag.bib 
        Documentation/Manuscripts/Irregu: irregu.tex 

Log message:
        Editing

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/Manuscripts/gzigzag.bib.diff?tr1=1.79&tr2=1.80&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/Manuscripts/Irregu/irregu.tex.diff?tr1=1.112&tr2=1.113&r1=text&r2=text

Patches:
Index: gzz/Documentation/Manuscripts/Irregu/irregu.tex
diff -u gzz/Documentation/Manuscripts/Irregu/irregu.tex:1.112 
gzz/Documentation/Manuscripts/Irregu/irregu.tex:1.113
--- gzz/Documentation/Manuscripts/Irregu/irregu.tex:1.112       Sat Nov 30 
06:25:49 2002
+++ gzz/Documentation/Manuscripts/Irregu/irregu.tex     Sat Nov 30 10:26:52 2002
@@ -668,134 +668,82 @@
 
 \subsubsection{The oldest trick in the book}
 
-Drawing the 
-shape multiple times
-
-The border can be approximated by 
-
-inside of a tear-out
-multiple times with the border color, each time shifting it a few pixels 
-(the line width or a fraction of it) to a diffrent direction.
+The oldest and conceptually simplest way to draw a black
+edge around a shape is to first draw the shape with black
+color several
+times shifted slightly to different directions
+before drawing the correctly colored, unshifted instance
+We have no idea when this approach has first been used or proposed.
 
 Shifting to the four screen axis directions is simple and 
-produces good results for small border widths.
+produces good results for narrow border widths (1 or 2 pixels).
 However, diagonal edges are drawn slightly too narrow, and
 the border around small features may end up sprinkled if
-the line width is more than one pixel.
-
-This method is general, but requires multiple passes
-of the envelope for drawing the border.
-If the edge is connected, it suffices to shift to the 
-positive $y$ and to positive and negative $x$ directions
-of the envelope.
+the line width is more than one pixel. 
+In such cases, a more complete set of shifted shapes
+is needed.
+
+% If the edge is connected, it suffices to shift to the 
+% positive $y$ and to positive and negative $x$ directions
+% of the envelope.
 
 %Quite fast, but still has overhead w.r.t.~just the shape.
 %Artifacts: edge thickness, small features 
 
-\subsubsection{Image-space algorithms}
-
-XXX: move to ``Drawing the edge''?
-
-Image-space algorithm: ... slow on NV10
-
-Depth discontinuities extracted with a differential operator
-\cite{saito90comprehensible}.
-
-\subsubsection{Mutltitexture}
-
 %Similar to multi-pass perturbed edge: values of surrounding fragments
 %computed in parallel for each fragment.
-With four texture units, it is possible to do the texture accesses
-corresponding to four different shifted edges for each fragment
-and use register combiners to determine if any of them
-is inside the tear-out.
-
-For connected edges, the texture coordinates do not change along 
-the $y$ direction of the envelope.
-Simply set up texture units so that each one has
-the same bound texture but texture coordinates a distance corresponding
-to border width (or a fraction of it) apart along the length of the envelope.
-The read texture values are positions of the torn edge along the normal of 
-the envelope.
-A fragment is inside the outer edge of the border, if its distance from
-any of the adjacent inner edge points is less than the line width.
-This computation can be carried out using register combiners.
 
-\subsubsection{Pre-computed borders}
 
-XXX:
+This method is general, but requires drawing the shape
+multiple times.
+With multiple texture units, 
+it is possible in some circumastances to do the texture accesses
+corresponding to different shifts for each fragment
+at the same time. 
+
+Also, since we know that the center of the shape is solid,
+that part doesn't need to be drawn for the shifted shapes.
+
+% For connected edges, the texture coordinates do not change along 
+% the $y$ direction of the envelope.
+% Simply set up texture units so that each one has
+% the same bound texture but texture coordinates a distance corresponding
+% to border width (or a fraction of it) apart along the length of the envelope.
+% The read texture values are positions of the torn edge along the normal of 
+% the envelope.
+% A fragment is inside the outer edge of the border, if its distance from
+% any of the adjacent inner edge points is less than the line width.
+% This computation can be carried out using register combiners.
 
-Both algorithms can be seen as computing the intersection of a
-\emph{ripple volume}, the volume below the surface $(\p, f(\p))$,
- and a \emph{cutting surface} $(E(x,g(y)), y)$, 
-and then mapping the intersection on the envelope $E(x,y)$ 
-using the parameters of the cutting surface.
-
-The function $g$ (actually its inverse) defines the profile of the 
-cutting surface, with $g(y) = y$ for the scattered case and $g(y) = 1/2$,
-i.e., a vertical surface, for the connected case. 
-
-Using the same parametrization for both surfaces, 
-
-Recall that the torn shape can be defined as the intersection
-of the ripple volume, i.e., the volume below $(x,y,f(x,y))$, 
-and a cutting surface $(x,g(y),y)$,
-which is actually a plane in the linear section of the envelope.
-
-It is possible to obtain the outer edge of the border 
-by simulating the procedure of drawing a thick line in the cutting plane:
-A circle on screen with radius corresponding to the desired border
-width is projected back to the cutting plane and then
-moved inside the cutting plane so that
-it always touches the ripple volume, but never crosses it. 
-The center of the projected circle (ellipse) draws the 
-back-projected outer edge of the border.
-
-If the cutting plane is then moved (without rotating it) 
-around the ripple volume, the outer edges corresponding to each
-position of the cutting plane draw a complete surface over
-the original surface.
-The same algorithm that draws the inner edge can then be 
-used to draw the outer edge by using a texture storing the new surface.
-However, the outer edge surface is different for different
-orientations of the cutting plane and for different line widths.
-
-An application generally uses only one or a few different 
-slopes of the cutting plane so there is no problem in storing
-these discrete choices in different textures.
-However, the tearout shape can rotate, requiring surfaces
-for all tearing directions in the canvas. 
-We compute the \emph{outer surfaces} for a small number of different 
-tearing directions and store them
-in the components of a texture. 
-The surface corresponding to a a tearing direction between 
-two stored angles is computed 
-by linearly interpolating between the two components of the
-texture using a dot product with GL\_NV\_register\_combiners.
-
-The interpolation works better for non-vertical cutting planes.
-For a vertical cutting plane, the circle may fit in a narrow valley
-only in a certain angle, making large changes in the outer surface
-over small changes of angle. 
-When the cutting plane is closer to horizontal, there can be no such gaps,
-because the surface is defined as a displacement from a horizontal plane.
-On the other hand, it suffices to store only half of the tearing angles
-of a vertical cutting plane, because 180 degree rotation of the plane 
-has no effect.
-A four-component texture can store angles 45 degress apart for a vertical 
-cutting plane and 90 degrees apart for a non-vertical plane.
+\subsubsection{Pre-computed borders}
+
+Drawing thick ($\approx 10$ pixels) borders by shifting gets to
+be inefficient due to the large number of shifts required for 
+good quality. In this section, we present an algorithm that is
+able to approximate the shape well in a single pass.
+
+The algorithm works by precalculating the displacement or offset
+of the outer edge of the black line, assuming that the shape algorithm
+draws the inner edge.
+The precalculated edge shapes are different for different orientations,
+but this can be approximated by storing the offsets at a discrete set
+of orientations in different components of a texture and interpolating
+by calculating dot products.
+This approximation is not completely free of artifacts (FIG), 
+but is sometimes acceptable and is fast to draw.
 
-Non-photorealistic line width scaling is obtained by computing
+Non-photorealistic line width scaling can be obtained by computing
 each mip-map\cite{williams83pyramidal}
 level of the outer surface textures separately 
 with the desired line width for that scale.
+This method of computing mip-maps is similar to the art maps used in 
+\cite{klein00nonphotorealistic}.
 Because the textures store displacement values, 
 the mip-map levels interpolate seamlessly.
 However, zooming above the highest level of detail in the mip-map
 will fall back to the linear scaling.
+
 %XXX: could interpolate towards inner edge with DP4 and texture w/ 3 angles
-This method of computing mip-maps is similar to the art maps used in 
-\cite{klein00nonphotorealistic}.
 
 %XXX: cite rip-maps
 
@@ -803,45 +751,62 @@
 %- projective mapping \\
 %- antialias \\
 
-\subsubsection{Offset texture}
+\subsubsection{Image-space algorithms}
+
+Image-space algorithms for drawing edges\cite{saito90comprehensible} 
+work somewhat analogously to the previous section; the difference
+is that instead of rendering the shape several times,
+a filter is applied
+to the depth buffer where the shapes have been rendered 
+to extract the discontinuities.
+
+The advantage of image-space algorithms is that their performance
+does not depend on the complexity of a scene; however, it appears
+that NV30/R300 generation of graphics chips is flexible enough
+to support image-based operations well, due to the number of texture
+accesses and floating point operations needed. Also, it is more
+difficult (although possible)
+to adjust the width of the border based on depth
+in this approach.
 
-Because the algorithm for drawing the shape is 
-equivalent to one-dimensional offsetting of a half-plane,
-the border can be drawn by offsetting 
+
+\subsubsection{A silly hack with offset texture mipmapping}
+
+The border can be drawn by offsetting 
 a texture with an image of a straight line.
-However, a sloped offset reduces the width of the distorted line.
+However, a sloped offset reduces the width 
+of the distorted line.
+This narrowing can be compensated by 
+using
+scale-invariant constant line width (in texels) 
+for the mipmaps of the image of the line.
 
-This problem can be overcome by computing the mipmaps of
-the edge texture with scale-invariant constant line width (in texels).
-The computed level of detail for each fragment is lower for a
+The trick is that the computed level of detail 
+for each fragment (at least on the NV25) is lower for a
 sloped offset, and the lower detail texture with thicker line
 will exactly compensate the reduced line width.
-Note that this no longer holds for two-dimensional offsetting.
+Note that this only holds when offsetting in the normal direction.
 Also, derivative discontinuities are sometimes visible
 as spikes in the border, if the border is more 
-than a few pixels wide.
-
-The edge texture can be one texel wide (if the image of the 
-edge is drawn horizontally), allowing for large height and
-so non-photorealistic scaling to large scales.
-Note that it still has to be a 2D texture for the mipmapping trick
-to work.
+than a few pixels wide. FIG
 
-Increasing the border width scaling exponent from 0 makes the
-border width less consistent with sloped offset.
+This trick only works if the line texture is 2D, but its other dimension can
+be 1. 
 
-\subsection{Future work: NV30 and R300}
-
-XXX
+% XXX really?
 
-With NV30, more accuracy with floating point textures.
-More procedural textures with fragment programs.
-A single texture unit can be accessed multiple
-times with displaced texture coordinates computed in a fragment program.
+% The edge texture can be one texel wide (if the image of the 
+% edge is drawn horizontally), allowing for large height and
+% so non-photorealistic scaling to large scales.
+% Note that it still has to be a 2D texture for the mipmapping trick
+% to work.
+% 
+% Increasing the border width scaling exponent from 0 makes the
+% border width less consistent with sloped offset.
 
-\subsection{Tearout shapes}
+\subsection{Polygonal undistorted shapes}
 
-In earlier sections, we have presented different ways of drawing
+In the previous sections we have presented different ways of drawing
 one linear section of the envelope. 
 In this section, we consider different ways of drawing complete
 tear-out shapes with contents.
@@ -997,6 +962,15 @@
 
 \section{Conclusions}
 
+
+XXX
+
+With NV30, more accuracy with floating point textures.
+More procedural textures with fragment programs.
+A single texture unit can be accessed multiple
+times with displaced texture coordinates computed in a fragment program.
+
+
 frequencies: only low/high in frames
 
 interaction with libpaper!!!
@@ -1032,6 +1006,9 @@
 
 The authors would like to thank \censor{Benja Fallenstein and
 Antti-Juhani Kaijanaho} for discussions.
+
+% References contain hard-to-typeset parts -- help TeX out a bit
+\hbadness=4000
 
 \bibliographystyle{plain}
 \bibliography{gzigzag}
Index: gzz/Documentation/Manuscripts/gzigzag.bib
diff -u gzz/Documentation/Manuscripts/gzigzag.bib:1.79 
gzz/Documentation/Manuscripts/gzigzag.bib:1.80
--- gzz/Documentation/Manuscripts/gzigzag.bib:1.79      Fri Nov 29 13:51:52 2002
+++ gzz/Documentation/Manuscripts/gzigzag.bib   Sat Nov 30 10:26:52 2002
@@ -1787,7 +1787,7 @@
   editor = "N. Phuan Ong and Ravin N. Bhatt",
   publisher = "Princeton University Press",
   year = "2001",
-  note = "Not really procedural texturing but related to our application of it"
+  comment = "Not really procedural texturing but related to our application of 
it"
 }
 
 @misc{cie78uniform,
@@ -1827,7 +1827,8 @@
     pages = "1101--1135",
     year = "1998",
     url = "citeseer.nj.nec.com/37285.html",
-    note="Many of these apply to us as well..."}
+    comment="Many of these apply to us as well..."
+    }
 
 @inproceedings{ heidrich99applications,
     author = "W. Heidrich and R. Westermann and H.-P. Seidel and T. Ertl",