Interpreting 3D information based on 2D slices of the data is notoriously difficult. Yet in the medical field makes intervention choices based on radiological scans on a daily basis. Volumetric reconstructions of these data sets, via voxel clouds and surface meshes can reduce the cognitive complexity of this task. However, creating these reconstructions requires extensive software training and time, often on the part of a technician separate from the treatment team. To shorten this process, we present a system designed for radiologists and surgeons on the care team. We integrate tools familiar to these experts and provide a stereoscopic environment for quick spatial comprehension and intuitive data curation. Based on the feedback from oncology collaborators on the system in its current state, it is not only helpful for communicating tumor progression but, additionally shows promise as a teaching tool to assist with building skills for traditional interpretation of radiology images.

Digital Elevation Models (DEMs) are crucial for modeling and analyzing terrestrial environments, but voids in DEMs can compromise their downstream use. Diff-DEM is a self-supervised method for filling DEM voids that leverages a Denoising Diffusion Probabilistic Model (DDPM). Conditioned on a void-containing DEM, the DDPM acts as a transition kernel in the diffusion reversal, progressively reconstructing a sharp and accurate DEM. Both qualitative and quantitative assessments demonstrate Diff-DEM outperforms existing DEM inpainting, including Generative Adversarial Network (GAN) methods, Inverse Distance Weighting (IDW), Kriging, LR B-spline, and Perona-Malik diffusion. The comparison is on Gavriil’s and on our benchmark that expands Gavriil’s dataset from 63 to 217 full-size (5051 × 5051) 10-meter GeoTIFF images sourced from the Norwegian Mapping Authority; and from 50 DEMs to three groups of 1k each of increasing void size. Code and dataset: https://github.com/kylelo/Diff-DEM.

Abstract To overcome the well‐known shape deficiencies of bi‐cubic subdivision surfaces, Evolving Guide subdivision (EG subdivision) generalizes C2 bi‐quartic (bi‐4) splines that approximate a sequence of piecewise polynomial surface pieces near extraordinary points. Unlike guided subdivision, which achieves good shape by following a guide surface in a two‐stage, geometry‐dependent process, EG subdivision is defined by five new explicit subdivision rules. While formally only C1 at extraordinary points, EG subdivision applied to an obstacle course of inputs generates surfaces without the oscillations and pinched highlight lines typical for Catmull‐Clark subdivision. EG subdivision surfaces join C2 with bi‐3 surface pieces obtained by interpreting regular sub‐nets as bi‐cubic tensor‐product splines and C2 with adjacent EG surfaces. The EG subdivision control net surrounding an extraordinary node can have the same structure as Catmull‐Clark subdivision: two rings of 4‐sided facets around each extraordinary nodes so that extraordinary nodes are separated by at least one regular node.

Abstract The idea of improving multi‐sided piecewise polynomial surfaces, by explicitly prescribing their behavior at a central surface point, allows for decoupling shape finding from enforcing local smoothness constraints. Quadratic‐Attraction Subdivision determines the completion of a quadratic expansion at the central point to attract a differentiable subdivision surface towards bounded curvature, with good shape also in‐the‐large.

For control nets outlining a large class of topological polyhedra, not just tensor-product grids, bi-cubic polyhedral splines form a piecewise polynomial, first-order differentiable space that associates one function with each vertex. Akin to tensor-product splines, the resulting smooth surface approximates the polyhedron. Admissible polyhedral control nets consist of quadrilateral faces in a grid-like layout, star-configuration where n ≠ 4 quadrilateral faces join around an interior vertex, n -gon configurations, where 2n quadrilaterals surround an n -gon, polar configurations where a cone of n triangles meeting at a vertex is surrounded by a ribbon of n quadrilaterals, and three types of T-junctions where two quad-strips merge into one. The bi-cubic pieces of a polyhedral spline have matching derivatives along their break lines, possibly after a known change of variables. The pieces are represented in Bernstein-Bézier form with coefficients depending linearly on the polyhedral control net, so that evaluation, differentiation, integration, moments, and so on, are no more costly than for standard tensor-product splines. Bi-cubic polyhedral splines can be used both to model geometry and for computing functions on the geometry. Although polyhedral splines do not offer nested refinement by refinement of the control net, polyhedral splines support engineering analysis of curved smooth objects. Coarse nets typically suffice since the splines efficiently model curved features. Algorithm 1032 is a C++ library with input-output example pairs and an IGES output choice.

