Reinforcement learning (RL) in continuous state-action spaces remains challenging in scientific computing due to poor sample efficiency and lack of pathwise physical consistency. We introduce Differential Reinforcement Learning (Differential RL), a novel framework that reformulates RL from a continuous-time control perspective via a differential dual formulation. This induces a Hamiltonian structure that embeds physics priors and ensures consistent trajectories without requiring explicit constraints. To implement Differential RL, we develop Differential Policy Optimization (dfPO), a pointwise, stage-wise algorithm that refines local movement operators along the trajectory for improved sample efficiency and dynamic alignment. We establish pointwise convergence guarantees, a property not available in standard RL, and derive a competitive theoretical regret bound of $\mathcal{O}(K^{5/6})$. Empirically, dfPO outperforms standard RL baselines on representative scientific computing tasks, including surface modeling, grid control, and molecular dynamics, under low-data and physics-constrained conditions.

We present DeblurSR, a novel motion deblurring approach that converts a blurry image into a sharp video. DeblurSR utilizes event data to compensate for motion ambiguities and exploits the spiking representation to parameterize the sharp output video as a mapping from time to intensity. Our key contribution, the Spiking Representation (SR), is inspired by the neuromorphic principles determining how biological neurons communicate with each other in living organisms. We discuss why the spikes can represent sharp edges and how the spiking parameters are interpreted from the neuromorphic perspective. DeblurSR has higher output quality and requires fewer computing resources than state-of-the-art event-based motion deblurring methods. We additionally show that our approach easily extends to video super-resolution when combined with recent advances in implicit neural representation.

Data tensors of orders 2 and greater are now routinely being generated. These data collections are increasingly huge and growing. Many scientific and medical data tensors are tensor fields (e.g., images, videos, geographic data) in which the spatial neighborhood contains important information. Directly accessing such large data tensor collections for information has become increasingly prohibitive. We learn approximate full-rank and compact tensor sketches with decompositive representations providing compact space, time and spectral embeddings of tensor fields. All information querying and post-processing on the original tensor field can now be achieved more efficiently and with customizable accuracy as they are performed on these compact factored sketches in latent generative space. We produce optimal rank-r sketchy Tucker decomposition of arbitrary order data tensors by building compact factor matrices from a sample-efficient sub-sampling of tensor slices. Our sample efficient policy is learned via an adaptable stochastic Thompson sampling using Dirichlet distributions with conjugate priors.

This paper introduces GenCorres, a novel unsupervised joint shape matching (JSM) approach. Our key idea is to learn a mesh generator to fit an unorganized deformable shape collection while constraining deformations between adjacent synthetic shapes to preserve geometric structures such as local rigidity and local conformality. GenCorres presents three appealing advantages over existing JSM techniques. First, GenCorres performs JSM among a synthetic shape collection whose size is much bigger than the input shapes and fully leverages the datadriven power of JSM. Second, GenCorres unifies consistent shape matching and pairwise matching (i.e., by enforcing deformation priors between adjacent synthetic shapes). Third, the generator provides a concise encoding of consistent shape correspondences. However, learning a mesh generator from an unorganized shape collection is challenging, requiring a good initialization. GenCorres addresses this issue by learning an implicit generator from the input shapes, which provides intermediate shapes between two arbitrary shapes. We introduce a novel approach for computing correspondences between adjacent implicit surfaces, which we use to regularize the implicit generator. Synthetic shapes of the implicit generator then guide initial fittings (i.e., via template-based deformation) for learning the mesh generator. Experimental results show that GenCorres considerably outperforms state-of-the-art JSM techniques. The synthetic shapes of GenCorres also achieve salient performance gains against state-of-the-art deformable shape generators.

A camera begins to sense light the moment we press the shutter button. During the exposure interval, relative motion between the scene and the camera causes motion blur, a common undesirable visual artifact. This paper presents E-CIR, which converts a blurry image into a sharp video represented as a parametric function from time to intensity. E-CIR leverages events as an auxiliary input. We discuss how to exploit the temporal event structure to construct the parametric bases. We demonstrate how to train a deep learning model to predict the function coefficients. To improve the appearance consistency, we further introduce a refinement module to propagate visual features among consecutive frames. Compared to state-of-the-art event-enhanced de-blurring approaches, E-CIR generates smoother and more realistic results. The implementation of E-CIR is available at https://github.com/chensong1995/E-CIR.

Hyperspectral images provide a rich representation of the underlying spectrum for each pixel, allowing for a pixel-wise classification/segmentation into different classes. As the acquisition of labeled training data is very time-consuming, unsupervised methods become crucial in hyperspectral image analysis. The spectral variability and noise in hyperspectral data make this task very challenging and define special requirements for such methods. Here, we present a novel unsupervised hyperspectral segmentation framework. It starts with a denoising and dimensionality reduction step by the well-established Minimum Noise Fraction (MNF) transform. Then, the Mumford-Shah (MS) segmentation functional is applied to segment the data. We equipped the MS functional with a novel robust distribution-dependent indicator function designed to handle the characteristic challenges of hyperspectral data. To optimize our objective function with respect to the parameters for which no closed form solution is available, we propose an efficient fixed point iteration scheme. Numerical experiments on four public benchmark datasets show that our method produces competitive results, which outperform three state-of-the-art methods substantially on three of these datasets.

Developing deep neural networks to generate 3D scenes is a fundamental problem in neural synthesis with immediate applications in architectural CAD, computer graphics, as well as in generating virtual robot training environments. This task is challenging because 3D scenes exhibit diverse patterns, ranging from continuous ones, such as object sizes and the relative poses between pairs of shapes, to discrete patterns, such as occurrence and co-occurrence of objects with symmetrical relationships. This paper introduces a novel neural scene synthesis approach that can capture diverse feature patterns of 3D scenes. Our method combines the strength of both neural network-based and conventional scene synthesis approaches. We use the parametric prior distributions learned from training data, which provide uncertainties of object attributes and relative attributes, to regularize the outputs of feed-forward neural models. Moreover, instead of merely predicting a scene layout, our approach predicts an over-complete set of attributes. This methodology allows us to utilize the underlying consistency constraints among the predicted attributes to prune infeasible predictions. Experimental results show that our approach outperforms existing methods considerably. The generated 3D scenes interpolate the training data faithfully while preserving both continuous and discrete feature patterns.

This paper introduces an unsupervised loss for training parametric deformation shape generators. The key idea is to enforce the preservation of local rigidity among the generated shapes. Our approach builds on an approximation of the as-rigid-as possible (or ARAP) deformation energy. We show how to develop the unsupervised loss via a spectral decomposition of the Hessian of the ARAP energy. Our loss nicely decouples pose and shape variations through a robust norm. The loss admits simple closed-form expressions. It is easy to train and can be plugged into any standard generation models, e.g., variational auto-encoder (VAE) and auto-decoder (AD). Experimental results show that our approach outperforms existing shape generation approaches considerably on public benchmark datasets of various shape categories such as human, animal and bone. Our code and data are available at https://github.com/GitBoSun/ARAPReg.

Polyhedral meshes are increasingly becoming an attractive option with particular advantages over traditional meshes for certain applications. What has been missing is a robust polyhedral meshing algorithm that can handle broad classes of domains exhibiting arbitrary curved boundaries and sharp features. In addition, the power of primal-dual mesh pairs, exemplified by Voronoi-Delaunay meshes, has been recognized as an important ingredient in numerous formulations. The VoroCrust algorithm is the first provably correct algorithm for conforming Voronoi meshing for non-convex and possibly non-manifold domains with guarantees on the quality of both surface and volume elements. A robust refinement process estimates a suitable sizing field that enables the careful placement of Voronoi seeds across the surface circumventing the need for clipping and avoiding its many drawbacks. The algorithm has the flexibility of filling the interior by either structured or random samples, while all sharp features are preserved in the output mesh. We demonstrate the capabilities of the algorithm on a variety of models and compare against state-of-the-art polyhedral meshing methods based on clipped Voronoi cells establishing the clear advantage of VoroCrust output.

