Repairing CAD models
We describe an algorithm for repairing polyhedral CAD models that have errors in their B-REP. Errors like cracks, degeneracies, duplication, holes and overlaps are usually introduced in solid models due to imprecise arithmetic, model transformations, designer errors, programming bugs, etc. Such errors often hamper further processing such as finite element analysis, radiosity computation and rapid prototyping. Our fault-repair algorithm converts an unordered collection of polygons to a shared-vertex representation to help eliminate errors. This is done by choosing, for each polygon edge, the most appropriate edge to unify it with. The two edges are then geometrically merged into one, by moving vertices. At the end of this process, each polygon edge is either coincident with another or is a boundary edge for a polygonal hole or a dangling wall and may be appropriately repaired. Finally, in order to allow user-inspection of the automatic corrections, we produce a visualization of the repair and let the user mark the corrections that conflict with the original design intent. A second iteration of the correction algorithm then produces a repair that is commensurate with the intent. This, by involving the users in a feedback loop, we are able to refine the correction to their satisfaction.

title: Hierarchical Back-Face Computation
abstract: We present a sub-linear algorithm to compute the set of back-facing polygons in a polyhedral model. The algorithm partitions the model into hierarchical clusters based on the orientations and positions of the polygons. As a pre-processing step, the algorithm constructs spatial decompositions with respect to each cluster. For a sequence of back-face computations, the algorithm exploits the coherence in view-point movement to efficiently determine if it is in front of or behind a cluster. Due to coherence, the algorithm’s performance is linear in the number of clusters on average. We have applied this algorithm to speed up the rendering of polyhedral models. On average, we are able to cull almost half the polygons. The algorithm accounts for 5 – 10% of the total CPU time per frame on an SGI Indigo2 Extreme. The overall frame rate is improved by 40 – 75% as compared to the standard back-face culling implemented in hardware.

title: Hierarchical back-face computation
abstract: We present a sub-linear algorithm to compute the set of back-facing polygons in a polyhedral model. The algorithm partitions the model into hierarchical clusters based on the orientations and positions of the polygons. As a pre-processing step, the algorithm constructs spatial decompositions with respect to each cluster. For a sequence of back-face computations, the algorithm exploits the coherence in view-point movement to efficiently determine whether it is in front of or behind a cluster. Due to coherence, the algorithm's expected running time is linear in the number of clusters on average. We have applied this algorithm to speed up the rendering of polyhedral models. On average, we are able to cull about 40% of the polygons. The algorithm accounts for 5% of the total CPU time per frame on an SGI Onyx. The overall frame rate is improved by 40–75% as compared to the standard back-face culling implemented in hardware. We also present an extension of our back-face computation algorithm to determine silhouettes of polygonal models. Our technique finds true perspective silhouettes by collecting edges at the common boundaries of back-facing and front-facing clusters.

title: On k-coverage in a mostly sleeping sensor network
abstract: Sensor networks are often desired to last many times longer than the active lifetime of individual sensors. This is usually achieved by putting sensors to sleep for most of their lifetime. On the other hand, surveillance kind of applications require guaranteed k-coverage of the protected region at all times. As a result, determining the appropriate number of sensors to deploy that achieves both goals simultaneously becomes a challenging problem. In this paper, we consider three kinds of deployments for a sensor network on a unit square - a √n x √n grid, random uniform (for all n points), and Poisson (with density n). In all three deployments, each sensor is active with probability p, independently from the others. Then, we claim that the critical value of the function npπr2/log(np) is 1 for the event of k-coverage of every point. We also provide an upper bound on the window of this phase transition. Although the conditions for the three deployments are similar, we obtain sharper bounds for the random deployments than the grid deployment, which occurs due to the boundary condition. In this paper, we also provide corrections to previously published results for the grid deployment model. Finally, we use simulation to show the usefulness of our analysis in real deployment scenarios.

title: Design of randomized multichannel packet storage for high performance routers
abstract: High performance routers require substantial amounts of memory to store packets awaiting transmission, requiring the use of dedicated memory devices with the density and capacity to provide the required storage economically. The memory bandwidth required for packet storage subsystems often exceeds the bandwidth of individual memory devices, making it necessary to implement packet storage using multiple memory channels. This raises the question of how to design multichannel storage systems that make effective use of the available memory and memory bandwidth, while forwarding packets at link rate in the presence of arbitrary packet retrieval patterns. A recent series of papers has demonstrated an architecture that uses on-chip SRAM to buffer packets going to/from a multichannel storage system, while maintaining high performance in the presence worst-case traffic patterns. Unfortunately, the amount of on-chip storage required grows as the product of the number of channels and the number of separate queues served by the packet storage system. This makes it too expensive to use in systems with large numbers of queues. We show how to design a practical randomized packet storage system that can sustain high performance using an amount of on-chip storage that is independent of the number of queues.

title: Physical simulation for animation and visual effects: parallelization and characterization for chip multiprocessors
abstract: We explore the emerging application area of physics-based simulation for computer animation and visual special effects. In particular, we examine its parallelization potential and characterize its behavior on a chip multiprocessor (CMP). Applications in this domain model and simulate natural phenomena, and often direct visual components of motion pictures. We study a set of three workloads that exemplify the span and complexity of physical simulation applications used in a production environment: fluid dynamics, facial animation, and cloth simulation. They are computationally demanding, requiring from a few seconds to several minutes to simulate a single frame; therefore, they can benefit greatly from the acceleration possible with large scale CMPs.
 Starting with serial versions of these applications, we parallelize code accounting for at least 96% of the serial execution time, targeting a large number of threads.We then study the most expensive modules using a simulated 64-core CMP.
 For the code representing key modules, we achieve parallel scaling of 45x, 50x, and 30x for fluid, face, and cloth simulations, respectively. The modules have a spectrum of parallel task granularity and locking behavior, and all but one are dominated by loop-level parallelism. Many modules operate on streams of data. In some cases, modules iterate over their data, leading to significant temporal locality. This streaming behavior leads to very high on-die and main memory bandwidth requirements. Finally, most modules have little inter-thread communication since they are data-parallel, but a few require heavy communication between data-parallel operations.

title: Asynchronous Genetic Algorithms for Heterogeneous Networks Using Coarse-Grained Dataflow
abstract: Genetic algorithms (GAs) are an attractive class of techniques for solving a variety of complex search and optimization problems. Their implementation on a distributed platform can provide the necessary computing power to address large-scale problems of practical importance. On heterogeneous networks, however, the performance of a global parallel GA can be limited by synchronization points during the computation, particularly those between generations. We present a new approach for implementing asynchronous GAs based on the dataflow model of computation -- an approach that retains the functional properties of a global parallel GA. Experiments conducted with an air quality optimization problem and others show that the performance of GAs can be substantially improved through dataflow-based asynchrony.

title: Error-resilient coding of 3-D graphic models via adaptive mesh segmentation
abstract: Current coding techniques for 3-D graphic models mainly focus on coding efficiency, which makes them extremely sensitive to channel errors due to the irregular mesh structure. We introduce a new approach for error-resilient coding of arbitrary 3-D graphic models by extending the error-free constructive traversal compression scheme proposed by Li and Kuo (see MPEG-4 Tokyo Meeting, 1998, , and Proc.  vol.86, p.1052-63, 1998). A 3-D mesh of an arbitrary structure is partitioned into pieces of a smaller uniform size with joint boundaries. The size of a piece is determined adaptively based on the channel error rate. The topology and geometry information of each joint boundary and each piece of a connected component is coded independently. The coded topology and first several important bit-planes of the joint-boundary data are protected against channel errors by using the Bose-Chaudhuri-Hocquenghem error-correcting code. At the decoder, each piece is decoded and checked for channel errors. The decoded joint-boundary information is used to perform data recovery and error concealment on the corrupted piece data. All decoded pieces are combined together according to their configuration to reconstruct all connected components of the complete 3-D model. Our experiments demonstrate that the proposed approach has excellent error resiliency at a reasonable bit-rate overhead. The techniques is also capable of incrementally rendering one connected component of the 3-D model at a time.