Abstract Point‐Augmented Subdivision (PAS) replaces complex geometry‐dependent guided subdivision, known to yield high‐quality surfaces, by explicit subdivision formulas that yield similarly‐good limit surfaces and are easy to implement using any subdivision infrastructure: map the control net d augmented by a fixed central limit point C, to a finer net (d̃,C) = M(d,C), where the subdivision matrix M is assembled from the provided stencil Tables. Point‐augmented bi‐cubic subdivision improves the state of the art so that bi‐cubic subdivision surfaces can be used in high‐end geometric design: the highlight line distribution for challenging configurations lacks the shape artifacts usually associated with explicit iterative generalized subdivision operators near extraordinary points. Five explicit formulas define Point‐augmented bi‐cubic subdivision in addition to uniform B‐spline knot insertion. Point‐augmented bi‐cubic subdivision comes in two flavors, either generating a sequence of C2‐joined surface rings (PAS2) or C1‐joined rings (PAS1) that have fewer pieces.

Abstract Polyhedral modeling and re‐meshing algorithms use T‐junctions to add or remove feature lines in a quadrilateral mesh. In many ways this is akin to adaptive knot insertion in a tensor‐product spline, but differs in that the designer or meshing algorithm does not necessarily protect the consistent combinatorial structure that is required to interpret the resulting quad‐dominant mesh as the control net of a hierarchical spline – and so associate a smooth surface with the mesh as in the popular tensor‐product spline paradigm. While G‐splines for multi‐sided holes or generalized subdivision can, in principle, convert quad‐dominant meshes with T‐junctions into smooth surfaces, they do not preserve the two preferred directions and so cause visible shape artifacts. Only recently have n‐gons with T‐junctions (T‐gons) in unstructured quad‐dominant meshes been recognized as a distinct challenge for generalized splines. This paper makes precise the notion of locally quad‐dominant mesh as quad‐meshes including τ‐nets, i.e. T‐gons surrounded by quads; and presents the first high‐quality G‐spline construction that can use τ‐nets as control nets for spline surfaces suitable, e.g., for automobile outer surfaces. Remarkably, T‐gons can be neighbors, separated by only one quad, both of T‐gons and of points where many quads meet. A τ‐net surface cap consists of 16 polynomial pieces of degree (3,5) and is refinable in a way that is consistent with the surrounding surface. An alternative, everywhere bi‐3 cap is not formally smooth, but achieves the same high‐quality highlight line distribution.

Abstract Converting quadrilateral meshes to smooth manifolds, guided subdivision offers a way to combine the good highlight line distribution of recent G‐spline constructions with the refinability of subdivision surfaces. This avoids the complex refinement of G‐spline constructions and the poor shape of standard subdivision. Guided subdivision can then be used both to generate the surface and hierarchically compute functions on the surface. Specifically, we present a C2 subdivision algorithm of polynomial degree bi‐6 and a curvature bounded algorithm of degree bi‐5. We prove that the common eigenstructure of this class of subdivision algorithms is determined by their guide and demonstrate that their eigenspectrum (speed of contraction) can be adjusted without harming the shape. For practical implementation, a finite number of subdivision steps can be completed by a high‐quality cap. Near irregular points this allows leveraging standard polynomial tools both for rendering of the surface and for approximately integrating functions on the surface.

For configurations of point-sets that are pairwise constrained by distance intervals, the EASAL software implements a suite of algorithms that characterize the structure and geometric properties of the configuration space. The algorithms generate, describe, and explore these configuration spaces using generic rigidity properties, classical results for stratification of semi-algebraic sets, and new results for efficient sampling by convex parametrization. The article reviews the key theoretical underpinnings, major algorithms, and their implementation. The article outlines the main applications such as the computation of free energy and kinetics of assembly of supramolecular structures or of clusters in colloidal and soft materials. In addition, the article surveys select experimental results and comparisons.

T-junctions occur where surface strips start or terminate. This paper develops a new way to create smooth piecewise polynomial free-form spline surfaces from quad-meshes that include T-junctions. All mesh nodes are interpreted as control points of GT-splines, that is, geometrically smoothly joined piecewise polynomials. GT-splines are akin to and compatible with B-splines and cover simple T-junctions by two polynomial pieces of degree bi-4 and more complex ones by four such patches. They complement multi-sided surface constructions in generating free-form surfaces with adaptive layout. Since GT-splines do not require a global coordination of knot intervals, GT-constructions are easy to deploy and can provide smooth surfaces with T-junctions where T-splines cannot have a smooth parameterization. GT-constructions display a uniform highlight linedistribution on input meshes where alternatives, such as Catmull-Clark subdivision, exhibit oscillations.

