Abstract Text is a crucial component of 3‐D environments and virtual worlds for user interfaces and wayfinding. Implementing text using standard antialiased texture mapping leads to blurry and illegible writing which hinders usability and navigation. While super‐sampling removes some of these artifacts, distracting artifacts can still impede legibility, especially for recent high‐resolution head‐mounted displays. We propose an analytic antialiasing technique that efficiently computes the coverage of text glyphs, over pixel footprints, designed to run at real‐time rates. It decomposes glyphs into piecewise‐biquadratics and trapezoids that can be quickly area‐integrated over a pixel footprint to provide crisp legible antialiased text, even when mapped onto an arbitrary surface in a 3‐D virtual environment.

Tracing the paths of collections of particles through a flow field is a key step for many flow visualization and analysis methods. When a flow field is interpolated from the nodes of an unstructured mesh, the process of advecting a particle must first find which cell in the unstructured mesh contains the particle. Since the paths of nearby particles often diverge, the parallelization of particle advection quickly leads to incoherent memory accesses of the unstructured mesh. We have developed a new block advection GPU approach that reorganizes particles into spatially coherent bundles as they follow their advection paths, which greatly improves memory coherence and thus shared-memory GPU performance. This approach works best for flows that meet the CFL criterion on unstructured meshes of uniformly sized elements, small enough to fit at least two timesteps in GPU memory.

Abstract We present a botanical simulation of secondary (cambial) tree growth coupled to a physical cracking simulation of its bark. Whereas level set growth would use a fixed resolution voxel grid, our system extends the deformable simplicial complex (DSC), supporting new biological growth functions robustly on any surface polygonal mesh with adaptive subdivision, collision detection and topological control. We extend the DSC with temporally coherent texturing, and surface cracking with a user‐controllable biological model coupled to the stresses introduced by the cambial growth model.

Modern object detection methods apply binary linear classifiers on Euclidean feature vectors. This paper shows that projecting feature vectors onto a hypersphere allows an approximate range query to accelerate these detectors within acceptable levels of accuracy. The expense of constructing the k-d tree used by these range queries is justified when many detectors are used. We demonstrate our acceleration technique on several existing detection systems, including a state of the art logo detector, and show that approximate range queries can detect logos at least half as well at 11× the speed of the full fidelity method.

Abstract The hierarchical edge bundle (HEB) method generates useful visualizations of dense graphs, such as social networks, but requires a predefined clustering hierarchy, and does not easily benefit from existing straight‐line visualization improvements. This paper proposes a new clustering approach that extracts the community structure of a network and organizes it into a hierarchy that is flatter than existing community‐based clustering approaches and maps better to HEB visualization. Our method not only discovers communities and generates clusters with better modularization qualities, but also creates a balanced hierarchy that allows HEB visualization of unstructured social networks without predefined hierarchies. Results on several data sets demonstrate that this approach clarifies real‐world communication, collaboration and competition network structure and reveals information missed in previous visualizations. We further implemented our techniques into a social network visualization application on facebook.com and let users explore the visualization and community clustering of their own social networks.

As an emerging technology, 3D video has shown a great potential to become the next generation media for tele-immersion. However, streaming and rendering this dynamic 3D data in real-time requires tremendous network bandwidth and computing resources. In this paper, we build a remote rendering model to better study different remote rendering designs and define 3D video rendering as an optimization problem. Moreover, we design a 3D video remote rendering system that significantly reduces the delay while maintaining high rendering quality. We also propose a reference viewpoint prediction algorithm with super sampling support that requires much less computation resources but provides better performance than the search-based algorithms proposed in the related work.

The level set method can implement a wide variety of shape modeling operations (e.g. offsetting, skeletonization, morphing, blending, smoothing, sharpening, embossing, denoising, sculpting, growing, texturing and fitting) simply by specifying a corresponding speed function that controls the growth of an evolving voxel isosurface. The problem is that the basic level set method is implemented on a fixed resolution grid, which limits the utility of these shape modeling operations. We instead represent surfaces with a collection of radial basis function dipole pairs, and derive the motion of these dipoles to implement a surface propagation similar to the level set method but on a smooth, arbitrary resolution model. We demonstrate the utility of this approach with new level set methods for surface fitting, blending and center redistribution for RBF dipole models.

