Today CAD programs are not just producing mind-blowing graphics pictures or convincing virtual models that can be interactively manipulated and changed. They also can yield tangible, physical artifacts, thanks to the development of many layered manufacturing techniques and the emergence of services such as Shapeways [2011] and Ponoko [2011],. Creating, manipulating, and studying such 3D artifacts adds a whole new loop of feedback to the design process. This extra experience is also highly useful in the teaching of computer-aided design. In a graduate course on Solid Modeling and Rapid Prototyping we have used the design and realization of dissection puzzles as a training tool. Dissection puzzles are particularly valuable design objects, since they not only train spatial understanding, but they also drive home issues concerning accuracy and tolerances in a very "hands-on" manner. In this poster and in the accompanying models we demonstrate some of the dissection models that we studied and elucidate the modeling issues associated with each type.

Summary form only given. Today's graphics programs cannot only produce stunning photo-realistic images or convincingly real scene displays for interactive exploration, they can also produce physical output - thanks to the emergence of several different layered manufacturing technologies. For many design activities creating tangible models through some rapid-prototyping prcess is a new and crucial feedback loop for debugging the functionality or customer-appeal of a new product. Dr. Séquin has two decades of experience with creating mathematical visualization models and designs ranging from university buildings to abstract geometrical sculptures. Turning these virtual creations into physical realities, however, raises a whole new set of issues that are often overlooked in the initial virtual design phase.

Summary form only given. Today's graphics programs cannot only produce stunning photo-realistic images or convincingly real scene displays for interactive exploration, they can also produce physi cal output - thanks to the emergence of several different layered manufacturing technologies. For many design activities creating tangible models through some rapid prototyping prcess is a new and crucial feedback loop for debugging the functionality or customer-appeal of a new product. Dr. Sequin has two decades of experience with creating mathematical visualization models and designs ranging from university buildings to abstract geometrical sculptures. Turning these virtual creations into physical realities, however, raises a whole new set of issues that are often overlooked in the initial virtual design phase.

Interactive 3D computer graphics extends beyond the creation and manipulation of fancy, virtual, on-screen models. It also plays an important role for making repetitive or symmetrical patterns, constructing 3D CAD files for rapid prototyping, or drawing 2D nets that can be folded up into 3D paper or cardboard models. To make effective mathematical visualization models one or more of these modes may have to be engaged. This will be demonstrated in the context of realizing highly symmetrical embeddings of regular maps on surfaces of higher genus.

An automated design synthesis system based on a multi-objective genetic algorithm (MOGA) has been developed for the optimization of surface-micromachined MEMS devices. A hierarchical component-based genotype representation is used, which incorporates specific engineering knowledge into the design and optimization process. Each MEMS component is represented by a gene with its own parameters defining its geometry and the way it can be modified from one generation to the next. The object-oriented genotype structures efficiently describe the hierarchical nature typical of engineering designs. They also prevent MOGA from wasting time exploring inappropriate regions of the search space. The automated MEMS design synthesis is demonstrated with surface-micromachined resonator and accelerometer designs. (Track Category: EVOLUTIONARY MULTIOBJECTIVE OPTIMIZATION)

The typical engineering design process can be decomposed into several phases: creative exploration of ideas, testing soundness of proposed concepts, refining concepts to realizable solutions, optimizing viable solutions with respect to performance/cost. Powerful computer algorithms have been developed for many of these tasks. Often these modules are rigid, allowing for little intervention by the designer, and the management of the interactions of these tasks mostly relies on human intelligence. Better user interfaces are required to integrate more fully human ingenuity and the assistance of the computer into the overall design process. The most powerful CAD systems should combine the power of programming, graphical visualization, and interactive adjustment of crucial design parameters.

For many applications, such as aesthetic designs or camera paths, nicely rounded, smooth, interpolatory paths -- free of cusps and abrupt hairpin turns -- are most important. Such curves can be obtained from globally optimized minimum variation curves (MVC) [Moreton and Séquin 1992], but at high computational costs. We present a blending scheme between circles that robustly produces equally good-looking G2-continuous curves through very challenging sets of interpolation points. One basic method produces such curves in the plane, on a sphere, and in 3D space.