We present a method called SketchyCoreSVD to compute the near-optimal rank r SVD of a data matrix by building random sketches only from its subsampled columns and rows. We provide theoretical guarantees under incoherence assumptions, and validate the performance of our SketchyCoreSVD method on various large static and time-varying datasets.

The Rayleigh quotient optimization is the maximization of a rational function, or a max-min problem, with simultaneous maximization of the numerator function and minimization of the denominator function. Here, we describe a low-rank, streaming solution for Rayleigh quotient optimization applicable for big-data scenarios where the data matrix is too large to be fully loaded into main memory. We apply this for a maximization of the Signal to Noise ratio of big-data, of very large static and dynamic data. Our implementation is shown to achieve faster processing time compared to a standard data read into memory. We demonstrate the trade-offs with synthetic and real data, on different scales to validate the approach in terms of accuracy, speed and storage.

Stein variational gradient descent (SVGD) is a particle-based inference algorithm that leverages gradient information for efficient approximate inference. In this work, we enhance SVGD by leveraging preconditioning matrices, such as the Hessian and Fisher information matrix, to incorporate geometric information into SVGD updates. We achieve this by presenting a generalization of SVGD that replaces the scalar-valued kernels in vanilla SVGD with more general matrix-valued kernels. This yields a significant extension of SVGD, and more importantly, allows us to flexibly incorporate various preconditioning matricesto accelerate the exploration in the probability landscape. Empirical results show that our method outperforms vanilla SVGD and a variety of baseline approaches over a range of real-world Bayesian inference tasks.

As computational modeling, simulation, and predictions are becoming integral parts of biomedical pipelines, it behooves us to emphasize the reliability of the computational protocol. For any reported quantity of interest (QOI), one must also compute and report a measure of the uncertainty or error associated with the QOI. This is especially important in molecular modeling, since in most practical applications the inputs to the computational protocol are often noisy, incomplete, or low-resolution. Unfortunately, currently available modeling tools do not account for uncertainties and their effect on the final QOIs with sufficient rigor. We have developed a statistical framework that expresses the uncertainty of the QOI as the probability that the reported value deviates from the true value by more than some user-defined threshold. First, we provide a theoretical approach where this probability can be bounded using Azuma-Hoeffding like inequalities. Second, we approximate this probability empirically by sampling the space of uncertainties of the input and provide applications of our framework to bound uncertainties of several QOIs commonly used in molecular modeling. Finally, we also present several visualization techniques to effectively and quantitavely visualize the uncertainties: in the input, final QOIs, and also intermediate states.

Establishing high-quality correspondence maps between geometric shapes has been shown to be the fundamental problem in managing geometric shape collections. Prior work has focused on computing efficient maps between pairs of shapes, and has shown a quantifiable benefit of joint map synchronization, where a collection of shapes are used to improve (denoise) the pairwise maps for consistency and correctness. However, these existing map synchronization techniques place very strong assumptions on the input shapes collection such as all the input shapes fall into the same category and/or the majority of the input pairwise maps are correct. In this paper, we present a multiple map synchronization approach that takes a heterogeneous shape collection as input and simultaneously outputs consistent dense pairwise shape maps. We achieve our goal by using a novel tensor-based representation for map synchronization, which is efficient and robust than all prior matrix-based representations. We demonstrate the usefulness of this approach across a wide range of geometric shape datasets and the applications in shape clustering and shape co-segmentation.

times the local feature size centered at each sample. The corners of the union of these balls on both sides of the surface are the Voronoi sites and the interface of their cells is a watertight surface reconstruction embedded in the dual shape of the union of balls. With the surface protected, the enclosed volume can be further decomposed by generating more sites inside it. Compared to clipping-based algorithms, VoroCrust cells are full Voronoi cells, with convexity and fatness guarantees. Compared to the power crust algorithm, VoroCrust cells are not filtered, are unweighted, and offer greater flexibility in meshing the enclosed volume by either structured or randomly genenerated samples.

Over the past decade, polyhedral meshing has been gaining popularity as a better alternative to tetrahedral meshing in certain applications. Within the class of polyhedral elements, Voronoi cells are particularly attractive thanks to their special geometric structure. What has been missing so far is a Voronoi mesher that is sufficiently robust to run automatically on complex models. In this video, we illustrate the main ideas behind the VoroCrust algorithm, highlighting both the theoretical guarantees and the practical challenges imposed by realistic inputs.

We introduce a principled approach for simultaneous mapping and clustering (SMAC) for establishing consistent maps across heterogeneous object collections (e.g., 2D images or 3D shapes). Our approach takes as input a heterogeneous object collection and a set of maps computed between some pairs of objects, and outputs a homogeneous object clustering together with a new set of maps possessing optimal intra- and inter-cluster consistency. Our approach is based on the spectral decomposition of a data matrix storing all pairwise maps in its blocks. We additionally provide tight theoretical guarantees on the exactness of SMAC under established noise models. We also demonstrate the usefulness of the approach on synthetic and real datasets.

In this paper, we introduce a robust algorithm, \textsl{TranSync}, for the 1D translation synchronization problem, in which the aim is to recover the global coordinates of a set of nodes from noisy measurements of relative coordinates along an observation graph. The basic idea of TranSync is to apply truncated least squares, where the solution at each step is used to gradually prune out noisy measurements. We analyze TranSync under both deterministic and randomized noisy models, demonstrating its robustness and stability. Experimental results on synthetic and real datasets show that TranSync is superior to state-of-the-art convex formulations in terms of both efficiency and accuracy.

Detecting and analyzing protein cavities provides significant information about active sites for biological processes (e.g., protein-protein or protein-ligand binding) in molecular graphics and modeling. Using the three-dimensional structure of a given protein (i.e., atom types and their locations in 3D) as retrieved from a PDB (Protein Data Bank) file, it is now computationally viable to determine a description of these cavities. Such cavities correspond to pockets, clefts, invaginations, voids, tunnels, channels, and grooves on the surface of a given protein. In this work, we survey the literature on protein cavity computation and classify algorithmic approaches into three categories: evolution-based, energy-based, and geometry-based. Our survey focuses on geometric algorithms, whose taxonomy is extended to include not only sphere-, grid-, and tessellation-based methods, but also surface-based, hybrid geometric, consensus, and time-varying methods. Finally, we detail those techniques that have been customized for GPU (Graphics Processing Unit) computing.

Most of the existing research in assembly pathway prediction/analysis of virus capsids makes the simplifying assumption that the configuration of the intermediate states can be extracted directly from the final configuration of the entire capsid. This assumption does not take into account the conformational changes of the constituent proteins as well as minor changes to the binding interfaces that continues throughout the assembly process until stabilization. This paper presents a statistical-ensemble based approach which provides sufficient samples of the configurational space for each monomer and the relative local orientation between monomers, to capture the uncertainties in their binding and conformations. Furthermore, instead of using larger capsomers (trimers, pentamers) as building blocks, we allow all possible sub-assemblies to bind in all possible combinations. We represent this assembly graph in two different ways. First, we use the Wilcoxon signed rank measure to compare the distributions of binding free energy computed on the sampled conformations to predict likely pathways. Second, we represent chemical equilibrium aspects of the transitions as a Bayesian Factor graph where both associations and dissociations are modeled based on concentrations and the binding free energies. Results from both of these experiments showed significant departure from those one would obtain if only the static configurations of the proteins were considered. Hence, we establish the importance of an uncertainty-aware protocol for pathway analysis, and provide a statistical framework as an important first step towards assembly pathway prediction with high statistical confidence.

