We present an automated method for modifying shapes to allow them to be produced by filament winding. The range of shapes where filament winding is applicable is limited due to the fact that the paths must follow (near-)geodesics on the surface without encountering concave regions. Our method allows us to take shapes with small protrusions or concavities that would prevent winding and modify them to similar shapes that are capable of being wound. We present a two-stage iterative approach for automatically making gradual modifications to a given shape to bring it into a reasonable condition, with the filament paths largely adhering to the surface and are roughly evenly covering the surface. In the push-out stage, we identify areas where filaments would be raised off of the surface during winding, developing a new approach for mapping between a raised filament and the surface it spans. In the pull-in stage, we identify regions where protrusions make it difficult to wind filaments over the surface. In both cases, we make local modifications to the surface (pulling in or pushing out the surface) to improve the likelihood of successfully winding in those areas, and generally make the arrangements of filaments more uniform. These stages are incorporated into an overall optimization process where repeated iterations are performed until winding is feasible everywhere. We present the results of this algorithm on several example shapes.

We introduce NeuBase , a neural parametric surface representation that both accurately fits target surfaces with fine geometric detail and supports intuitive real time surface deformation. NeuBase consists of a Catmull-Clark subdivision base surface and an offset field defined by a set of neural basis functions encoded via a neural map. By construction, NeuBase surfaces exhibit four fundamental geometric properties, i.e., linearity, locality, smoothness, and affine equivariance, enabling real-time, direct manipulation without retraining the neural network. In addition, we propose a scalable neural map that maintains memory efficiency even for complex shapes with dense control meshes. Experiments on a large-scale dataset demonstrate that our method achieves better fitting accuracy than state-of-the-art neural parametric surface representations.

Piecewise parametric surfaces have long been established as prevalent geometric representations; however, they often require surface refinement or sophisticated quadrangulation to accurately represent complex geometries. Geometric deep learning has shown that neural networks can provide greater representational power than conventional methods. Nevertheless, approaches using a single parametric surface for shape fitting struggle to capture fine-grained geometric details, while multi-patch methods fail to ensure seamless connections between adjacent patches. We present Neural Piecewise Parametric Surfaces ( NeuPPS ), the first piecewise neural surface representation that allows for coarse patch layouts composed of arbitrary n -sided surface patches to model complex surface geometries with high precision, offering enhanced flexibility compared with traditional parametric surfaces. This new surface representation guarantees, by construction, the continuity between adjacent patches, a property that other neural patch-based approaches cannot ensure. Two novel components are introduced: a learnable feature complex and a continuous mapping function approximated by multi-layer perceptrons (MLPs). We apply the proposed NeuPPS to surface fitting and shape space learning tasks. Extensive experiments demonstrate the advantages of NeuPPS over traditional parametric representations and existing patch-based learning approaches.

ABSTRACT We present a method for simulating granular materials faster within a position based dynamics framework. We do this by combining an adaptive particle sampling scheme with an upsampling approach. This allows for faster simulations in interactive applications, while maintaining visual resolution. Particles are merged or split based on their distance from the boundary, allowing for high details in areas of importance such as the surface and edges. Merging particles into a single particle reduces the number of particles for which collisions have to be simulated, thus reducing the overall simulation time. The adaptive sampling technique is then combined with an upsampling scheme that gives the coarser particle simulation the appearance of much finer resolution.

Neural implicit representations are increasingly used to depict three-dimensional (3D) shapes owing to their inherent smoothness and compactness, contrasting with traditional discrete representations. Yet, the multilayer perceptron–based neural representation, because of its smooth nature, rounds sharp corners or edges, rendering it unsuitable for representing objects with sharp features like computer-aided design (CAD) models. Moreover, neural implicit representations need long training times to fit 3D shapes. While previous works address these issues separately, we present a unified neural implicit representation called Patch-Grid , which efficiently fits complex shapes, preserves sharp features delineating different patches, and can also represent surfaces with open boundaries and thin geometric features. Patch-Grid learns a signed distance field (SDF) to approximate an encompassing surface patch of the shape with a learnable patch feature volume. To form sharp edges and corners in a CAD model, Patch-Grid merges the learned SDFs via the constructive solid geometry (CSG) approach. Core to the merging process is a novel merge grid design that organizes different patch feature volumes in a common octree structure. This design choice ensures robust merging of multiple learned SDFs by confining the CSG operations to localized regions. Additionally, it drastically reduces the complexity of the CSG operations in each merging cell, allowing the proposed method to be trained in seconds to fit a complex shape at high fidelity. Experimental results demonstrate that the proposed Patch-Grid representation is capable of accurately reconstructing shapes with complex sharp features, open boundaries, and thin geometric elements, achieving state-of-the-art reconstruction quality with high computational efficiency within seconds.

