This is an erratum for the article “Lifted Surfacing of Generalized Sweep Volumes” published in ACM Trans. Graph. 44, 6, Article 249 (December 2025), 17 pages.

We present a new method for simplifying the topology of a 3D shape. Unlike existing methods that either remove all topological features or offer indirect control over the target topology, our method aims at exactly preserving the user-prescribed numbers of topological features of each type (e.g., components, handles, and voids), while making minimal geometric changes. Guided by persistent homology , our method removes features with low persistence by performing either cutting or filling. This is achieved by an algorithm for computing candidate cuts and fills that remove only low-persistence features, an efficient algorithm for selecting an optimal subset of candidates by computing a weighted independent set, and an iterative framework that alternates between candidate computation and selection. Our method is shown to be highly successful in achieving the prescribed topology on a large test suite involving many complex 3D shapes and target topologies.

Computing the boundary surface of the 3D volume swept by a rigid or deforming solid remains a challenging problem in geometric modeling. Existing approaches are often limited to sweeping rigid shapes, cannot guarantee a watertight surface, or struggle with modeling the intricate geometric features (e.g., sharp creases and narrow gaps) and topological features (e.g., interior voids). We make the observation that the sweep boundary is a subset of the projection of the intersection of two implicit surfaces in a higher dimension, and we derive a characterization of the subset using winding numbers. These insights lead to a general algorithm for any sweep represented as a smooth time-varying implicit function satisfying a genericity assumption, and it produces a watertight and intersection-free surface that better approximates the geometric and topological features than existing methods.

Surface reconstruction from points is a fundamental problem in computer graphics. While numerous methods have been proposed, it remains challenging to reconstruct from sparse and non-uniform point distributions, particularly when normals are absent. We present a robust and scalable method for reconstructing an implicit surface from points without normals. By exploring the locality of natural neighborhoods, we propose local reformulations of a previous global method, known for its ability to surface sparse points but high computational cost, thereby significantly improving its scalability while retaining its robustness. Experiments show that our method achieves comparable speed to existing reconstruction methods on large inputs while producing fewer artifacts in under-sampled regions.

We present a method for generating a simplicial (e.g., triangular or tetrahedral) grid to enable adaptive discretization of implicit shapes defined by a vector function. Such shapes, which we call implicit complexes, are generalizations of implicit surfaces and useful for representing non-smooth and non-manifold structures. While adaptive grid generation has been extensively studied for polygonizing implicit surfaces, few methods are designed for implicit complexes. Our method can generate adaptive grids for several implicit complexes, including arrangements of implicit surfaces, CSG shapes, material interfaces, and curve networks. Importantly, our method adapts the grid to the geometry of not only the implicit surfaces but also their lower-dimensional intersections. We demonstrate how our method enables efficient and detail-preserving discretization of non-trivial implicit shapes.

Abstract Medial axis (MA) is a classical shape descriptor in graphics and vision. The practical utility of MA, however, is hampered by its sensitivity to boundary noise. To prune unwanted branches from MA, many definitions of significance measures over MA have been proposed. However, pruning MA using these measures often comes at the cost of shrinking desirable MA branches and losing shape features at fine scales. We propose a novel significance measure that addresses these shortcomings. Our measure is derived from a variational pruning process, where the goal is to find a connected subset of MA that includes as many points that are as parallel to the shape boundary as possible. We formulate our measure both in the continuous and discrete settings, and present an efficient algorithm on a discrete MA. We demonstrate on many examples that our measure is not only resistant to boundary noise but also excels over existing measures in preventing MA shrinking and recovering features across scales.

Tree-like structures are common, naturally occurring objects that are of interest to many fields of study, such as plant science and biomedicine. Analysis of these structures is typically based on skeletons extracted from captured data, which often contain spurious cycles that need to be removed. We propose a dynamic programming algorithm for solving the NP-hard tree recovery problem formulated by (Estrada et al. 2015), which seeks a least-cost partitioning of the graph nodes that yields a directed tree. Our algorithm finds the optimal solution by iteratively contracting the graph via node-merging until the problem can be trivially solved. By carefully designing the merging sequence, our algorithm can efficiently recover optimal trees for many real-world data where (Estrada et al. 2015) only produces sub-optimal solutions. We also propose an approximate variant of dynamic programming using beam search, which can process graphs containing thousands of cycles with significantly improved optimality and efficiency compared with (Estrada et al. 2015).