We present a rapid occlusion culling algorithm specifically designed for urban environments. For each frame, an occlusion horizon is being built on-the-fly during a hierarchical front-to-back traversal of the scene. All conservatively hidden objects are culled, while all the occluding impostors of all conservatively visible objects are added to the 2½D occlusion horizon. Our framework also supports levels-of-detail (LOD) rendering by estimating the visible area of the projection of an object in order to select the appropriate LOD for each object. This algorithm requires no substantial preprocessing and no excessive storage. In a test scene of 10,000 buildings, the cull phase took 11 ms on a PentiumII 333 MHz and 45 ms on an SGI Octane per frame on average. In typical views, the occlusion horizon culled away 80-90% of the objects that were within the view frustum, giving a 10 times speedup over view frustum culling alone. Combining the occlusion horizon with LOD rendering gave a 17 times speedup on an SGI Octane, and 23 times on a PII.

M.C. Escher created a myriad of amazing planar tessellations, yet only a few three-dimensional ones such as his wooden fish ball and dodecahedral flower. We have developed an interactive program to design and manufacture "Escher Spheres" - sets of tiles that can be assembled into spherical balls. The user chooses from a set of predefined symmetry groups and then deforms the boundaries of the basic domain tile; all corresponding points based on the chosen symmetry class move concurrently, instantly showing the overall result. The interior of the tile can be embellished with a bas-relief. Finally the tile is radially extruded and output as a solid model suitable for free-form fabrication. Categories and Subject Descriptors J.6 [Computer Appl.]: Computer-Aided Engineering General Terms Computer-aided design (CAD) Keywords M.C. Escher, solid modeling, tessellation, spherical symmetry, spherical tiling, tile editor 1.

This paper describes the integration of the Berkeley Architectural Walkthrough Program with the National Institute of Standards and Technology's CFAST fire simulator.The integrated system creates a simulation based design environment for building fire safety systems; it also allows fire safety engineers to evaluate the performance of building designs, and helps make performance-based fire codes possible.We demonstrate that the visibility preprocessing and spatial decomposition used in the Walkthru also allow optimization of the data transfer between the simulator and visualizer.This optimization improves the ability to use available communication bandwidth to get needed simulation data to the Walkthru in the best order to visualize results in real time; an appropriate communication model and data structures are presented.General issues arising in the integration of environmental simulations and virtual worlds are discussed, as well as the specifics of the Walkthru-CFAST system, including relevant aspects of the user interface and of the visualization and simulation programming interfaces.A recommendation is made to structure future simulators in such a way that they can selectively direct their computational efforts toward specified spacetime regions of interest and thereby support real-time, interactive virtual environment visualization more effectively.

Manipulation in immersive virtual environments is difficult partly because users must do without the haptic contact with real objects they rely on in the real world to orient themselves and their manipulanda. To compensate for this lack, we propose exploiting the one real object every user has in a virtual environment, his body. We present a unified framework for virtual-environment interaction based on proprioception, a person's sense of the position and orientation of his body and limbs. We describe three forms of body-relative interaction: • Direct manipulation—ways to use body sense to help control manipulation • Physical mnemonics—ways to store/recall information relative to the body • Gestural actions—ways to use body-relative actions to issue commands Automatic scaling is a way to bring objects instantly within reach so that users can manipulate them using proprioceptive cues. Several novel virtual interaction techniques based upon automatic scaling and our proposed framework of proprioception allow a user to interact with a virtual world intuitively, efficiently, precisely, and lazily. We report the results of both informal user trials and formal user studies of the usability of the body-relative interaction techniques presented. CR

This paper describes a software framework to aid in designing and implementing convenient manipulation behaviors for objects in a 3D virtual environment. A combination of almost realistic-looking pseudo-physical behavior and idealized goal-oriented properties, called object associations, is used to disambiguate the mapping of the 2D cursor motion on the display screen into an appropriate object motion in the 3D virtual world and to determine a valid and desirable final location for the objects to be placed. Objects selected for relocation actively look for nearby objects to associate and align themselves with; an automated implicit grouping mechanism also falls out from this process. Concept, structure, and our implementation of such an object association framework in the context of the Berkeley Soda Hall WALKTHRU environment are presented.