Neural implicit fields, such as the neural signed distance field (SDF) of a shape, have emerged as a powerful representation for many applications, e.g., encoding a 3D shape and performing collision detection. Typically, implicit fields are encoded by Multi-layer Perceptrons (MLP) with positional encoding (PE) to capture high-frequency geometric details. However, a notable side effect of such PE-equipped MLPs is the noisy artifacts present in the learned implicit fields. While increasing the sampling rate could in general mitigate these artifacts, in this paper we aim to explain this adverse phenomenon through the lens of Fourier analysis. We devise a tool to determine the appropriate sampling rate for learning an accurate neural implicit field without undesirable side effects. Specifically, we propose a simple yet effective method to estimate the intrinsic frequency of a given network with randomized weights based on the Fourier analysis of the network's responses. It is observed that a PE-equipped MLP has an intrinsic frequency much higher than the highest frequency component in the PE layer. Sampling against this intrinsic frequency following the Nyquist-Sannon sampling theorem allows us to determine an appropriate training sampling rate. We empirically show in the setting of SDF fitting that this recommended sampling rate is sufficient to secure accurate fitting results, while further increasing the sampling rate would not further noticeably reduce the fitting error. Training PE-equipped MLPs simply with our sampling strategy leads to performances superior to the existing methods.

We propose a method, named DualMesh-UDF, to extract a surface from unsigned distance functions (UDFs), encoded by neural networks, or neural UDFs. Neural UDFs are becoming increasingly popular for surface representation because of their versatility in presenting surfaces with arbitrary topologies, as opposed to the signed distance function that is limited to representing a closed surface. However, the applications of neural UDFs are hindered by the notorious difficulty in extracting the target surfaces they represent. Recent methods for surface extraction from a neural UDF suffer from significant geometric errors or topological artifacts due to two main difficulties: (1) A UDF does not exhibit sign changes; and (2) A neural UDF typically has substantial approximation errors.DualMesh-UDF addresses these two difficulties. Specifically, given a neural UDF encoding a target surface $\bar S$ to be recovered, we first estimate the tangent planes of $\bar S$ at a set of sample points close to $\bar S$. Next, we organize these sample points into local clusters, and for each local cluster, solve a linear least squares problem to determine a final surface point. These surface points are then connected to create the output mesh surface, which approximates the target surface. The robust estimation of the tangent planes of the target surface and the subsequent minimization problem constitute our core strategy, which contributes to the favorable performance of DualMesh-UDF over other competing methods. To efficiently implement this strategy, we employ an adaptive Octree. Within this framework, we estimate the location of a surface point in each of the octree cells identified as containing part of the target surface. Extensive experiments show that our method outperforms existing methods in terms of surface reconstruction quality while maintaining comparable computational efficiency.

Multiscale design is the widely practiced use of space and scale to visually explore and articulate relationships. Free-form web curation (FFWC) is an approach to supporting multiscale design, involving creative strategies of collecting content, assembling it to juxtapose and organize, sketching, writing, shifting perspective to navigate, and exhibiting to share and collaborate. Our long term goal is to support design students with automatic, on demand feedback.

Abstract We quantitatively measure how different low‐level visual details can influence people's perceived stiffness of a deformable sphere under physically based simulation. The result can be used to create a metric for artists in designing textures to enhance or reduce the stiffness perceived by a viewer. We use a checkerboard texture to render the simulation of a free falling sphere that collides with the ground and bounces up. We vary the spatial frequency and contrast of the checkerboard pattern according to results seen in a previous study on the Spatial‐Temporal Contrast Sensitivity Function (CSF). We find that checkerboard pattern with certain combinations of spatial frequency and contrast can reduce the perceived stiffness. We also add a high contrast checkerboard background to study how complex backgrounds can influence the effect of low‐level details in textures of foreground objects. Our study shows that the effect of low‐level visual details in foreground objects observed previously disappears in this situation. This indicates the importance of background, even if it is static.

The papers in this special issue include four extended papers from the 2015 ACM Symposium on Interactive 3D Graphics and Games. This edition marked the 29th year since the first conference.

