Graphics

ESCC
Changxi Zheng and Doug L. James, Energy-based Self-Collision Culling for Arbitrary Mesh Deformations.
ACM Transaction on Graphics (SIGGRAPH 2012), 31(4), August 2012

Paper(PDF) Project Page Abstract Bibtex
In this paper, we accelerate self-collision detection (SCD) for a deforming triangle mesh by exploiting the idea that a mesh cannot self collide unless it deforms enough. Unlike prior work on subspace self-collision culling which is restricted to low-rank deformation subspaces, our energy-based approach supports arbitrary mesh deformations while still being fast. Given a bounding volume hierarchy (BVH) for a triangle mesh, we precompute Energy-based Self-Collision Culling (ESCC) certificates on bounding-volume-related sub-meshes which indicate the amount of deformation energy required for it to self collide. After updating energy values at runtime, many bounding-volume self-collision queries can be culled using the ESCC certificates. We propose an affine-frame Laplacian-based energy definition which sports a highly optimized certificate preprocess, and fast runtime energy evaluation. The latter is performed hierarchically to amortize Laplacian energy and affine-frame estimation computations. ESCC supports both discrete and continuous SCD, detailed and nonsmooth geometry. We demonstrate significant culling on various examples, with SCD speed-ups up to 26X. 
@article{ZHENG12:ESCC,
    author = {Changxi Zheng and Doug L. James},
    title  = {Energy-based Self-Collision Culling for Arbitrary Mesh Deformations},
    journal = {ACM Transactions on Graphics (Proceedings of SIGGRAPH 2012)},
    year = {2012},
    volume = {31},
    number = {4},
    month  = Aug,
    url = {http://www.cs.cornell.edu/projects/escc}
}
AccNoise
Jeffrey N. Chadwick, Changxi Zheng and Doug L. James, Precomputed Acceleration Noise for Improved Rigid-Body Sound.
ACM Transaction on Graphics (SIGGRAPH 2012), 31(4), August 2012

Paper(PDF) Project Page Abstract Bibtex
We introduce an efficient method for synthesizing acceleration noise due to rigid-body collisions using standard data provided by rigid-body solvers. We accomplish this in two main steps. First, we estimate continuous contact force profiles from rigid-body impulses using a simple model based on Hertz contact theory. Next, we compute solutions to the acoustic wave equation due to short acceleration pulses in each rigid-body degree of freedom. We introduce an efficient representation for these solutions - Precomputed Acceleration Noise - which allows us to accurately estimate sound due to arbitrary rigid-body accelerations. We find that the addition of acceleration noise significantly complements the standard modal sound algorithm, especially for small objects. 
@article{Chadwick12,
    author = {Jeffrey N. Chadwick and Changxi Zheng and Doug L. James},
    title  = {Precomputed Acceleration Noise for Improved Rigid-Body Sound},
    journal = {ACM Transactions on Graphics (Proceedings of SIGGRAPH 2012)},
    year = {2012},
    volume = {31},
    number = {4},
    month  = Aug,
    url = {http://www.cs.cornell.edu/projects/Sound/impact}
}
FastAccNoise
Jeffrey N. Chadwick, Changxi Zheng and Doug L. James, Faster Acceleration Noise for Multibody Animations using Precomputed Soundbanks.
ACM/Eurographics Symposium on Computer Animation (SCA), July 2012

Paper(PDF) Project Page Abstract Bibtex
We introduce an efficient method for synthesizing rigid-body acceleration noise for complex multibody scenes. Existing acceleration noise synthesis methods for animation require object-specific precomputation, which is prohibitively expensive for scenes involving rigid-body fracture or other sources of small, procedurally generated debris. We avoid precomputation by introducing a proxy-based method for acceleration noise synthesis in which precomputed acceleration noise data is only generated for a small set of ellipsoidal proxies and stored in a proxy soundbank. Our proxy model is shown to be effective at approximating acceleration noise from scenes with lots of small debris (e.g., pieces produced by rigid-body fracture). This approach is not suitable for synthesizing acceleration noise from larger objects with complicated non-convex geometry; however, it has been shown in previous work that acceleration noise from objects such as these tends to be largely masked by modal vibration sound. We manage the cost of our proxy soundbank with a new wavelet-based compression scheme for acceleration noise and use our model to significantly improve sound synthesis results for several multibody animations. 
@article{Chadwick12:SCA,
    author = {Jeffrey N. Chadwick and Changxi Zheng and Doug L. James},
    title  = {Faster Acceleration Noise for Multibody Animations using
    Precomputed Soundbanks},
    journal = {ACM/Eurographics Symposium on Computer Animation},
    year = {2012},
    month  = July,
    url = {http://www.cs.cornell.edu/projects/Sound/proxy}
}
Modal Contact
Changxi Zheng and Doug L. James, Toward High-Quality Modal Contact Sound.
ACM Transaction on Graphics (SIGGRAPH 2011), 30(4), August 2011

Paper(PDF) Project Page Abstract Bibtex
Contact sound models based on linear modal analysis are commonly used with rigid body dynamics. Unfortunately, treating vibrating objects as "rigid" during collision and contact processing fundamentally limits the range of sounds that can be computed, and contact solvers for rigid body animation can be ill-suited for modal contact sound synthesis, producing various sound artifacts. In this paper, we resolve modal vibrations in both collision and frictional contact processing stages, thereby enabling non-rigid sound phenomena such as micro-collisions, vibrational energy exchange, and chattering. We propose a frictional multibody contact formulation and modified Staggered Projections solver which is well-suited to sound rendering and avoids noise artifacts associated with spatial and temporal contact-force fluctuations which plague prior methods. To enable practical animation and sound synthesis of numerous bodies with many coupled modes, we propose a novel asynchronous integrator with model-level adaptivity built into the frictional contact solver. Vibrational contact damping is modeled to approximate contact-dependent sound dissipation. Results are provided that demonstrate high-quality contact resolution with sound. 
@article{ZHENG11,
    author = {Changxi Zheng and Doug L. James},
    title  = {Toward High-Quality Modal Contact Sound},
    journal = {ACM Transactions on Graphics (Proceedings of SIGGRAPH 2011)},
    year = {2011},
    volume = {30},
    number = {4},
    month  = Aug,
    url = {http://www.cs.cornell.edu/projects/Sound/mc}
}
Rigid Fracture
Changxi Zheng and Doug L. James, Rigid-Body Fracture Sound with Precomputed Soundbanks.
ACM Transaction on Graphics (SIGGRAPH 2010), 29(3), July 2010

Paper(PDF) Project Page Abstract Bibtex
We propose a physically based algorithm for synthesizing sounds synchronized with brittle fracture animations. Motivated by laboratory experiments, we approximate brittle fracture sounds using time-varying rigid-body sound models. We extend methods for fracturing rigid materials by proposing a fast quasistatic stress solver to resolve near-audio-rate fracture events, energy-based fracture pattern modeling and estimation of "crack"-related fracture impulses. Multipole radiation models provide scalable sound radiation for complex debris and level of detail control. To reduce soundmodel generation costs for complex fracture debris, we propose Precomputed Rigid-Body Soundbanks comprised of precomputed ellipsoidal sound proxies. Examples and experiments are presented that demonstrate plausible and affordable brittle fracture sounds. 
@article{ZHENG10,
    author = {Changxi Zheng and Doug L. James},
    title  = {Rigid-Body Fracture Sound with Precomputed Soundbanks},
    journal = {ACM Transactions on Graphics (Proceedings of SIGGRAPH 2010)},
    year = {2010},
    volume = {29},
    number = {3},
    month  = jul,
    url = {http://www.cs.cornell.edu/projects/fracturesound/}
}
Fluid Sound
Changxi Zheng and Doug L. James, Harmonic Fluids.
ACM Transaction on Graphics (SIGGRAPH 2009), 28(3), August 2009

Paper(PDF) Project Page Abstract Bibtex
Fluid sounds, such as splashing and pouring, are ubiquitous and familiar but we lack physically based algorithms to synthesize them in computer animation or interactive virtual environments. We propose a practical method for automatic procedural synthesis of synchronized harmonic bubble-based sounds from 3D fluid animations. To avoid audio-rate time-stepping of compressible fluids, we acoustically augment existing incompressible fluid solvers with particle-based models for bubble creation, vibration, advection, and radiation. Sound radiation from harmonic fluid vibrations is modeled using a time-varying linear superposition of bubble oscillators. We weight each oscillator by its bubble-to-ear acoustic transfer function, which is modeled as a discrete Green's function of the Helmholtz equation. To solve potentially millions of 3D Helmholtz problems, we propose a fast dual-domain multipole boundary-integral solver, with cost linear in the complexity of the fluid domain's boundary. Enhancements are proposed for robust evaluation, noise elimination, acceleration, and parallelization. Examples of harmonic fluid sounds are provided for water drops, pouring, babbling, and splashing phenomena, often with thousands of acoustic bubbles, and hundreds of thousands of transfer function solves. 
@article{ZHENG09,
    author = {Changxi Zheng and Doug L. James},
    title  = {Harmonic Fluids},
    journal = {ACM Transactions on Graphics (Proceedings of SIGGRAPH 2009)},
    year = {2009},
    volume = {28},
    number = {3},
    month  = Aug,
    url = {http://www.cs.cornell.edu/projects/HarmonicFluids/}
}


Robotics

Placement IJRR
Yun Jiang, Marcus Lim, Changxi Zheng, and Ashutosh Saxena, Learning to Place New Objects in a Scene.
In International Journal of Robotics Research (IJRR), 2012

Paper(PDF) Project Page Abstract Bibtex
Placing is a necessary skill for a personal robot to have in order to perform tasks such as arranging objects in a disorganized room. The object placements should not only be stable but also be in their semantically preferred placing areas and orientations. This is challenging because an environment can have a large variety of objects and placing areas that may not have been seen by the robot before.
In this paper, we propose a learning approach for placing multiple objects in different placing areas in a scene. Given point-clouds of the objects and the scene, we design appropriate features and use a graphical model to encode various properties, such as the stacking of objects, stability, object-area relationship and common placing constraints. The inference in our model is an integer linear program, which we solve efficiently via an LP relaxation. We extensively evaluate our approach on 98 objects from 16 categories being placed into 40 areas. Our robotic experiments show a success rate of 98% in placing known objects and 82% in placing new objects stably. We use our method on our robots for performing tasks such as loading several dish-racks, a bookshelf and a fridge with multiple items. 
@article{jiang2012placingobjects,
  title={Learning to Place New Objects in a Scene},
  author={Yun Jiang and Marcus Lim and Changxi Zheng and Ashutosh Saxena},
  year={2012},
  volume={31},
  number={9},
  journal={IJRR}
}
Placement
Yun Jiang, Changxi Zheng, Marcus Lim, Ashutosh Saxena, Learning to Place New Objects.
In International Conference on Robotics and Automation (ICRA), 2012. First appeared in RSS workshop on mobile manipulation, June 2011.

Paper(PDF) Project Page Abstract Bibtex
The ability to place objects in an environment is an important skill for a personal robot. An object should not only be placed stably, but should also be placed in its preferred location/orientation. For instance, a plate is preferred to be inserted vertically into the slot of a dish-rack as compared to be placed horizontally in it. Unstructured environments such as homes have a large variety of object types as well as of placing areas. Therefore our algorithms should be able to handle placing new object types and new placing areas. These reasons make placing a challenging manipulation task.
In this work, we propose a supervised learning algorithm for finding good placements given the point-clouds of the object and the placing area. It learns to combine the features that capture support, stability and preferred placements using a shared sparsity structure in the parameters. Even when neither the object nor the placing area is seen previously in the training set, our algorithm predicts good placements. In extensive experiments, our method enables the robot to stably place several new objects in several new placing areas with 98% success-rate; and it placed the objects in their preferred placements in 92% of the cases. 
@inproceedings{jiang2011learningtoplace,
  title={Learning to place new objects},
  author={Jiang, Y. and Zheng, C. and Lim, M. and Saxena, A.},
  booktitle={International Conference on Robotics and Automation (ICRA)},
  year={2012},
}


Networking

IP Hajack
Changxi Zheng, Lusheng Ji, Dan Pei, Jia Wang and Paul Francis, A Light-Weight Distributed Scheme for Detecting IP Prefix Hijacks in Real-time.
Proc. of ACM SIGCOMM, Kyoto, Japan, August 2007

Paper(PDF) Abstract Bibtex
As more and more Internet IP prefix hijacking incidents are being reported, the value of hijacking detection services has become evident. Most of the current hijacking detection approaches monitor IP prefixes on the control plane and detect inconsistencies in route advertisements and route qualities. We propose a different approach that utilizes information collected mostly from the data plane. Our method is motivated by two key observations: when a prefix is not hijacked, 1) the hop count of the path from a source to this prefix is generally stable; and 2) the path from a source to this prefix is almost always a super-path of the path from the same source to a reference point along the previous path, as long as the reference point is topologically close to the prefix. By carefully selecting multiple vantage points and monitoring from these vantage points for any departure from these two observations, our method is able to detect prefix hijacking with high accuracy in a light-weight, distributed, and real-time fashion. Through simulations constructed based on real Internet measurement traces, we demonstrate that our scheme is accurate with both false positive and false negative ratios below 5%. 
@inproceedings{Zheng:2007,
    author = {Zheng, Changxi and Ji, Lusheng and Pei, Dan and Wang, Jia and Francis, Paul},
    title = {A light-weight distributed scheme for detecting ip prefix hijacks in real-time},
    booktitle = {Proceedings of the 2007 conference on Applications, technologies, 
                 architectures, and protocols for computer communications},
    series = {SIGCOMM '07},
    year = {2007},
    location = {Kyoto, Japan},
    pages = {277--288},
    numpages = {12},
    publisher = {ACM},
    address = {New York, NY, USA},
}


Earlier Papers

Guobin Shen, Changxi Zheng, Wei Pu and Shipeng Li, Distributed Segment Tree: A Unified Architecture to Support Range Query and Cover Query.
Technical Report MSR-TR-2007-30, 2007

Paper(PDF)
Changxi Zheng, Guobin Shen, Shipeng Li, and Scott Shenker, Distributed Segment Tree: Support of Range Query and Cover Query over DHT.
The 5th International Workshop on Peer-to-Peer Systems (IPTPS) Santa Barbara, US, February 2006

Paper(PDF) Abstract Bibtex
Range query, which is defined as to find all the keys in a certain range over the underlying P2P network, has received a lot of research attentions recently. However, cover query, which is to find all the ranges currently in the system that cover a given key, is rarely touched. In this paper, we first identify that cover query is a highly desired functionality by some popular P2P applications, and then propose distributed segment tree (DST), a layered DHT structure that incorporates the concept of segment tree. Due to the intrinsic capability of segment tree in maintaining the sturcture of ranges, DST is shown to be very efficient for supporting both range query and cover query in a uniform way. It also possesses excellent parallelizability in query operations and can achieve O(1) complexity for moderate query ranges. To balance the load among DHT nodes, we design a downward load stripping mechanism that controls tradeoffs between load and performance. We implemented DST on publicly available OpenDHT service and performed extensive real experiments. All the results and comparisons demonstrate the effectiveness of DST for several important metrics. 
@inproceedings{Zheng06DST,
    author      = {Changxi Zheng and Guobin Shen and Shipeng Li and Scott Shenker},
    title       = {Distributed segment tree: Support of range query and cover query over dht},
    booktitle   = {In proceedings of the 5th International Workshop on 
                   Peer-to-Peer Systems (IPTPS 06)},
    year        = {2006}
}
Ke Liang, Zaoyang Gong, Changxi Zheng, and Guobin Shen, MOVIF: A Lower Power Consumption Live Video Multicasting Framework over Ad-hoc Networks with Terminal Collaboration.
International Symposium on Intelligent Signal Processing and Communication Systems (ISPACS), Hong Kong, December 2005

Paper(PDF) Abstract
Live video multicasting over wireless ad hoc networks is a tough problem due to the restricted computational ability of the mobile devices and non-predictive networks status. In this paper, we propose MoViF, a lower power consumption multicasting framework for live video multicasting over ad-hoc networks. The proposed MoViF adopts distributed video coding (DVC) scheme and, as a result, enjoys all the beneļ¬ts of DVC such as lightweight encoder and built-in error resilient capability. Moreover, MoViF manages to apply an elegant strategy to minimize the overall power consumption for all the receivers while improving their decoding quality by dynamically assign the tasks of aid information extraction to some intermediate powerful nodes in the multicast tree. Simulation results demonstrate that the optimal strategy can lower down the overall power consumption comparing to the random strategy.
Changxi Zheng, Guobin Shen, and Shipeng Li, Distributed Prefetching Scheme for Random Seek Support in Peer-to-Peer Streaming Applications.
Workshop on Advances in Peer-to-Peer Multimedia Streaming, ACM Multimedia 2005, Singapore, November 2005

Paper(PDF) Abstract
Through analysis of large volume of user behavior logs during playing multimedia streaming, we extract a user viewing pattern. The pattern indicates that random seek is a pervasive phenomenon, contrary to the common assumptions that users would watch a video session sequentially and passively in most works on peer-to-peer streaming. We propose to use efficient prefetching to facilitate the random seek functionality. Because of the statistical nature of the user viewing pattern and the ignorance of the users to the content, we argue that the pattern should be used as a guidance to the random seek. Based on the pattern, we set up an analogy between the optimization problem of minimizing the seeking distance and the optimal scalar quantization problem. We then propose an optimal prefetching scheduling algorithm based on the optimal scalar quantization theory. We further propose a hierarchical prefetching scheme to carry out the prefetching more effectively. Real user viewing logs are used to drive the simulations which demonstrate that the proposed prefetching scheduling algorithm and the hierarchical prefetching scheme can improve the seeking performance significantly.
Changxi Zheng, Guobin Shen, and Shipeng Li, Segment Tree Based Control Plane Protocol for Peer-to-Peer On-Demand Streaming Service Discovery.
Proc. of Visual Communication and Image Processing (VCIP), Beijing, China, July 2005

Paper(PDF) Abstract Bibtex
As the intense academic interest in video streaming over peer-to-peer(P2P) network, more and more streaming protocols have been proposed to address different problems on this field, such as QoS, load balancing, transmission reliability, bandwidth efficiency, etc. However, to the best of our knowledge, an important component of any practical P2P streaming system, the streaming service discovery, is rarely granted particular considerations, which is to discover potential peers from which a newcomer could receive the requested stream. In this paper, we are inspired from a special data structure, named Segment Tree(ST), and propose a protocol to address this problem specifically. Furthermore, we fully decouple the control plane and data plane on video streaming, and hence provide more flexibilities in designing protocols on both of them. 
@inproceedings{Zheng05VCIP,
    author      = {Changxi Zheng and Guobin Shen and Shipeng Li},
    title       = {Segment Tree Based Control Plane Protocol for Peer-to-Peer 
                   On-Demand Streaming Service Discovery},
    booktitle   = {In proceedings of Visual Communication and Image Processing (VCIP)},
    year        = {2006}
}
Changxi Zheng, Guobin Shen, Shipeng Li and Qianni Deng, Joint Sender/Receiver Optimization Algorithm for Multi-Path Video Streaming Using High Rate Erasure Resilient Code.
Proc. of IEEE International Conference on Multimedia and Expo (ICME), Amsterdam, Netherlands, July 2005

Paper(PDF) Abstract Bibtex
In this paper we present a joint sender/receiver optimization algorithm and a seamless rate adjustment protocol to reduce the total number of packets over different paths in a streaming framework with a variety of constraints such as target throughput, dynamic packet loss ratio, and available bandwidths. We exploit the high rate erasure resilient code for the ease of packet loss adaption and seamless rate adjustment. The proposed algorithm and adjustment protocol can be applied at an arbitrary scale. Simulation results demonstrate that the overall traffic is significantly reduced with the proposed algorithm and protocol. 
@inproceedings{Zheng05ICME,
    author      = {Changxi Zheng and Guobin Shen and Shipeng Li and Qianni Deng},
    title       = {Joint Sender/Receiver Optimization Algorithm for Multi-Path Video Streaming 
                   Using High Rate Erasure Resilient Code},
    booktitle   = {IEEE International Conference on Multimedia and Expo (ICME)}, 
    month       = July,
    year        = {2005}
}


PhD Thesis

PhD Thesis

Changxi Zheng, Physics-Based Sound Rendering for Computer Animation.
Department of Computer Science, Cornell University, August 2012

Paper(PDF) Abstract
The real world is full of sounds: a babbling brook winding through a tranquil forest, an agitated shopping cart plugging down a flight of stairs, or a falling piggybank breaking on the ground. Unfortunately virtual worlds simulated by current simulation algorithms are still inherently silent. Sounds are added as afterthoughts, often using "canned sounds" which have little to do with the animated geometry and physics. While recent decades have seen dramatic success of 3D computer animation, our brain still expects a full spectrum of sensations. The lack of realistic sound rendering methods will continue to cripple our ability to enable highly interactive and realistic virtual experiences as computers become faster.

This dissertation presents a family of algorithms for procedural sound synthesis for computer animation. These algorithms are built on physics-based simulation methods for computer graphics, simulating both the object vibrations for sound sources and sound propagation in virtual environments. These approaches make it feasible to automatically generate realistic sounds synchronized with animated dynamics.

Our first contribution is a physically based algorithm for synthesizing sounds synchronized with brittle fracture animations. Extending time-varying rigid-body sound models, this method first resolves near-audio-rate fracture events using a fast quasistatic elastic stress solver, and then estimates fracture patterns and resulting fracture impulses using an energy-based model. To make it practical for a large number of fracture debris, we exploit human perceptual ambiguity when synthesizing sounds from many objects, and propose to use pre-computed sound proxies for reduced cost of sound-model generation.

We then introduce a contact sound model for improved sound quality. This method captures very detailed non-rigid sound phenomena by resolving modal vibrations in both collision and frictional contact processing stages, thereby producing contact sounds with much richer audible details such as micro-collisions and chattering. This algorithm is practical, enabled by a novel asynchronous integrator with model-level adaptivity built into a frictional contact solver.

Our third contribution focuses on another major type of sound phenomena, fluid sounds. We propose a practical method for automatic synthesis of bubble-based fluid sounds from fluid animations. This method first acoustically augments existing incompressible fluid solvers with particle-based models for bubble creation, vibration, and advection. To model sound propagation in both fluid and air domain, we weight each single-bubble sound by its bubble-to-ear acoustic transfer function value, which is modeled as a discrete Green's function of the Helmholtz equation. A fast dual-domain multipole boundary-integral solver is introduced for hundreds of thousands of Helmholtz solves in a typical babbling fluid simulation.

Finally, we switch gear and present a fast self-collision detection method for deforming triangle meshes. This method can accelerate deformable simulations and lead to faster sound synthesis of deformable phenomena. Inspired by a simple idea that a mesh cannot self collide unless it deforms enough, this method supports arbitrary mesh deformations while still being fast. Given a bounding volume hierarchy (BVH) for a triangle mesh, we operate on bounding-volume-related submeshes, and precompute Energy-based Self-Collision Culling (ESCC) certificates, which indicate the amount of deformation energy required for the submesh to self collide. After updating energy values at runtime, many bounding-volume self-collision queries can be culled using the ESCC certificates. We propose an affine-frame Laplacian-based energy definition which sports a highly optimized certificate preprocess and fast runtime energy evaluation.