We introduce an algorithmic framework for tuning the spatial density of disks in a maximal random packing, without changing the sizing function or radii of disks. Starting from any maximal random packing such as a Maximal Poisson-disk Sampling (MPS), we iteratively relocate, inject (add), or eject (remove) disks, using a set of three successively more-aggressive local operations. We may achieve a user-defined density, either more dense or more sparse, almost up to the theoretical structured limits. The tuned samples are conflict-free, retain coverage maximality, and, except in the extremes, retain the blue noise randomness properties of the input. We change the density of the packing one disk at a time, maintaining the minimum disk separation distance and the maximum domain coverage distance required of any maximal packing. These properties are local, and we can handle spatially-varying sizing functions. Using fewer points to satisfy a sizing function improves the efficiency of some applications. We apply the framework to improve the quality of meshes, removing non-obtuse angles; and to more accurately model fiber reinforced polymers for elastic and failure simulations.

We present an algorithm to compute an approximation of the generalized Voronoi diagram (GVD) on arbitrary collections of 2D or 3D geometric objects. In particular, we focus on datasets with closely spaced objects; GVD approximation is expensive and sometimes intractable on these datasets using previous algorithms. With our approach, the GVD can be computed using commodity hardware even on datasets with many, extremely tightly packed objects. Our approach is to subdivide the space with an octree that is represented with an adjacency structure. We then use a novel adaptive distance transform to compute the distance function on octree vertices. The computed distance field is sampled more densely in areas of close object spacing, enabling robust and parallelizable GVD surface generation. We demonstrate our method on a variety of data and show example applications of the GVD in 2D and 3D.

There continue to be increasing occurrences of both atomistic structure models in the PDB (possibly reconstructed from X-ray diffraction or NMR data), and 3D reconstructed cryo-electron microscopy (3D EM) maps (albeit at coarser resolution) of the same or homologous molecule or molecular assembly, deposited in the EMDB. To obtain the best possible structural model of the molecule at the best achievable resolution, and without any missing gaps, one typically aligns (match and fits) the atomistic structure model with the 3D EM map. We discuss a new algorithm and generalized framework, named PF(2) fit (Polar Fast Fourier Fitting) for the best possible structural alignment of atomistic structures with 3D EM. While PF(2) fit enables only a rigid, six dimensional (6D) alignment method, it augments prior work on 6D X-ray structure and 3D EM alignment in multiple ways: Scoring. PF(2) fit includes a new scoring scheme that, in addition to rewarding overlaps between the volumes occupied by the atomistic structure and 3D EM map, rewards overlaps between the volumes complementary to them. We quantitatively demonstrate how this new complementary scoring scheme improves upon existing approaches. PF(2) fit also includes two scoring functions, the non-uniform exterior penalty and the skeleton-secondary structure score, and implements the scattering potential score as an alternative to traditional Gaussian blurring. Search. PF(2) fit utilizes a fast polar Fourier search scheme, whose main advantage is the ability to search over uniformly and adaptively sampled subsets of the space of rigid-body motions. PF(2) fit also implements a new reranking search and scoring methodology that considerably improves alignment metrics in results obtained from the initial search.

Discoveries in computational molecular - cell biology and bioinformatics promise to provide new therapeutic interventions to disease. With the rapid growth of sequence and structural information for thousands of proteins and hundreds of cell types, computational processing are a restricting factor in obtaining quantitative understanding of molecular-cellular function. Processing and analysis is necessary both for input data (often from imaging) and simulation results. To make biological conclusions, this data must be input to and combined with results from computational analysis and simulations. Furthermore, as parallelism is increasingly prevalent, utilizing the available processing power is essential to development of scalable solutions needed for realistic scientific inquiry. However, complex image processing and even simulations performed on large clusters, multi-core CPU, GPU-type parallelization means that naïve cache unaware algorithms may not efficiently utilize available hardware. Future gains thus require improvements to a core suite of algorithms underpinning the data processing, simulation, optimization and visualization needed for scientific discovery. In this talk, I shall highlight current progress on these algorithms as well as provide several challenges for the visualization community.

We introduce a tomographic reconstruction method implemented using a shape-based regularization technique. Spatial models of known features in the structure being reconstructed are integrated into the reconstruction process as regularizers. Our regularization scheme is driven locally through shape information obtained from segmentation and compared with a known spatial model. We demonstrated our method on tomography data from digital phantoms, simulated data, and experimental electron tomography (ET) data of virus complexes. Our reconstruction showed reduced blurring and an improvement in the resolution of the reconstructed volume was also measured. This method also produced improved demarcation of spike boundaries in viral membranes when compared with popular techniques like weighted back projection and the algebraic reconstruction technique. Improved ET reconstructions will provide better structure elucidation and improved feature visualization, which can aid in solving key biological issues. Our method can also be generalized to other tomographic modalities.

MOTIVATION: We present the 'Dynamic Packing Grid' (DPG), a neighborhood data structure for maintaining and manipulating flexible molecules and assemblies, for efficient computation of binding affinities in drug design or in molecular dynamics calculations. RESULTS: DPG can efficiently maintain the molecular surface using only linear space and supports quasi-constant time insertion, deletion and movement (i.e. updates) of atoms or groups of atoms. DPG also supports constant time neighborhood queries from arbitrary points. Our results for maintenance of molecular surface and polarization energy computations using DPG exhibit marked improvement in time and space requirements. AVAILABILITY: http://www.cs.utexas.edu/~bajaj/cvc/software/DPG.shtml.

The functions of proteins are often realized through their mutual interactions. Determining a relative transformation for a pair of proteins and their conformations which form a stable complex, reproducible in nature, is known as docking. It is an important step in drug design, structure determination, and understanding function and structure relationships. In this paper, we extend our nonuniform fast Fourier transform-based docking algorithm to include an adaptive search phase (both translational and rotational) and thereby speed up its execution. We have also implemented a multithreaded version of the adaptive docking algorithm for even faster execution on multicore machines. We call this protein-protein docking code F2Dock (F2 = Fast Fourier). We have calibrated F2Dock based on an extensive experimental study on a list of benchmark complexes and conclude that F2Dock works very well in practice. Though all docking results reported in this paper use shape complementarity and Coulombic-potential-based scores only, F2Dock is structured to incorporate Lennard-Jones potential and reranking docking solutions based on desolvation energy .

In this paper, we describe a new method to generate a smooth algebraic spline (AS) approximation of the molecular surface (MS) based on an initial coarse triangulation derived from the atomic coordinate information of the biomolecule, resident in the Protein data bank (PDB). Our method first constructs a triangular prism scaffold covering the PDB structure, and then generates a piecewise polynomial F on the Bernstein-Bezier (BB) basis within the scaffold. An ASMS model of the molecular surface is extracted as the zero contours of F, which is nearly C1 and has dual implicit and parametric representations. The dual representations allow us easily do the point sampling on the ASMS model and apply it to the accurate estimation of the integrals involved in the electrostatic solvation energy computations. Meanwhile comparing with the trivial piecewise linear surface model, fewer number of sampling points are needed for the ASMS, which effectively reduces the complexity of the energy estimation.

Level set method based segmentation provides an efficient tool for topological and geometrical shape handling. Conventional level set surfaces are only C(0) continuous since the level set evolution involves linear interpolation to compute derivatives. Bajaj et al. present a higher order method to evaluate level set surfaces that are C(2) continuous, but are slow due to high computational burden. In this paper, we provide a higher order GPU based solver for fast and efficient segmentation of large volumetric images. We also extend the higher order method to multi-domain segmentation. Our streaming solver is efficient in memory usage.

Whereas traditional finite element methods use meshes to define domain geometry, weighted extended B-spline finite element methods rely on a weight function. A weight function is a smooth, strictly positive function which vanishes at the domain boundary at an appropriate rate. We describe a method for generating weight functions for a general class of domains based on A-splines. We demonstrate this approach and address the relationship between weight function quality and error in the resulting finite element solutions.