Adaptive k-means clustering algorithms have been used in several artificial neural network architectures, such as radial basis function networks or feature-map classifiers, for a competitive partitioning of the input domain. This paper presents an enhancement of the traditional k-means algorithm. It approximates an optimal clustering solution with an efficient adaptive learning rate, which renders it usable even in situations where the statistics of the problem task varies slowly with time. This modification Is based on the optimality criterion for the k-means partition stating that: all the regions in an optimal k-means partition have the same variations if the number of regions in the partition is large and the underlying distribution for generating input patterns is smooth. The goal of equalizing these variations is introduced in the competitive function that assigns each new pattern vector to the "appropriate" region. To evaluate the optimal k-means algorithm, the authors first compare it to other k-means variants on several simple tutorial examples, then the authors evaluate it on a practical application: vector quantization of image data.

We describe an adaptive display algorithm for interactive frame rates during visualization of very complex virtual environments.The algorithm relies upon a hierarchical model representation in which objects are described at multiple levels of detail and can be drawn with various rendering algorithms.The idea behind the algorithm is to adjust image quality adaptively to maintain a uniform, user-specified target frame rate.We perform a constrained optimization to choose a level of detail and rendering algorithm for each potentially visible object in order to generate the "best" image possible within the target frame time.Tests show that the algorithm generates more uniform frame rates than other previously described detail elision algorithms with little noticeable difference in image quality during visualization of complex models.

Abstract Four functionals for the computation of minimum cost curves are compared. Minimization of these functionals result in the widely studied Minimum Energy Curve (MEC), the recently introduced Minimum Variation Curve (MVC), and their scale‐invariant counterparts, (SI‐MEC, SI‐MVC). We compare the stability and fairness of these curves using a variety of simple interpolation problems. Previously, we have shown MVC to possess superior fairness. In this paper we show that while MVC have fairness and stability superior to MEC they are still not stable in all configurations. We introduce the SI‐MVC as a stable alternative to the MVC. Like the MVC, circular and helical arcs are optimal shapes for the SI‐MVC. Additionally, the application of scale invariance to functional design allows us to investigate locally optimal curves whose shapes are dictated solely by their topology, free of any external interpolation or arc length constraints.

Two generalizations of the classic corner-stitched data structure for planar polygonal layouts to geometrics including circles or arbitrary curved shapes are introduced and analyzed. Such an extended data structure can be built with just the additional space required to store the more complicated curved boundaries. Alternatively, the definition of the curved shapes may also be based on geometrical area mapping similar to those used in finite-element methods. The tradeoffs between different encoding schemes that minimize either overall data storage needs or the complexity of individual tiles are discussed. The topology of the linkage of tiles by the corner-stitching pointers is equivalent to that of simpler patterns with trapezoidal tiles, but the various tests and operations running on this data structure may become considerably more complicated, and the achievable runtimes will be highly implementation dependent.>

We describe techniques for managing large amounts of data during an interactive walkthrough of an architectural model.These techniques are based on a spatial subdivision, visibility analysis, and a display database containing objects described at multiple levels of detail.In each frame of the walkthrough, we compute a set of objects to render, i.e. those potentially visible from the observer's viewpoint, and a set of objects to swap into memory, i.e. those that might become visible in the near future.We choose an appropriate level of detail at which to store and to render each object, possibly using very simple representations for objects that appear small to the observer, thereby saving space and time.Using these techniques, we cull away large portions of the model that are irrelevant from the observer's viewpoint, and thereby achieve interactive frame rates.

This paper presents a simple-to-use mechanism for the creation of complex smoothly shaped surfaces of any genus or topological type.The surfaces are specified through interpolated geometric constraints consisting of positions and, optionally, surface normals and surface curvatures.From a designer's point of view, this is a very natural way to specify a desired shape, whether free-form or technical.Nonlinear optimization techniques are then used to minimize a fairness functional based on the variation of curvature.This functional produces very high quality surfaces with predictable, intuitive behavior, while generating, where possible, simple shapes, such as cylinders, spheres, or tori, which are commonly used in geometric modeling.While easy to use, this optimization-based approach is computationally quite demanding.With more efficient optimization algorithms and with the ever increasing processing power available on every desk-top, the techniques described here will provide the basis for a new class of practical interactive geometric modeling tools.