Abstract We present a generalization of the scalar importance function employed by Metropolis Light Transport (MLT) and related Markov chain rendering algorithms. Although MLT is known for its user‐designable mutation rules, we demonstrate that its scalar contribution function is similarly programmable in an unbiased manner. Normally, MLT samples light paths with a tendency proportional to their brightness. For a range of scenes, we demonstrate that this importance function is undesirable and leads to poor sampling behaviour. Instead, we argue that simple user‐designable importance functions can concentrate work in transport effects of interest and increase estimator efficiency. Unlike mutation rules, these functions are not encumbered with the calculation of transitional probabilities. We introduce alternative importance functions, which encourage the Markov chain to aggressively pursue sampling goals of interest to the user. In addition, we prove that these importance functions may adapt over the course of a render in an unbiased fashion. To that end, we introduce multi‐stage MLT, a general rendering setting for creating such adaptive functions. This allows us to create a noise‐sensitive MLT renderer whose importance function explicitly targets noise. Finally, we demonstrate that our techniques are compatible with existing Markov chain rendering algorithms and significantly improve their visual efficiency.

Abstract We describe a rendering system that converts a 3D meshed model into the stylized 2D filled‐region vector‐art commonly found in clip‐art libraries. To properly define filled regions, we analyze and combine accurate but jagged face‐normal contours with smooth but inaccurate interpolated vertex normal contours, and construct a new smooth shadow contour that properly surrounds the actual jagged shadow contour. We decompose region definition into geometric and topological components, using machine precision for geometry processing and raster‐precision to accelerate topological queries. We extend programmable stylization to simplify, smooth and stylize filled regions. The result renders 10K‐face meshes into custom clip‐art in seconds.

This paper proposes novel methods for visualizing specifically the large power-law graphs that arise in sociology and the sciences. In such cases a large portion of edges can be shown to be less important and removed while preserving component connectedness and other features (e.g. cliques) to more clearly reveal the network's underlying connection pathways. This simplification approach deterministically filters (instead of clustering) the graph to retain important node and edge semantics, and works both automatically and interactively. The improved graph filtering and layout is combined with a novel computer graphics anisotropic shading of the dense crisscrossing array of edges to yield a full social network and scale-free graph visualization system. Both quantitative analysis and visual results demonstrate the effectiveness of this approach.

Isochords is a visualization of music that aids in the classification of musical structure. The Isochords visualization highlights the consonant intervals between notes and common chords in music. It conveys information about interval quality, chord quality, and the chord progression synchronously during playback of digital music. Isochords offers listeners a means to grasp the underlying structure of music that, without extensive training, would otherwise remain unobserved or unnoticed. In this paper we present the theory of the Isochords structure, the visualization, and comments from novice and experienced users.

Shape deformation is a common practice in digital image editing, but can unrealistically stretch or compress texture detail. We propose an image editing system that decouples feature position from pixel color generation, by resynthesizing texture from the source image to preserve its detail and orientation around a new feature curve location. We introduce a new distortion to patch-based texture synthesis that aligns texture features with image features. A dense correspondence field between source and target images generated by the control curves then guides texture synthesis.

Resampling raw surface meshes is one of the most fundamental operations used by nearly all digital geometry processing systems. The vast majority of this work has focused on triangular remeshing, yet quadrilateral meshes are preferred for many surface PDE problems, especially fluid dynamics, and are best suited for defining Catmull-Clark subdivision surfaces. We describe a fundamentally new approach to the quadrangulation of manifold polygon meshes using Laplacian eigenfunctions, the natural harmonics of the surface. These surface functions distribute their extrema evenly across a mesh, which connect via gradient flow into a quadrangular base mesh. An iterative relaxation algorithm simultaneously refines this initial complex to produce a globally smooth parameterization of the surface. From this, we can construct a well-shaped quadrilateral mesh with very few extraordinary vertices. The quality of this mesh relies on the initial choice of eigenfunction, for which we describe algorithms and hueristics to efficiently and effectively select the harmonic most appropriate for the intended application.

