Computer graphics

...and a few other things.

I've been interested in computer graphics for over twenty years, and I've had a few ideas which I haven't seen elsewhere. Fully descriptive pages are coming on these ideas (this site has just been revamped, so please give me a few days).

These ideas may be known, or indeed common practice, but in case they aren't they are presented here, in no particular order, as a selection of graphics rhinestones (and a few non-graphical crystals of cubic zirconia).

Bressenham line drawing variant

Rather than stepping in the direction of greatest distance, it is of course possible to step the other way. By using an integer divide, the number of pixels in each run can be determined, and by updating the error term accordingly the Bressenham test can be performed for the one pixel in doubt (corresponding to rounding up or rounding down). To avoid the divide, the scan can simply be run as a traditional Bressenham until the second step (bearing in mind that the first run is half length, and is a separate issue), and the result multiplied to determine whether the last pixel should be counted. Or even that can be avoided by conservatively working out which way to round. This is worthy of more detailed explanation. The point, of course, is that for most graphics architectures it's possible to fill in a number of horizontal pixels more quickly than running the Bressenham algorithm for each pixel. Other gradients can be supported as different base gradients from which to determine an offset.

Z buffer divide

This is pretty implausible, but since divides are slow on many processor architectures it might just be feasible to throw pixels at the display architecture and let the Z buffer hardware (which is highly pipelined) do the divides for you. This might just help in a ray tracer, or similarly highly parallel (and partly SIMD) application, on a good day. I doubt it'll help with a modern processor, since it depends on very good graphics bandwidth; obviously this is no competitor to graphics hardware actually capable of inherent raytracing, as suggested in the Stanford paper on "Ray Tracing on Programmable Graphics Hardware" (SIGGRAPH 2002).

Ray tracing fur

I have an implementation of this nearly complete. Basically, it's a voxel approach, with the option of using photon mapping to handle sub-"surface" scattering (see 2001 SIGGRAPH papers). Each voxel can hold a list of contained hair fragements, but an alternative is to hold a coverage value and two bytes of hair orientation in polar coordinates (as Jensen suggests in his photon mapping book) to represent each hair. Another byte can be used to double the voxel space in each dimension by providing bit-mapped 8-way coverage (and round up to a word per hair per voxel), making a 512 cube usable rather than 256 cube, in my test. Specular hair illumination is determined by producing a virtual surface normal as a cross product of the hair vector and a vector at right angles to the hair vector and the view direction. It's not as efficient as PRMan hair, but it's doable.

Summed area tables