Computing injective maps with low distortions is a long-standing problem in computer graphics. Such maps are particularly challenging to obtain in the presence of positional constraints, because an injective initial map is often not available. Recently, several energies were proposed and shown to be highly successful in optimizing injectivity from non-injective initial maps while satisfying positional constraints. However, minimizing these energies tends to produce elements with significant isometric distortions. This paper presents simple variants of these energies that retain their desirable traits while promoting isometry. While our method is not guaranteed to provide an injective map, we observe that, on large-scale 2D and 3D data sets, minimizing the proposed isometric variants results in a similar level of success in recovering injectivity as the original energies but a significantly lower isometric distortion.

Abstract We present a method for removing unwanted topological features (e.g., islands, handles, cavities) from a sequence of shapes where each shape is nested in the next. Such sequences can be found in nature, such as a multi‐layered material or a growing plant root. Existing topology simplification methods are designed for single shapes, and applying them independently to shapes in a sequence may lose the nesting property. We formulate the nesting‐constrained simplification task as an optimal labelling problem on a set of candidate shape deletions (“cuts”) and additions (“fills”). We explored several optimization strategies, including a greedy heuristic that sequentially propagates labels, a state‐space search algorithm that is provably optimal, and a beam‐search variant with controllable complexity. Evaluation on synthetic and real‐world data shows that our method is as effective as single‐shape simplification methods in reducing topological complexity and minimizing geometric changes, and it additionally ensures nesting. Also, the beam‐search strategy is found to strike the best balance between optimality and efficiency.

Implicit surface networks, such as arrangements of implicit surfaces and materials interfaces, are used for modeling piecewise smooth or partitioned shapes. However, accurate and numerically robust algorithms for discretizing either structure on a grid are still lacking. We present a unified approach for computing both types of surface networks for piecewise linear functions defined on a tetrahedral grid. Both algorithms are guaranteed to produce a correct combinatorial structure for any number of functions. Our main contribution is an exact and efficient method for partitioning a tetrahedron using the level sets of linear functions defined by barycentric interpolation. To further improve performance, we designed look-up tables to speed up processing of tetrahedra involving few functions and introduced an efficient algorithm for identifying nested 3D regions.

Feature lines are important geometric cues in characterizing the structure of a CAD model. Despite great progress in both explicit reconstruction and implicit reconstruction, it remains a challenging task to reconstruct a polygonal surface equipped with feature lines, especially when the input point cloud is noisy and lacks faithful normal vectors. In this paper, we develop a multistage algorithm, named RFEPS , to address this challenge. The key steps include (1) denoising the point cloud based on the assumption of local planarity, (2) identifying the feature-line zone by optimization of discrete optimal transport, (3) augmenting the point set so that sufficiently many additional points are generated on potential geometry edges, and (4) generating a polygonal surface that interpolates the augmented point set based on restricted power diagram. We demonstrate through extensive experiments that RFEPS, benefiting from the edge-point augmentation and the feature preserving explicit reconstruction, outperforms state of the art methods in terms of the reconstruction quality, especially in terms of the ability to reconstruct missing feature lines.

Injective parameterizations of triangulated meshes are critical across applications but remain challenging to compute. Existing algorithms to find injectivity either require initialization from an injective starting state, which is currently only possible without positional constraints, or else can only prevent triangle inversion, which is insufficient to ensure injectivity. Here we present, to our knowledge, the first algorithm for recovering a globally injective parameterization from an arbitrary non-injective initial mesh subject to stationary constraints. These initial meshes can be inverted, wound about interior vertices and/or overlapping. Our algorithm in turn enables globally injective mapping for meshes with arbitrary positional constraints. Our key contribution is a new energy, called smooth excess area (SEA), that measures non-injectivity in a map. This energy is well-defined across both injective and non-injective maps and is smooth almost everywhere, making it readily minimizable using standard gradient-based solvers starting from a non-injective initial state. Importantly, we show that maps minimizing SEA are guaranteed to be locally injective and almost globally injective, in the sense that the overlapping area can be made arbitrarily small. Analyzing SEA's behavior over a new benchmark set designed to test injective mapping, we find that optimizing SEA successfully recovers globally injective maps for 85% of the benchmark and obtains locally injective maps for 90%. In contrast, state-of-the-art methods for removing triangle inversion obtain locally injective maps for less than 6% of the benchmark, and achieve global injectivity (largely by chance as prior methods are not designed to recover it) on less than 4%.

