Thouis "Ray" Jones

Once upon a time, I worked in graphics and did graphics research, at MERL and in the MIT CSAIL Graphics Group. This page collects that work for reference purposes, but in general I no longer work in these areas or keep up on new results, except in the area of Poisson-disk pattern generation.

Graphics and other CS Publications

Linear-Time Poisson-Disk Patterns (Preprint)
Journal of Graphics, GPU, and Game Tools, 2011, Vol. 15, Issue 3, pp. 177-182.
Thouis Jones, David R. Karger

We present an algorithm for generating Poisson-disk patterns taking O(N) time to generate N points. The method is based on a grid of regions that can contain no more than one point in the final pattern, and which uses an explicit model of point-arrival times under a uniform Poisson process.

Efficient Generation of Poisson-Disk Sampling Patterns (Preprint)
Journal of Graphics Tools, 2006, Vol. 11, Issue 2, pp. 27-36.
Thouis Jones

Poisson Disk sampling patterns are of interest to the graphics community because their blue-noise properties are desirable in sampling patterns for rendering, illumination, and other computations. Until now, such patterns could only be generated by slow methods with poor convergence, or could only be approximated by jittering individual samples or tiling sets of samples.

We present a simple and efficient randomized algorithm for generating true Poisson Disk sampling patterns in a square domain, given a minimum radius R between samples. The algorithm runs in O(N logN) time for a pattern of N points. The method is based on the Voronoi diagram. Source code is available online.

See also the work by Daniel Dunbar and Greg Humphreys to appear in SIGGRAPH 2006.

Normal Improvement for Point Rendering
to appear in IEEE Computer Graphics & Applications, July/August 2004, pages 53-56.
Thouis Jones, Frédo Durand, Matthias Zwicker

Point models from scanned data invariably contain noise. Most denoising methods concentrate on positional information rather than normals, even though rendered images are affected more strongly by noise in normals than positions. We propose a novel method for denoising normals for point models, based on the bilateral filter. We treat the filter as a spatial deformation and update normals iteratively. The bilateral filter is feature-preserving; our extension to normals inherits this trait.

The source code for this paper was written as a PointShop3D plugin. It can be downloaded here. It may or may not work with the latest version of PointShop3D. I have not tested it recently. However, I tried to keep the code as clean as possible, so that it could be used as a reference for other implementations.

Interpolation Search for Non-Independent Data
in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), January 2004, pages 823-832.
Erik D. Demaine, Thouis Jones, Mihai Patrascu

We define a deterministic metric of "well-behaved data" that enables searching along the lines of interpolation search. Specifically, define $\Delta$ to be the ratio of distances between the farthest and nearest pair of adjacent elements. We develop a data structure that stores a dynamic set of $n$ integers subject to insertions, deletions, and predecessor/successor queries in $O(\lg \Delta)$ time per operation. This result generalizes interpolation search and interpolation search trees smoothly to nonrandom (in particular, nonindependent) input data. In this sense, we capture the amount of "pseudorandomness" required for effective interpolation search.
Errata: There is an error in our lemma for behavior on the uniform distribution. The behavior is correct, but the justification is not. A correction will be forthcoming. Thanks to Steven Gortler for finding this error.

Non-Iterative, Feature-Preserving Mesh Smoothing (Slides, Didactic demo)
SIGGRAPH 2003, pp. 943-949
Thouis R. Jones, Frédo Durand, Mathieu Desbrun

With the increasing use of geometry scanners to create 3D models, there is a rising need for fast and robust mesh smoothing to remove inevitable noise in the measurements. While most previous work has favored diffusion-based iterative techniques for feature-preserving smoothing, we propose a radically different approach, based on robust statistics and local first-order predictors of the surface. The robustness of our local estimates allows us to derive a non-iterative feature-preserving filtering technique applicable to arbitrary "triangle soups". We demonstrate its simplicity of implementation and its efficiency, which make it an excellent solution for smoothing large, noisy, and non-manifold meshes.


Example-Based Super-Resolution
Computer Graphics and Applications 22(2), March 2002, pp. 56-65
William T. Freeman, Thouis R. Jones, Egon C. Pasztor

Image-based models for computer graphics lack resolution independence: they cannot be zoomed much beyond the pixel resolution they were sampled at without a degradation of quality. Interpolating images usually results in a blurring of edges and image details. We describe image interpolation algorithms which use a database of training images to create plausible high-frequency details in zoomed images. Image pre-processing steps allow the use of image detail from regions of the training images which may look quite different from the image to be processed. These methods preserve fine details, such as edges, generate believable textures, and can give good results even after zooming multiple octaves.

Adaptively Sampled Distance Fields: A General Representation of Shape for Computer Graphics
SIGGRAPH 2000, pp. 249-254
Sarah F. Frisken, Ronald N. Perry, Alyn P. Rockwood, Thouis R. Jones

Adaptively Sampled Distance Fields (ADFs) are a unifying representation of shape that integrate numerous concepts in computer graphics including the representation of geometry and volume data and a broad range of processing operations such as rendering, sculpting, level-of-detail management, surface offsetting, collision detection, and color gamut correction. Its structure is uncomplicated and direct, but is especially effective for quality reconstruction of complex shapes, e.g., artistic and organic forms, precision parts, volumes, high order functions, and fractals. We characterize one implementation of ADFs, illustrating its utility on two diverse applications: 1) artistic carving of fine detail, and 2) representing and rendering volume data and volumetric effects. Other applications are briefly presented.

Antialiasing with Line Samples
Rendering Techniques '00 (Proceedings of the 11th Eurographics Workshop on Rendering), pp. 197-205
Thouis R. Jones, Ronald N. Perry

Antialiasing is a necessary component of any high quality renderer. An antialiased image is produced by convolving the scene with an antialiasing filter and sampling the result, or equivalently by solving the antialiasing integral at each pixel. Though methods for analytically computing this integral exist, they require the continuous two-dimensional result of visible-surface computations. Because these computations are expensive, most renderers use supersampling, a discontinuous approximation to the integral. We present a new algorithm, line sampling, combining a continuous approximation to the integral with a simple visible-surface algorithm. Line sampling provides high quality antialiasing at significantly lower cost than analytic methods while avoiding the visual artifacts caused by supersampling's discontinuous nature.

A line sample is a line segment in the image plane, centered at a pixel and spanning the footprint of the antialiasing filter. The segment is intersected with scene polygons, visible subsegments are determined, and the antialiasing integral is computed with those subsegments and a one-dimensional reparameterization of the integral.

On simple scenes where edge directions can be precomputed, one correctly oriented line sample per pixel suffices for antialiasing. Complex scenes can be antialiased by combining multiple line samples weighted according to the orientation of the edges they intersect.


Useful Things: