bluuebunny/crossref_metadata_2025 huggingface dataset:
Java client ahead-of-time compiler for embedded systems
Authors: Hong SungHyun , Kim Jin-Chul , Shin Jin Woo , Moon Soo-Mook , Oh Hyeong-Seok , Lee Jaemok , Choi Hyung-Kyu
Published: September 2007

The performance of embedded Java virtual machine can be improved by ahead-of-time compiler (AOTC), which translates bytecode into machine code in the server and installs the machine code on the client device. Although AOTC is more advantageous than just-in-time compiler (JITC) due to its absence of the translation overhead, AOTC cannot be applicable to dynamically downloaded classes at runtime. This paper proposes client-AOTC (c-AOTC) which performs AOTC on the client device using the JITC module installed on the device, complementing the server-AOTC. The machine code of a method translated by JITC is cached on a persistent memory of the device, and when the method is invoked again in a later run of the program, the machine code is loaded and executed directly without the translation and interpretation overhead. One of major issues in c-AOTC is relocation because some of the addresses used by the cached machine code are not correct when the machine code is loaded and used in a different run; those addresses should be corrected before they are used. Constant pool resolution and inlining complicate the relocation problem and we propose our solutions. We developed a c-AOTC on Sun's CDC VM reference implementation (RI) and our evaluation results indicate that c-AOTC can improve the performance significantly, as much as an average of 12%. We also experiment with the issue of reducing the number of c-AOTC methods to be cached when the persistent space is tight, with a graceful degradation of performance.
Optimistic coalescing for heterogeneous register architectures
Authors: Ahn Minwook , Lee Jooyeon , Paek Yunheung
Published: September 2007

In this paper, Optimistic coalescing has been proven as an elegant and effective technique that provides better chances of safely coloring more registers in register allocation than other coalescing techniques. Its algorithm originally assumes
homogeneous
registers which are all gathered in the same register file. Although this register architecture is still common in most general-purpose processors, embedded processors often contain
heterogeneous
registers which are scattered in physically different register files dedicated for each dissimilar purpose and use. In this work, we developed a modified algorithm for optimal coalescing that helps a register allocator for an embedded processor to better handle such heterogeneity of the register architecture. In the experiment, an existing register allocator was able to achieve up to 10% reduction in code size through our coalescing, and avoid many spills that would have been generated without our scheme.
Tetris
Authors: Xu Weifeng , Tessier Russell
Published: September 2007

The run-time performance of VLIW (very long instruction word) microprocessors depends heavily on the effectiveness of its associated optimizing compiler. Typical VLIW compiler phases include instruction scheduling, which maximizes instruction level parallelism (ILP), and register allocation, which minimizes data spills to external memory. If ILP is maximized without considering register constraints, high register pressure may result, leading to increased spill code and reduced run-time performance. In this paper, a new register pressure reduction technique for embedded VLIW processors is presented to control register pressure prior to instruction scheduling and register allocation. By modifying the relative ordering of operations, this technique restructures code to better reduce spills. Our technique has been implemented in Trimaran, an academic VLIW compiler, and evaluated using a series of VLIW benchmarks. Experimental results show that, on average, our algorithm reduces dynamic spills and improves overall cycle counts by 6% for a VLIW architecture with 8 functional units and 32 registers versus previous spill code reduction techniques.
Enabling seamless mobility
Authors: Engelsma Jonathan
Published: September 2007

Seamless mobility entails providing consumers an enhanced experience -- with reduced effort -- as they move between different devices and environments. Because of the increasing diversity of user preferences, device capabilities and environmental conditions, engineering
efficient
and
usable
seamless mobility solutions can be quite challenge. This talk will present an applications research perspective on realizing seamless mobility, focusing on ongoing research in developing enablers for mobile gaming, device-to-device interactions, sensing, advertising and cross-device context sharing. Understanding the device limitations as well as the user expectations of the technology is critical to developing seamless mobility solutions that are both useful and commercially viable. From the tools and development perspective, we see opportunities and challenges in the four phases of realization --
design & development, deployment, usage
and
evolution
. This talk will conclude with a look at existing support for tools and enablers for seamless mobility, and a discussion on future research directions for the developer community.
Joint throughput and energy optimization for pipelined execution of embedded streaming applications
Authors: Huang Po-Kuan , Hashemi Matin , Ghiasi Soheil
Published: September 2007

We present a methodology for synthesizing streaming applications, modeled as task graphs, for pipelined execution on multi-core architectures. We develop a task graph extraction and characterization framework that accurately determines the structure, computation and communication characteristics of application task graph from its specification in C. Furthermore, we develop a provably optimal algorithm that jointly balances the workload assigned to each core, and minimizes inter-core communication traffic. Experiment results show that our versatile method improves the through-put of streaming applications significantly under a variety of hardware configurations.
Interface synthesis for heterogeneous multi-core systems from transaction level models
Authors: Cho Hansu , Abdi Samar , Gajski Daniel
Published: September 2007

This paper presents a tool for automatic synthesis of RTL interfaces for heterogeneous MPSoC from transaction level models (TLMs). The tool captures the communication parameters in the platform and generates interface modules called universal bridges between buses in the design. The design and configuration of the bridges depend on several platform components including heterogeneity of the components, traffic on the bus, size of messages and so on. We define these parameters and show how the synthesizable RTL code for the bridge can be automatically derived based on these parameters. We use industrial strength design drivers such as an MP3 decoder to test our automatically generated bridges for a variety of platforms and compare them to manually designed bridges on different quality metrics. Our experimental results show that performance of automatically generated bridges are within 5% of manual design for simple platforms but surpasses them for more complex platforms. The area and RTL code size is consistently better than manual design while giving 5 orders of improvement in development time.
External memory page remapping for embedded multimedia systems
Authors: Ning Ke , Kaeli David
Published: September 2007

As memory speeds and bus capacitances continue to rise, external memory bus power will make up an increasing portion of the total system power budget for system-on-a-chip embedded systems. Both hardware and software approaches can be explored to balance the power/performance tradeoff associated with the external memory.

In this paper we present a hardware-based, programmable external memory page remapping mechanism which can significantly improve performance and decrease the power budget due to external memory bus accesses. Our approach was developed by studying common data access patterns present in embedded multimedia applications. In the paper, we evaluate a mechanism that can perform page remapping of external memory. We also develop an efficient algorithm to map application data and instruction memory into external memory pages. We employ graph-coloring techniques to guide the page mapping procedure. The objective is to avoid page misses by remapping conflicting pages to different memory banks (i.e., by assigning them different colors). Our algorithm can significantly reduce the memory page miss rate by 70-80% on average. For a 4-bank SDRAM memory system, we reduced external memory access time by 12.6%. The proposed algorithm can reduce power consumption in majority of the benchmarks, averaged by 13.2% of power reduction. Combining the effects of both power and delay, our algorithm can benefit significantly to the total energy cost.
Scratchpad allocation for data aggregates in superperfect graphs
Authors: Li Lian , Nguyen Quan Hoang , Xue Jingling
Published: September 2007

Existing methods place data or code in scratchpad memory, i.e., SPM by either relying on heuristics or resorting to integer programming or mapping it to a graph coloring problem.

In this work, the SPM allocation problem is formulated as an interval coloring problem. The key observation is that in many embedded applications, arrays (including structs as a special case) are often related in the following way: For any two arrays, their live ranges are often such that one is either disjoint from or contains the other. As a result, array interference graphs are often superperfect graphs and optimal interval colorings for such array interference graphs are possible. This has led to the development of two new SPM allocation algorithms. While differing in whether live range splits and spills are done sequentially or together, both algorithms place arrays in SPM based on examining the cliques in an interference graph. In both cases, we guarantee optimally that all arrays in an interference graph can be placed in SPM if its size is no smaller than the clique number of the graph. In the case that the SPM is not large enough, we rely on heuristics to split or spill a live range until the graph is colorable. Our experiment results using embedded benchmarks show that our algorithms can outperform graph coloring when their interference graphs are superperfect or nearly so although graph coloring is admittedly more general and may also be effective to applications with arbitrary interference graphs.
Can ISPS and P2P users cooperate for improved performance?
Authors: Aggarwal Vinay , Feldmann Anja , Scheideler Christian
Published: September 2007

Peer-to-peer (P2P) systems, which are realized as overlays on top of the underlying Internet routing architecture, contribute a significant portion of today's Internet traffic. While the P2P users are a good source of revenue for the Internet Service Providers (ISPs), the immense P2P traffic also poses a significant traffic engineering challenge to the ISPs. This is because P2P systems either implement their own routing in the overlay topology or may use a P2P routing underlay [1], both of which are largely independent of the Internet routing, and thus impedes the ISP's traffic engineering capabilities. On the other hand, P2P users are primarily interested in finding their desired content quickly, with good performance. But as the P2P system has no access to the underlying network, it either has to measure the path performance itself or build its overlay topology agnostic of the underlay. This situation is disadvantageous for both the ISPs and the P2P users.

To overcome this, we propose and evaluate the feasibility of a solution where the ISP offers an "oracle" to the P2P users. When the P2P user supplies the oracle with a list of possible P2P neighbors, the oracle ranks them according to certain criteria, like their proximity to the user or higher bandwidth links. This can be used by the P2P user to choose appropriate neighbors, and therefore improve its performance. The ISP can use this mechanism to better manage the immense P2P traffic, e.g., to keep it inside its network, or to direct it along a desired path. The improved network utilization will also enable the ISP to provide better service to its customers.
How to read a paper
Authors: Keshav S.
Published: September 2007

Researchers spend a great deal of time reading research papers. However, this skill is rarely taught, leading to much wasted effort. This article outlines a practical and efficient
three-pass method
for reading research papers. I also describe how to use this method to do a literature survey.
HCI is in business---focusing on organizational tasks and management
Authors: Te'eni Dov
Published: September 2007

Although not many managers have been hands-on computer users until recently, they were critical users of computer output from the beginning of business computing, in the 1960s. Information Systems research, for example, has included an HCI thread for 40 years. Unfortunately, our fields have not interacted effectively, as noted in my January-February 2006 column. In this, the second guest-authored Timelines column, Dov Te'eni reviews four decades of HCI research in IS, describes its state today, and suggests where it is headed. ---Jonathan Grudin, Timelines editor
A type discipline for authorization policies
Authors: Fournet Cédric , Gordon Andrew D. , Maffeis Sergio
Published: September 2007

Distributed systems and applications are often expected to enforce high-level authorization policies. To this end, the code for these systems relies on lower-level security mechanisms such as digital signatures, local ACLs, and encrypted communications. In principle, authorization specifications can be separated from code and carefully audited. Logic programs in particular can express policies in a simple, abstract manner.

We consider the problem of checking whether a distributed implementation based on communication channels and cryptography complies with a logical authorization policy. We formalize authorization policies and their connection to code by embedding logical predicates and claims within a process calculus. We formulate policy compliance operationally by composing a process model of the distributed system with an arbitrary opponent process. Moreover, we propose a dependent type system for verifying policy compliance of implementation code. Using Datalog as an authorization logic, we show how to type several examples using policies and present a general schema for compiling policies.
The trace partitioning abstract domain
Authors: Rival Xavier , Mauborgne Laurent
Published: September 2007

In order to achieve better precision of abstract interpretation-based static analysis, we introduce a new generic abstract domain, the trace partitioning abstract domain. We develop a theoretical framework allowing a wide range of instantiations of the domain, proving that all these instantiations give correct results. From this theoretical framework, we go into implementation details of a particular instance developed in the Astrée static analyzer. We show how the domain is automatically configured in Astrée and the gain and cost in terms of performance and precision.
Enforcing resource bounds via static verification of dynamic checks
Authors: Chander Ajay , Espinosa David , Islam Nayeem , Lee Peter , Necula George C.
Published: September 2007

We show how to limit a program's resource usage in an efficient way, using a novel combination of dynamic checks and static analysis. Usually, dynamic checking is inefficient due to the overhead of checks, while static analysis is difficult and rejects many safe programs. We propose a hybrid approach that solves these problems. We split each resource-consuming operation into two parts. The first is a dynamic check, called reserve. The second is the actual operation, called consume, which does not perform any dynamic checks. The programmer is then free to hoist and combine reserve operations. Combining reserve operations reduces their overhead, while hoisting reserve operations ensures that the program does not run out of resources at an inconvenient time. A static verifier ensures that the program reserves resources before it consumes them. This verification is both easier and more flexible than an a priori static verification of resource usage. We present a sound and efficient static verifier based on Hoare logic and linear inequalities. As an example, we present a version of tar written in Java.
The Internet's role in offshored services
Authors: Dossani Rafiq , Denny Nathan
Published: September 2007

Using India as a case study, this article analyzes how the Internet influenced its export-oriented software industry. We show that prior to the Internet, domestic entrepreneurship was the key factor for the industry's origin and growth. The industry suffered from relatively low value-addition. As a result, domestic firms, though they were industry leaders within India, were followers of the global leadership provided by transnational firms. With the arrival of the Internet, there was a rise in the level of domain expertise. We show that the Internet facilitated the transfer of domain expertise for foreign firms more than it helped the acquisition of domain expertise by domestic firms. While the value-addition of the industry increased as a result, industry leadership began to pass to foreign firms. The strategic lesson for other countries trying to rapidly develop an export-oriented software industry is unambiguous: exclusive reliance on domestic entrepreneurship will usually result in the domestic industry falling behind its global competitors, while granting unrestricted entry to transnational firms will lead to the domestic firms losing industry leadership in most cases.
SADIe
Authors: Harper Simon , Bechhofer Sean
Published: September 2007

Visually impaired users are hindered in their efforts to access the largest repository of electronic information in the world, namely, the World Wide Web (web). A visually impaired user's information and presentation requirements are different from a sighted user's. These requirements can become problems in that the web is visually centric with regard to presentation and information order/layout. Finding semantic information already encoded directly into documents can help to alleviate these problems. Our approach can be loosely described as follows. For a particular cascading stylesheet (CSS), we provide an extension to an upper-level ontology which represents the interface between web documents and the programmatic transformation mechanism. This extension gives the particular characteristics of the elements appearing in that specific CSS. We can consider this extension to be an annotation of the CSS elements implicitly encoded into the web document. This means that one ontology can be used to accuratly transform every web document that references the CSS used to generate that ontology. Simply one ontology accuratly transforms an entire site using a generalized programmatic machinery able to cope with all sites using CSS. Here we describe our method, implementation, and technical evaluation.
Experience distributing objects in an SMMP OS
Authors: Appavoo Jonathan , Silva Dilma Da , Krieger Orran , Auslander Marc , Ostrowski Michal , Rosenburg Bryan , Waterland Amos , Wisniewski Robert W. , Xenidis Jimi , Stumm Michael , Soares Livio
Published: September 2007

Designing and implementing system software so that it scales well on shared-memory multiprocessors (SMMPs) has proven to be surprisingly challenging. To improve scalability, most designers to date have focused on concurrency by iteratively eliminating the need for locks and reducing lock contention. However, our experience indicates that locality is just as, if not more, important and that focusing on locality ultimately leads to a more scalable system.

In this paper, we describe a methodology and a framework for constructing system software structured for locality, exploiting techniques similar to those used in distributed systems. Specifically, we found two techniques to be effective in improving scalability of SMMP operating systems: (i) an object-oriented structure that minimizes sharing by providing a natural mapping from independent requests to independent code paths and data structures, and (ii) the selective partitioning, distribution, and replication of object implementations in order to improve locality. We describe concrete examples of distributed objects and our experience implementing them. We demonstrate that the distributed implementations improve the scalability of operating-system-intensive parallel workloads.
VLIW instruction scheduling for minimal power variation
Authors: Xiao Shu , Lai Edmund M.-K.
Published: September 2007

The focus of this paper is on the minimization of the variation in power consumed by a VLIW processor during the execution of a target program through instruction scheduling. The problem is formulated as a mixed-integer program (MIP) and a problem-specific branch-and-bound algorithm has been developed to solve it more efficiently than generic MIP solvers. Simulation results based on the TMS320C6711 VLIW digital signal processor using benchmarks from Mediabench and Trimaran showed that over 40% average reduction in power variation can be achieved without sacrificing execution speed of these benchmarks. Computational requirements and convergence rates of our algorithm are also analyzed.
An efficient B-tree layer implementation for flash-memory storage systems
Authors: Wu Chin-Hsien , Kuo Tei-Wei , Chang Li Ping
Published: September 2007

With the significant growth of the markets for consumer electronics and various embedded systems, flash memory is now an economic solution for storage systems design. Because index structures require intensively fine-grained updates/modifications, block-oriented access over flash memory could introduce a significant number of redundant writes. This might not only severely degrade the overall performance, but also damage the reliability of flash memory. In this paper, we propose a very different approach, which can efficiently handle fine-grained updates/modifications caused by B-tree index access over flash memory. The implementation is done directly over the flash translation layer (FTL); hence, no modifications to existing application systems are needed. We demonstrate that when index structures are adopted over flash memory, the proposed methodology can significantly improve the system performance and, at the same time, reduce both the overhead of flash-memory management and the energy dissipation. The average response time of record insertions and deletions was also significantly reduced.
Improving security for periodic tasks in embedded systems through scheduling
Authors: Xie Tao , Qin Xiao
Published: September 2007

While many scheduling algorithms for periodic tasks ignore security requirements posed by sensitive applications and are, consequently, unable to perform properly in embedded systems with security constraints, in this paper, we present an approach to scheduling periodic tasks in embedded systems subject to security and timing constraints. We design a necessary and sufficient feasibility check for a set of periodic tasks with security requirements. With the feasibility test in place, we propose a scheduling algorithm, or SASES (security-aware scheduling for embedded systems), which accounts for both security and timing requirements. SASES judiciously distributes slack times among a variety of security services for a set of periodic tasks, thereby optimizing security for embedded systems without sacrificing schedulability. To demonstrate the effectiveness of SASES, we apply the proposed SASES to real-world embedded systems such as an automated flight control system. We show, through extensive simulations, that SASES is able to maximize security for embedded systems while guaranteeing timeliness. In particular, SASES significantly improves security over three baseline algorithms by up to 107%.
XQuery layers
Authors: Braga Daniele , Campi Alessandro , Ceri Stefano , Spoletini Paola
Published: September 2007

XML is becoming widespread as data interoperability standard in many application domains. An increasing number of researchers and professionals, who are not computer scientists (although they may have a strong technical background), needs to query and transform XML data during their working activities. Such tasks typically require simple queries and partial awareness of the XML data model, in the context of a given, domain-specific XML-based protocol.

The W3C community has proposed XQuery as the standard query language for XML [9]. XQuery has a huge expressive power - as it encompasses features belonging both to query and functional languages, but it may be considered as too complex for the above user profiles; well-designed subsets of XQuery are sufficient to satisfy their needs.

In this paper, we propose six layered subsets of XQuery, targeted to cover user communities with increasing needs. The initial layers are based upon XQBE (XQuery By Example), a visual XML query language, strictly less expressive than XQuery. We argue that the first layers are easier to learn and to master than the full language, also thanks to the availability of simple visual interfaces, and that these layers cover most of the needs of many user communities.
Static analysis of XML processing with data values
Authors: Segoufin Luc
Published: September 2007

Most theoretical work on static analysis for XML and its query languages models XML documents by labeled ordered unranked trees, where the labels are from a finite set. Attribute values are usually ignored. This was quite successful for many applications like, to mention only some of them, the study of the navigational fragment of XPath known asCore-XPath[20], a complete picture of the complexity of satisfiability and inclusion of XPath queries without joins [4], XML-schema design with no integrity constraints [28, 31], type-checking [40]. The reader is invited to have a look at the Database Theory columns [32, 37, 40, 39] for an introduction on this rich production.
Stefano Ceri speaks out on many-book researchers and one-startup researchers, web modeling, the vanishing US-Europe research gap, the semantic web services train, and more
Authors: Winslett Marianne
Published: September 2007

Welcome to this installment of ACM SIGMOD Record's series of interviews with distinguished members of the database community. I'm Marianne Winslett, and today we are at the L3S Research Institute in Hannover, Germany, where I am spending the fall of 2006. I have here with me Stefano Ceri, who is a Professor of Information Engineering at the Politecnico di Milano. Stefano's research interests include distributed, deductive, active, and object-oriented databases, and XML query languages; his recent work is on the design of Web applications. He is a co-inventor of WebML (Web Modeling Language), and has a startup company that is commercializing WebRatio, a product based on WebML. Stefano was a founder of EDBT and is still a member of the EDBT Endowment, and he has been a member of the VLDB Endowment for twelve years. He was an editor of
ACM Transactions on Database Systems
and
IEEE Transactions on Software Engineering
. He is a coauthor of 9 books, and his PhD is from the Politecnico di Milano. So, Stefano, welcome!
Image deblurring with blurred/noisy image pairs
Authors: Yuan Lu , Sun Jian , Quan Long , Shum Heung-Yeung
Published: September 2007

Taking satisfactory photos under dim lighting conditions using a hand-held camera is challenging. If the camera is set to a long exposure time, the image is blurred due to camera shake. On the other hand, the image is dark and noisy if it is taken with a short exposure time but with a high camera gain. By combining information extracted from both blurred and noisy images, however, we show in this paper how to produce a high quality image that cannot be obtained by simply denoising the noisy image, or deblurring the blurred image alone.

Our approach is image deblurring with the help of the noisy image. First, both images are used to estimate an accurate blur kernel, which otherwise is difficult to obtain from a single blurred image. Second, and again using both images, a residual deconvolution is proposed to significantly reduce ringing artifacts inherent to image deconvolution. Third, the remaining ringing artifacts in smooth image regions are further suppressed by a gain-controlled deconvolution process. We demonstrate the effectiveness of our approach using a number of indoor and outdoor images taken by off-the-shelf hand-held cameras in poor lighting environments.
Constraint-based motion optimization using a statistical dynamic model
Authors: Chai Jinxiang , Hodgins Jessica K.
Published: September 2007

In this paper, we present a technique for generating animation from a variety of user-defined constraints. We pose constraint-based motion synthesis as a
maximum a posterior
(MAP) problem and develop an optimization framework that generates natural motion satisfying user constraints. The system automatically learns a statistical dynamic model from motion capture data and then enforces it as a motion prior. This motion prior, together with user-defined constraints, comprises a trajectory optimization problem. Solving this problem in the low-dimensional space yields optimal natural motion that achieves the goals specified by the user. We demonstrate the effectiveness of this approach by generating whole-body and facial motion from a variety of spatial-temporal constraints.
Volume conserving finite element simulations of deformable models
Authors: Irving Geoffrey , Schroeder Craig , Fedkiw Ronald
Published: September 2007

We propose a numerical method for modeling highly deformable nonlinear incompressible solids that conserves the volume locally near each node in a finite element mesh. Our method works with arbitrary constitutive models, is applicable to both passive and active materials (e.g. muscles), and works with simple tetrahedra without the need for multiple quadrature points or stabilization techniques. Although simple linear tetrahedra typically suffer from locking when modeling incompressible materials, our method enforces incompressibility per node (in a one-ring), and we demonstrate that it is free from locking. We correct errors in volume without introducing oscillations by treating position and velocity in separate implicit solves. Finally, we propose a novel method for treating both object contact and self-contact as linear constraints during the incompressible solve, alleviating issues in enforcing multiple possibly conflicting constraints.
Locally controllable stylized shading
Authors: Todo Hideki , Anjyo Ken-ichi , Baxter William , Igarashi Takeo
Published: September 2007

Recent progress in non-photorealistic rendering (NPR) has led to many stylized shading techniques that efficiently convey visual information about the objects depicted. Another crucial goal of NPR is to give artists simple and direct ways to express the abstract ideas born of their imaginations. In particular, the ability to add intentional, but often unrealistic, shading effects is indispensable for many applications. We propose a set of simple stylized shading algorithms that allow the user to freely add localized light and shade to a model in a manner that is consistent and seamlessly integrated with conventional lighting techniques. The algorithms provide an intuitive, direct manipulation method based on a paint-brush metaphor, to control and edit the light and shade locally as desired. Our prototype system demonstrates how our method can enhance both the quality and range of applicability of conventional stylized shading for offline animation and interactive applications.
Line drawings via abstracted shading
Authors: Lee Yunjin , Markosian Lee , Lee Seungyong , Hughes John F.
Published: September 2007

We describe a GPU-based algorithm for rendering a 3D model as a line drawing, based on the insight that a line drawing can be understood as an abstraction of a shaded image. We thus render lines along tone boundaries or thin dark areas in the shaded image. We extend this notion to the dual: we render highlight lines along thin bright areas and tone boundaries. We combine the lines with toon shading to capture broad regions of tone.

The resulting line drawings effectively convey both shape and material cues. The lines produced by the method can include silhouettes. creases, and ridges, along with a generalization of suggestive contours that responds to lighting as well as viewing changes. The method supports automatic level of abstraction, where the size of depicted shape features adjusts appropriately as the camera zooms in or out. Animated models can be rendered in real time because costly mesh curvature calculations are not needed.
Parameterization-free projection for geometry reconstruction
Authors: Lipman Yaron , Cohen-Or Daniel , Levin David , Tal-Ezer Hillel
Published: September 2007

We introduce a Locally Optimal Projection operator (LOP) for surface approximation from point-set data. The operator is parameterization free, in the sense that it does not rely on estimating a local normal, fitting a local plane, or using any other local parametric representation. Therefore, it can deal with noisy data which clutters the orientation of the points. The method performs well in cases of ambiguous orientation, e.g., if two folds of a surface lie near each other, and other cases of complex geometry in which methods based upon local plane fitting may fail. Although defined by a global minimization problem, the method is effectively local, and it provides a second order approximation to smooth surfaces. Hence allowing good surface approximation without using any explicit or implicit approximation space. Furthermore, we show that LOP is highly robust to noise and outliers and demonstrate its effectiveness by applying it to raw scanned data of complex shapes.
Multi-scale capture of facial geometry and motion
Authors: Bickel Bernd , Botsch Mario , Angst Roland , Matusik Wojciech , Otaduy Miguel , Pfister Hanspeter , Gross Markus
Published: September 2007

We present a novel multi-scale representation and acquisition method for the animation of high-resolution facial geometry and wrinkles. We first acquire a static scan of the face including reflectance data at the highest possible quality. We then augment a traditional marker-based facial motion-capture system by two synchronized video cameras to track expression wrinkles. The resulting model consists of high-resolution geometry, motion-capture data, and expression wrinkles in 2D parametric form. This combination represents the facial shape and its salient features at multiple scales. During motion synthesis the motion-capture data deforms the high-resolution geometry using a linear shell-based mesh-deformation method. The wrinkle geometry is added to the facial base mesh using nonlinear energy optimization. We present the results of our approach for performance replay as well as for wrinkle editing.
Rendering for an interactive 360° light field display
Authors: Jones Andrew , McDowall Ian , Yamada Hideshi , Bolas Mark , Debevec Paul
Published: September 2007

