Yuanchen Zhu

Sensor Network Localization Using Sensor Perturbation

Zhu, Y., Gortler, S. J., and Thurston, D. 2008. Short version appears in Proceedings of the 28th Conference on Computer Communications (IEEE INFOCOM 2009), April 2009, pp. 2796–2800.

Full version appears in ACM Transactions on Sensor Networks, vol. 7, no. 4, pp. 46.

Download — short version, full version.

Abstract — Sensor network localization is an instance of the NP-HARD graph realization problem. Thus, methods used in practice are not guaranteed to find the correct localization, even if it is uniquely determined by the input distances.

In this paper, we show the following: if the sensors are allowed to wiggle, giving us perturbed distance data, we can apply a novel algorithm to realize arbitrary generically globally rigid graphs (GGR), or certain vertex subsets in non-GGR graphs whose relative positions are fixed (which include vertex sets of GGR subgraphs). And this strategy works in any dimension.

In the language of structural rigidity theory, our approach corresponds to calculating the approximate kernel of a generic stress matrix for the given graph and distance data. To make our algorithm suitable for real-world application, we also present (i) various techniques for improving the robustness of the algorithm in the presence of measurement noise (ii) an algorithm for detecting certain subsets of graph vertices whose relative positions are fixed in any generic realization of the graph and robustly localizing these subsets of vertices (iii) a strategy for reducing the number of measurements needed by the algorithm.

We provide simulation results of our algorithm.

Index Terms — Generic global rigidity, globally linked, localization, rigidity theory, sensor networks, sensor perturbation

3D Deformation Using Moving Least Squares

Zhu, Y., and Gortler, S.J. 2007. Harvard University Technical Report, TR-10-07.

Download — paper, video (xvid/mp3 encoded avi).

Abstract — We present a 3d deformation method based on Moving Least Squares that extends the work by Schaefer et al. [2006] to the 3d setting. The user controls the deformation by manipulating a set of point handles. Locally, the deformation takes the form of either a rigid transformation or optionally a similarity transformation, and tends to preserve local features. Our derivation of the closed-form solution is based on singular value decomposition, and is applicable to deformation in arbitrary dimensions, as opposed to the planar case in [Schaefer et al. 2006]. Our prototype implementation allows interactive deformation of meshes of over 100k vertices.

For the application of 3d mesh deformation, we further introduce a weighting scheme that determines the influence of point handles on vertices based on approximate mesh geodesics. In practice, the new scheme gives much better deformation results for limbed character models, compared with simple Euclidean distance based weighting. The new weighting scheme can be of use to the traditional skinny based deformation technique as well.

Index Terms — Deformations, character animation, moving least squares, rigid transformation, mesh geodesic

Uniform Remeshing with an Adaptive Domain: A New Scheme for View-Dependent Level-of-Detail Rendering of Meshes

Zhu, Y. 2005. In IEEE Transactions on Visualization and Computer Graphics, vol. 11, no. 3, pp. 306–316.

Initially a research project/paper for the Intel International Science and Engineering Fair 2004, Project ID: CS038.

Download — paper, demo (zip of win32 executable), and Intel ISEF poster.

Abstract — We present a new algorithm for view-dependent level-of-detail rendering of meshes. Not only can it effectively resolve complex geometry features similar to edge collapse based schemes, but it also produces meshes that modern graphics hardware can render efficiently. This is accomplished through a novel hybrid approach: for each frame, we view-dependently refine the progressive mesh (PM) representation of the original mesh and use the output as the base domain of uniform regular refinements. The algorithm exploits frame-to-frame coherence and only updates portions of the output mesh corresponding to modified domain triangles. The PM representation is built using a custom volume preservation based error function. A simple k-d tree enhanced jump-and-walk scheme is used to quickly map from the dynamic base domain to the original mesh during regular refinements. In practice, the PM refinement provides a view-optimized base domain for later regular refinements. The regular refinements ensure almost everywhere regularity of output meshes, allowing optimization for vertex cache coherence and caching of geometry data in high-performance graphics memory. Combined, they also have the effect of allowing our algorithm to operate on uniform clusters of triangles instead of individual ones, reducing CPU workload.

Index Terms — Level-of-detail, view-dependent meshes, remeshing, multi-resolution representation, frame-to-frame coherence.

A New Algorithm for View-Dependent Optimization of Terrain with Sub-Linear Time CPU Processing

Zhu, Y. 2005. Harvard University Technical Report, TR-07-08.

This is the developed form of the 2001 Intel International Science and Engineering Fair project

Download — paper.

Abstract — This paper presents new schemes for view-dependent continuous level-of-detail (LOD) rendering of terrain which update output meshes with sub-linear CPU processing.

We use a directed acyclic graph (DAG) abstraction for the longest-edge-bisection based multiresolution model. The other component of our refinement framework is the saturated monotonic perspective-division based error function. We made the critical observation that, for a vertex, the difference between the reciprocals of this particular error function for two different viewpoints is bounded by the distance between the two viewpoints, times a per-vertex constant. We call this the bounded variation property.

Utilizing this property, we introduce the distance deferral table, a circular array based structure that schedules deferred processing of DAG vertices according to viewpoint motion. We then use the distance deferral table to optimize the traditional threshold-based refinement algorithm and the dual-queue constrained optimization algorithm to allow sub-linear CPU run-time.

Index Terms — Viewing algorithms, virtual reality, visualization techniques and methodologies, terrain visualization, continuous level-of-detail, view-dependent optimization, deferred processing, multiresolution representation

Real-Time Continuous Level-of-Detail Terrain Rendering with Nested Splitting Space

Zhu., Y. Intel International Science and Engineering Fair 2001, Project ID: CS012.

Download — paper, demo (zip of win32 executable), and Intel ISEF poster.

Abstract — Real-time visualization of large-scale terrain models requires complex continuous level-of-detail (LOD) schemes to reduce the prohibitively large geometry complexity of natural terrain to an acceptable level while maintaining high image quality. This paper presents new algorithms and data structures to solve this problem.

Our solution centers on computing independent per-vertex error bounds, which we call nested splitting space, for vertices in the height field according to screen-space error metrics and vertex dependence hierarchy. Based on this, a framework for circular array based, frame-coherent mesh refinement and reduction is devised. A simple mechanism to support vertex morphing requiring zero storage overhead is proposed, and methods for procedural generation of error bounds are given, providing support for real-time on-demand procedural details generation.

The algorithm accomplishes LOD updates in time proportional to the number of LOD changes needed for each frame. In our sample implementation, updating the mesh takes less than one tenth of the time spent on processing and rendering the mesh by the graphics hardware.

The contributions of this paper are twofold: First, the idea of computing independent per-vertex error bounds, which can also be utilized by other LOD algorithms, is presented; Secondly, accompanying schemes of frame-coherence optimization, vertex morphing support, and procedural error bounds generation for continuous LOD rendering of terrain, which outperform existing methods in terms of efficiency, storage requirement, supported features and ease of implementation, are proposed.

Index Terms — Level-of-detail, view-dependent, terrain rendering.