[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: srfi-25@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx*Subject*: Re: Not quite enough abstraction*From*: oleg@xxxxxxxxx*Date*: Mon, 28 Jan 2002 21:10:10 -0800 (PST)*Cc*: lucier@xxxxxxxxxxxxxxx, feeley@xxxxxxxxxxxxxxxx*Delivered-to*: srfi-25@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx*Reply-to*: oleg@xxxxxxxxx

Hello! I'd like to point out a corroborating evidence in favor of abstract vectors. The evidence is from a different domain: procedural texture generation. A texture is a function on a matrix (pixelmap). A paper presented by Jerzy Karczmarczuk at PADL02 shows that even intricate and exquisite textures can be described declaratively (combinatorially) -- often by an order of magnitude shorter than in traditional, imperative, pixel-shoving approach. It has to be stressed that textures are expressed in a coordinate-free way. Therefore, the definition of a complex texture does not depend on storage and other details of the pixelmap. A summary of Jerzy's talk is enclosed. I'd like to make one remark though. The abstract vectors provide 'random' access to vector elements, so to speak. That is, an abstract vector is a function Int->Value (or, Range->Value or even Lattice->Value). The function yields the value of a vector element given an arbitrary, 'random' index within vector's domain. Sometimes, random access is overkill. Surprisingly many problems can be solved with only a sequential access to a vector or a matrix: with matrix streams. Purely functionally, sequential access is defined by fold-like combinators (accumulating traversals) and by 'subranging' (and perhaps, general domain transformer functions). For performance reasons, we may want to define mapping (i.e., a point-wise transform) and folding of an associative function. A program that uses these higher-order combinators can be subjected to automated deforestation, which fuses traversals where possible. * Functional Approach to Texture Generation Jerzy Karczmarczuk. PADL02, January 20, 2002. The talk describes 'Clastic', a system for generation of _procedural_ textures. http://users.info.unicaen.fr/~karczma/Work/Clastic_distr/clastic.html The web site refers to a tutorial with many beautiful pictures. Raster graphics algorithms can be partitioned into "active" and "passive". Active algorithms take a pixelmap and actively modify it: they traverse the pixelmap or a subset of it -- often in complex ways -- and examine and set pixel values. Bresenham line drawing and contour filling algorithms belong to that class. Passive algorithms on the other hand do not actively draw anything. The algorithm is expressed as a function f(x,y). A rendering engine passes the function coordinates of a point and expects in return the color value at that point. The values of x and y of two consecutive invocations of f(x,y) are generally unpredicable. The function f(x,y) does not have access to a pixelmap and can't examine pixel values. Texture mapping algorithms belong to the passive category. Such algorithms -- shaders -- are used in animation and ray tracing pipelines. Clastic is an exploratory tool for passive raster graphics. The tool can generate regular (geometric) or random textures _described_ as relationships between 2D points and their colors. In Clastic, a texture is a function R^2 -> R^3, a function from points to RGB color vectors. The relationship is described purely declaratively. In Clastic, a texture function can be specified in a low-level way, for example circle (x,y) = if x*x + y*y <= 1.0 then tx (x,y) else rgb_white (x,y) which creates a circle filled with a texture tx(x,y) on a white foreground. However, if we define a texture combinator fmask h f g = \x -> if (h x == 0.0) then g x else f x and an overloaded function step x | x < zero = zero | x > zero = one | otherwise = half then we can write 'circle' as circle = fmask (\p -> step (1.0 - norm2 p)) tx rgb_white or even circle = fmask (step . (sone .- norm2)) tx rgb_white where sone p = 1.0 norm2 (x,y) = x*x+y*y and .- is subtraction lifted to (Float,Float)->Float functions. What is remarkable about the latter definition of 'circle' is that point coordinates do not appear at all. The shader 'circle' is defined as a pure combination of primitive textures. This coordinate-free style of programming is strongly encouraged by Clastic [*]. In Clastic, we transform things rather than coordinates. The coordinates should be hidden inside higher-order operators such as translate, rotate, scale; inside primitive textures such as rgb_white; inside 'soft objects' Point->Float such as 'sone'; and inside blending combinators such as fmask and `over`. As the paper and the Clastic tutorial show, combining a few primitives yields surprisingly complex textures such as impressive geometric patterns, tesselations and wallpaper including Escher reptiles, and woven patterns. Clastic uses purely functional, stateless random number generators (advocated by Ward). The generators are pure functions Integer->Float with a property that function values do not visibly correlate even for neighboring arguments. The "random noise" generators let Clastic produce dithering, fractal patterns (e.g., clouds), turbulence, and more complex marble-like textures and bump-maps. Finally, Clastic can apply transformers to other transformers: deformers. Examples include warping, lenses and random displacement to generate irregular wooden grain. The problem of inverting a transformation is generally rather complex. Still Clastic can deal with it. As the paper stresses, warping and deformation can be used abstractly, can be used generically and can be composed. This may make the coding by an order of magnitude shorter and easier than in the imperative approach. [*] Clastic uses programming version of Clean for Windows OS. The examples above are paraphrased in Haskell.

- Prev by Date:
**Re: Not quite enough abstraction** - Next by Date:
**Re: Not quite enough abstraction** - Previous by thread:
**Re: Not quite enough abstraction** - Next by thread:
**Re: Not quite enough abstraction** - Index(es):