We describe a set of rendering techniques for an autostereoscopic light field display able to present interactive 3D graphics to multiple simultaneous viewers 360 degrees around the display. The display consists of a high-speed video projector, a spinning mirror covered by a holographic diffuser, and FPGA circuitry to decode specially rendered DVI video signals. The display uses a standard programmable graphics card to render over 5,000 images per second of interactive 3D graphics, projecting 360-degree views with 1.25 degree separation up to 20 updates per second. We describe the system's projection geometry and its calibration process, and we present a multiple-center-of-projection rendering technique for creating perspective-correct images from arbitrary viewpoints around the display. Our projection technique allows correct vertical perspective and parallax to be rendered for any height and distance when these parameters are known, and we demonstrate this effect with interactive raster graphics using a tracking system to measure the viewer's height and distance. We further apply our projection technique to the display of photographed light fields with accurate horizontal and vertical parallax. We conclude with a discussion of the display's visual accommodation performance and discuss techniques for displaying color imagery.
Wrinkled flames and cellular patterns
Authors: Hong Jeong-Mo , Shinar Tamar , Fedkiw Ronald
Published: September 2007

We model flames and fire using the Navier-Stokes equations combined with the level set method and jump conditions to model the reaction front. Previous works modeled the flame using a combination of propagation in the normal direction and a curvature term which leads to a level set equation that is parabolic in nature and thus overly dissipative and smooth. Asymptotic theory shows that one can obtain more interesting velocities and fully hyperbolic (as opposed to parabolic) equations for the level set evolution. In particular, researchers in the field of detonation shock dynamics (DSD) have derived a set of equations which exhibit characteristic cellular patterns. We show how to make use of the DSD framework in the context of computer graphics simulations of flames and fire to obtain interesting features such as flame wrinkling and cellular patterns.
Efficient simulation of inextensible cloth
Authors: Goldenthal Rony , Harmon David , Fattal Raanan , Bercovier Michel , Grinspun Eitan
Published: September 2007

Many textiles do not noticeably stretch under their own weight. Unfortunately, for better performance many cloth solvers disregard this fact. We propose a method to obtain very low strain along the warp and weft direction using Constrained Lagrangian Mechanics and a novel fast projection method. The resulting algorithm acts as a velocity filter that easily integrates into existing simulation code.
Multiscale shape and detail enhancement from multi-light image collections
Authors: Fattal Raanan , Agrawala Maneesh , Rusinkiewicz Szymon
Published: September 2007

We present a new image-based technique for enhancing the shape and surface details of an object. The input to our system is a small set of photographs taken from a fixed viewpoint, but under varying lighting conditions. For each image we compute a multiscale decomposition based on the bilateral filter and then reconstruct an enhanced image that combines detail information at each scale across all the input images. Our approach does not require any information about light source positions, or camera calibration, and can produce good results with 3 to 5 input images. In addition our system provides a few high-level parameters for controlling the amount of enhancement and does not require pixel-level user input. We show that the bilateral filter is a good choice for our multiscale algorithm because it avoids the halo artifacts commonly associated with the traditional Laplacian image pyramid. We also develop a new scheme for computing our multiscale bilateral decomposition that is simple to implement, fastO(N2logN) and accurate.
Post-production facial performance relighting using reflectance transfer
Authors: Peers Pieter , Tamura Naoki , Matusik Wojciech , Debevec Paul
Published: September 2007

We propose a novel post-production facial performance relighting system for human actors. Our system uses just a dataset of view-dependent facial appearances with a neutral expression, captured for a static subject using a Light Stage apparatus. For the actual performance, however, a potentially different actor is captured under known, but static, illumination. During post-production, the reflectance field of the reference dataset actor is transferred onto the dynamic performance, enabling image-based relighting of the entire sequence. Our approach makes post-production relighting more practical and could easily be incorporated in a traditional production pipeline since it does not require additional hardware during principal photography. Additionally, we show that our system is suitable for real-time post-production illumination editing.
Rotational symmetry field design on surfaces
Authors: Palacios Jonathan , Zhang Eugene
Published: September 2007

Designing rotational symmetries on surfaces is a necessary task for a wide variety of graphics applications, such as surface parameterization and remeshing, painterly rendering and pen-and-ink sketching, and texture synthesis. In these applications, thetopologyof a rotational symmetry field such assingularitiesandseparatricescan have a direct impact on the quality of the results. In this paper, we present a design system that provides control over the topology of rotational symmetry fields on surfaces.

As the foundation of our system, we provide comprehensive analysis for rotational symmetry fields on surfaces and present efficient algorithms to identify singularities and separatrices. We also describe design operations that allow a rotational symmetry field to be created and modified in an intuitive fashion by using the idea of basis fields and relaxation. In particular, we provide control over the topology of a rotational symmetry field by allowing the user to remove singularities from the field or to move them to more desirable locations.