Bio-molecules reach their stable configuration in solvent which is primarily water with a small concentration of salt ions. One approximation of the total free energy of a bio-molecule includes the classical molecular mechanical energy EMM (which is understood as the self intra-molecular energy in vacuum) and the solvation energy Gsol which is caused by the change of the environment of the molecule from vacuum to solvent (and hence also known as the molecule-solvent interaction energy). This total free energy is used to model and study the stability of bio-molecules in isolation or in their interactions with drugs. In this paper we present fast O (N log N) multi-level grid based approximation algorithms (where N is the number of atoms) for efficiently estimating the compute-intensive terms of EMM and Gsol. The fast octree-based algorithm for Gsol is additionally dependent on an O (N) size computation of the biomolecular surface and its spatial derivatives (normals). We also provide several examples with timing results, and speed/accuracy tradeoffs, demonstrating the efficiency and scalability of our fast free energy estimation of bio-molecules, potentially with millions of atoms.

Motivated by the need for correct and robust 3D models of neuronal processes, we present a method for reconstruction of spatially realistic and topologically correct models from planar cross sections of multiple objects. Previous work in 3D reconstruction from serial contours has focused on reconstructing one object at a time, potentially producing inter-object intersections between slices. We have developed a robust algorithm that removes these intersections using a geometric approach. Our method not only removes intersections but can guarantee a given minimum separation of objects. This paper describes the algorithm for geometric adjustment, proves correctness, and presents several results of our high-fidelity modeling.

Mixed finite element methods solve a PDE involving two or more variables. In typical problems from electromagnetics and electrodiffusion, the degrees of freedom associated to the different variables are stored on both primal and dual domain meshes and a discrete Hodge star is used to transfer information between the meshes. We show through analysis and examples that the choice of discrete Hodge star is essential to the model and numerical stability of a finite element method. We also show how to define interpolation functions and discrete Hodge stars on dual meshes which can be used to create previously unconsidered mixed methods.

We present the "Dynamic Packing Grid" (DPG) data structure along with details of our implementation and performance results, for maintaining and manipulating flexible molecular models and assemblies. DPG can efficiently maintain the molecular surface (e.g., van der Waals surface and the solvent contact surface) under insertion/deletion/movement (i.e., updates) of atoms or groups of atoms. DPG also permits the fast estimation of important molecular properties (e.g., surface area, volume, polarization energy, etc.) that are needed for computing binding affinities in drug design or in molecular dynamics calculations. DPG can additionally be utilized in efficiently maintaining multiple "rigid" domains of dynamic flexible molecules. In DPG, each up-date takes only O (log w) time w.h.p. on a RAM with w-bit words i.e., O (1) time in practice, and hence is extremely fast. DPG's queries include the reporting of all atoms within O (rmax) distance from any given atom center or point in 3-space in O (log log w) (= O (1)) time w.h.p., where rmax is the radius of the largest atom in the molecule. It can also answer whether a given atom is exposed or buried under the surface within the same time bound, and can return the entire molecular surface in O (m) worst-case time, where m is the number of atoms on the surface. The data structure uses space linear in the number of atoms in the molecule.

Electrostatic interactions play a significant role in determining the binding affinity of molecules and drugs. While significant effort has been devoted to the accurate computation of biomolecular electrostatics based on an all-atomic solution of the Poisson-Boltzmann (PB) equation for smaller proteins and nucleic acids, relatively little has been done to optimize the efficiency of electrostatic energetics and force computations of macromolecules at varying resolutions (also called coarse-graining). We have developed an efficient and comprehensive framework for computing coarse-grained PB electrostatic potentials, polarization energetics and forces for smooth multi-resolution representations of almost all molecular structures, available in the PDB. Important aspects of our framework include the use of variational methods for generating C2-smooth and multi-resolution molecular surfaces (as dielectric interfaces), a parameterization and discretization of the PB equation using an algebraic spline boundary element method, and the rapid estimation of the electrostatic energetics and forces using a kernel independent fast multipole method. We present details of our implementation, as well as several performance results on a number of examples.

Current mesh reduction techniques, while numerous, all primarily reduce mesh size by successive element deletion (e.g. edge collapses) with the goal of geometric and topological feature preservation. The choice of geometric error used to guide the reduction process is chosen independent of the function the end user aims to calculate, analyze, or adaptively refine. In this paper, we argue that such a decoupling of structure from function modeling is often unwise as small changes in geometry may cause large changes in the associated function. A stable approach to mesh decimation, therefore, ought to be guided primarily by an analysis of functional sensitivity, a property dependent on both the particular application and the equations used for computation (e.g. integrals, derivatives, or integral/partial differential equations). We present a methodology to elucidate the geometric sensitivity of functionals via two major functional discretization techniques: Galerkin finite element and discrete exterior calculus. A number of examples are given to illustrate the methodology and provide numerical examples to further substantiate our choices.

Computer Tomography (CT) and in particular super fast, 64 and 256 detector CT has rapidly advanced over recent years, such that high resolution cardiac imaging has become a reality. In this paper, we briefly introduce a framework that we have built to construct three dimensional (3D) finite-element and boundary element mesh models of the human heart directly from high resolution CT imaging data. Although, the overall IMAGING-MODELING framework consists of image processing, geometry processing and meshing algorithms, our main focus in this paper will revolve around three key geometry processing steps which are parts of the so-called IMAGING-MODELING framework. These three steps are geometry cleanup or CURATION, anatomy guided annotation or SEGMENTATION and construction of GENERALIZED OFFSET SURFACE. These three algorithms, due to the very nature of the computation involved, can also be thought as parts of a more generalized modeling technique, namely geometric modeling with distance function. As part of the results presented in the paper, we will show that our algorithms are robust enough to effectively deal with the challenges posed by the real-world patient CT data collected from our radiologist collaborators.

Building surfaces from cross-section curves has wide applications including bio-medical modeling. Previous work in this area has mostly focused on connecting simple closed curves on parallel cross-sections. Here we consider the more general problem where input data may lie on non-parallel cross-sections and consist of curve networks that represent the segmentation of the underlying object by different material or tissue types (e.g., skin, muscle, bone, etc.) on each cross-section. The desired output is a surface network that models both the exterior surface and the internal partitioning of the object. We introduce an algorithm that is capable of handling curve networks of arbitrary shape and topology on cross-section planes with arbitrary orientations. Our algorithm is simple to implement and is guaranteed to produce a closed surface network that interpolates the curve network on each cross-section. Our method is demonstrated on both synthetic and bio-medical examples.

We present computational solutions to two problems of macromolecular structure interpretation from reconstructed three-dimensional electron microscopy (3D-EM) maps of large bio-molecular complexes at intermediate resolution (5A-15 A). The two problems addressed are: 1) 3D structural alignment (matching) between identified and segmented 3D maps of structure units (e.g. trimeric configuration of proteins), and 2) the secondary structure identification of a segmented protein 3D map (i.e.locations of alpha-helices, beta-sheets). For problem 1, we present an efficient algorithm to correlate spatially (and structurally) two 3D maps of structure units. Besides providing a similarity score between structure units, the algorithm yields an effective technique for resolution refinement of repeated structure units, by 3D alignment and averaging. For problem 2, we present an efficient algorithm to compute eigenvalues and link eigenvectors of a Gaussian convoluted structure tensor derived from the protein 3D Map, thereby identifying and locating secondary structural motifs of proteins. The efficiency and performance of our approach is demonstrated on several experimentally reconstructed 3D maps of virus capsid shells from single-particle cryo-electron microscopy (cryo-EM), as well as computationally simulated protein structure density 3D maps generated from protein model entries in the Protein Data Bank.

We present a general framework for a higher-order spline level-set (HLS) method and apply this to smooth surface constructions. Starting from a first order energy functional, we obtain a general level set formulation of geometric partial differential equation, and provide an efficient approach to solve this partial differential equation using a C2spline basis. We also present a fast cubic spline interpolation algorithm based on convolution and the Z-transform, which exploits the local relationship of interpolatory cubic spline coefficients with respect to given function data values. We provide two demonstrative smooth surface construction examples of our HLS method. The first is the construction of a smooth surface model (an implicit solvation interface) of bio-molecules in solvent, given their individual atomic coordinates and solvated radii. The second is the smooth surface reconstruction from a cloud of points generated from a 3D surface scanner.