We propose a video editing system that allows a user to apply a time-coherent texture to a surface depicted in the raw video from a single uncalibrated camera, including the surface texture mapping of a texture image and the surface texture synthesis from a texture swatch. Our system avoids the construction of a 3D shape model and instead uses the recovered normal field to deform the texture so that it plausibly adheres to the undulations of the depicted surface. The texture mapping method uses the nonlinear least-squares optimization of a spring model to control the behavior of the texture image as it is deformed to match the evolving normal field through the video. The texture synthesis method uses a coarse optical flow to advect clusters of pixels corresponding to patches of similarly oriented surface points. These clusters are organized into a minimum advection tree to account for the dynamic visibility of clusters. We take a rather crude approach to normal recovering and optical flow estimation, yet the results are robust and plausible for nearly diffuse surfaces such as faces and t-shirts.

We present a novel algorithm for the rendering of hard shadows cast by a point light source. The well-known Z-pass method for rasterizing shadow volumes is not always correct. Our algorithm, which we call ZP+, elegantly corrects Z-pass defects. ZP+ takes advantage of triangle strips and the fast culling capabilities of graphics hardware not available to conventional robust methods like Z-fail. While Z-fail can be up to 80% slower than Z-pass, our new method ZP+ is typically less than 10% slower than Z-pass. Finally, we compare the three methods. When a scene is geometry-bound, ZP+ is always faster than Z-fail. We also explain why, in some situations, Z-pass (hence ZP+) is surprisingly slower than Z-fail on more recent graphics hardware.

Particle systems are an effective tool for visualizing information in a variety of contexts. This paper focuses on the use of surface-constrained particles to visualize information about the surface. We have designed a particle system programming framework consisting of behaviors, attributes and shaders that allows users to rapidly create, debug, and deploy particle systems for sensing and extracting specific surface information and displaying this information in an visually effective manner. We also introduce a simple particle system "little language" to facilitate the articulation of these particle programs. We demonstrate the flexibility and power of this framework for surface visualization with the applications of singularity detection and display, non-photorealistic surface illustration, and surface mesh algorithm visualization.

No abstract available.

Surface painting is a technique that allows a user to paint a texture directly onto a surface, usually with a texture atlas: a 1:1 mapping between the surface and its texture image. Many good automatic texture atlas generation methods exist that evenly distribute texture samples across a surface based on its area and/or curvature, and some are even sensitive to the frequency spectrum of the input texture. However, during the surface painting process, the texture can change non-uniformly and unpredictably and even the atlases are static and can thus fail to reproduce sections of finely painted detail such as surface illustration.We present a new texture atlas algorithm that distributes initial texture samples evenly according to surface area and texture frequency, and, more importantly, maintains this distribution as the texture signal changes during the surface painting process. The running time is further accelerated with a novel GPU implementation of the surface painting process. The redistribution of samples is transparent to the user, resulting in a surface painting system of seemingly unlimited resolution. The atlas construction is local, making it fast enough to run interactively on models containing over 100K faces.

We combine existing techniques for shape-from-shading and texture synthesis to create a new tool for texturing objects in photographs. Our approach clusters pixels with similar recovered normals into patches on which texture is synthesized. Distorting the texture based on the recovered normals creates the illusion that the texture adheres to the undulations of the photographed surface. Inconsistencies in the recovered surface are disguised by the graphcut blending of the individually textured patches. Further applications include the generation of detail on manually-shaded painting, extracting and synthesizing a displacement map from a texture swatch, and the embossed transfer of normals from one image to another, which would be difficult to create with current image processing packages.

No abstract available.

