Publications


PODC 84 Mitchell, Don and Michael Merritt, "A Distributed Algorithm for Deadlock Detection and Resolution", Principles of Distributed Computing, 1984.

A realization of Dijkstra's idea of the diffusing computation. A deadlock cycle can be discovered by processes reading and writing messages on objects. (pdf)

Mitchell, Don, "Generating Antialiased Images at Low Sampling Densities", SIGGRAPH 87.

This described an Antialiasing Module, a general routine for building an image by non-uniform sampling of a function. Specifically, a tile of blue-noise samples are used, along with a nonlinear reconstruction filter. (pdf, fig1, fig2, fig7)

SIGGRAPH 87
SIGGRAPH 88 Mitchell, Don and Arun Netravali, "Reconstruction Filters in Computer Graphics", SIGGRAPH 88.

The infamous "Mitchell filter" is derived by studying cubic filters, both mathematically and subjectively. Reconstruction with derivative values is also discussed. We wrote a simple ray tracer that returned image gradient values, but I only touched on it in the paper. (pdf, fig4, fig5, fig6, fig8, fig9, fig10, fig11, fig12, fig15, fig16)

Amanatides, John and Don Mitchell, "Megacycles", SIGGRAPH 89 Electronic Theater.

Johnny and I wrote a ray tracer called FX for the AT&T Pixel Machine, and this movie was our demo. The ray tracer parsed lisp, and so the model was a small file with recursive CSG definitions. Here is a high-resolution rendering of the final scene, and here is a wmv of the video (22 MB).

SIGGRAPH 89
GI 90 Mitchell, Don, "Robust Ray Intersection with Interval Arithmetic", Proc. Graphics Interface 90.

The FX ray tracer had a powerful system of nonlinear solvers that used interval arithmetic and automatic differentiation. With only 256K of memory per node, the Pixel Machine encourage highly procedural and recursive approaches to texture and modeling. ( pdf, fig1, fig2, fig3, fig4 )

Amanatides, John and Don Mitchell, "Some Regularization Problems in Ray Tracing", Proc. Graphics Interface 90.

FX did careful book-keeping to avoid numerical intersection errors, even when rays were near the corners of transparent objects. (pdf, fig1, fig2, fig3, fig4 )

GI 90
SIGGRAPH 90 Amanatides, John and Don Mitchell, "Antialiasing of Interlaced Video Animation", SIGGRAPH 90.

Generating interlaced video requires careful multidimensional filtering to avoid spatial, temporal and chroma aliasing. Interlacing images is a bad design, making these problems unnecessarily difficult. (pdf, fig5, fig6, fig8, fig10, fig11)

Mitchell, Don, "The Antialiasing Problem in Ray Tracing", Advanced Topics in Ray Tracing, Course Notes, SIGGRAPH 90.

Even by 1990, it was necessary to start out by refuting erroneous claims that "jaggies" were not caused by aliasing! Of course, there are other causes of jaggies, like bad gamma correction or nearest-neighbor image enlargement. (pdf)

SIGGRAPH 90
SIGGRAPH 91 Mitchell, Don, "Spectrally Optimal Sampling for Distribution Ray Tracing", SIGGRAPH 91.