In this paper, we describe a new method to generate a smooth algebraic spline (AS) model approximation of the molecular surface (MS), based on an initial coarse triangulation derived from the atomic coordinate information of the biomolecule, resident in the PDB (Protein data bank). Our method first constructs a triangular prism scaffold Ps covering the PDB structure, and then generates piecewise polynomial Bernstein-Bezier (BB) spline function approximation F within Ps, which are nearly C1 everywhere. Approximation error and point sampling convergence bounds are also computed. An implicit AS model of the MS which is free of singularity, is extracted as the zero contours of F. Furthermore, we generate a polynomial parametrization of the implicit MS, which allows for an efficient point sampling on the MS, and thereby simplifies the accurate estimation of integrals needed for electrostatic solvation energy calculations.

We present an approach for three-dimensional (3D) image skeletonization, based on the local structure tensor idea. Two major types of features are addressed: helical and planar. Accordingly, we also discussed how the skeletonization approach is successfully applied to the protein secondary structure analysis, including the alpha-helix (helical type) and beta-sheet (planar type) identifications.

We present an algorithm to identify the flat and tubular regions of a three dimensional shape from its point sample. We consider the distance function to the input point cloud and the Morse structure induced by it on R3. Specifically we focus on the index 1 and index 2 saddle points and their unstable manifolds. The unstable manifolds of index 2 saddles are one dimensional whereas those of index 1 saddles are two dimensional. Mapping these unstable manifolds back onto the surface, we get the tubular and flat regions. The computations are carried out on the Voronoi diagram of the input points by approximating the unstable manifolds with Voronoi faces. We demonstrate the performance of our algorithm on several point sampled objects.

The contour tree has been used to compute the topology of isosurfaces, generate a minimal seed set for accelerated isosurface extraction, and provide a user interface to segment individual contour components in a scalar field. In this paper, we extend the benefits of the contour tree to time-varying data visualization. We define temporal correspondence of contour components and describe an algorithm to compute the correspondence information in time-dependent contour trees. A graph representing the topology changes of time-varying isosurfaces is constructed in real-time for any selected isovalue using the precomputed correspondence information. Quantitative properties, such as surface area and volume of contour components, are computed and labeled on the graph. This topology change graph helps users to detect significant topological and geometric changes in time-varying isosurfaces. The graph is also used as an interactive user interface to segment, track, and visualize the evolution of any selected contour components over time.

Abstract With the increased sophistication and use of heated gas, fire, and explosion simulations in computer graphics applications, there is a corresponding impetus to improve the visual realism in the rendering of such simulated phenomena. In visualizing these turbulent fluids, an appropriate incorporation of their incandescent properties into the rendering significantly enhances the realism of visual effects. In this paper, we effectively synthesize the light emission phenomena of hot gaseous fluids by extending the photon mapping global illumination method. In particular, we add two new photon maps to capture the thermal radiation effects. First, we define anemissionphoton map to store the photons emitted within hot gaseous fluids. Second, we utilize additionalflashandflash reflectionphoton maps, which are effective in creating a visual effect of light that intensively and instantly propagates outside hot gaseous fluids, visually capturing shock waves. Our current technique, while based on the theory of blackbody radiation, is parameterized to enable an animator to generate a wide range of visual effects with fairly intuitive user control. We demonstrate the effectiveness of our new rendering technique and user‐controlled generation of visual effects with several example pictures and animations. Copyright © 2005 John Wiley & Sons, Ltd.

We present an automatic algorithm to segment all the local and global asymmetric units of a three-dimensional density map of icosahedral viruses. This approach is readily applicable to the structural analysis of a broad range of virus structures that are reconstructed using cryo-electron microscopy (cryo-EM) technique. Our algorithm includes three major steps operating on the three dimensional density map: the detection of critical points of the volumetric density function, the detection of global and local symmetry axes, and, finally, the boundary segmentation of all the asymmetric units. We demonstrate the efficacy of our algorithm and report our results on several experimental volumetric datasets, consisting of both reconstructed cryo-EM molecular density maps taken from the European Bioinformatics Institute archive, as well our own synthetically generated (blurred) maps calculated from X-ray resolution molecular structural data taken from the Protein Data Bank.

In this paper we describe a fast approach for image contrast enhancement, based on localized contrast manipulation. Our approach is not only last and easy to implement, but also has several other promising properties (adaptive, multiscale, weighted localization, etc.). We will also discuss in this paper an anisotropic version of our approach. Several examples of medical images, including brain MR images, chest CT images and mammography images, will be provided to demonstrate the performance of our approach.

While molecular visualization software has advanced over the years, today, most tools still operate on individual molecular structures with limited facility to manipulate large multicomponent complexes. We approach this problem by extending 3D image-based rendering via programmable graphics units, resulting in an order of magnitude speedup over traditional triangle-based rendering. By incorporating a biochemically sensitive level-of-detail hierarchy into our molecular representation, we communicate appropriate volume occupancy and shape while dramatically reducing the visual clutter that normally inhibits higher-level spatial comprehension. Our hierarchical, image based rendering also allows dynamically computed physical properties data (e.g. electrostatics potential) to be mapped onto the molecular surface, tying molecular structure to molecular function. Finally, we present another approach to interactive molecular exploration using volumetric and structural rendering in tandem to discover molecular properties that neither rendering mode alone could reveal. These visualization techniques are realized in a high-performance, interactive molecular exploration tool we call TexMol, short for Texture Molecular viewer.

The increased programmability of graphics hardware allows efficient graphical processing unit (GPU) implementations of a wide range of general computations on commodity PCs. An important factor in such implementations is how to fully exploit the SIMD computing capacities offered by modern graphics processors. Linear expressions in the form of ȳ = Ax̄ + b̄, where A is a matrix, and x̄, ȳ and b̄ are vectors, constitute one of the most basic operations in many scientific computations. In this paper, we propose a SIMD code optimization technique that enables efficient shader codes to be generated for evaluating linear expressions. It is shown that performance can be improved considerably by efficiently packing arithmetic operations into four-wide SIMD instructions through reordering of the operations in linear expressions. We demonstrate that the presented technique can be used effectively for programming both vertex and pixel shaders for a variety of mathematical applications, including integrating differential equations and solving a sparse linear system of equations using iterative methods.

Abstract The 3D structures of individual proteins or small complexes, such as most of the Protein Data Bank entries, are still unable to yield the ''full picture'' of a functional biological complex. The study of large macromolecular complexes, such as viruses, ion channels, the ribosome and other macromolecular machines of various types, offer more complete structural and functional description of the nano‐machinery of life. In addition to x‐ray crystallography. NMR spectroscopy, electron cryomicroscopy (cryoEM) imaging of single particles, and in‐vivo molecular tomographic imaging has become indispensable at revealing the structures of large macromolecular complexes at subnanometer resolutions. In this talk, I shall describe some of the recent computational advances in filtering, modeling, analysis and visualization, that have propelled structure determination by cryoEM and tomographic imaging, to steadily increasing accuracy.

We present a unified anisotropic geometric diffusion PDE model for smoothing (fairing) out noise both in triangulated two-manifold surface meshes inIR3and functions defined on these surface meshes, while enhancing curve features on both by careful choice of an anisotropic diffusion tensor. We combine theC1limit representation of Loop's subdivision for triangular surface meshes and vector functions on the surface mesh with the established diffusion model to arrive at a discretized version of the diffusion problem in the spatial direction. The time direction discretization then leads to a sparse linear system of equations. Iteratively solving the sparse linear system yields a sequence of faired (smoothed) meshes as well as faired functions.

We propose the use of surface subdivision as adaptive and higher-order boundary elements for solving a Helmholtz partial differential equation to calculate accurate acoustic scattering on arbitrary manifolds. Such acoustic transfer functions prove useful for designing and tuning hearing aid devices for hearing impaired individuals. The number of unknowns of the discretized linear system is the same as that in a linear element approach. Our results show that the accuracy of the subdivision approach is much better than that of the linear element approach.