We present a novel representation of solid models for shape design. Like Constructive Solid Geometry (CSG), the solid shape is constructed from a set of halfspaces without the need for an explicit boundary structure. Instead of using Boolean expressions as in CSG, the shape is defined by sparsely placed samples on the boundary of each halfspace. This representation, called Boundary-Sampled Halfspaces (BSH), affords greater agility and expressiveness than CSG while simplifying the reverse engineering process. We discuss theoretical properties of the representation and present practical algorithms for boundary extraction and conversion from other representations. Our algorithms are demonstrated on both 2D and 3D examples.

Mapping a source mesh into a target domain while preserving local injectivity is an important but highly non-trivial task. Existing methods either require an already-injective starting configuration, which is often not available, or rely on sophisticated solving schemes. We propose a novel energy form, called Total Lifted Content (TLC), that is equipped with theoretical properties desirable for injectivity optimization. By lifting the simplices of the mesh into a higher dimension and measuring their contents (2D area or 3D volume) there, TLC is smooth over the entire embedding space and its global minima are always injective. The energy is simple to minimize using standard gradient-based solvers. Our method achieved 100% success rate on an extensive benchmark of embedding problems for triangular and tetrahedral meshes, on which existing methods only have varied success.

We present a novel algorithm for simplifying the topology of a 3D shape, which is characterized by the number of connected components, handles, and cavities. Existing methods either limit their modifications to be only cutting or only filling, or take a heuristic approach to decide where to cut or fill. We consider the problem of finding a globally optimal set of cuts and fills that achieve the simplest topology while minimizing geometric changes. We show that the problem can be formulated as graph labelling, and we solve it by a transformation to the Node-Weighted Steiner Tree problem. When tested on examples with varying levels of topological complexity, the algorithm shows notable improvement over existing simplification methods in both topological simplicity and geometric distortions.

We propose a new method for reconstructing an implicit surface from an un-oriented point set. While existing methods often involve non-trivial heuristics and require additional constraints, such as normals or labelled points, we introduce a direct definition of the function from the points as the solution to a constrained quadratic optimization problem. The definition has a number of appealing features: it uses a single parameter (parameter-free for exact interpolation), applies to any dimensions, commutes with similarity transformations, and can be easily implemented without discretizing the space. More importantly, the use of a global smoothness energy allows our definition to be much more resilient to sampling imperfections than existing methods, making it particularly suited for sparse and non-uniform inputs.

Abstract In this work we present the first algorithm for restoring consistency between curve networks on non‐parallel cross‐sections. Our method addresses a critical but overlooked challenge in the reconstruction process from cross‐sections that stems from the fact that cross‐sectional slices are often generated independently of one another, such as in interactive volume segmentation. As a result, the curve networks on two non‐parallel slices may disagree where the slices intersect, which makes these cross‐sections an invalid input for surfacing. We propose a method that takes as input an arbitrary number of non‐parallel slices, each partitioned into two or more labels by a curve network, and outputs a modified set of curve networks on these slices that are guaranteed to be consistent. We formulate the task of restoring consistency while preserving the shape of input curves as a constrained optimization problem, and we propose an effective solution framework. We demonstrate our method on a data‐set of complex multi‐labeled input cross‐sections. Our technique efficiently produces consistent curve networks even in the presence of large errors.