Rapid advances in high-resolution, high-throughput 3D microscopy techniques in the past decade have opened up new avenues for brain research. One such technique developed in our lab is called the Knife-Edge Scanning Microscopy (KESM). The basic principle of KESM is to line-scan image while simultaneously sectioning thin tissue blocks using a diamond microtome. We have successfully sectioned and imaged whole mouse brains and portions of a rat brain processed with different stains to investigate the microstructures within. In this paper, we will present a fully automated soma (cell body) detection method based on random forests, working on Nissl-stained rat brain specimen. The method enables fast and accurate cell counting and density measurement in different brain regions.

3D modeling systems form the basis for many of the most widely used graphics applications. Although interfaces have long provided the ability to paint directly on a 3D model, the colors are usually stored in a 2D domain, such as in a texture map. Despite its widespread use and several advantages, texture mapping has several shortcomings in the context of 3D painting. 3D painting usually requires only a local surface parameterization, while many parameterization methods are global and cannot be applied directly for 3D paints. The computing cost can be too high for realtime parameterization and obvious texture distortions can arise. One of the key works to address these shortcomings is by Schmidt et al. [Schmidt et al. 2006] on decal compositing, who provided an efficient local parameterization for 3D painting. They try to minimize the distortion of textures by approximating the exponential map. However, their work still has many limitations on 3D paintings. Their local parameterization method relies on the topology of the local mesh structure, which implies that this method is not stable on different mesh topologies that represent the same geometric shape. Experimental examples showed particular problems when models include large numbers of sliver triangles. Due to the sensitivity to the mesh topology, there is not an error bound between their approximation and the exponential mapping. While their method works well in many standard situations, the limitations can cause significant texture distortion in other cases.

We verify two hypotheses which are assumed to be true only intuitively in many rigid body simulations. I: In large scale rigid body simulation, viewers may not be able to perceive distortion incurred by an approximated simulation method. II: Fixing objects under a pile of objects does not affect the visual plausibility. Visual plausibility of scenarios simulated with these hypotheses assumed true are measured using subjective rating from viewers. As expected, analysis of results supports the truthfulness of the hypotheses under certain simulation environments. However, our analysis discovered four factors which may affect the authenticity of these hypotheses: number of collisions simulated simultaneously, homogeneity of colliding object pairs, distance from scene under simulation to camera position, and simulation method used.