Anisotropic diffusion has been widely used in image processing for its efficiency of smoothing the noisy images while preserving the sharp edges. In this paper we explore a general version of anisotropic diffusion schemes for vector-valued images, based on the polar-coordinate representation of the vectors. As an example, we apply our method to color images and show its ability of edge-preserving smoothing on vector-valued images.

Adaptive mesh refinement (AMR) is a popular computational simulation technique used in various scientific and engineering fields. Although AMR data is organized in a hierarchical multi-resolution data structure, the traditional volume visualization algorithms such as ray-casting and splatting cannot handle the form without converting it to a sophisticated data structure. In this paper, we present a hierarchical multi-resolution splatting technique using k-d trees and octrees for AMR data that is suitable for implementation on the latest consumer PC graphics hardware. We describe a graphical user interface to set transfer function and viewing/rendering parameters interactively. Experimental results obtained on a general purpose PC equipped with NVIDIA GeForce card are presented to demonstrate that the technique can interactively render AMR data (over 20 frames per second). Our scheme can easily be applied to parallel rendering of time-varying AMR data.

In triangulated surface meshes, there are often very noticeable size variances (the vertices are distributed unevenly). The presented noise of such surface meshes is therefore composite of vast frequencies. We solve a diffusion partial differential equation numerically for noise removal of arbitrary triangular manifolds using an adaptive time discretization. The proposed approach is simple and is easy to incorporate into any uniform timestep diffusion implementation with significant improvements over evolution results with the uniform timesteps. As an additional alternative to the adaptive discretization in the time direction, we also provide an approach for the choice of an adaptive diffusion tensor in the diffusion equation.

When interactive real-time applications are developed with very large volume data, the use of lossy compression is often inevitable. Lossy compression schemes generally encode data without consideration of the purpose of visualization that is actually performed, which often results in inefficient compression. In this paper, we present a new method for classifying voxels according to their importance in visualization, and assigning appropriate weights to them. The associated weight information can be combined with lossy compression schemes to reduce the visual degradation of reconstructed images, resulting in higher compression rates and visual fidelity. Test results demonstrate that the proposed technique improves both the amount of compression and the quality of visualization significantly.

This paper presents a new 3D RGB image compression scheme designed for interactive real-time applications. In designing our compression method, we have compromised between two important goals: high compression ratio and fast random access ability, and have tried to minimize the overhead caused during run-time reconstruction. Our compression technique is suitable for applications wherein data are accessed in a somewhat unpredictable fashion, and real-time performance of decompression is necessary. The experimental results on three different kinds of 3D images from medical imaging, image-based rendering, and solid texture mapping suggest that the compression method can be used effectively in developing real-time applications that must handle large volume data, made of color samples taken in three- or higher-dimensional space.

Multi-resolution techniques and models have been shown to be effective for the display and transmission of large static geometric object. Dynamic environments with internally deforming models and scientific simulations using dynamic meshes pose greater challenges in terms of time and space, and need the development of similar solutions. We introduce the T-DAG, an adaptive multi-resolution representation for dynamic meshes with arbitrary deformations including attribute, position, connectivity and topology changes. T-DAG stands for time-dependent directed acyclic graph which defines the structure supporting this representation. We also provide an incremental algorithm (in time) for constructing the T-DAG representation of a given input mesh. This enables the traversal and use of the multi-resolution dynamic model for partial playback while still constructing new time-steps.

Article Free Access Share on Error bounded regular algebraic spline curves Authors: Chandrajit L. Bajaj Department of Computer Science, University of Texas, Austin, TX Department of Computer Science, University of Texas, Austin, TXView Profile , Guoliang Xu State Key Laboratory of Scientific and Engineering Computing, ICMSEC, Chinese Academy of Sciences, Beijing State Key Laboratory of Scientific and Engineering Computing, ICMSEC, Chinese Academy of Sciences, BeijingView Profile Authors Info & Claims SCG '99: Proceedings of the fifteenth annual symposium on Computational geometryJune 1999 Pages 332–340https://doi.org/10.1145/304893.304987Online:13 June 1999Publication History 0citation256DownloadsMetricsTotal Citations0Total Downloads256Last 12 Months0Last 6 weeks0 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

We propose a new layering structure to partition an arbitrary triangular mesh (no-manifold and arbitrary-genus) into generalized triangle strips. An efficient and flexible encoding of the connectivity, vertex coordinates and attribute data yields excellent single-resolution compression. This scheme gracefully solves the "crack" problem and also prevents error propagation while providing efficient prediction coding for both geometry and photometry data such as positions, color, normal, and texture coordinates. We present an encoder and decoder. We introduce a layering scheme to partition input data, we address the coding of connectivity and geometry, and discuss the attribute coding. Experimental results are presented.

While 2D texture mapping is one of the most powerful rendering techniques that make 3D objects appear visually interesting, it suffers from visual artifacts produced when 2D image patterns are wrapped onto the surface of objects with arbitrary shapes. On the other hand, 3D texture mapping generates highly natural visual effects in which objects appear carved from lumps of materials rather than laminated with thin sheets as in 2D texture mapping. Storing 3D texture images in a table for fast mapping computations, instead of evaluating procedures on the fly, however, has been considered impractical due to the extremely high memory requirements. In this paper, we present a new effective method for 3D texture mapping designed for real-time rendering of polygonal models. Our scheme attempts to resolve the potential texture memory problem arising from the very large size of 3D images by compressing them using a wavelet-based encoding method. The experimental results on various non-trivial 3D textures and polygonal models show that high compression rates are achieved with few visual artifacts in the rendered image and a small impact on rendering time. The simplicity of our compression-based scheme will make it possible to implement practical 3D texture mapping in software/hardware rendering systems including the real-time 3D graphics APIs like OpenGL and Direct3D.

The recent growth in the size and availability of large triangular surface models has generated interest in compact multi-resolution progressive representation and data transmission. An ongoing challenge is to design an efficient data structure that encompasses both compactness of geometric representations and visual quality of progressive representations. We introduce a topological layering based data structure and an encoding scheme to build a compact progressive representation of an arbitrary triangular mesh (a 2D simplicial complex in 3D) with attached attribute data. This compact representation is composed of multiple levels of detail that can be progressively transmitted and displayed. The global topology, which is the number of holes and connected components, can be flexibly changed among successive levels while still achieving guaranteed size of the coarsest level mesh for very complex models. The flexibility in our encoding scheme also allows topology preserving progressivity.

Scalar fields arise in every scientific application. Existing scalar visualization techniques require that the user infers the global scalar structure from what is frequently an insufficient display of information. We present a visualization technique which numerically detects the structure at all scales, removing from the user the responsibility of extracting information implicit in the data, and presenting the structure explicitly for analysis. We further demonstrate how scalar topology detection proves useful for correct visualization and image processing applications such as image co-registration, isocontouring, and mesh compression.

Real cubic algebraic surfaces may be described by either implicit or parametric equations. One particularly useful representation is the rational parametrization, where the three spatial coordinates are given by rational functions of two parameters. These parametrizations take on different forms for different classes of cubic surfaces. Classification of real cubic algebraic surfaces into five families for the nonsingular case is based on the configuration of 27 lines on them. We provide a method of extracting all these lines by constructing and solving a polynomial of degree 27. Simple roots of this polynomial correspond to real lines on the surface, and real skew lines are used to form rational parametrizations for three of these families. Complex conjugate skew lines are used to parametrize surfaces from the fourth family. The parametrizations for these four families involve quotients of polynomials of degree no higher than four. Each of these parametrizations covers the whole surface except for a few points, lines, or conic sections. The parametrization for the fifth family, as noted previously in the literature, requires a square root. We also analyze the image of the derived rational parametrization for both real and complex parameter values, together with “base” points where the parametrizations are ill-defined.