We present a novel algorithm for computing the medial axes of 3D shapes. We make the observation that the medial axis of a voxel shape can be simply yet faithfully approximated by the interior Voronoi diagram of the boundary vertices, which we call the voxel core. We further show that voxel cores can approximate the medial axes of any smooth shape with homotopy equivalence and geometric convergence. These insights motivate an algorithm that is simple, efficient, numerically stable, and equipped with theoretical guarantees. Compared with existing voxel-based methods, our method inherits their simplicity but is more scalable and can process significantly larger inputs. Compared with sampling-based methods that offer similar theoretical guarantees, our method produces visually comparable results but more robustly captures the topology of the input shape.

We present an algorithm for segmenting a mesh into patches whose boundaries are aligned with prominent ridge and valley lines of the shape. Our key insight is that this problem can be formulated as correlation clustering (CC), a graph partitioning problem originating from the data mining community. The formulation lends two unique advantages to our method over existing segmentation methods. First, since CC is non-parametric, our method has few parameters to tune. Second, as CC is governed by edge weights in the graph, our method offers users direct and local control over the segmentation result. Our technical contributions include the construction of the weighted graph on which CC is defined, a strategy for rapidly computing CC on this graph, and an interactive tool for editing the segmentation. Our experiments show that our method produces qualitatively better segmentations than existing methods on a wide range of inputs.

We present FlowRep , an algorithm for extracting descriptive compact 3D curve networks from meshes of free-form man-made shapes. We infer the desired compact curve network from complex 3D geometries by using a series of insights derived from perception, computer graphics, and design literature. These sources suggest that visually descriptive networks are cycle-descriptive , i.e their cycles unambiguously describe the geometry of the surface patches they surround. They also indicate that such networks are designed to be projectable , or easy to envision when observed from a static general viewpoint; in other words, 2D projections of the network should be strongly indicative of its 3D geometry. Research suggests that both properties are best achieved by using networks dominated by flowlines , surface curves aligned with principal curvature directions across anisotropic regions and strategically extended across sharp-features and isotropic areas. Our algorithm leverages these observation in the construction of a compact descriptive curve network. Starting with a curvature aligned quad dominant mesh we first extract sequences of mesh edges that form long, well-shaped and reliable flowlines by leveraging directional similarity between nearby meaningful flowline directions We then use a compact subset of the extracted flowlines and the model's sharp-feature, or trim, curves to form a sparse, projectable network which describes the underlying surface. We validate our method by demonstrating a range of networks computed from diverse inputs, using them for surface reconstruction, and showing extensive comparisons with prior work and artist generated networks.

In this work we present the first algorithm for reconstructing multi-labeled material interfaces the allows for explicit topology control. Our algorithm takes in a set of 2D cross-sectional slices (not necessarily parallel), each partitioned by a curve network into labeled regions representing different material types. For each label, the user has the option to constrain the number of connected components and genus. Our algorithm is able to not only produce a material interface that interpolates the curve networks but also simultaneously satisfy the topological requirements. Our key innovation is defining a space of topology-varying material interfaces, which extends the family of level sets in a scalar function, and developing discrete methods for sampling distinct topologies in this space. Besides specifying topological constraints, the user can steer the algorithm interactively, such as by scribbling. We demonstrate, on synthetic and biological shapes, how our algorithm opens up new opportunities for topology-aware modeling in the multi-labeled context.

In the analysis of histopathological images, both holistic (e.g., architecture features) and local appearance features demonstrate excellent performance, while their accuracy may vary dramatically when providing different inputs. This motivates us to investigate how to fuse results from these features to enhance the accuracy. Particularly, we employ content-based image retrieval approaches to discover morphologically relevant images for image-guided diagnosis, using holistic and local features, both of which are generated from the cell detection results by a stacked sparse autoencoder. Because of the dramatically different characteristics and representations of these heterogeneous features (i.e., holistic and local), their results may not agree with each other, causing difficulties for traditional fusion methods. In this paper, we employ a graph-based query-specific fusion approach where multiple retrieval results (i.e., rank lists) are integrated and reordered based on a fused graph. The proposed method is capable of combining the strengths of local or holistic features adaptively for different inputs. We evaluate our method on a challenging clinical problem, i.e., histopathological image-guided diagnosis of intraductal breast lesions, and it achieves 91.67% classification accuracy on 120 breast tissue images from 40 patients.

