Michael Garland - US grants

The project researches a new form of operating system to manage a model of
computing called an Active Space. It integrates physical spaces that contain
ubiquitous computers into a computational environment that supports human
activity and applications. With anytime/anywhere ubiquitous devices, the
users' view of the computational environment is extended beyond the physical
limits of a computer and is placed into the surrounding physical space,
augmented with computers that sense and affect that space around the user.
Applications become mapped not just to views associated with specific
windows in a monitor but instead to the physical environment. Therefore,
the physical space, augmented with communicating computer devices, becomes a
distributed computing system.
Active Spaces have the potential for creating multi-billion dollar
industries. Automated surgery, collaboration and engaged learning are a few
of the compelling examples. Gaia, an operating system for Active Spaces,
will accommodate diversity by exploiting standards for interoperation and
cooperation. System services track, authenticate and support mobile users
with reconfigurable graphics, multimedia and Active Space applications. A
unifying object bus, component model, and adaptive stream model extends plug
and play to distributed mobile ubiquitous computers cooperating to support a
computational environment within physical spaces like cities, buildings and
rooms.

Proposal #0098170
U of Ill Urbana-Champaign
Michael Garland

Numerous graphics applications in areas ranging from CAD/CAM to realistic immersive simulators rely on increasingly complex datasets to achieve convincing levels of visual realism. However, the enormity of the raw geometric data frequently makes it impossible to efficiently process such datasets given limited hardware capacity. Surface models containing millions of triangles are now commonplace, and advances in acquisition technology are making models containing several billion triangles available. Consequently, there has been considerable interest over the last decade in techniques for the automatic simplification of highly detailed polygonal models. However, current methods are, almost without exception, completely incapable of
processing input models of this enormous magnitude. This is a very serious shortcoming, as these are exactly the class of models for which effective simplification methods are most pressingly needed. The goal of this project is to develop new techniques for representing and processing very large scale polygonal surface models, enabling the efficient use of extremely complex models far beyond the capability of current systems.

Algorithmic scalability is essential in this domain. This research is focused on developing simplification methods which combine simple out-of-core data operations with more complex output-sensitive (i.e., dependent only on the output, rather than the input, size) processing phases. The general approach
of this project is to adopt recursive partitioning strategies directed by quadric error metrics. An approximation can be produced from any partition of the vertex set by merging all vertices within each cell of the partition. The use of quadric error metrics means that the aggressive simplification methods
designed for this project can be seamlessly coupled with other quadric-based simplification algorithms in a multi-phase process.

The goal of this project is to develop methods enabling the visual exploration of large, complex, non-planar graphs. New algorithms are being developed for coarsening graphs that preserve the overall structure of the graph while greatly reducing its complexity. These algorithmic techniques allow for building multi-scale representations that make traditional graph analysis and data mining operations far more efficient. They also provide a basis for advanced visual exploration of complex graphs. In addition, this project is also seeking to leverage the latest advances in computer graphics hardware and rendering technology to generate graph visualizations of the greatest possible clarity in real time, so that a user can interactively explore and understand the most structurally intricate of graph structures.
These technologies have broad application in many diverse and important domains, including protein function analysis, social network understanding, communication network design, data mining, and security market analysis. The new visualization methods are implemented in software systems developed in this project and released under an open source license to aid others in research and development projects. The software, publications and other information on this project can be accessed on the Web site (http://graphics.cs.uiuc.edu/~garland/research/graphs.html).