Abstract 'Class A surface’ is a term in the automotive design industry, describing spline surfaces with aesthetic, non‐oscillating highlight lines. Tensor‐product B‐splines of degree bi‐3 (bicubic) are routinely used to generate smooth design surfaces and are often the de facto standard for downstream processing. To bridge the gap, this paper explores and gives a concrete suggestion, how to achieve good highlight line distributions for irregular bi‐3 tensor‐product patch layout by allowing, along some seams, a slight mismatch of normals below the industry‐accepted tolerance of one tenth of a degree. Near the irregularities, the solution can be viewed as transforming a higher‐degree, high‐quality formally smooth surface into a bi‐3 spline surface with few pieces, sacrificing formal smoothness but qualitatively retaining the shape.

A curved or higher-order surface, such as spline patch or a Bézier patch, is rendered pixel-accurate if it displays neither polyhedral artifacts nor parametric distortion. This paper shows how to set the evaluation density for a patch just finely enough so that parametric surfaces render pixel-accurate in the standard graphics pipeline. The approach uses tight estimates, not of the size under screen-projection, but of the variance under screen projection between the exact surface and its triangulation. An implementation, using the GPU tessellation engine, runs at interactive rates comparable to standard rendering.

Abstract The paper develops a rational bi‐cubic G2 (curvature continuous) analogue of the non‐uniform polynomial C2 cubic B‐spline paradigm. These rational splines can exactly reproduce parts of multiple basic shapes, such as cyclides and quadrics, in one by default smoothly‐connected structure. The versatility of this new tool for processing exact geometry is illustrated by conceptual design from basic shapes.

We exhibit the essentially unique projective linear (rational linear) reparameterization for constructing Cssurfaces of genus g>0. Conversely, for quadrilaterals and isolated vertices of valence 8, we show constructively for s=1,2 that this map yields a projective linear spline space for surfaces of genus greater or equal to 1. This establishes the reparametrization to be the simplest possible transition map.

A key problem when interpolating a network of curves occurs at vertices: an algebraic condition called the vertex enclosure constraint must hold wherever an even number of curves meet. This paper recasts the constraint in terms of the local geometry of the curve network. This allows formulating a new geometric constraint, related to Euler's Theorem on local curvature, that implies the vertex enclosure constraint and is equivalent to it where four curve segments meet without forming an X.

Popular subdivision algorithms like Catmull-Clark and Loop are C 2 almost everywhere, but suffer from shape artifacts and reduced smoothness exactly near the so-called "extraordinary vertices" that motivate their use. Subdivision theory explains that inherently, for standard stationary subdivision algorithms, curvature-continuity and the ability to model all quadratic shapes requires a degree of at least bi-6. The existence of a simple-to-implement C 2 subdivision algorithm generating surfaces of good shape and piecewise degree bi-3 in the polar setting is therefore a welcome surprise. This paper presents such an algorithm, the underlying insights, and a detailed analysis. In bi-3 C 2 polar subdivision the weights depend, as in standard schemes, only on the valence, but the valence at one central polar vertex increases to match Catmull-Clark-refinement.

We convert any quad manifold mesh into an at least C¹ surface consisting of bi-cubic tensor-product splines with localized perturbations of degree bi-5 near non-4-valent vertices. There is one polynomial piece per quad facet, regardless of the valence of the vertices. Particular care is taken to derive simple formulas so that the surfaces are computed efficiently in parallel and match up precisely when computed independently on the GPU.

We present a fast algorithm for converting quad meshes on the GPU to smooth surfaces. Meshes with 12,000 input quads, of which 60% have one or more non-4-valent vertices, are converted, evaluated and rendered with 9times9 resolution per quad at 50 frames per second. The conversion reproduces bi-cubic splines wherever possible and closely mimics the shape of the Catmull-Clark subdivision surface by c-patches where a vertex has a valence different from 4. The smooth surface is piecewise polynomial and has well-defined normals everywhere. The evaluation avoids pixel dropout.

