With the completion of the human genome sequence, and with the proliferation of genome-related annotation data, the need for scalable and more intuitive means for analysis becomes critical, At Variagenics and Small Design Firm, we have addressed this problem with a coherent three-dimensional space in which all data can be seen in a single context. This tool aids in integrating information at vastly divergent scales while maintaining accurate spatial and size relationships. Our visualization was successful in communicating to project teams with diverse backgrounds the magnitude and biological implication of genetic variation.

Techniques are discussed for creating a rendered view into a 3D scene, interactively based on the locations and orientations of the observer’s head and the display surface. Stereoscopic headmounted displays (HMDs) demonstrate a simplified, special case of these techniques, because the eyes and monitors move in unison. A largely overlooked class of interactive displays uses the relative positions between the eyes and monitor as input. These displays can be stereo or monoscopic, fixed or mobile, and the rendering process should incorporate the correct perspective distortion, which depends on the locations of the viewpoint(s) and the display monitor. Three real-time graphics display systems were prototyped and examined: a high-resolution display which corrects the perspective projection based on the location of the observer’s eye; the same display, extended to modify the view as the monitor is tilted and swiveled; and a handheid LCD display which can be freely moved and rotated as it displays a view based on the eye and monitor positions. A simple experiment indicates that tracking the head and providing the appropriate view improves the ability to pick specific 3D locations in space using a 2D display, when compared to a fixed view and a mouse-controlled view.

We have developed a virtual environment system which supports multiple simulations, including virtual actors. These actors exhibit motor behavior in response to activity in the environment. We present an example actor, whose low-level behavior is modeled after physiological analyses of cockroach motor behavior. The sensori-motor activity of our roach is generated by a hierarchical control structure. Coupled oscillators generate basic gait patterns, which are modified by reflexes feeding in from the environment. Stepping and stance are executed by kinematic motor programs, which move the legs and body. The reactive level associates motor behavior with events in the virtual environment, to simulate perception and implement higher level behaviors. The activity of the virtual actor is determined only when it is situated in the environment, and interacts with the user and other simulations.

Accurate simulation of Newtonian mechanics is essential for simulating realistic motion of joined figures. Dynamic simulation requires, however, a large amount of computation when compared to kinematic methods, and the control of dynamic figures can be quite complex. We have implemented an efficient forward dynamic simulation algorithm for articulated figures which has a computational complexity linear in the number of joints. In addition, we present a strategy for the coordination of the locomotion of a six-legged figure - a simulated insect - which has two main components: a gait controller which sequences stepping, and motor programs which control motions of the figure by the application of forces. The simulation is capable of generating gait patterns and walking phenomena observed in nature, and our simulated insect can negotiate planar and uneven terrain in a realistic manner. The motor program techniques should be generally applicable to other control problems.

Let an arrangement of blue lines in 3-space be fixed, and imagine a movable red line entangled in the arrangement. We show an Ο(n4α(n)) algorithm for building a data structure that permits enumeration of mutually inaccessible classes of such red lines, where α(n) is the inverse Ackermann function. The core of the algorithm is a construction of Ο(n2) 2-D arrangement of hyperbolas, each in Ο(n2α(n)) time.The algorithm is applied to stabbing 3-polytopes, enumerating pairwise-visible face pairs, enumerating 2-D projections of convex 4-polytopes, and other problems, resulting in Ο(n4α(n)) algorithms in each case.

An O( n 2 ) hidden-surface removal algorithm is shown. This is an improvement over the previous best worst-case performance of O( n 2 log n ). It has been established that the hidden-line and hidden-surface problems have an Ω( n 2 ) worst-case lower bound, so the algorithm is optimal. However, the algorithm is not output-size sensitive. Two corollaries to the result are (1) hidden-lines can be removed in optimal O( n 2 ) time, and (2) the portion of a 3-D polyhedron visible from a given interior point is constructible in optimal O( n 2 ) time.

Let P be a convex polytope in Rd. We discuss the problem of placing a light source at infinity so as to minimize or maximize the shadow area of the polytope. By shadow area we mean the (d-1)-volume of the orthogonal projection of P on a hyperplane normal to the direction of illumination. Let n be the number of (d-1)-dimensional facets of the polytope. We exhibit two algorithms for finding the optimal placement of the light source. One algorithm uses O(nd-1) space and time to find the optimal placement. The other uses O(n) space to find the optimal placement in O(nd-1 log n) time. Also, we present an interesting result relating the minimum and maximum shadow areas of P to the radii of the inscribed and circumscribed sphere of a zonotope derived from P.