Reconstructing the shape of a 3D object from a digital scan of its surface has a range of applications, such asreverse engineering, authoring 3D synthetic worlds, shape analysis, 3D faxing and tailor-fit modeling. Input data

For 2D or 3D meshes that represent a continuous function to the reals, the contours---or isosurfaces---of a specified value are an important way to visualize it. To find such contours, a seed set can be used for the starting points from which the traversal of the contours can start. This paper gives the first methods to obtain seed sets that are provably small in size. They are based on a variant of the contour tree (or topographic change tree). We give a new, simple algorithm to compute such a tree in regular and irregular meshes that requires O(n log n) time in 2D for meshes with n elements, and in O(n 2 ) time in higher dimensions. The additional storage overhead is proportial to the maximum size of any contour (linear in the worst case, but typically less). Given the contour tree, a minimum size seed set can be computed in polynomial time and storage. Since in practice at most linear storage is allowed, we develop a simple approximation algorithm giving a seed set of size at most...

The authors introduce the contour spectrum, a user interface component that improves qualitative user interaction and provides real-time exact quantification in the visualization of isocontours. The contour spectrum is a signature consisting of a variety of scalar data and contour attributes, computed over the range of scalar values /spl omega//spl isin/R. They explore the use of surface, area, volume, and gradient integral of the contour that are shown to be univariate B-spline functions of the scalar value /spl omega/ for multi-dimensional unstructured triangular grids. These quantitative properties are calculated in real-time and presented to the user as a collection of signature graphs (plots of functions of /spl omega/) to assist in selecting relevant isovalues /spl omega//sub 0/ for informative visualization. For time-varying data, these quantitative properties can also be computed over time, and displayed using a 2D interface, giving the user an overview of the time-varying function, and allowing interaction in both isovalue and time step. The effectiveness of the current system and potential extensions are discussed.