While playing a fundamental role in shape understanding, the medial axis is known to be sensitive to small boundary perturbations. Methods for pruning the medial axis are usually guided by some measure of significance. The majority of significance measures over the medial axes of 3D shapes are locally defined and hence unable to capture the scale of features. We introduce a global significance measure that generalizes in 3D the classical Erosion Thickness (ET) measure over the medial axes of 2D shapes. We give precise definition of ET in 3D, analyze its properties, and present an efficient approximation algorithm with bounded error on a piece-wise linear medial axis. Experiments showed that ET outperforms local measures in differentiating small boundary noise from prominent shape features, and it is significantly faster to compute than existing global measures. We demonstrate the utility of ET in extracting clean, shape-revealing and topology-preserving skeletons of 3D shapes.

In this work we detail the first algorithm that provides topological control during surface reconstruction from an input set of planar cross-sections. Our work has broad application in a number of fields including surface modeling and biomedical image analysis, where surfaces of known topology must be recovered. Given curves on arbitrarily oriented cross-sections, our method produces a manifold interpolating surface that exactly matches a user-specified genus. The key insight behind our approach is to formulate the topological search as a divide-and-conquer optimization process which scores local sets of topologies and combines them to satisfy the global topology constraint. We further extend our method to allow image data to guide the topological search, achieving even better results than relying on the curves alone. By simultaneously satisfying both geometric and topological constraints, we are able to produce accurate reconstructions with fewer input cross-sections, hence reducing the manual time needed to extract the desired shape.

Abstract We present an interactive method for mesh segmentation that is inspired by the classical live‐wire interaction for image segmentation. The core contribution of the work is the definition and computation of wires on surfaces that are likely to lie at segment boundaries. We define wires as geodesics in a new tensor‐based anisotropic metric, which improves upon previous metrics in stability and feature‐awareness. We further introduce a simple but effective mesh embedding approach that allows geodesic paths in an anisotropic path to be computed efficiently using existing algorithms designed for Euclidean geodesics. Our tool is particularly suited for delineating segmentation boundaries that are aligned with features or curvature directions, and we demonstrate its use in creating artist‐guided segmentations.

Parallel vectors (PV), the loci where two vector fields are parallel, are commonly used to represent curvilinear features in 3D for data visualization. Methods for extracting PV usually operate on a 3D grid and start with detecting seed points on a cell face. We propose, to the best of our knowledge, the first provably correct test that determines the parity of the number of PV points on a cell face. The test only needs to sample along the face boundary and works for any choice of the two vector fields. A discretization of the test is described, validated, and compared with existing tests that are also based on boundary sampling. The test can guide PV-extraction algorithms to ensure closed curves wherever the input fields are continuous, which we exemplify in extracting ridges and valleys of scalar functions.

Abstract We present an algorithm for obtaining a triangulation of multiple, non‐planar 3D polygons. The output minimizes additive weights, such as the total triangle areas or the total dihedral angles between adjacent triangles. Our algorithm generalizes a classical method for optimally triangulating a single polygon. The key novelty is a mechanism for avoiding non‐manifold outputs for two and more input polygons without compromising optimality. For better performance on real‐world data, we also propose an approximate solution by feeding the algorithm with a reduced set of triangles. In particular, we demonstrate experimentally that the triangles in the Delaunay tetrahedralization of the polygon vertices offer a reasonable trade off between performance and optimality.

Generating surfaces from 3D curve networks has been a longstanding problem in computer graphics. Recent attention to this area has resurfaced as a result of new sketch based modeling systems. In this work we present a new algorithm for finding cycles that bound surface patches. Unlike prior art in this area, the output of our technique is unrestricted, generating both manifold and non-manifold geometry with arbitrary genus. The novel insight behind our method is to formulate our problem as finding local mappings at the vertices and curves of our network, where each mapping describes how incident curves are grouped into cycles. This approach lends us the efficiency necessary to present our system in an interactive design modeler, whereby the user can adjust patch constraints and change the manifold properties of curves while the system automatically re-optimizes the solution.