Morse theory reveals the topological structure of a shape based on the critical points of a real function over the shape. A poor choice of this real function can lead to a complex configuration of an unnecessarily high number of critical points. This paper solves a relaxed form of Laplace's equation to find a "fair" Morse function with a user-controlled number and configuration of critical points. When the number is minimal, the resulting Morse complex cuts the shape into a disk. Specifying additional critical points at surface features yields a base domain that better represents the geometry and shares the same topology as the original mesh, and can also cluster a mesh into approximately developable patches. We make Morse theory on meshes more robust with teflon saddles and flat edge collapses, and devise a new "intermediate value propagation" multigrid solver for finding fair Morse functions that runs in provably linear time.

We present an algorithm to construct a tight bounding polyhedron for a recursive procedural model. We first use an iterated function system (IFS) to represent the extent of the procedural model. Then we present an algorithm that expresses the IFS-bounding problem as a set of linear convex optimization. As such, our algorithm is guaranteed to find the recursively optimal bounding polyhedron, if it exists. Finally, we demonstrate examples of this algorithm on two and three dimensional recursive procedural models.

No abstract available.

No abstract available.

We compress storage and accelerate performance of precomputed radiance transfer (PRT), which captures the way an object shadows, scatters, and reflects light. PRT records over many surface points a transfer matrix. At run-time, this matrix transforms a vector of spherical harmonic coefficients representing distant, low-frequency source lighting into exiting radiance. Per-point transfer matrices form a high-dimensional surface signal that we compress using clustered principal component analysis (CPCA), which partitions many samples into fewer clusters each approximating the signal as an affine subspace. CPCA thus reduces the high-dimensional transfer signal to a low-dimensional set of per-point weights on a per-cluster set of representative matrices. Rather than computing a weighted sum of representatives and applying this result to the lighting, we apply the representatives to the lighting per-cluster (on the CPU) and weight these results per-point (on the GPU). Since the output of the matrix is lower-dimensional than the matrix itself, this reduces computation. We also increase the accuracy of encoded radiance functions with a new least-squares optimal projection of spherical harmonics onto the hemisphere. We describe an implementation on graphics hardware that performs real-time rendering of glossy objects with dynamic self-shadowing and interreflection without fixing the view or light as in previous work. Our approach also allows significantly increased lighting frequency when rendering diffuse objects and includes subsurface scattering.

Complex virtual environments can be simulated with physical or procedural motion. Physical motion is more realistic, but requires the integration of an ordinary differential equation from an initial state. Procedural motion has the advantage of being randomly accessible, though it is not physically based. We combine these techniques into a multiresolution model. A coarse-level simulation is sampled to yield keyframes. Then a physical motion between keyframes is calculated and distorted to meet its boundary conditions. We demonstrate these ideas with a simple virtual world consisting of wind blowing trees and leaves that can be entered and experienced efficiently at any point in time.

In 1994, Witkin and Heckbert developed a method for interactively modeling implicit surfaces by simultaneously constraining a particle system to lie on an implicit surface and vice-versa. This interface was demonstrated to be effective and easy to use on example models containing a few blobby spheres and cylinders. This system becomes much more difficult to implement and operate on more complex implicit models. The derivatives needed for the particle system behavior can become laborious and error-prone when implemented for more complex models. We have developed, implemented and tested techniques for automatic and numerical differentiation of the implicit surface function. Complex models also require a large number of parameters, and the management and control of these parameters is often not intuitive. We have developed adapters, which are special shape-transformation operators that automatically adjust the underlying parameters to yield the same effect as the transformation. These new techniques allow constrained particle systems to sample and control more complex models than before possible.

Surface texturing aids the visualization of polygonal meshes by providing additional surface orientation cues and feature annotations. Such texturing is usually implemented via texture mapping, which is easier and more effective when the distortion of the mapping from the surface to the texture map is kept small. We have previously shown that distortion occurs when areas of high surface curvature are flattened into the texture map. By cutting the surface in these areas one can reduce texture map distortion at the expense of additional seam artifacts. This paper describes a faster technique for guiding a texture map seam through high distortion regions, while restricting the seam to regions of low visibility. This results in distortion reducing seams that are less visually distracting and take less time to compute. We have also observed that visibility considerations improve the speed of a recent method that adds cuts to reduce a surface genus.