One of the first quasi-random solutions to distribution ray tracing, although based on spectral analysis, not low-discrepancy quasi-random numbers. (pdf, fig8 & 9, fig11 & 12, fig13 & 14,

Mitchell, Don, "Three Applications of Interval Analysis in Computer Graphics". Frontiers of Rendering, Course Notes, SIGGRAPH 91.

More information about the techniques used by the FX ray tracer. (pdf)

SIGGRAPH 91
SIGGRAPH 92 Mitchell, Don, Pat Hanrahan, "Illumination from Curved Reflectors", SIGGRAPH 92.

One day, I told Pat that I knew how to do caustics: solve the Lagrange multiplier problem with interval solvers, and compute brightness from wavefront curvature. He said, "Let's visit the Geometry Center and program with no distractions!". We froze our asses off in Minneapolis, it was -25º F. (pdf, fig1, fig2, fig3, extra)

Mitchell, Don, "Ray Tracing and Irregularities of Distribution", Proc. 3rd Eurographics Workshop on Rendering, 1992.

Arbitrary-edge discrepancy was introduced. Optimal sampling patterns were found by Monte Carlo estimation of discrepancy. (pdf)

Eurographics 92
GI 93 Dobkin, David and Don Mitchell, "Random-Edge Discrepancy of Super-sampling Patterns", Proc. Graphics Interface 93.

Dobkin and I invented an algorithm for computing discrepancy. No need anymore for Monte Carlo estimation. (pdf)

Lacy, J. B., D. P. Mitchell, W. M. Schell, "CryptoLib: Cryptography in software.", Proc. 4th UXENIX Security Workshop, 1993.

Robert Morris Jr. and I modified my fast DES code to do fast UNIX password hashing. He later did something very naughty with that code, although I don't believe he intended the damaging effects of his internet worm. (pdf)

USENIX 93
SIGGRAPH 95 Kolb, Craig, Don Mitchell, and Pat Hanrahan, "A Realistic Camera Model for Computer Graphics", SIGGRAPH 95.

Pat and I had talked about this at Princeton, so they invited me to visit Stanford and help. I programmed the depth of field sampling on a lap-top I brought with me. (pdf)

Mitchell, Don, "From MUDs To Virtual Worlds", Microsoft Virtual Worlds Group, 1995.

A lot can be learned from text-based MUDS, but most VR enthusiasts were hostile to the idea that people could become immersed in a world without 3D graphics and head-mounted displays. I believe the people who designed Everquest understood this.

The ppt presentation is a talk at W.R.I.T.E. 95. (htm, ppt)

VWorlds 95
SIGGRAPH 96 Mitchell, Don, "Consequences of Stratefied Sampling in Graphics", SIGGRAPH 96.

This was a weekend hack in the middle of the virtual worlds project at Microsoft. But of course I had been thinking about this for years, so it was a very focused weekend! (pdf, fig1)

Dobkin, David P, David Eppstein, Don. P. Mitchell, "Computing the Discrepancy with Applications to Supersampling Patterns", ACM Trans. Graphics Vol 15, No. 4 (Oct. 1996).

Here you see a low-discrepancy pattern of 16 points. But I recommend blue noise, not low discrepancy. Discrepancy is too closely coupled to box-fitering. (pdf)

TOG 96
USENIX 98 Vellon, M., Kirk Marple, Don Mitchell, Steve Drucker, "The Architecture of a Distributed Virtual Worlds System", Proc. 4th USENIX Conf. on Object-Oriented Technologies and Systems, 1998.

We rejected VRML and designed a more MUD-like object model. This project ultimately grew into a huge confused effort, unfortunately. (pdf)

Betrisey, C., Blinn, J. F., Dresevic, B., Hill, B., Hitchcock, G., Keely, B., Mitchell, D. P., Platt, J. C., Whitted, T., "Displaced Filtering for Patterned Displays," Proc. Society for Information Display Symposium, 2000.

After Keely and Hitchcock invented ClearType, I wrote up the first technical analysis of what I called RGB decimation. The scientific problem has been overshadowed by politics. (pdf, fig1)

SID 2000
SIGGRAPH 2001 Mitchell, Don, "Quasirandom Techniques", SIGGRAPH 2001 Course 29.

Have I mentioned that I think blue noise works better than quasirandom sampling? (ppt)

Snyder, John, Don Mitchell, "Sampling-Efficient Mapping of Spherical Images", Microsoft Technical Report, 2001.

We develop measures of quality for mappings from the plane to the sphere. A number of mappings are analyzed, including some used to represent spherical textures and environment maps in graphics. (pdf, figa, figb, figc, figd, fige)

Sphere Mapping 2001
UW CSE 02-12-07 Shade, Jonathan, Michael F. Cohen, Don P. Mitchell, "Tiling Layered Depth Images", Tech. Report CSE 02-12-07, University of Washington, 2002.

Several years ago, I suggested to Michael that 3D ground cover would make multiuser game environments much more realistic. Jonathan found Wang tiles, which is a wonderful concept, making non-periodic expanses of texture from a finite set of square tiles. (pdf)

Home


Copyright © 2003 Don P. Mitchell. All rights reserved.