At the core of our analysis and design implementations is the observations thatN-way rotational symmetries can be described by symmetricN-th order tensors, which allows an efficient vector-based representation that not only supports coherent definitions of arithmetic operations on rotational symmetries but also enables many analysis and design operations for vector fields to be adapted to rotational symmetry fields.

To demonstrate the effectiveness of our approach, we apply our design system to pen-and-ink sketching and geometry remeshing.
Design of tangent vector fields
Authors: Fisher Matthew , Schröder Peter , Desbrun Mathieu , Hoppe Hugues
Published: September 2007

Tangent vector fields are an essential ingredient in controlling surface appearance for applications ranging from anisotropic shading to texture synthesis and non-photorealistic rendering. To achieve a desired effect one is typically interested in smoothly varying fields that satisfy a sparse set of user-provided constraints. Using tools from Discrete Exterior Calculus, we present a simple and efficient algorithm for designing such fields over arbitrary triangle meshes. By representing the field as scalars over mesh edges (i.e., discrete 1-forms), we obtain an intrinsic, coordinate-free formulation in which field smoothness is enforced through discrete Laplace operators. Unlike previous methods, such a formulation leads to a linear system whose sparsity permits efficient pre-factorization. Constraints are incorporated through weighted least squares and can be updated rapidly enough to enable interactive design, as we demonstrate in the context of anisotropic texture synthesis.
A theory of locally low dimensional light transport
Authors: Mahajan Dhruv , Shlizerman Ira Kemelmacher , Ramamoorthi Ravi , Belhumeur Peter
Published: September 2007

Blockwise or Clustered Principal Component Analysis (CPCA) is commonly used to achieve real-time rendering of shadows and glossy reflections with precomputed radiance transfer (PRT). The vertices or pixels are partitioned into smaller coherent regions, and light transport in each region is approximated by alocally low-dimensional subspaceusing PCA. Many earlier techniques such as surface light field and reflectance field compression use a similar paradigm. However, there has been no clear theoretical understanding of how light transport dimensionality increases with local patch size, nor of the optimal block size or number of clusters.

In this paper, we develop a theory of locally low dimensional light transport, by using Szego's eigenvalue theorem to analytically derive the eigenvalues of the covariance matrix for canonical cases. We show mathematically that for symmetric patches of areaA, the number of basis functions for glossy reflections increases linearly withA, while for simple cast shadows, it often increases as √A. These results are confirmed numerically on a number of test scenes. Next, we carry out an analysis of the cost of rendering, trading off local dimensionality and the number of patches, deriving an optimal block size. Based on this analysis, we provide useful practical insights for setting parameters in CPCA and also derive a new adaptive subdivision algorithm. Moreover, we show that rendering time scales sub-linearly with the resolution of the image, allowing for interactive all-frequency relighting of 1024 x 1024 images.
Harmonic coordinates for character articulation
Authors: Joshi Pushkar , Meyer Mark , DeRose Tony , Green Brian , Sanocki Tom
Published: September 2007

In this paper we consider the problem of creating and controlling volume deformations used to articulate characters for use in high-end applications such as computer generated feature films. We introduce a method we call harmonic coordinates that significantly improves upon existing volume deformation techniques. Our deformations are controlled using a topologically flexible structure, called a cage, that consists of a closed three dimensional mesh. The cage can optionally be augmented with additional interior vertices, edges, and faces to more precisely control the interior behavior of the deformation. We show that harmonic coordinates are generalized barycentric coordinates that can be extended to any dimension. Moreover, they are the first system of generalized barycentric coordinates that are non-negative even in strongly concave situations, and their magnitude falls off with distance as measured within the cage.
Key Point Subspace Acceleration and soft caching
Authors: Meyer Mark , Anderson John
Published: September 2007

Many applications in Computer Graphics contain computationally expensive calculations. These calculations are often performed at many points to produce a full solution, even though the subspace of reasonable solutions may be of a relatively low dimension. The calculation of facial articulation and rendering of scenes with global illumination are two example applications that require these sort of computations. In this paper, we present Key Point Subspace Acceleration and Soft Caching, a technique for accelerating these types of computations.

Key Point Subspace Acceleration (KPSA) is a statistical acceleration scheme that uses examples to compute a statistical subspace and a set of characteristic key points. The full calculation is then computed only at these key points and these points are used to provide a subspace based estimate of the entire calculation. The soft caching process is an extension to the KPSA technique where the key points are also used to provide a confidence estimate for the KPSA result. In cases with high anticipated error the calculation will then "fail through" to a full evaluation of all points (a cache miss), while frames with low error can use the accelerated statistical evaluation (a cache hit).