We describe an implementation of procedural solid texturing that uses the texture atlas, a one-to-one mapping from an object's surface into its texture space. The method uses the graphics hardware to rasterize the solid texture coordinates as colors directly into the atlas. A texturing procedure is applied per-pixel to the texture map, replacing each solid texture coordinate with its corresponding procedural solid texture result. The procedural solid texture is then mapped back onto the object surface using standard texture mapping. The implementation renders procedural solid textures in real time, and the user can design them interactively.The quality of this technique depends greatly on the layout of the texture atlas. A broad survey of texture atlas schemes is used to develop a set of general purpose mesh atlases and tools for measuring their effectiveness at distributing as many available texture samples as evenly across the surface as possible. The main contribution of this paper is a new multiresolution texture atlas. It distributes all available texture samples in a nearly uniform distribution. This multiresolution texture atlas also supports MIP-mapped minification antialiasing and linear magnification filtering.

Expands the role of the new field of computational topology by surveying methods for incorporating connectedness in shape modeling. Two geometric representations in particular-recurrent models and implicit surfaces-can (often unpredictably) become connected or disconnected based on typical changes in modeling parameters. Two methodologies for controlling connectedness are identified: connectedness loci and Morse theory. The survey concludes by identifying several open problems remaining in shape modeling for computational topology to solve.

Summary form only given. We present comparative results obtained in the context of 24-bit true color image encoding by using searchless vs. search-based fractal compression techniques in a perceptually uniform color space. A pixel in the color space is represented as a vector with each component corresponding to a color channel. The least squares approximation of an image block by an iterated function system (IFS) is adapted to reflect the added color dimensions. To account for the nonlinearity of the human visual perception, compression in the L*a*b* uniform color space is proposed. In this color space, two pairs of colors with the same Euclidean distance metric are perceptually almost equally similar or different. Comparisons are presented both with regard to compression in the RGB and YIQ color spaces vs. the perceptually uniform L*a*b* color space, as well as with regard to fractal color image compression in the L*a*b* color space obtained by means of an extension of Monro and Dudbridge's bath fractal transform (BFT) vs. an adaptation of Jacquin's iterated transform technique (ITT) for 3-dimensional color. The use of a uniform color space produced rate-distortion results comparable with recently reported fractal compression results, but yielded compressed images with visibly less noticable color distortion than other methods.

Article Free Access Share on Guaranteeing the topology of an implicit surface polygonization for interactive modeling Authors: Barton T. Stander Strata, 1562 El Vista Circle, Saint George, UT and School of EECS, Washington State University, Pullman, WA Strata, 1562 El Vista Circle, Saint George, UT and School of EECS, Washington State University, Pullman, WAView Profile , John C. Hart School of EECS, Washington State University, Pullman, WA School of EECS, Washington State University, Pullman, WAView Profile Authors Info & Claims SIGGRAPH '97: Proceedings of the 24th annual conference on Computer graphics and interactive techniquesAugust 1997 Pages 279–286https://doi.org/10.1145/258734.258868Published:03 August 1997Publication History 96citation770DownloadsMetricsTotal Citations96Total Downloads770Last 12 Months23Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Implicit surface techniques provide useful tools for modeling and rendering smooth surfaces. Deriving implicit formulations for fractal representations extends the scope of implicit surface techniques to rough surfaces. Linear fractals modeled by recurrent iterated function systems may be defined implicitly using either geometric distance or escape time. Random fractals modeled using Perlin's noise function are already defined implicitly when described as “hypertexture.” Deriving new implicit formulae is only the first step. Unlike their smooth counterparts, rough implicit surfaces require special rendering techniques that do not rely on continuous differentiation of the defining function. Preliminary experiments applying blending operations to rough surfaces have succeeded in an initial attempt to overcome current challenges in natural modeling. The grafting of a stem onto the base of a linear fractal leaf continuously blends smooth detail into rough detail. The blend of two textured cylinders interpolates geometric bark across branching points in a tree.