Abstract Polyhedral meshes consisting of triangles, quads, and pentagons and polar configurations cover all major sampling and modeling scenarios. We give an algorithm for efficient local, parallel conversion of such meshes to an everywhere smooth surface consisting of low‐degree polynomial pieces. Quadrilateral facets with 4‐valent vertices are ‘regular’ and are mapped to bi‐cubic patches so that adjacent bi‐cubics join C2 as for cubic tensor‐product splines. The algorithm can be implemented in the vertex and geometry shaders of the GPU pipeline and does not use the fragment shader. Its implementation in DirectX 10 achieves conversion plus rendering at 659 frames per second with 42.5 million triangles per second on input of a model of 1300 facets of which 60% are not regular.

We introduce and analyze an efficient reconstruction algorithm for FCC-sampled data. The reconstruction is based on the 6-direction box spline that is naturally associated with the FCC lattice and shares the continuity and approximation order of the triquadratic B-spline. We observe less aliasing for generic level sets and derive special techniques to attain the higher evaluation efficiency promised by the lower degree and smaller stencil-size of the C1 6-direction box spline over the triquadratic B-spline.

We complete and bring together two pairs of surface constructions that use polynomial pieces of degree (3,3) to associate a smooth surface with a mesh. The two pairs complement each other in that one extends the subdivisionmodeling paradigm, the other the NURBS patch approach to free-form modeling. Both Catmull-Clark [3] and polar subdivision [7] generalize bi-cubic spline subdivision. Together, they form a powerful combination for smooth object design: while Catmull-Clark subdivision is more suitable where few facets join, polar subdivision nicely models regions where many facets join, as when capping extruded features. We show how to easily combine the meshes of these two generalizations of bi-cubic spline subdivision. A related but different generalization of bi-cubic splines is to model non-tensor-product configurations by a finite set of smoothly connected bi-cubic patches. PCCM [12] does so for layouts where Catmull-Clark would apply. We show that a single NURBS patch can be used where polar subdivision would be applied. This spline is singularly parametrized, but, using a novel technique, we show that the surface is C1 and has bounded curvatures.

We describe and analyze a subdivision scheme that generalizes bicubic spline subdivision to control nets with polar structure. Such control nets appear naturally for surfaces with the combinatorial structure of objects of revolution and at points of high valence in subdivision meshes. The resulting surfaces are C 2 except at a finite number of isolated points where the surface is C 1 and the curvature is bounded.

A sequence of mesh manipulations that preserves the Euler invariant is called an Euler encoding. We propose new, efficient Euler encodings for primal and dual mesh refinement. The implementations are analyzed and compared to array-based, connectivity-free refinement and to reconstruction of the refined mesh.

A tight estimate on the maximum distance between a subdivision surface and its linear approximation is introduced to guide adaptive subdivision with guaranteed accuracy.

By organizing the control mesh of subdivision in texture memory so that irregularities occur strictly inside independently refinable fragment meshes, all major features of subdivision algorithms can be realized in the framework of highly parallel stream processing. Our implementation of Catmull-Clark subdivision as a GPU kernel in programmable graphics hardware can model features like semi-smooth creases and global boundaries; and a simplified version achieves near-realtime depth-five re-evaluation of moderate-sized subdivision meshes. The approach is easily adapted to other refinement patterns, such as Loop, Doo-Sabin or √3 and it allows for postprocessing with additional shaders.

Abstract Accurate and robust interference detection and ray‐tracing of subdivision surfaces requires safe linear approximations. Approximation of the limit surface by the subdivided control polyhedron can be both inaccurate and, due to the exponential growth of the number of facets, costly. This paper shows how a standard intersection hierarchy, such as an OBB tree, can be made safe and efficient for subdivision surface interference detection. The key is to construct, on the fly, optimally placed facets, whose spherical offsets tightly enclose the limit surface. The spherically offset facets can be locally subdivided and they can be efficiently intersected based on standard triangle‐triangle interference detection. Categories and Subject Descriptors (according to ACM CCS): I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling

4-3 direction subdivision combines quad and triangle meshes. On quad submeshes it applies a 4-direction alternative to Catmull-Clark subdivision and on triangle submeshes a modification of Loop's scheme. Remarkably, 4-3 surfaces can be proven to be C1 and have bounded curvature everywhere. In regular mesh regions, they are C2 and correspond to two closely-related box-splines of degree four. The box-spline in quad regions has a smaller stencil than Catmull-Clark and defines the unique scheme with a 3 × 3 stencil that can model constant features without ripples both aligned with the quad grid and diagonal to it. From a theoretical point of view, 4-3 subdivision near extraordinary points is remarkable in that the eigenstructure of the local subdivision matrix is easy to determine and a complete analysis is possible. Without tweaking the rules artificially to force a specific spectrum, the leading eigenvalues ordered by modulus of all local subdivision matrices are 1, 1/2, 1/2, 1/4 where the multiplicity of the eigenvalue 1/4 depends on the valence of the extraordinary point and the number of quads surrounding it. This implies equal refinement of the mesh, regardless of the number of neighbors of a mesh node.

To improve the visual quality of existing triangle-based art in realtime entertainment, such as computer games, we propose replacing flat triangles with curved patches and higher-order normal variation. At the hardware level, based only on the three vertices and three vertex normals of a given flat triangle, we substitute the geometry of a three-sided cubic Bezier patch for the triangle's flat geometry, and a quadratically varying normal for Gouraud shading. These curved point-normal triangles, or PN triangles, require minimal or no change to existing authoring tools and hardware designs while providing a smoother, though not necessarily everywhere tangent continuous, silhouette and more organic shapes. CR Categories: I.3.5 [surface representation, splines]: I.3.6--- graphics data structures Keywords: curved surface, PN Triangle, hardware, real-time, surface tessellation NSF NYI CCR-9457806, [email protected], [email protected], [email protected], [email protected] 1 Introduction ...

This paper presents a simple algorithm for associating a smooth, low-degree polynomial surface with triangulations whose extraordinary mesh nodes are separated by sufficiently many ordinary, 6-valent mesh nodes. Output surfaces are at least tangent continuous and are C 2 sufficiently far away from extraordinary mesh nodes; they consist of three-sided Bézier patches of degree 4. In particular, the algorithm can be used to skin a mesh generated by a few steps of Loop's generalization of three-direction box-spline subdivision.

Named after the title, the PCCM transformation is a simple, explicit algorithm that creates large, smoothly joining bicubic Nurbs patches from a refined Catmull-Clark subdivision mesh. The resulting patches are maximally large in the sense that one patch corresponds to one quadrilateral facet of the initial, coarsest quadrilateral mesh before subdivision. The patches join parametrically C2 and agree with the Catmull-Clark limit surface except in the immediate neighborhood of extraordinary mesh nodes; in such a neighborhood they join at least with tangent continuity and interpolate the limit of the extraordinary mesh node. The PCCM transformation integrates naturally with array-based implementations of subdivision surfaces.

We show how to efficiently smooth a polygon with an approximating spline that stays to one side of the polygon.We also show how to find a smooth spline path between two polygons that form a channel.Problems of this type arise in many physical motion planning tasks where not only forbidden regions have to be avoided but also a smooth traversal of tbe motion path is required.Both algorithms are based on a new tight and efficiently computable bound on the distance of a spline from its control polygon and employ only standard linear and quadratic ptogmmming techniques.

An explicit spline representation of smooth free-form surfaces is combined with a hierarchy of meshes to form the basis of an interactive sculpting environment.The environment offers localii hierarchical modeling at different levels of detail, direct surface manipulation, change of connectivity for extrusion and to form holes and bridges, and built-in tangent continuity across th& surface where wanted.The free-form surface is represented and can be exported either in NURBS form or as cubic triangular BCzier patches.Key characteristics of the approach are: (1) mesh pieces and surface pieces are related by strictly local averaging rules; (2) refinement rules depend only on direct, coarser-level ancestors and not on adjacent submeshes or patches; (3) submeshes at different levels look alike.The underlying data structure is a single winged-edge structure with additional pointem to support the hierarchy.Multiply refined regions may be directly adjacent to umefined regions, and mesh fragments at different levels of refinement can be connected.CR Categories: 1.

Combining a polynomial free-form surface representation with Gauss' divergence theorem allows efficient and exact calculation of the moments of the enclosed objects. For example, for an cubic representation, volume, center of mass, and the inertia tensor can be computed in seconds even for complex objects with serval thousand patches while change due to local modification of the surface geometry can be computed in real-time as feedback for animation or design. Speed and simplicity of the approach allow solving the inverse problem of modeling to match prescribed moments.