Field design has wide applications in graphics and visualization. One of the main challenges in field design has been how to provide users with both intuitive control over the directions in the field on one hand and robust management of its topology on the other hand. In this paper, we present a design paradigm for line fields that addresses this challenge. Rather than asking users to input all singularities as in most methods that offer topology control, we let the user provide a partitioning of the domain and specify simple flow patterns within the partitions. Represented by a selected set of harmonic functions, the elementary fields within the partitions are then combined to form continuous fields with rich appearances and well-determined topology. Our method allows a user to conveniently design the flow patterns while having precise and robust control over the topological structure. Based on the method, we developed an interactive tool for designing line fields from images, and demonstrated the utility of the fields in image stylization.

Analysis of gene expression patterns in brain images obtained from high-throughput in situ hybridization requires accurate and consistent annotations of anatomical regions/subregions. Such annotations are obtained by mapping an anatomical atlas onto the gene expression images through intensity- and/or landmark-based registration methods or deformable model-based segmentation methods. Due to the complex appearance of the gene expression images, these approaches require a pre-processing step to determine landmark correspondences in order to incorporate landmark-based geometric constraints. In this paper, we propose a novel method for landmark-constrained, intensity-based registration without determining landmark correspondences a priori. The proposed method performs dense image registration and identifies the landmark correspondences, simultaneously, using a single higher-order Markov Random Field model. In addition, a machine learning technique is used to improve the discriminating properties of local descriptors for landmark matching by projecting them in a Hamming space of lower dimension. We qualitatively show that our method achieves promising results and also compares well, quantitatively, with the expert's annotations, outperforming previous methods.

An accurate labeling of a multi-part, complex anatomical structure (e.g., brain) is required in order to compare data across images for spatial analysis. It can be achieved by fitting an object-specific geometric atlas that is constructed using a partitioned, high-resolution deformable mesh and tagging each of its polygons with a region label. Subdivision meshes have been used to construct such an atlas because they can provide a compact representation of a partitioned, multi-resolution, object-specific mesh structure using only a few control points. However, automated fitting of a subdivision mesh-based geometric atlas to an anatomical structure in an image is a difficult problem and has not been sufficiently addressed. In this paper, we propose a novel Markov Random Field-based method for fitting a planar, multi-part subdivision mesh to anatomical data. The optimal fitting of the atlas is obtained by determining the optimal locations of the control points. We also tackle the problem of landmark matching in tandem with atlas fitting by constructing a single graphical model to impose pose-invariant, landmark-based geometric constraints on atlas deformation. The atlas deformation is also governed by additional constraints imposed by the mesh's geometric properties and the object boundary. We demonstrate the potential of the proposed method on the difficult problem of segmenting a mouse brain and its interior regions in gene expression images which exhibit large intensity and shape variability. We obtain promising results when compared with manual annotations and prior methods.

Extremal surfaces are a class of implicit surfaces that have been found useful in a variety of geometry reconstruction applications. Compared to iso-surfaces, extremal surfaces are particularly challenging to construct in part due to the presence of boundaries and the lack of a consistent orientation. We present a novel, grid-based algorithm for constructing polygonal approximations of extremal surfaces that may be open or unorientable. The algorithm is simple to implement and applicable to both uniform and adaptive grid structures. More importantly, the resulting discrete surface preserves the structural property of the extremal surface in a grid-independent manner. The algorithm is applied to extract ridge surfaces from intensity volumes and reconstruct surfaces from point sets with unoriented normals.

Abstract Thinning is a commonly used approach for computing skeleton descriptors. Traditional thinning algorithms often have a simple, iterative structure, yet producing skeletons that are overly sensitive to boundary perturbations. We present a novel thinning algorithm, operating on objects represented as cell complexes, that preserves the simplicity of typical thinning algorithms but generates skeletons that more robustly capture global shape features. Our key insight is formulating a skeleton significance measure, calledmedial persistence, which identify skeleton geometry at various dimensions (e.g., curves or surfaces) that represent object parts with different anisotropic elongations (e.g., tubes or plates). The measure is generally defined in any dimensions, and can be easily computed using a single thinning pass. Guided by medial persistence, our algorithm produces a family of topology and shape preserving skeletons whose shape and composition can be flexible controlled by desired level of medial persistence.

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.