This research explores the principles, implementation, and optimization of a competitive volume compression system based on fractal image compression. The extension of fractal image compression to volumetric data is trivial in theory. However, the simple addition of a dimension to existing fractal image compression algorithms results in infeasible compression times and noncompetitive volume compression results. This paper extends several fractal image compression enhancements to perform properly and efficiently on volumetric data, and introduces a new 3D edge classification scheme based on principal component analysis. Numerous experiments over the many parameters of fractal volume compression suggest aggressive settings of its system parameters. At this peak efficiency, fractal volume compression surpasses vector quantization and approaches within 1 dB PSNR of the discrete cosine transform. When compared to the DCT, fractal volume compression represents surfaces in volumes exceptionally well at high compression rates, and the artifacts of its compression error appear as noise instead of deceptive smoothing or distracting ringing.

Quaternions play a vital role in the representation of rotations in computer graphics, primarily for animation and user interfaces. Unfortunately, quaternion rotation is often left as an advanced topic in computer graphics education due to difficulties in portraying the four-dimensional space of the quaternions. One tool for overcoming these obstacles is the quaternion demonstrator, a physical visual aid consisting primarily of a belt. Every quaternion used to specify a rotation can be represented by fixing one end of the belt and rotating the other. Multiplication of quaternions is demonstrated by the composition of rotations, and the resulting twists in the belt depict visually how quaternions interpolate rotation. This article introduces to computer graphics the exponential notation that mathematicians have used to represent unit quaternions. Exponential notation combines the angle and axis of the rotation into concise quaternion expression. This notation allows the article to present more clearly a mechanical quaternion demonstrator consisting of a ribbon and a tag, and develop a computer simulation suitable for interactive educational packages. Local deformations and the belt trick are used to minimize the ribbon's twisting and simulate a natural-appearing interactive quaternion demonstrator.

Small data networks are usually easy to maintain. However, the cost of support for growing networks can start to increase exponentially. If allowed to continue, additional network expansion comes up against a limit known as the complexity barrier. It then becomes too costly to add new network capabilities. The article discusses how today's data networks can more adequately deal with complexity using existing technology, and how tomorrow's data networks will change using emerging technologies. Intended for networking professionals involved in the planning and implementation of current and future data networks, the article depicts a vision of how changes can simplify data networking across a variety of networking environments.>

Object instancing is the efficient method of representing an hierarchical object with a directed graph instead of a tree. If this graph contains a cycle then the object it represents is a linear fractal. Linear fractals are difficult to render for three specific reasons: (1) ray-fractal intersection is not trivial, (2) surface normals are undefined and (3) the object aliases at all sampling resolutions.Ray-fractal intersections are efficiently approximated to sub-pixel accuracy using procedural bounding volumes and a careful determination of the size of a pixel, giving the perception that the surface is infinitely detailed. Furthermore, a surface normal for these non-differentiable surfaces is defined and analyzed. Finally, the concept of antialiasing "covers" is adapted and used to solve the problem of sampling fractal surfaces.An initial bounding volume estimation method is also described, allowing a linear fractal to be rendered given only its iterated, function system. A parallel implementation of these methods is described and applications of these results to the rendering of other fractal models are given.

The first half of a two-step quaternion Julia set visualization system is described. This step uses a quarternion square root function to adapt the classic inverse iteration algorithm to the quaternions. The augmented version produces a 3-D Julia set defined by a point cloud that can be interactively manipulated on a graphics workstation. Several cues are assigned to the point cloud to increase depth perception. Finally, a short theorem is proven that extends the domain of the inverse iteration method to a rotational family of quadratic quaternion Julia sets.>

As shown in 1982, Julia sets of quadratic functions as well as many other deterministic fractals exist in spaces of higher dimensionality than the complex plane. Originally a boundary-tracking algorithm was used to view these structures but required a large amount of storage space to operate. By ray tracing these objects, the storage facilities of a graphics workstation frame buffer are sufficient. A short discussion of a specific set of 3-D deterministic fractals precedes a full description of a ray-tracing algorithm applied to these objects. A comparison with the boundary-tracking method and applications to other 3-D deterministic fractals are also included.