Proceedings Template Word
Improving Noise
Ken Perlin
Media Research Laboratory, Dept. of Computer Science, New York University
perlin@cat.nyu.edu
is shaded; then the surface normal (which is itself a derivative
ABSTRACT
operator) has a visibly discontinuous derivative (Figure 1a).
Two deficiencies in the original Noise algorithm are corrected:
second order interpolation discontinuity and unoptimal gradient
computation. With these defects corrected, Noise both looks
better and runs faster. The latter change also makes it easier to
define a uniform mathematical reference standard.
Keywords
procedural texture
1 INTRODUCTION
Since its introduction 17 years ago [Perlin 1984; Perlin 1985;
Perlin and Hoffert 1989], Noise has found wide use in graphics
[Foley et al. 1996; Upstill 1990]. The original algorithm, although
efficient, suffered from two defects: second order discontinuity
across coordinate-aligned integer boundaries, and a needlessly
expensive and somewhat problematic method of computing the
gradient. We (belatedly) remove these defects.
2 DEFICIENCIES IN ORIGINAL ALGORITHM
Figure 1a: Noise-displaced superquadric with old interpolants
As detailed in [Ebert et al 1998], Noise is determined at point
(x,y,z) by computing a pseudo-random gradient at each of the
eight nearest vertices on the integer cubic lattice and then doing
splined interpolation. Let (i,j,k) denote the eight points on this
cube, where i is the set of lower and upper bounding integers on
x: {| x |,| x |+1}, and similarly j = { | y |,| y |+1} and k = { | z |,| z
|+1}. The eight gradients are given by gi,j,k = G[P[P[P[i]+j]+k]]
where precomputed arrays P and G contain, respectively, a
pseudo-random permutation, and pseudo-random unit-length
gradient vectors. The successive application of P hashes each
lattice point to de-correlate the indices into G. The eight linear
functions gi,j,k ยท (x-i,y-j,z-k) are then trilinearly interpolated by
s(x-| x |), s(y-| y |) and s(z-| z |), where s(t) = 3t2-2t3.
The above algorithm is very efficient but contains some
deficiencies. One is in the cubic interpolant function's second
derivative 6-12t, which is not zero at either t=0 or t=1. This non-
zero value creates second order discontinuities across the
coordinate-aligned faces of adjoining cubic cells. These
discontinuities become noticeable when a Noise-displaced surface
Figure 1b: Noise-displaced superquadric with new interpolants
The second deficiency is that whereas the gradients in G are
distributed uniformly over a sphere, the cubic grid itself has
directional biases, being shortened along the axes and elongated
on the diagonals between opposite cube vertices. This directional
asymmetry tends to cause a sporadic clumping effect, where
nearby gradients that are almost axis-aligned, and therefore close
together, happen to align with each other, causing anomalously
high values in those regions (Figure 2a).
thereby avoiding the possibility of axis-aligned clumping, and (ii)
it allows the eight inner products to be effected without requiring
any multiplies, thereby removing 24 multiplies from the
computation.
To avoid the cost of dividing by 12, we pad to 16 gradient
directions, adding an extra (1,1,0),(-1,1,0),(0,-1,1) and (0,-1,-1).
These form a regular tetrahedron, so adding them redundantly
introduces no visual bias in the texture. The final result has the
same non-directional appearance as the original distribution but
less clumping, as can be seen in Figure 2b.
4 PERFORMANCE
In a timing comparison (C implementations on the Intel
optimizing compiler running on a Pentium 3), the new algorithm
runs approximately ten percent faster than the original. The cost
of the extra multiplies required to compute the three corrected
interpolants is apparently outweighed by the savings from the
Figure 2a: High-frequency Noise, with old gradient distributions
multiplies no longer required to compute the eight inner products.
Examination of the assembly code indicates that the Intel
processor optimizes by pipelining the successive multiplies of the
three interpolant calculations since no memory fetches are
required within this block of computations.
Rather than use a 12-entry table to avoid inner product multiples,
the G table can also be expanded and used to replace the last
lookup into P. Whether this method is more efficient is processor
dependent. For example, 3D inner products are single operations
on both nVidia and ATI pixel processors.
5 CONCLUSIONS
The described changes result in an implementation of Noise
which is both visually improved and computationally more
efficient. Also, with the pseudo-random gradient table removed,
the only pseudo-random component left is the ordering of the
permutation table P. Once a standard permutation order is
determined, it will at last be possible to give a uniform
mathematical definition for the Noise function, identical across all
Figure 2b: High-frequency Noise, with new gradient distributions
software and hardware environments.
3 MODIFICATIONS
ACKNOWLEDGEMENTS
The above deficiencies are addressed as follows. 3t2-2t3 is
Thanks to the reviewers for constructive criticisms that improved
replaced by 6t5-15t4+10t3, which has zero first and second
the paper, to Denis Zorin for his invaluable suggestions, and to
derivatives at both t=0 and t=1. The absence of artifacts can be
Nathan Wardrip-Fruin and Chris Poultney, who helped greatly in
seen in Figure 1b.
the rush of production.
The key to removing directional bias in the gradients is to skew
References
the set of gradient directions away from the coordinate axes and
EBERT, D. ET AL. 1998. Texturing and Modeling; A Procedural
long diagonals. In fact, it is not necessary for G to be random at
Approach, Second Edition. AP Professional, Cambridge.
all, since P provides plenty of randomness. The corrected version
FOLEY, J. ET AL. 1996. Computer Graphics: Principles and
replaces G with the 12 vectors defined by the directions from the
Practice. Addison-Wesley, Reading.
center of a cube to its edges:
PERLIN, K., ACM SIGGRAPH 84 conference, course in
"Advanced Image Synthesis."
(1,1,0),(-1,1,0),(1,-1,0),(-1,-1,0),
PERLIN, K. 1985. An Image Synthesizer. In Computer Graphics
(1,0,1),(-1,0,1),(1,0,-1),(-1,0,-1),
(Proceedings of ACM SIGGRAPH 85), 24. 3.
(0,1,1),(0,-1,1),(0,1,-1),(0,-1,-1)
PERLIN, K. AND HOFFERT, E. 1989. Hypertexture. In Computer
Graphics (Proceedings of ACM SIGGRAPH 89), 23, 3.
Gradients from this set are chosen by using the result of P,
U
modulo 12. This set of gradient directions was chosen for two
PSTILL, S. 1990. The RenderMan Companion: A Programmer's
Guide to Realistic Computer Graphics. Addison-Wesley.
reasons: (i) it avoids the main axis and long diagonal directions,