Associating specific gene activity with functional locations in the brain results in a greater understanding of the role of the gene. To perform such an association for the more than 20 000 genes in the mammalian genome, reliable automated methods that characterize the distribution of gene expression in relation to a standard anatomical model are required. In this paper, we propose a new automatic method that results in the segmentation of gene expression images into distinct anatomical regions in which the expression can be quantified and compared with other images. Our contribution is a novel hybrid atlas that utilizes a statistical shape model based on a subdivision mesh, texture differentiation at region boundaries, and features of anatomical landmarks to delineate boundaries of anatomical regions in gene expression images. This atlas, which provides a common coordinate system for internal brain data, is being used to create a searchable database of gene expression patterns in the adult mouse brain. Our framework annotates the images about four times faster and has achieved a median spatial overlap of up to 0.92 compared with expert segmentation in 64 images tested. This tool is intended to help scientists interpret large-scale gene expression patterns more efficiently.

Dual Contouring (DC) is a feature-preserving isosurfacing method that extracts crack-free surfaces from both uniform and adaptive octree grids. We present an extension of DC that further guarantees that the mesh generated is a manifold even under adaptive simplification. Our main contribution is an octree-based topology-preserving vertex-clustering algorithm for adaptive contouring. The contoured surface generated by our method contains only manifold vertices and edges, preserves sharp features, and possesses much better adaptivity than those generated by other isosurfacing methods under topologically safe simplification.

Massive amounts of data are being generated in an effort to represent for the brain the expression of all genes at cellular resolution. Critical to exploiting this effort is the ability to place these data into a common frame of reference. Here we have developed a computational method for annotating gene expression patterns in the context of a digital atlas to facilitate custom user queries and comparisons of this type of data. This procedure has been applied to 200 genes in the postnatal mouse brain. As an illustration of utility, we identify candidate genes that may be related to Parkinson disease by using the expression of a dopamine transporter in the substantia nigra as a search query pattern. In addition, we discover that transcription factor Rorb is down-regulated in the barrelless mutant relative to control mice by quantitative comparison of expression patterns in layer IV somatosensory cortex. The semi-automated annotation method developed here is applicable to a broad spectrum of complex tissues and data modalities.

Constructing a function that interpolates a set of values defined at vertices of a mesh is a fundamental operation in computer graphics. Such an interpolant has many uses in applications such as shading, parameterization and deformation. For closed polygons, mean value coordinates have been proven to be an excellent method for constructing such an interpolant. In this paper, we generalize mean value coordinates from closed 2D polygons to closed triangular meshes. Given such a mesh P , we show that these coordinates are continuous everywhere and smooth on the interior of P . The coordinates are linear on the triangles of P and can reproduce linear functions on the interior of P . To illustrate their usefulness, we conclude by considering several interesting applications including constructing volumetric textures and surface deformation.

As the logical next step after sequencing the mouse genome, biologists have developed laboratory methods for rapidly determining where each of the 30K genes in the mouse genome is synthesizing protein. Applying these methods to the mouse brain, biologists are currently generating large numbers of 2D cross-sectional images that record the expression pattern for each gene in the mouse genome. In this paper, we describe the structure of a geometric database for the mouse brain that allows biologists to organize and search this gene expression data. The central component of this database is an atlas that explicitly partitions the mouse brain into key anatomical regions. This atlas is represented as a Catmull-Clark subdivision mesh with anatomical regions separated by a network of B-spline crease curves. New gene expression images are added to the database by deforming this atlas onto each image using techniques developed for fitting subdivision surfaces to scatter data. Due to this partitioning of the subdivision mesh, user queries comparing expression data between various genes can be restricted to anatomical regions without difficulty while the multi-resolution structure of the subdivision mesh allows these queries to be processed efficiently.

This paper describes a new method for contouring a signed grid whose edges are tagged by Hermite data (i.e; exact intersection points and normals). This method avoids the need to explicitly identify and process "features" as required in previous Hermite contouring methods. Using a new, numerically stable representation for quadratic error functions, we develop an octree-based method for simplifying contours produced by this method. We next extend our contouring method to these simpli£ed octrees. This new method imposes no constraints on the octree (such as being a restricted octree) and requires no "crack patching". We conclude with a simple test for preserving the topology of the contour during simplification.