Some computational geometry and physics projects

Cool projects related to geometry and physics, at DGI:

Geomechanics --

Extracting a liquid from porous rock, (say water from an aquifer or oil from a hydrocarbon deposit), may lead to compaction of the rocky medium. Compaction at one point causes displacement of the rocky medium at nearby points, both higher and lower than the point of extraction. And, displacement at one point in turn causes displacement at other points.

Downward displacement is called *subsidence*. Subsidence is frequently of great interested, both at the surface and in the subterranean medium. Subsidence at any particular point is affected by the extraction of fluid at all other points.

For a major oil company client, I provided an application to compute subsidence and dependent quantities based on given changes in spatiotemporally varying geophysical quantities in their reservoir models, principally, pressure changes. These are irregular 4D cellular models with typically tens of millions of cells, and the computational field would be sampled on 3D grids with billions of points. The theory behind the computation is from 1973. The major computational cost is in evaluating many high-resolution 2D convolutions, nasty non-separable ones with kernels as large the signals. I satisfied the client's requirement to provide results for their models in semi-interactive time on engineering workstations by exploiting their available parallel resources, both with multi-core CPUs and GPUs in their existing graphics cards. The CPU parallelization uses OpenMP, the GPU version uses CUDA. Both versions use 2D fast Fourier transforms to compute the 2D convolutions.

Seismic simulation --

Geology is all about strata, layers that are tilted and broken by faults. The interface between two strata with different acoustic impedance (i.e., layers in which the speed of sound is different) produces reflections of impinging sound waves. Seismic studies, which collect reflected signals over a large 2D field resulting from known "pings" provide an important tool in mineral exploration and in monitoring of the effects of extraction. Producing some sort of image of the subterranean structure from the seismic data is the well-known seismic inversion problem, which is typically performed on supercomputers.

My seismic simulation project goes in the opposite direction: From a given state of the cellular reservoir model, to show the expected response everywhere to a hypothetical seismic ping, given as a wavelet. This is easier than the seismic inversion problem, but still computationally intensive, involving many 1D convolutions. Variations in the formats and conventions of the input data complicated the coding. The app is now highly used in various workflows of the client geophysics groups.

Nitty-gritty geometry --

Various applications involving intersections and interpolations in large 3D irregular cellular models. My planar curtain cross-section code put our company way ahead of the competition.

Interactive isosurfaces in large gridded fields, based on marching cubes, parallelized for multi-core and for GPU.

Geometry and physics prior to DGI

Physics and geometry engines for immersive 3D games. 1995-1999 --

As a consultant, major contributions to about half-a-dozen shrink-wrapped games for PCs in C++ using Direct3D, including first-person shooters and car racing games. I had the best 3D collision detection in published games c. 1998, using my own temporal extension to the separating axis theorem (See Siggraph Proceedings 1996).

One of the most fun game projects was my first, in which the client's unusual idea was to locate the interactive play (a campy miniature golf game inspired by the movie Betelgeuse) in a universe constructed from many still photographic images of tabletop models constructed by the model shop at Industrial Light and Magic--physical models, not digital effects. One of the interesting problems was camera calibration from noisy data from photos from various viewpoints with fiducial marks on fragile models constructed to be temporary. Another class of interesting problems was providing tools for the artists, for example for sketching in outlines of occluders.

NASA Ames, Institute for Advanced Computation, 1980-83 --

Solving partial differential equations (full compressible, transonic Navier-Stokes) on vector supercomputers.

PhD dissertation, University of California --

"The Compact Euclidean Space Forms of Dimension Four" was a novel application of computational methods to a problem in pure mathematics, being a special case of Hilbert's 18th Problem. From one point of view, it was a question in four-dimensional crystallography. The computational representation involved algebraic groups of 4x4 integer matrices. Entirely discrete, not a single floating point operation in the project.