Someone at SIGGRAPH 2001 was trying to present an average area table, which seems trivially not to work (if there's an explanation I'd like to see it, but the audience member querying the lack of precision didn't seem to get a good answer). However, by producing a mip-map style area average you could produce a lossy summed area offset from area averages, within the original number of bpp. This may or may not be any more efficient than just using SATs.

Back face cull by presorted angle

This is only really for isometric projections, but if the polygons in a scene are stored sorted (in a 2-d BSD?) by their surface normal, the back-face culling can be performed without visiting the culled portions of the scene graph (regardless of viewing angle). An approximate, pessimistic variant can be used for perspective.

Second RAMDAC

If the frame rates of two displays match and line rates are integer multiples, a frame-line sized buffer is sufficient to construct one filtered output from another, without additional bandwidth.

100Hz television (120Hz for US readers)

This one puzzles me. I own a 100Hz Sony television (with an apalling user interface, but that's another story), which allegedly contains some "DRC" motion interpolation circuitry. The result takes horizontally smooth scrolling text and seems to make it judder at 25Hz - and none of the alternative display modes (other than 50Hz progressive scan) helps. While I appreciate that interpolating the motion would be nice, the point of a 100Hz display is primarily to reduce flicker - not to produce smoother motion; at least, I can see a 50Hz tube flickering out of the corner of my eye, but I've never heard of anyone objecting to the fluidity of motion. Why not just interpolate the colours between the fields of successive frames in order to construct the extra information? Presumably there are (or were) 100Hz systems doing this, and I can't think they make more of a mess of the picture than this allegedly top of the line Sony does. A variant would be to support refresh at 150Hz, which would allow the interlaced fields to be interpolated in a relatively obvious manner; while this would alleviate much of the problem with the image processing, producing such a high frequency display (even at low, TV resolution) may be difficult at the physical size of high end CRT televisions.

100Hz digital television revisited

Assuming that motion compensation is wanted for intermediate fields of a high refresh frequency television, a set containing a digital encoder (which mine does not) could use the motion compensation encoded in the MPEG stream to try to produce the intermediate fields. I'd be interested to know whether any digital sets attempt this.

On MPEG

There are two issues with MPEG which I would like to see addressed (I'm not up to speed on the standards process, so these may well have been considered already). Firstly, and most simply, MPEG handles full screen fades (to black or white) very badly - with large bands of quantized colour and sudden jumps; since this is a common televisual feature, it would seem practical to provide support as a special case. Secondly, since digital recorders such as TiVo and Sky+ are becoming more common, it would be nice to have a coordinated mechanism for adapting the bandwidth of the encoding. Perhaps this will be addressed in a future, wavelet-based variant; certainly the ability to encode the original digital stream, without quantization errors, would be nice (Sky+ may be able to do this, but I presume TiVo can't).

On image editing

Some features I'd like, and will program into an editing utility one of these days. Firstly, continuing the quantization theme, my previous comments on MPEG apply equally to (the older variant) of JPEG. That is, I have yet to meet a (general) image editing application with the option of preserving the JPEG settings of the read image, thus avoiding repeated quantization errors to unmodified sections. It would also be possible to support changes in the compression level in such a manner as to minimise changes in quantization boundaries. I also have a planned utility which would support optimizing the quantization levels to allow a particularly good match for some sections of the image, chosen preferentially over others according to the importance assigned by the user - if only by manually editing the quantization levels and supporting clamping to a multiple of this level in some regions; I gather some form of such a utility is commercially available, although I'm not sure exactly what its functionality is.

Drawing encodedly

A corollary to the above is to enable the user to draw directly in the compressed (or at least quantized) representation. It's feasible to allow direct manipulation of the factors of a JPEG cell under the "brush", possibly within preselected quantization levels; there are a number of options which spring to mind for the user interface to this. Equally, and more intuitively, one can draw directly with wavelets. There may be a steep learning curve in this (I don't think I would struggle, but I probably have more experience of compression related image transformations than the average artist), but the result would be useful for those particularly concerned with image sizes, such as web designers. Editing the quantized representation in this way is substantially easier than any attempt to manipulate the positioning of image components so as to optimize the non-lossy portions of compression. By the latter I mean such tricks as picking alternative dither patterns and orders so as to reduce the file size under LZW or LZ77 compression (for GIF and PNG respectively); this would be nice if there was a way to do it, but the knock-on effect means that, other than last minute selection between options, it is impractical - a change which makes a file smaller could well have an adverse effect on the representation of later changes.

GIF subdivision

One possible exception to the above allegation that GIF optimization is impractical (er, okay, in addition to colour reduction, despeckling, and all that jazz) would be to identify some region of the image which is locally similar, in encoding terms. Then this region could be encoded as a second frame with zero delay; in order to remove the boundary from interfering with the spatial coherence of the former layer (and indeed the encoding of the second frame should also be improved). While this approach could be applied automatically, with a bit of experimentation, this mechanism could also be applied to encode layers of a bitmap image (such as used by, e.g., PhotoShop). A concern is that some applications do not support animated GIFs and therefore would not display the result correctly.

On printing

Another art package feature; I notice that Epson (and now HP?) have colour calibration for their printers, and certainly printer drivers have for some time supported colour translation targetted directly at their own inks. Some drawing packages (I think particularly of CorelXARA/Xara X) have a "show printer colours" option, which attempts to represent the printer's colour gamut on the monitor. This is inherently doomed to represent a particular set of viewing conditions. Given that the printer drivers already contain information about the ink and paper properties, would it not be possible to make this data available to the art package in such a way that it is possible to edit the image while viewing it under a number of configurable light conditions? Windows may not support this, but it may be a feature of future systems. Such a system would make it easier to design spot colour and special effect products, and enable proper previewing of, for example, combinations of matte and gloss effects.

Combining ray tracing and polygon rendering

Ray tracing can be efficient for determining visibility in large scenes; if shading is simple, the polygons hit by the ray-tracer can be thrown at a polygon renderer (thus avoiding rendering the unnecessary polygons) to use the hardware shading facilities. Correspondingly, and this is better known, a polygon renderer can be used to determine pixel to polygon mapping, and a ray-tracer can then be used for the shading (and to redetermine additional shading arguments).

Silhouette transparency

A visibility map can be determined for pixels in a polygon, mapping whether the surface "behind" the polygon is hit by a ray passing through that pixel in a given direction. The full data is an arbitrary 2d function per pixel, but the paper in SIGGRAPH 2001 (or possibly 1999, have to check) on mapping lighting information on a per-pixel basis (to a quadratic) might make it possible to do something efficient. I'll produce an example of this shortly. Anything continuous is probably better than the plain polygon.

Eye ray photon maps

By storing "eye ray photons", an estimation of the contribution of each section of the scene graph to the image can be generated. High density regions should probably be more highly tesselated, and should gain higher resolution photon map information.

GIFSCII

i.e. bitmap to ASCII converter. I've been working on variants of these for a while. One idea to try, attempting to retain the full resolution of the character definition, is to examine a wavelet encoding of the character map in comparison with the encoding of the relevant image cell. Small differences in the size, offset or orientation of the most significant wavelets imply a good match. More details to follow. Note that this doesn't work well with boundary highlighting.

YARGH

Yet another raytracing graphics hardware (architecture). Not surprisingly, having spent four years at Advanced Rendering Technology, there are a few ideas I would like to try out as an alternative hardware ray-tracer. I'm working on the principle of 64-bit integer (fixed point) geometry and a large number of very simple execution units, running in a dataflow manner. More details on-line soon; I'm expanding my fluency in VHDL to try to produce a simple example and explain myself better.

Tiled Perlin noise

There is, I am sure, a much better way of doing this, but this is a RenderMan trick that I have used in the past. The problem I was trying to solve is to get a two dimensional, tiled, noise texture (for use on a desktop backdrop, for example). Merely mirroring the texture was rejected as being too visible (as well as having a possible higher order discontinuity), so I needed a noise function which was appropriately periodic without passing back through the same texture coordinates. I used a four dimensional noise function (provided by newer variants of the RenderMan Shading Language), with the u ordinate mapping to the angle around a circle in the first two noise coordinates, and the v ordinate correspondingly tracing a circle in the other two noise coordinates. The disadvantage of this approach is that the noise function is aligned to cartesian coordinates, so there is some variation in the frequency of the noise as the alignment of the tangent to the circles varies; some correction could be made to compensate for this. I did consider tracing a square rather than a cube, which would avoid the frequency variation, but turning a right angle may cause a high order discontinuity depending on the noise function in use.

MandelJulia

This is a simple idea for a pretty picture (which I have produced) which is a mathematical variant of a photomosaic. The idea was simply to render a low resolution Mandelbrot set, with each cell made up of a low resolution Julia set (seeded at the coordinates of the corresponding Mandelbrot sample). The number of Mandelbrot iterations before exceeding the limit defines the saturation of the cell; the Julia set affects only the hue of the pixels of the sub-image. The concept which makes this possible is the resolution of a modern ink-jet printer. I rendered a square of approximately A4 width at 1440x720dpi printer resolution, that is 11918x5959 pixels, on an Epson Photo 870. This enabled the Mandelbrot set to be rendered with 101x101 cells, each a 118x59 pixel Julia set rendering. I'll put the (trivial) source on-line shortly, but the image itself is obviously huge, and doesn't compress down very easily...

Pole position 6809

This is a trivial one - my watch (a Timex Datalink) has a programmable Motorola 6809 in it. I have an idea for how to fit a Pole Position-style racing game into the 1K available. Details following...

Datalink compiler

Not graphics, but programming. I'm planning on knocking out a compiler for the Datalink, working entirely on C++ preprocessing (include a header, write the program you want, compile it, run it, get the binary for the watch). I know how to do it, it's just finding time. I thought this approach was really horrible until I saw Larry Paulson do the same thing in "ML for the Working Programmer"...

Maze solving

In my Part IB project, I was required to produce a maze solver as part of learning C. In the process, I came up with several interesting ways of solving mazes, some of which are obscure. I'll be putting these on-line shortly (they're hard to describe in brief).

And finally... my PhD proposal

On beam tracing, with algebraic integration. The proposal itself is available as gzipped PostScript here.

Return to the Home page.