Introduction We present a locality-based algorithm to solve the problem of splitting a complex of convex polytopes with a hyperplane or a convex subset of it. The solution to this problem has several applications. One goal is to perform boolean set operations. The solution can also be used to decompose a polyhedron into convex polytopes [3] and to generate good meshes [4]. In higher dimensional spaces it can be used to efficiently compute isocontours of linear approximations of scalar fields (a basic technique of Scientific Visualization) [17, 19]. The approach taken here can also be included in a set of robust algorithms [11, 13, 15, 20, 27, 28] based on finite precision arithmetic. It is also defined in a dimension independent framework [5, 16, 24, 25]. The main contributions of this approach are: (i) it can be applied to polyhedral complexes of any dimension d; (ii) the algorithm is robust (it always produces valid output) and consistent (the topological structure of the resu

No abstract available.

We present an efficient and uniform approach for the automatic reconstruction of surfaces of CAD (computer aided design) models and scalar fields defined on them, from an unorganized collection of scanned point data.A possible application is the rapid computer model reconstruction of an existing part or prototype from a three dimensional (3D) points scan of its surface.Color, texture or some scalar material property of the physical part, define natural scalar fields over the surface of the CAD model.Our reconstruction algorithm does not impose any convexity or differentiability restrictions on the surface of the original physical part or the scalar field function, except that it assumes that there is a sufficient sampling of the input point data to unambiguously reconstruct the CAD model.Compared to earlier methods our algorithm has the advantages of simplicity, efficiency and uniformity (both CAD model and scalar field reconstruction).The simplicity and efficiency of our approach is based on several novel uses of appropriate sub-structures (alpha shapes) of a three-dimensional Delaunay Triangulation, its dual the three-dimensional Voronoi diagram, and dual uses of trivariate Bernstein-Bézier forms.The boundary of the CAD model is modeled using implicit cubic Bernstein-Bézier patches, while the scalar field is reconstructed with functional cubic Bernstein-Bézier patches.

We present a sufficient criterion for the Bernstein Bezier (BB) form of a trivariate polynomial within a tetrahedron, such that the real zero contour of the polynomial defines a smooth and single-sheeted algebraic surface patch, We call this an A-patch.We present algorithms to build a mesh of cubic A-patches to interpolate a given set of scattered point data in three dimensions, respecting tbe topology of any surface triangulation T of the given point set.In these algorithms we first specify "normals" an the data points, then build a simplicial hull consisting of tetrahedral surrounding the surface triangulation 2', and finally construct cubic A-patches within each tetrahedron.The resulting surface constructed is C' (tangent plane) continuous and single sheeted in each of the tetrahedral.We also show how to adjust the free parameters of the A-patches to achieve both local and global shape control.

We present a comprehensive algorithm to construct a topologically correct triangulation of the real affine part of a rational parametric surface with few restrictions on the defining rational functions. The rational functions are allowed to be undefined on domain curves (pole curves) and at certain special points (base points), and the surface is allowed to have nodal or cuspidal self-intersections. We also recognize that for a complete display, some real points on the parametric surface may be generated only by complex parameter values, and that some finite points on the surface may be generated only by infinite parameter values; we show how to compensate for these conditions. Our techniques for handling these problems have applications in scientific visualization, rendering non-standard NURBS, and in finite-element mesh generation.>

We address the issue of architectures and abstractions to implement multimedia scientific manipulation systems in a Concurrent Engineering setting, where experts in a cooperating group communicate and interact to solve problems. We propose a model for the integration of software tools into a multi-user distributed and collaborative environment on the multimedia desktop, and describe a prototype CSCW infrastructure which we have used to implement scientific problem solving tools. Finally, we briefly describe a prototype CE system built on this infrastructure. Shastra presents a unified prototype for some crucial enabling technologies for Concurrent Engineering — Multimedia Communication, Framework Integration, Coordination, and Enterprise Integration.

We discuss the application of multimedia in scientific design, and describe a multi-user distributed and collaborative scientific manipulation environment, Shastra, implemented on the multimedia desktop. We highlight salient features of the underlying collaboration infrastructure -- an application conferencing substrate that enables user level cooperation. We demonstrate that, in conjunction with shared contexts, multimedia interfaces -- incorporating text, graphics, audio and video, greatly empowers users in the process of collaborative scientific design.

NC algorithms are given for determining the number and degrees of the factors, irreducible over the complex numbers ${\bf C}$, of a multivariate polynomial with rational coefficients and for approximating each irreducible factor. NC is the class of functions computable by logspace-uniform boolean circuits of polynomial size and polylogarithmic depth. The measures of size of the input polynomial are its degree, coefficient length, number of variables (d, c, and n, respectively). If n is fixed, we give a deterministic NC algorithm. If the number of variables is not fixed, we give a random (Monte-Carlo) NC algorithm in these input measures to find the number and degree of each irreducible factor. After reducing to the two-variable, square-free case, we apply the classical algebraic geometry fact that the absolute irreducible factors of $(P(z_1 ,z_2 ) = 0)$ correspond to the connected components of the real surface (or complex curve) $P(z_1 ,z_2 ) = 0$ minus its singular points. In finding the number of connected components of the surface $P = 0$, the surface is projected to the the $z_2 $-plane. The singular points of $P(z_1 ,z_2 )$ lie over the projection’s critical values. The inverse image of a grid isolating the critical values in the $z_2 $-plane lifts to a one-dimensional real curve skeleton on the surface $(P = 0)$ whose number of connected components is precisely the number of connected components of $P = 0$ minus its singular points. The connectivity of this curve skeleton is constructed symbolically using Sturm sequences associated with the various polynomials defining these maps. Given the number of irreducible factors and their degrees, the actual factors can be reconstructed using the recent result of Neff [Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pp. 152–162] on finding zeros of one-variable polynomials in NC.

In this article, we characterize the solution space of low-degree, implicitly defined, algebraic surfaces which interpolate and/or least-squares approximate a collection of scattered point and curve data in three-dimensional space. The problem of higher-order interpolation and least-squares approximation with algebraic surfaces under a proper normalization reduces to a quadratic minimization problem with elegant and easily expressible solutions. We have implemented our algebraic surface-fitting algorithms, and included them in the distributed and collaborative geometric environment SHASTRA. Several examples are given to illustrate how our algorithms are applied to algebraic surface design.

Polyhedron "smoothing" is an efficient construction scheme for generating complex boundary models of solid physical objects.This paper presents efficient algorithms for generating families of curved solid objects with boundaty topology related to an input polyhedron.Individual faces of a polyhedron are replaced by low degree implicit algebraic surface patches with local support.These quintic patches replace the @ contacts of planar facets with C' continuity along all irtterpatch boundaries.Selection of suitable instances of implicit surfaces as well as local control of the individual surface patches are achieved via simultaneouss interpolation and weighted least-squares approximation.

This paper presents a simple algorithm to compute a convex decomposition of a nonconvex polyhedron of arbitrary genus (handles) and shells (internal voids). For such a polyhedron S with n edges and rnotches (features causing nonconvexity in polyhedra), the algorithm produces a worst-case optimal $O(r^2 )$ number of convex polyhedra $S_i $, with $U_{i = 1}^k S_i = S$, in $O(nr^2 + r^{7/2} )$ time and $O(nr + r^{5/2} )$ space. Recently, Chazelle and Palios have given a fast $O((n + r^2 )\log r$) time and $O(n + r^2 )$ space algorithm to tetrahedralize a nonconvex polyhedron. Their algorithm, however, works for a simple polyhedron of genus zero and with no shells (internal voids). The algorithm, presented here, is based on the simple cut and split paradigm of Chazelle. With the help of zone theorems on arrangements, it is shown that this cut and split method is quite efficient. The algorithm is extended to work for a certain class of nonmanifold polyhedra. Also presented is an algorithm for the same problem that uses clever heuristics to overcome the numerical inaccuracies under finite precision arithmetic.

This paper presents an efficient algorithm called Hermite interpolation, for constructing low-degree algebraic surfaces, which contain, with C 1 or tangent plane continuity, any given collection of points and algebraic space curves having derivative information. Positional as well as derivative constraints on an implicitly defined algebraic surface are translated into a homogeneous linear system, where the unknowns are the coefficients of the polynomial defining the algebraic surface. Computaional details of the Hermite interpolation algorithm are presented along with several illustrative applications of the interpolation technique to construction of joining or blending surfaces for solid models as well as fleshing surfaces for curved wire frame models. A heuristic approach to interactive shape control of implicit algebraic surfaces is also given, and open problems in algebraic surface design are discussed.

The set of solutions to a collection of polynomial equations is referred to as an algebraic set. An algebraic set that cannot be represented as the union of two other distinct algebraic sets, neither containing the other, is said to be irreducible. An irreducible algebraic set is also known as an algebraic variety. This paper deals with geometric computations with algebraic varieties. The main results are algorithms to (1) compute the degree of an algebraic variety, (2) compute the rational parametric equations (a rational map from points on a hyperplane) for implicitly defined algebraic varieties of degrees two and three. These results are based on sub-algorithms using multi-polynomial resultants and multi-polynomial remainder sequences for constructing a one-to-one projection map of an algebraic variety to a hypersurface of equal dimension, as well as, an inverse rational map from the hypersurface to the algebraic variety. These geometric computations arise naturally in geometric modeling, computer aided design, computer graphics, and motion planning, and have been used in the past for special cases of algebraic varieties, i.e. algebraic curves and surfaces.

An operation that is frequently needed during the creation and manipulation of geometric models is the sorting of points along an algebraic curve. Given a segment $\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{AB}$ of an algebraic curve, a set of points on the curve is sorted from A to B along $\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{AB}$ by putting them into the order that they would be encountered in traveling continuously from A to B along $\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{AB}$. A new method for sorting points along a plane or space algebraic curve is presented. Key steps in this method are the decomposition of a plane algebraic curve into convex segments and point location in this decomposition. This new method can sort points on an arbitrary algebraic curve (including points spread over several connected components) and it is particularly efficient because of its preprocessing, both of which make it superior to conventional methods. The complexity of the new method is analyzed, and execution times of various sorting methods on a number of algebraic curves are presented. The theory developed for sorting can also be used to locate points on an arbitrary segment of an algebraic curve and to decide whether two points lie on the same connected component.

We present a simple characterization of the lowest degree, implicitly defined, real algebraic surfaces, which smoothly contain any given number of points and algebraic space curves, of arbitrary degree. The characterization is constructive, yielding efficient algorithms for generating families of such algebraic surfaces. Smooth containment of space curves yields C1-continuous surface fitting, and is a generalization of standard Hermite interpolation applied to fitting curves through point data, equating derivatives at those points. We deal with the containment and matching of “normals” (vectors orthogonal to tangents), possibly varying along the entire span of the space curves. Such Hermite interpolated surfaces prove useful as “blending” or “joining” surfaces for solid models as well as “fleshing” surfaces for curved wireframe models.

We give NC algorithms for determining the number and degrees of the absolute factors (factors irreducible over the complex numbers C) of a multi-variate polynomial with rational coefficients. NC is the class of functions computable by logspace-uniform Boolean circuits of polynomial size and polylogarithmic depth. The measures of size of the input polynomial are its degree d, coefficient length c, number of variables n, and for sparse polynomials, the number of non-zero coefficients s. For the general case, we give a random (Monte-Carlo) NC algorithm in these input measures. If n is fixed, or if the polynomial is dense, we give a deterministic NC algorithm. The algorithm also works in random NC for polynomials represented by straight-line programs, provided the polynomial can be evaluated at integer points in NC. Finally, we discuss a method for obtaining an approximation to the coefficients of each factor whose running time is polynomial in the size of the original (dense) polynomial. These methods rely on the fact that the connected components of a complex hypersurface P(z1…,zn) = 0 minus its singular points correspond to the absolute factors of P.

For an irreducible algebraic space curve C that is implicitly defined as the intersection of two algebraic surfaces, f ( x , y , z ) = 0 and g ( x , y , z ) = 0, there always exists a birational correspondence between the points of C and the points of an irreducible plane curve P , whose genus is the same as that of C . Thus C is rational if the genus of P is zero. Given an irreducible space curve C = ( f ∩ g ), with f and g not tangent along C , we present a method of obtaining a projected irreducible plane curve P together with birational maps between the points of P and C . Together with [4], this method yields an algorithm to compute the genus of C , and if the genus is zero, the rational parametric equations for C . As a biproduct, this method also yields the implicit and parametric equations of a rational surface S containing the space curve C . The birational mappings of implicitly defined space curves find numerous applications in geometric modeling and computer graphics since they provide an efficient way of manipulating curves in space by processing curves in the plane. Additionally, having rational surfaces containing C yields a simple way of generating related families of rational space curves.

Algebraic algorithms are presented for generating the boundary of configuration space obstacles arising from the motion of a sphere among obstacles. The boundaries of the obstacles are given by patches of algebraic surfaces. Algorithms are given for both implicit and parametric surface patches. Both convex and nonconvex obstacles are considered. In the case of convex obstacles, the topology of convolution faces is the same as the adjacency graph of faces, edges, and vertices of the obstacle. Further, there are no redundancies in the convolution faces. Redundancies on the convolution can occur in the case of nonconvex obstacles. It is possible to detect these redundancies from the the intersections and self-intersections of convolution faces. Simple solids are also considered.>

We present algebraic algorithms to generate the boundary of configuration space obstacles arising from the translatory motion of objects amongst obstacles. In particular we consider obtaining compliant motion paths where a curved convex object with fixed orientation moves in continuous contact with the boundary of curved convex obstacles in three Dimensions. Both the boundaries of the objects and obstacles are given by patches of algebraic surfaces. We also give a method to obtain approximate geodesic paths on convex C-space obstacles with algebraic boundary surfaces.

We present algebraic algorithms to generate the boundary of planar configuration space obstacles arising from the translatory motion of objects amongst obstacles. Both the boundaries of the objects and obstacles are given by segments of algebraic curves.