Unrestricted control polyhedra facilitate modeling free-form surfaces of arbitrary topology and local patch-layout by allowing n -sided, possibly nonplanar, facets and m -valent vertices. By cutting off edges and corners, the smoothing of an unrestricted control polyhedron can be reduced to the smoothing of a planar-cut polyhedron . A planar-cut polyhedron is a generalization of the well-known tensor-product control structure. The routine Pcp2Nurb in turn translates planar-cut polyhedra to a collection of four-sided linearly trimmed bicubic B-splines and untrimmed biquadratic B-splines. The routine can thus serve as central building block for overcoming topological constraints in the mathematical modeling of smooth surfaces that are stored, transmitted, and rendered using only the standard representation in industry. Specifically, on input of a nine-point subnet of a planar-cut polyhedron, the routine outputs a trimmed bicubic NURBS patch. If the subnet does not have geometrically redundant edges, this patch joins smoothly with patches from adjacent subnets as a four-sided piece of a regular C 1 surface. The patch integrates smoothly with untrimmed biquadratic tensor-product surfaces derived from subnets with tensor-product structure. Sharp features can be retained in this representation by using geometrically redundant edges in the planar-cut polyhedron. The resulting surface follows the outlines of the planar-cut polyhedron in the manner traditional tensor-product splines follow the outline of their rectilinear control polyhedron. In particular, it stays in the local convex hull of the planar-cut polyhedron.

The volume of a solid enclosed by a recursive subdivision surface can be approximated based on the closed‐form representation of regular parts of the subdivision surface and a tight estimate of the local convex hull near extraordinary points. The approach presented is efficient, i.e. non‐exponential, and robust in that it yields rapidly contracting error bounding boxes. An extension to measuring higher‐order moments is sketched.

Given a polyhedron, construct a new polyhedron by connecting every edge-midpoint to its four neighboring edge-midpoints. This refinement rule yields a C 1 surface and the surface has a piecewise quadratic parametrozation except at a finite number of isolated points. We analyze and improve the construction.

Polyhedra Made EasyA mesh of points outlining a surface is polyhedral if all cells are either quadrilateral or planar.A mesh is vertex-degree bounded if at most four cells meet at every vertex.This paper shows that if a mesh has both properties then simple averaging of its points yields the Bemstein-B6zier coefficients of a smooth, at most cubic, surface that consists of twice as many three-sided polynomial pieces as there are interior edges in the mesh.Meshes with checkerboard structure, that is, rectilinear meshes, are a special case and result in a quadratic surface.Since any bivariate mesh and, in particular, any wireframe of a polyhedron can be refined, by averaging, to a vertex-degree-bounded polyhedral mesh the above allows reinterpretation of a number of algorithms that construct smooth surfaces and advertises the corresponding averaging formulas as a model for a wider class of algorithms.

Polynomials of the total degree d in m variables have a geometrically intuitive representation in the Bernstein-Be´zier form defined over an m -dimensional simplex. The two algorithms given in this article evaluate the Bernstein-Be´zier form on a large number of points corresponding to a regular partition of the simplicial domain. The first algorithm is an adaptation of isoparametric evaluation. The second is a subdivision algorithm. In contrast to de Casteljau's algorithm, both algorithms have a cost of evaluation per point that is linear in the degree regardless of the number of variables. To demonstrate practicality, implementations of both algorithms on a triangular domain are compared with generic implementations of six algorithms in the literature.

Abstract We compare several implemented approaches to parallelizing the network simplex method on the SEQUENT shared memory multiprocessor. The experiments underscore the importance of parallel pricing and show that specialized processes and single pivots are more efficient than are uniform processes with parallel pivots. We describe the PARNET implementation that combines the best features of the experimental codes. In its least parallel version, PARNET outperforms NETFLO, a standard sequential code, by a factor of 12. The total execution time (including i/o and statistics) for any problem with 5000 nodes and 25,000 arcs taken from a standard set of NETGEN benchmark problems is less than 25 sec wall clock time on the Sequent Symmetry S‐81 using six processors. The incremental speedup is linear up to six processors on the test set and improves with the problem size and the density of the underlying graph. For a problem with 1000 nodes and 500,000 ares, PARNET achieves incremental linear speedup up to 12 processors.

This paper develops and explains the construction of a piecewise quartic space curve that interpolates positional, tangent, and curvature data. The construction is local and explicit; that is, it does not involve the solution of equations. If only positional data are known, then the tangent and curvature data can he derived by simple local default rules. Another option is to reduce the degree of the curve or minimize the a-norm of its derivative by solving a diagonally dominant, banded, linear system.