The number of polygons comprising interesting architectural models is many more than can be rendered at interactive frame rates. However, due to occlusion by opaque surfaces (e.g., walls), only a small fraction of a typical model is visible from most viewpoints.We describe a method of visibility preprocessing that is efficient and effective for axis-aligned or axial architectural models. A model is subdivided into rectangular cells whose boundaries coincide with major opaque surfaces. Non-opaque portals are identified on cell boundaries, and used to form an adjacency graph connecting the cells of the subdivision. Next, the cell-to-cell visibility is computed for each cell of the subdivision, by linking pairs of cells between which unobstructed sightlines exist.During an interactive walkthrough phase, an observer with a known position and view cone moves through the model. At each frame, the cell containing the observer is identified, and the contents of potentially visible cells are retrieved from storage. The set of potentially visible cells is further reduced by culling it against the observer's view cone, producing the eye-to-cell visibility. The contents of the remaining visible cells are then sent to a graphics pipeline for hidden-surface removal and rendering.Tests on moderately complex 2-D and 3-D axial models reveal substantially reduced rendering loads.

A silicon compilation system for CMOS operational amplifiers (OPASYN) is discussed. The synthesis system takes as inputs system-level specifications, fabrication-dependent technology parameters, and geometric layout rules. It produces a design-rule-correct compact layout of an optimized operational amplifier. The synthesis proceeds in three stages: (1) heuristic selection of a suitable circuit topology; (2) parametric circuit optimization based on analytic models; and (3) mask geometry construction using a macro cell layout style. The synthesis process is fast enough for the program to be used interactively at the system design level by system designers who are inexperienced in operational amplifier design.>

Zone-refining refers to a technique that forms a basis for layout compaction algorithms intermediate between one-dimensional (1-D) compactors and two-dimensional (2-D) placement techniques. An expanded zone in which 2-D refinement techniques are employed is repeatedly swept across the layout in different directions. The basic principle is reviewed and the computational complexity of zone refining is analyzed. The difficulties that had to be overcome in making the basic concept useful for compaction of integrated circuit layouts is discussed. One implementation is described, and some of the tradeoffs made and data structures used to obtain an efficient compactor are examined. The scope of possibilities for other implementations are discussed.>

SoGOLaR (Sea-of-Gates Optimized Layout and Routing) is a program that generates functional cells for static CMOS circuits in the Sea-of-Gates layout style. Our generator is flexible and general enough to produce efficient layout for a wide variety of Sea-of-Gates template geometries. SoGOLaR has been used to make quantitative comparisons of several different templates with respect to area utilization and cell routability. We present the results of our comparative study and draw some conclusions for the selection of a basic Sea-of-Gates template geometry.

The construction and refinement of a computer graphics scene is unacceptably slow when using ray tracing. We introduce a new technique to speed up the generation of successive ray traced images when the geometry of the scene remains constant and only the light source intensities and the surface properties need to be adjusted. When the scene is first ray traced, an expression parameterized in the color of all lights and the surface property coefficients of all objects is calculated and stored for each pixel. Redisplaying a scene with a new set of lights and colors then consists of substituting values for the corresponding parameters and re-evaluating the expressions for the pixels. This parameter updating and redisplay takes only a few seconds, as compared to the many minutes or hours required to ray trace the entire scene again, but it uses much more memory and disk space. With suitable expression sharing, however, these storage needs can be reduced to an acceptable level.

An analog silicon compiler for CMOS op amps (OPASYN) has been developed. The synthesis system takes as inputs system-level specifications, fabrication-dependent technology parameters, and geometric layout rules. Based on the general domain of the specifications, the program first selects an appropriate circuit topology from a database and determines optimal values for the set of design parameters so as to meet the design objectives. Subsequently, a mask-level layout for the given circuit with its optimized device sizes is constructed using an approach based on a few leaf-cell generators and on circuit-dependent slicing trees that guarantee sound arrangements of the individual components. The synthesis process is fast enough for the program to be used interactively at the system-design level by system engineers who are inexperienced in op amp design.>

A general area router that integrates the phases of global routing and detailed routing has been developed. The global phase coarsely places the nets based on the congestion of the routing region, and the detailed phase modifies the course wiring to find legal positions for all wire segments. Both phases use the same grid space of routing tracks with two or more levels of interconnect. With this integrated data structure, the router can alternate between global and detailed routing operations, both of which use rip-up and reroute techniques. This integration has resulted in a router that can solve difficult problems not solvable by other programs while exhibiting runtimes that grow only moderately with the size of the routing problem.>

