From research.att.com!compgeom-owner Tue Jun 4 21:05:20 1996 From: Paul.Heckbert@HOSTESS.GRAPHICS.CS.CMU.EDU To: compgeom-discuss@RESEARCH.ATT.COM Subject: comments on "Application Challenges to CG" Content-Length: 8628 X-Lines: 191 Comments on the report "Application Challenges to Computational Geometry" by the Computational Geometry Impact Task Force (http://www.cs.princeton.edu/~chazelle/taskforce/CGreport.ps) I like this report! First, below, my general comments on the state of computational geometry and then some specific comments on additional challenges in the areas of computer graphics and mesh generation. General Comments on the State of Computational Geometry I agree that computational geometry can be much more relevant and helpful to the larger scientific and engineering communities by becoming more applied and more interdisciplinary. I believe that computational geometers too often get caught up in pointless "big Oh races". There is much, much more to the design and analysis of algorithms than asymptotic worst case analysis. Anyone who wants their algorithms to be implemented and used should keep in mind that the "n" in problem sizes is typically bounded and often quite small! Bounded because it is typically limited by current memory size on the computer, and often quite small because of the statistics of the input. Instead of spending one's time reducing log* to inverse Ackermann, wouldn't it do more good for mankind to optimize the solution to a common problem by an actual factor of 10 or 100? Constants matter! Certainly, pure theory has its place, but I believe that computational geometry has to balance theory and practice. Currently the field is out of balance, leaning too far toward theory. As a concrete example of the difference between the theoretical mindset and the practical mindset, consider the problem of point inclusion testing within an n-sided polygon. If you asked most computational geometers (or computational geometry books) about point inclusion testing, they might say: "it's O(log n) for concave polygons if you triangulate as a preprocess and then use Kirkpatrick's algorithm" but if you looked in the practical computer graphics literature, specifically Eric Haines' paper "Point in Polygon Strategies" [Graphics Gems IV, Paul Heckbert, ed., Academic Press, 1994], you'd conclude: "for small n, test against the line equation of each edge", "for large n, use a grid data structure, and you'll typically get O(1)" Quite a different answer! Haines points out that typically n=3 or 4 when ray tracing surface models. Haines' paper is certainly not the last word in practical point inclusion testing, but it does provide basic, important information that cannot be found in most computational geometry texts. (Randolph Franklin has also explored practical algorithms for this problem.) Shouldn't practical algorithms for basic geometric operations be within the scope of computational geometry? Or do computational geometers prefer to let computer graphics and geographic information systems programmers claim that "territory"? As another example, Voronoi diagrams can be computed on discrete grids, yielding an O(1) discrete nearest neighbor algorithm [Danielsson, Comp. Graph. & Image Proc., 14, 1980, 227-248]. Sometimes a discrete Voronoi is good enough. This algorithm is used in low level software for color image quantization to 8 bit pixels on some personal computers. One typically does not hear about such algorithms in computational geometry. I propose that computational geometry research should not focus on minimization of asymptotic worst case complexity and the computation of "optimal" solutions as its primary goals, but should broaden its scope to include additional goals, among them: * min. asymptotic expected case complexity, for realistic inputs * min. expected cost for typical problem sizes * min. expected memory cost * fast computation of approximate solutions * reasonably efficient, easily implementable algorithms * working implementations shared on the internet Additional Challenges from Computer Graphics Some additional research challenges from computer graphics beyond those listed in the report: * What is the best data structure to optimize intersection testing with surfaces in ray tracing? (regular grid, octree, k-d tree, BSP tree?) * What is the best data structure to optimize visibility culling (of off-screen or occluded objects) in a z-buffer algorithm [see Greene-Kass-Miller, SIGGRAPH 93]. * Answer the two questions above in a dynamic scene. * What is an analyzable, yet realistic parameterized statistical model for scene geometry? (The fractal dimension of scenes varies.) * How do you deal with very complex scenes larger than what can fit in primary memory? (i.e. how do you use disks?) Multiresolution modeling is a promising approach. * How do you simplify a surface model to a given size or a given geometric approximation error? [Heckbert-Garland, Graphics Interface 94]. * Promising early work in scanline (sweepline) and object space (continuous) rendering algorithms has largely been overtaken, in practice, by more brute force image space (discrete sampling) algorithms such as z-buffer and ray tracing, mostly because the latter are more easily put in hardware or generalized. How can computational geometry recast some of its algorithms to take advantage of the large existing base of z-buffer and ray tracing hardware and software? * What are the lessons for computational geometry here, regarding simple vs. complex algorithms? * How do you morph one polygon into another? One polyhedron into another? (choosing a "good" correspondence is the hard part) Additional Challenges from Mesh Generation Adding to the current (very good) discussion in the report: * The desired element shape depends on the problem being solved (e.g. structural analysis FEM, fluid flow FEM, or surface modeling for display). Computational geometers need to understand the varied geometric needs of different applications. * Anisotropic meshes are particularly important for viscous flow [Simpson, Applied Numer. Math., 14(1-3), 1994]. * Maximizing the minimum angle, minimizing the maximum angle, and Delaunay triangulation are not always the answer (even though they are theoretically "pretty"). * No mesh can be fully judged without its basis functions. The basis functions often place constraints on acceptable meshes. Computational geometers working in this area need to learn more about FEM methods. * Many FEM practitioners know what meshes work for their particular problem (e.g. one person does only structural analysis of bridges, another generates studies aerodynamics of wings), but much of the work is art, not science. There are few researchers attempting to formalize the entire field of mesh generation, and few researchers doing theoretical error analysis of FEM solutions as a function of mesh geometry [Zienkiewicz-Zhu, Intl. J. Numer. Meth. Eng., 32, 783-810, 1991]. There is great potential for innovation here. * Output from some CAD systems is near-garbage (e.g. poorly designed file formats, buggy software), making mesh generation of these models very difficult. [Ernst Mucke, ANSYS, personal communication] Perhaps more computational geometers should be involved in file format standardization efforts. * A survey of the practical side of mesh generation is [Thompson & Weatherill, Aspects of Numerical Grid Generation: Current Science and Art, 11th AIAA Applied Aerodynamics Conf., Aug. 1993, pp. 1029-1070] Software The five Graphics Gems books contain some computational geometry code. The code is at ftp://ftp-graphics.stanford.edu/pub/Graphics/GraphicsGems/ Correction to References The Heckbert-Garland tech report cited as [68] is now two tech reports: Michael Garland and Paul S. Heckbert, Fast Polygonal Approximation of Terrains and Height Fields, CS Dept., Carnegie Mellon U., Sept. 1995, CMU-CS-95-181, http://www.cs.cmu.edu/~garland/scape Paul S. Heckbert and Michael Garland, Survey of Polygonal Surface Simplification Algorithms, CS Dept., Carnegie Mellon U., to appear, In order to encourage the discussion and reevaluation of computational geometry mentioned in the report, I hope my comments and those of others will be available somewhere on the World Wide Web in collected form. Paul Heckbert ph@cs.cmu.edu Computer Science Dept., Carnegie Mellon University 5000 Forbes Ave, Pittsburgh PA 15213-3891, USA World Wide Web: http://www.cs.cmu.edu/~ph