Physically simulating non-rigid virtual objects which can deform or break apart within their environments is now common in state-of-the-art virtual simulations such as video games or surgery simulations. Real-time performance requires a physical model which provides an approximation to the true solution for fast computations but at the same time conveys enough believability of the simulation to the user. By embedding a complex surface mesh within simpler physical geometry, the mesh complexity can be separated from the algorithmic complexity of the physical simulation. Embedding methods have been successful in production quality products (e.g. [Parker and O'Brien 2009]). In the presence of fracture it is still unclear how to derive the graphical representation of a solid object defined only as a surface mesh with no volume information.

We present a simulation control to support art-directable stacking designs by automatically adding constraints to stabilize the stacking structure. We begin by adapting equilibrium analysis in a local scheme to find "stable" objects of the stacking structure. Next, for stabilizing the structure, we pick suitable objects from those passing the equilibrium analysis and then restrict their DOFs by managing the insertion of constraints on them. The method is suitable for controlling stacking behavior of large scale. Results show that our control method can be used in varied ways for creating plausible animation. In addition, the method can be easily implemented as a plug-in into existing simulation solvers without changing the fundamental operations of the solvers.

We present an inference-based surface reconstruction algorithm that is capable of identifying objects of interest among a cluttered scene, and reconstructing solid model representations even in the presence of occluded surfaces. Our proposed approach incorporates a predictive modeling framework that uses a set of user-provided models for prior knowledge, and applies this knowledge to the iterative identification and construction process. Our approach uses a local to global construction process guided by rules for fitting high-quality surface patches obtained from these prior models. We demonstrate the application of this algorithm on several example data sets containing heavy clutter and occlusion.

In this paper, we will review a novel microscopy modality called Knife-Edge Scanning Microscopy (KESM) that we have developed over the past twelve years (since 1999) and discuss its relevance to connectomics and neural networks research. The operational principle of KESM is to simultaneously section and image small animal brains embedded in hard polymer resin so that a near-isotropic, sub-micrometer voxel size of 0.6 μm × 0.7 μm × 1.0 μm can be achieved over ~1 cm3volume of tissue which is enough to hold an entire mouse brain. At this resolution, morphological details such as dendrites, dendritic spines, and axons are visible (for sparse stains like Golgi). KESM has been successfully used to scan whole mouse brains stained in Golgi (neuronal morphology), Nissl (somata), and India ink (vasculature), providing unprecedented insights into the system-level architectural layout of microstructures within the mouse brain. In this paper, we will present whole-brain-scale data sets from KESM and discuss challenges and opportunities posed to connectomics and neural networks research by such detailed yet system-level data.

THE 2009 SIAM/ACM Joint Conference on Geometric Design and Solid and Physical Modeling (GDSPM), which was a federation of the 2009 SIAM Conference on Geometric Design and the 2009 ACM Symposium on Solid and Physical Modeling, was held in San Francisco, CA, from 5 October to 8 October 2009. The goal of the conference was to present theoretically well-founded new methods for geometric and physical modeling that have useful practical applications. In response to the call for papers of the conference, 85 papers were submitted on many aspects of geometric and physical modeling, and their application in design, analysis, manufacturing, biomedicine, digital entertainment, and other areas. All papers were assessed by five reviewers, usually a member from the international program committee. A total of 24 papers were selected for plenary presentation and publication as full papers, and an additional 18 papers for poster presentation and publication as short papers. All papers appeared in the proceedings of the conference, published by ACM. From the full papers, we selected the four papers here for extended publication in this special section. The papers were chosen on the basis of their high quality and their suitability for the readership of IEEE Transactions on Visualization and Computer Graphics (TVCG). All the papers were revised and expanded from the version that appeared in the conference proceedings, and all papers went through further review and revision. We are very pleased with the quality of the resulting papers, and we believe they will be of interest to a wide audience. “Model Synthesis: A General Procedural Modeling Algorithm,” by Paul Merrell and Dinesh Manocha, presents a method for automatically generating geometric models that resemble those provided by an input example. The method examines input models to determine a variety of geometric constraints (such as connectivity and spacing between various features) that help describe the given shape. These constraints are then used in a procedural method to generate new models that follow the same constraints. As a result, a wide variety of new models that resemble the input model can be created very easily, which should be beneficial for numerous graphics applications that require extensive geometry creation with limited user input. “GPU-Accelerated Minimum Distance and Clearance Queries,” by Adarsh Krishnamurthy, Sara McMains, and Kirk Haller, presents a number of fundamental algorithms for computing distance queries for NURBS surfaces. Bounded distance measures are computed for axis-aligned bounding boxes rapidly using the GPU. This allows one to quickly compute the nearest point on a NURBS surface, given a point in space, or to compute clearance between two NURBS models. The paper provides a significant performance increase for fundamental geometric queries that form the basis for several operations in CAD and other applications. “Voronoi-Based Curvature and Feature Estimation from Point Clouds,” by Quentin Merigot, Maks Ovsjanikov, and Leonidas Guibas, an extension of the best paper award winner at the conference, presents a method for estimating certain surface properties directly from point cloud data. In particular, normals, principal curvatures, and sharp features can be computed on point clouds. Perhaps more importantly, theoretical guarantees on many of the computations are provided, including robustness to noise in the point sampling. This paper provides a significant advance in making use of point cloud data sets. “Ball-Morph: Definition, Implementation, and Comparative Evaluation,” by Brian Whited and Jaroslaw (Jarek) Rossignac, describes three methods in detail for computing morphs between pairs of certain planar curves. These methods are compared to several standard morphing methods, and it is shown that the proposed morphs consistently provide better performance on particular metrics. This paper offers a significant improvement to 2D morphing, and should be of particular interest in animation applications. We believe that these four papers are strong representatives of the papers presented at the conference, and hope that you will enjoy reading them. We thank all the authors of the papers and the reviewers for their work in ensuring the high quality of these final papers, along with Dr. Tom Ertl and the TVCG staff for their help in seeing this special section published.

We present a method for directly modeling piles of objects in multi-body simulations. Piles of objects represent some of the more interesting, but also most time-consuming portion of simulation. We propose a method for reducing computation in many of these situations by explicitly modeling the piles that the objects may form into. By modeling pile behavior rather than the behavior of all individual objects, we can achieve realistic results in less time, and without directly modeling the frictional component that leads to desired pile shapes. Our method is simple to implement and can be easily integrated with existing rigid body simulations. We observe notable speedups in several rigid body examples, and generate a wider variety of piled structures than possible with strict impulse-based simulation.

The coloring of 3D models using 2D or 3D texture mapping has well-known intrinsic problems, such as mapping discontinuities and limitations to model editing after coloring. Workarounds for these problems often require adopting very complex approaches. Here we propose a new technique, called mesh colors, for associating color data directly with a polygonal mesh. The approach eliminates problems deriving from using a map from texture space to model space. Mesh colors is an extension of vertex colors where, in addition to keeping color values on each vertex, they are also kept on edges and faces. Like texture mapping, the approach allows higher texture resolution than model resolution, but at the same time it guarantees one-to-one correspondence between the model surface and the color data, and eliminates discontinuities. We show that mesh colors integrate well with the current graphics pipeline and can be used to generate very high-quality textures.

The behavior of Catmull-Rom curves heavily depends on the choice of parameter values at the control points. We analyze a class of parameterizations ranging from uniform to chordal parameterization and show that, within this class, curves with centripetal parameterization contain properties that no other curves in this family possess. Researchers have previously indicated that centripetal parameterization produces visually favorable curves compared to uniform and chordal parameterizations. However, the mathematical reasons behind this behavior have been ambiguous. In this paper we prove that, for cubic Catmull-Rom curves, centripetal parameterization is the only parameterization in this family that guarantees that the curves do not form cusps or self-intersections within curve segments. Furthermore, we provide a formulation that bounds the distance of the curve to the control polygon and explain how globally intersection-free Catmull-Rom curves can be generated using these properties.

Despite the visual importance of hair and the attention paid to hair modeling in the graphics research, modeling realistic hair still remains a very challenging task that can be performed by very few artists. In this paper we present hair meshes , a new method for modeling hair that aims to bring hair modeling as close as possible to modeling polygonal surfaces. This new approach provides artists with direct control of the overall shape of the hair, giving them the ability to model the exact hair shape they desire. We use the hair mesh structure for modeling the hair volume with topological constraints that allow us to automatically and uniquely trace the path of individual hair strands through this volume. We also define a set of topological operations for creating hair meshes that maintain these constraints. Furthermore, we provide a method for hiding the volumetric structure of the hair mesh from the end user, thus allowing artists to concentrate on manipulating the outer surface of the hair as a polygonal surface. We explain and show examples of how hair meshes can be used to generate individual hair strands for a wide variety of realistic hair styles.

We present a framework for segmenting and storing filament networks from scalar volume data. Filament networks are encountered more and more commonly in biomedical imaging due to advances in high-throughput microscopy. These data sets are characterized by a complex volumetric network of thin filaments embedded in a scalar volume field. High-throughput microscopy volumes are also difficult to manage since they can require several terabytes of storage, even though the total volume of the embedded structure is much smaller. Filaments in microscopy data sets are difficult to segment because their diameter is often near the sampling resolution of the microscope, yet these networks can span large regions of the data set. We describe a novel method to trace filaments through scalar volume data sets that is robust to both noisy and undersampled data. We use graphics hardware to accelerate the tracing algorithm, making it more useful for large data sets. After the initial network is traced, we use an efficient encoding scheme to store volumetric data pertaining to the network.

Figure 1: Traced and segmented microvasculature of the mouse spinal cord. The entire network has been traced and displayed (orange) as well as several sub-networks (green and purple) represented as cliques within the network. We present a framework for segmenting and storing filament net-works from scalar volume data. Filament structures are commonly found in data generated using high-throughput microscopy. These data sets can be several gigabytes in size because they are either spa-tially large or have a high number of scalar channels. Filaments in microscopy data sets are difficult to segment because their diameter is often near the sampling resolution of the microscope, yet single filaments can span large data sets. We describe a novel method to trace filaments through scalar volume data sets that is robust to both noisy and under-sampled data. We use a GPU-based scheme to ac-celerate the tracing algorithm, making it more useful for large data sets. After the initial structure is traced, we can use this informa-tion to create a bounding volume around the network and encode the volumetric data associated with it. Taken together, this frame-work provides a convenient method for accessing network structure and connectivity while providing compressed access to the original volumetric data associated with the network.

Abstract We present a new method for rapidly computing shadows from semi‐transparent objects like hair. Our deep opacity maps method extends the concept of opacity shadow maps by using a depth map to obtain a per pixel distribution of opacity layers. This approach eliminates the layering artifacts of opacity shadow maps and requires far fewer layers to achieve high quality shadow computation. Furthermore, it is faster than the density clustering technique, and produces less noise with comparable shadow quality. We provide qualitative comparisons to these previous methods and give performance results. Our algorithm is easy to implement, faster, and more memory efficient, enabling us to generate high quality hair shadows in real‐time using graphics hardware on a standard PC.

When rendering light colored hair, multiple fiber scattering is essential for the right perception of the overall hair color. In this context, we present a novel technique to efficiently approximate multiple fiber scattering for a full head of human hair or a similar fiber based geometry. In contrast to previous ad-hoc approaches, our method relies on the physically accurate concept of the Bidirectional Scattering Distribution Functions and gives physically plausible results with no need for parameter tweaking. We show that complex scattering effects can be approximated very well by using aggressive simplifications based on this theoretical model. When compared to unbiased Monte-Carlo path tracing, our approximations preserve photo-realism in most settings but with rendering times at least two-orders of magnitude lower. Time and space complexity are much lower compared to photon mapping-based techniques and we can even achieve realistic results in real-time on a standard PC with consumer graphics hardware.

Understanding the structure of microvasculature structures and their relationship to cells in biological tissue is an important and complex problem. Brain microvasculature in particular is known to play an important role in chronic diseases. However, these networks are only visible at the microscopic level and can span large volumes of tissue. Due to recent advances in microscopy, large volumes of data can be imaged at the resolution necessary to reconstruct these structures. Due to the dense and complex nature of microscopy data sets, it is important to limit the amount of information displayed. In this paper, we describe methods for encoding the unique structure of microvascular data, allowing researchers to selectively explore microvascular anatomy. We also identify the queries most useful to researchers studying microvascular and cellular relationships. By associating cellular structures with our microvascular framework, we allow researchers to explore interesting anatomical relationships in dense and complex data sets.

Both hair rendering and global illumination are known to be computationally expensive, and for this reason we see very few examples using global illumination techniques in hair rendering. In this paper, we elaborate on different simplification approaches to allow practical global illumination solutions for high quality hair rendering. We categorize light paths of a full global illumination solution, and analyze their costs and illumination contributions both theoretically and experimentally. We also propose two different implementation techniques using our novel projection based indirect illumination computation approach and state of the art ray tracing for hair. Our results show that by using our simplifications, a global illumination solution for hair is practical.

In this paper we present a method for deforming objects for graphics applications, based on the results of internal physical simulations. As driving examples, we describe in detail methods for simulating the bending of burning matches, and the crumpling of burning paper. In these cases, the small-scale changes in a chemical process result in large-scale deformations of the given object. We propose the use of a free form deformation to model such largescale deformations. Changing object properties are mapped onto the edges of a proxy object, which is then modified by treating the edges as springs. This proxy object then serves as a control structure for defining the deformation of the underlying object. The results we present are fast, controllable, and visually plausible.

We present a new method for the real-time simulation of fluid surface waves and their interactions with floating objects. The method is based on the new concept of wave particles, which offers a simple, fast, and unconditionally stable approach to wave simulation. We show how graphics hardware can be used to convert wave particles to a height field surface, which is warped horizontally to account for local wave-induced flow. The method is appropriate for most fluid simulation situations that do not involve significant global flow. It is demonstrated to work well in constrained areas, including wave reflections off of boundaries, and in unconstrained areas, such as an ocean surface. Interactions with floating objects are easily integrated by including wave forces on the objects and wave generation due to object motion. Theoretical foundations and implementation details are provided, and experiments demonstrate that we achieve plausible realism. Timing studies show that the method is scalable to allow simulation of wave interaction with several hundreds of objects at real-time rates.

Shape decomposition and skeletonization share many common properties and applications. However, they are generally treated as independent computations. In this paper, we propose an iterative approach that simultaneously generates a hierarchical shape decomposition and a corresponding set of multi-resolution skeletons. In our method, a skeleton of a model is extracted from the components of its decomposition --- that is, both processes and the qualities of their results are interdependent. In particular, if the quality of the extracted skeleton does not meet some user specified criteria, then the model is decomposed into finer components and a new skeleton is extracted from these components. The process of simultaneous shape decomposition and skeletonization iterates until the quality of the skeleton becomes satisfactory. We provide evidence that the proposed framework is efficient and robust under perturbation and. deformation. We also demonstrate that our results can readily be used in problems including skeletal deformations and virtual reality navigation.

Thread-like structures are becoming more common in modern volumetric data sets as our ability to image vascular and neural tissue at higher resolutions improves. The thread-like structures of neurons and micro-vessels pose a unique problem in visualization since they tend to be densely packed in small volumes of tissue. This makes it difficult for an observer to interpret useful patterns from the data or trace individual fibers. In this paper we describe several methods for dealing with large amounts of thread-like data, such as data sets collected using Knife-Edge Scanning Microscopy (KESM) and Serial Block-Face Scanning Electron Microscopy (SBF-SEM). These methods allow us to collect volumetric data from embedded samples of whole-brain tissue. The neuronal and microvascular data that we acquire consists of thin, branching structures extending over very large regions. Traditional visualization schemes are not sufficient to make sense of the large, dense, complex structures encountered. In this paper, we address three methods to allow a user to explore a fiber network effectively. We describe interactive techniques for rendering large sets of neurons using self-orienting surfaces implemented on the GPU. We also present techniques for rendering fiber networks in a way that provides useful information about flow and orientation. Third, a global illumination framework is used to create high-quality visualizations that emphasize the underlying fiber structure. Implementation details, performance, and advantages and disadvantages of each approach are discussed.

Motion blur is one important method for increasing the visual quality of real-time applications. This is increasingly true in the area of interactive applications, where designers often seek to add graphical flair or realism to their programs. These applications often have animated characters with a polygonal mesh wrapped around an animated skeleton; and as the skeleton moves the mesh deforms with it. This thesis presents a method for adding a geometric motion blur to a deforming polygonal mesh. The scheme presented tracks an object's motion silhouette, and uses this to create a polygonal mesh. When this mesh is added to the scene, it gives the appearance of a motion blur on a single object or particular character. The method is generic enough to work on nearly any type of moving polygonal model. Examples are given that show how the method could be expanded and how changes could be made to improve its performance.

Motion blur is an important method for increasing the visual quality of real-time applications. This is especially true in the area of interactive applications, where designers often seek to add graphical flair to their programs. In many cases, these applications use animated characters, where a polygonal mesh is wrapped around an animated skeleton. As the skeleton moves, the mesh deforms. In this paper, we present a method for adding a geometric motion blur to a deforming polygonal mesh. The scheme we present keeps track of a character's motion silhouette, and uses this to create a polygonal mesh. When this mesh is inserted into the scene, it gives the appearance of an artistic motion blur for an object or particular character. This method is generic enough to work on nearly any type of moving polygonal model, and also approximates swept volumes.

We propose a method for applying genetic algorithms to create 3D terrain data sets. Existing procedural algorithms for generation of terrain have several shortcomings. The most popular approach, fractal-based terrain generation, is efficient, but is difficult for a user to control. Other methods tend to require too much user input. In this paper, we provide an alternative method of terrain generation that uses a two-pass genetic algorithm approach to produce a variety of terrain types using only intuitive user inputs. We allow a user to specify a rough sketch of terrain region boundaries, and we refine these boundaries using a genetic algorithm. We then couple this with a database of given terrain data to generate an artificial terrain, which we optimize using a second genetic algorithm.

For simulations involving complex objects, a number of different properties must be represented. An example of this is in modeling an object undergoing combustion---heat amounts, fuel consumption, and even object shape must be modeled and changed over time. Ideally we would put everything into a unified representation, but this is sometimes not possible/feasible due to measurement limitations or the suitability of a specific representation. In this paper we define a multi-representation framework for dealing with multiple properties and their interactions within an object. This model is especially useful in physically based modeling, where the time variation of some properties affect other properties including geometry or topology. As a motivating example case, we present a method for modeling decomposition of a burning object.

We describe a method for processing large amounts of volumetric data collected from a Knife Edge Scanning Microscope (KESM). The neuronal data that we acquire consists of thin, branching structures extending over very large regions that prior volumetric representations have difficulty dealing with efficiently. Since the full volume data set can be extremely large, on-the-fly processing of the data is necessary.

We present a simple yet effective method for modeling of object decomposition under combustion. A separate simulation models the flame production and generates heat from a combustion process, which is used to trigger pyrolysis of the solid object. The decomposition is modeled using level set methods, and can handle complex topological changes. Even with a very simple flame model on a coarse grid, we can achieve a plausible decomposition of the burning object.

In this paper, we describe a fast and interactive method for simulating and controlling the combustion process together with the decomposition of burning solids. The combustion and decomposition processes are integrated to create a physically-based model that runs at interactive rates.

In this paper we describe a fast and interactive model to simulate and control the fire phenomenon. We use a modified interactive fluid dynamics solver to describe the motion of a 3-gas system. We simulate the motion of oxidizing air, fuel gases, and exhaust gases. The burning process is simulated by consuming fuel and air based on the amounts of fuel and air inside each grid cell. By modeling heat distribution, we also simulate the spread of fire to and self-ignition in other combustible solids.

Artificial clouds play an important role in the computer generation of natural outdoor scenes. Realistic modeling and rendering of such scenes is important for applications in games, military training simulations, flight simulations, and even in the creation of digital artistic media. We propose a model for simulating cloud formation based on an efficient computational fluid solver We combine the fluid solver with a model of the natural processes of cloud formation, including buoyancy, relative humidity, and condensation. This allows us to simulate the formation and growth of clouds at interactive rates.

Many geometric problems like generalized Voronoi diagrams, medial axis computations and boundary evaluation involve computation and manipulation of non-linear algebraic primitives like curves and surfaces. The algorithms designed for these problems make decisions based on signs of geometric predicates or on the roots of polynomials characterizing the problem. The reliability of the algorithm depends on the accurate evaluation of these signs and roots. In this paper, we present a {\em naive precision-driven computational model} to perform these computations reliably and demonstrate its effectiveness on a certain class of problems like sign of determinants with rational entries, boundary evaluation and curve arrangements. We also present a novel algorithm to compute all the roots of a univariate polynomial to any desired accuracy. The computational model along with the underlying number representation, precision-driven arithmetic and all the algorithms are implemented as part of a stand-alone software library, PRECISE.

No abstract available.

We present techniques for fast motion planning by using discrete approximations of generalized Voronoi diagrams, computed with graphics hardware. Approaches based on this diagram computation are applicable to both static and dynamic environments of fairly high complexity. We compute a discrete Voronoi diagram by rendering a 3D distance mesh for each Voronoi site. The sites can be points, line segments, polygons, polyhedra, curves and surfaces. The computation of the generalized Voronoi diagram provides fast proximity query toolkits for motion planning. The tools provide the distance to the nearest obstacle stored in the Z-buffer, as well as the Voronoi boundaries, Voronoi vertices and weighted Voronoi graphs extracted from the frame buffer using continuation methods. We have implemented these algorithms and demonstrated their performance for path planning in a complex dynamic environment composed of more than 140,000 polygons.

We present MAPC, a library for exact representation of geometric objects-specifically points and algebraic curves in the plane.Our library makes use of several new algorithms, which we present here, including methods for fmding the sign of a determinant, fmding intersections between two curves, and breaking a curve into monotonic segments.These algorithms are used to speed up the underlying computations.The library provides C++ classes that can be used to easily instantiate, manipulate, and perform queries on points and curves in the plane.The point classes can be used to represent points known in a variety of.ways (e.g. as exact rational coordinates or algebraic numbers) in a unified manner.The curve class can be used to represent a portion of an algebraic curve.We have used MAPC for applications dealing with algebraic points and curves, including sorting points along a curve, computing arrangement of curves, medial axis computations, and boundary' evaluation on curved primitives.As compared to earlier algorithms and implementations utilizing exact arithmetic, our library is able to achieve more than an order of magnitude improvement in performance.

Article Fast computation of generalized Voronoi diagrams using graphics hardware Share on Authors: Kenneth E. Hoff University of North Carolina at Chapel Hill, Department of Computer Science University of North Carolina at Chapel Hill, Department of Computer ScienceView Profile , John Keyser University of North Carolina at Chapel Hill, Department of Computer Science University of North Carolina at Chapel Hill, Department of Computer ScienceView Profile , Ming Lin University of North Carolina at Chapel Hill, Department of Computer Science University of North Carolina at Chapel Hill, Department of Computer ScienceView Profile , Dinesh Manocha University of North Carolina at Chapel Hill, Department of Computer Science University of North Carolina at Chapel Hill, Department of Computer ScienceView Profile , Tim Culver University of North Carolina at Chapel Hill, Department of Computer Science University of North Carolina at Chapel Hill, Department of Computer ScienceView Profile Authors Info & Claims SIGGRAPH '99: Proceedings of the 26th annual conference on Computer graphics and interactive techniquesJuly 1999 Pages 277–286https://doi.org/10.1145/311535.311567Published:01 July 1999 311citation3,192DownloadsMetricsTotal Citations311Total Downloads3,192Last 12 Months86Last 6 weeks4 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 SiteGet Access