A new technique for 2-dimensional layout compaction of integrated circuits is presented. After a traditional one-dimentional precompaction step, the size of the layout is further reduced with a technique that bears a strong similarity to the technique of 'zone-refining' used in the purification of crystal ingots. Individual circuit components or small clusters of components are peeled off row by row from the precompacted layout, moved across an open zone, and reassembled at the other end of this zone in a denser configuration. In this process both coordinates of the moved components are altered and jogs are introduced in the connecting wires between them to produce the needed flexibility for placing components into optimal positions. The constraint graphs in both the x- and y-direction are used and updated concurrently.

We have developed the concept of an abstract timing verifier that accepts plug-compatible timing models in a common framework containing the scheduling algorithms and the user interface. Depending on the design phase and the particular level of design representation used, the most suitable timing model can be plugged into this framework and operated in a standard way.

Algorithms for computer graphics or solids modeling must often infer the structure of geometrical objects from numerical data. Unavoidable errors (due to limited precision) affect the calculations from which these data are produced and may thus affect topological information so derived. Ambiguities or even contradictions may result from inferences made from an object's representation.To resolve these ambiguities for arbitrary polyhedral objects, we introduce a minimum feature size and a face thickness and show how to convert any object description into a form which insures topological immunity to numerical perturbations. The minimum feature size depends on the object's overall dimensions and on its placement in space. The face thickness depends on how well a face's vertices conform to its computed plane.

A high probability of detecting errors caused by hardware faults is an essential property of any fault-tolerant system. VLSI technology makes the use of duplication and matching for error detection practical and attractive. A critical circuit in this context is a self-testing comparator. Faults in the comparator must be detected so that they do not mask discrepancies between the duplicated modules.

The RISC (reduced instruction set computer) architecture attempts to achieve high performance without resorting to complex instructions and irregular pipelining schemes. One of the novel features of this architecture is a large register file which is used to minimize the overhead involved in procedure calls and returns. This paper investigates several strategies for managing this register file. The costs of practical strategies are compared with a lower bound on this management overhead, obtained from a theoretical optimal strategy, for several register file sizes.

A new interconnection topology for incrementally expansible multicomputer systems is described, which combines the easy expansibility of tree structures with the compactness of the n-dimensional hypercube. The addition of n-cube links to the binary tree structure provides direct paths between nodes which have frequent data exchange in algorithms such as sorting and fast Fourier transforms (FFT's). The derivation of a family of such Hypertree structures is outlined, and the basic properties such as average path length, uniformity of the distribution of message traffic, and routing algorithms are analyzed.

In the mid 1980's it will be possible to put a million devices (transistors or active MOS gate electrodes) onto a single silicon chip. General trends in the evolution of silicon integrated circuits are reviewed and design constraints for emerging VLSI circuits are analyzed. Desirable architectural features in modern computers are then discussed and consequences for an implementation with large-scale integrated circuits are investigated. The resulting recommended processor design includes features such as an on-chip memory hierarchy, multiple homogeneous caches for enhanced execution parallelism, support for complex data structures and high-level languages, a flexible instruction set, and communication hardware. It is concluded that a viable modular building block for the next generation of computing systems will be a self-contained computer on a single chip. A tentative allocation of the one milion transistors to the various functional blocks is given, and the result is a memory intensive design.

X-NODE is a single-chip VLSI processor to be realized in the mid 1980's and to be used as a building block for a tree-structured multiprocessor system (X-TREE). Three major trends influence the design of this processor: the continuing evolution of VLSI technology, the requirements for parallelism and communication in a multiprocessor system, and the need for better support of software and high level language constructs. The influence of these trends on the processor architecture are discussed and the current state of the design of X-NODE is outlined. X-NODE will introduce several new features exploiting the full potential of VLSI technology. The processor and hierarchical memory of multiple device types will be combined on a single chip to provide a powerful processor. With basically a memory-to-memory architecture, an on-chip caching scheme provides the performance of a register based architecture. This on-chip memory hierarchy contains program and data, as well as microcode. The instruction set of any processor can thus be dynamically changed and tailored to the specific problem being executed. It is planned to support high level language constructs directly in hardware through mechanisms such as bounds checking.