Most additive manufacturing processes fabricate objects by stacking planar layers of solidified material. As a result, produced parts exhibit a so-called staircase effect, which results from sampling slanted surfaces with parallel planes. Using thinner slices reduces this effect, but it always remains visible where layers almost align with the input surfaces. In this research we exploit the ability of some additive manufacturing processes to deposit material slightly out of plane to dramatically reduce these artifacts. We focus in particular on the widespread Fused Filament Fabrication (FFF) technology, since most printers in this category can deposit along slightly curved paths, under deposition slope and thickness constraints. Our algorithm curves the layers, making them either follow the natural slope of the input surface or on the contrary, make them intersect the surfaces at a steeper angle thereby improving the sampling quality. Rather than directly computing curved layers, our algorithm optimizes for a deformation of the model which is then sliced with a standard planar approach. We demonstrate that this approach enables us to encode all fabrication constraints, including the guarantee of generating collision-free toolpaths, in a convex optimization that can be solved using a QP solver. We produce a variety of models and compare print quality between curved deposition and planar slicing.

Implicit models can be combined by using composition operators; functions that determine the resulting shape. Recently, gradient-based composition operators have been used to express a variety of behaviours including smooth transitions, sharp edges, contact surfaces, bulging, or any combinations. The problem for designers is that building new operators is a complex task that requires specialized technical knowledge. In this work, we introduce an automatic method for deriving a gradient-based implicit operator from 2D drawings that prototype the intended visual behaviour. To solve this inverse problem, in which a shape defines a function, we introduce a general template for implicit operators. A user's sketch is interpreted as samples in the 3D operator's domain. We fit the template to the samples with a non-rigid registration approach. The process works at interactive rates and can accommodate successive refinements by the user. The final result can be applied to 3D surfaces as well as to 2D shapes. Our method is able to replicate the effect of any blending operator presented in the literature, as well as generating new ones such as non-commutative operators. We demonstrate the usability of our method with examples in font-design, collision-response modeling, implicit skinning, and complex shape design.

In order to safely operate sailboats, captains often rely on proper interpretation of several marine aspects to make decisions. In this project, we have developed an Augmented Reality System (ARS) to provide captains of sailboats with a centralized sensor data server and a visualization method. We have deployed an experimental proof-of-concept version of this system on our research vessel, SV Moon shadow. Assistance in navigation is of particular interest for small sailing vessels as they are sometimes sailed by the captain alone. At the same time there are a large number of data inputs such as wind, tide, weather, position, and presence of obstacles such as logs or kelp that have to be considered to choose the proper course of action. We introduce a visualization tool that provides an interface for representing a wide spectrum of relevant marine data. The interface relies on a real-time data server that provides information about the status of the vessel (wind, GPS, gyro, accelerometer, depth sounder etc.) An important component of the interface is a debris detector that analyzes data from a camera mounted on the bow in order to warn a captain about a potential collision. We have also examined initial feedback on this tool from a number of users.

Abstract Texture mapping is an essential component for creating 3D models and is widely used in both the game and the movie industries. Creating texture maps has always been a complex task and existing methods carefully balance flexibility with ease of use. One difficulty in using texturing is the repeated placement of individual textures over larger areas. In this paper, we propose a method which uses decals to place images onto a model. Our method allows the decals to compete for space and to deform as they are being pushed by other decals. A spherical field function is used to determine the position and the size of each decal and the deformation applied to fit the decals. The decals may span multiple objects with heterogeneous representations. Our method does not require an explicit parametrization of the model. As such, varieties of patterns, including repeated patterns like rocks, tiles and scales can be mapped. We have implemented the method using the GPU where placement, size and orientation of thousands of decals are manipulated in real time.

We present a novel approach to interactive character skinning, which is robust to extreme character movements, handles skin contacts and produces the effect of skin elasticity (sliding). Our approach builds on the idea of implicit skinning in which the character is approximated by a 3D scalar field and mesh-vertices are appropriately re-projected. Instead of being bound by an initial skinning solution used to initialize the shape at each time step, we use the skin mesh to directly track iso-surfaces of the field over time. Technical problems are two-fold: firstly, all contact surfaces generated between skin parts should be captured as iso-surfaces of the implicit field; secondly, the tracking method should capture elastic skin effects when the joints bend, and as the character returns to its rest shape, so the skin must follow. Our solutions include: new composition operators enabling blending effects and local self-contact between implicit surfaces, as well as a tangential relaxation scheme derived from the as-rigid-as possible energy to solve the tracking problem.

We introduce a new family of binary composition operators that solves four major problems of constructive implicit modeling: suppressing bulges when two shapes merge, avoiding unwanted blending at a distance, ensuring that the resulting shape keeps the topology of the union, and enabling sharp details to be added without being blown up. The key idea is that field functions should not only be combined based on their values, but also on their gradients . We implement this idea through a family of C ∞ composition operators evaluated on the GPU for efficiency, and illustrate it by applications to constructive modeling and animation.

Geometric skinning techniques, such as smooth blending or dual-quaternions, are very popular in the industry for their high performances, but fail to mimic realistic deformations. Other methods make use of physical simulation or control volume to better capture the skin behavior, yet they cannot deliver real-time feedback. In this paper, we present the first purely geometric method handling skin contact effects and muscular bulges in real-time. The insight is to exploit the advanced composition mechanism of volumetric, implicit representations for correcting the results of geometric skinning techniques. The mesh is first approximated by a set of implicit surfaces. At each animation step, these surfaces are combined in real-time and used to adjust the position of mesh vertices, starting from their smooth skinning position. This deformation step is done without any loss of detail and seamlessly handles contacts between skin parts. As it acts as a post-process, our method fits well into the standard animation pipeline. Moreover, it requires no intensive computation step such as collision detection, and therefore provides real-time performances.

Skeletal implicit modelling systems have been used to design models of both organic and man-made structures, however existing systems lack convenient and accurate methods for users to define fillets when building prototype engineering models. In this work we extend the methodology and skeletal primitives found in the BlobTree and introduce an improved method for modelling fillets. This is done by interpolating between hard-edged and soft-edged representations of a primitive, using the field to control the interpolation. Blending planes are introduced as a way of providing user control for this interpolation. The new methods are expressed as blend operators between two objects and can thus be implemented as a new node in the BlobTree. In addition we introduce an efficient methodology for modelling hard edged primitives.

Abstract Blending is both the strength and the weakness of functionally based implicit surfaces (such as F‐reps or soft‐objects). While it gives them the unique ability to smoothly merge into a single, arbitrary shape, it makes implicit modelling hard to control since implicit surfaces blend at a distance, in a way that heavily depends on the slope of the field functions that define them. This paper presents a novel, generic solution to blending of functionally‐based implicit surfaces: the insight is that to be intuitive and easy to control, blends should be located where two objects overlap, while enabling other parts of the objects to come as close to each other as desired without being deformed. Our solution relies on automatically defined blending regions around the intersection curves between two objects. Outside of these volumes, a clean union of the objects is computed thanks to a new operator that guarantees the smoothness of the resulting field function; meanwhile, a smooth blend is generated inside the blending regions. Parameters can automatically be tuned in order to prevent small objects from blurring out when blended into larger ones, and to generate a progressive blend when two animated objects come in contact.

Abstract Bounding volume hierarchies (BVHs) are a popular method for speeding up raytracing, but they can consume a large amount of memory for complex scenes. We investigate a hierarchical scheme for encoding BVHs that reduces the BVH storage requirements by 63%–75%. The computational overhead of the scheme can be reduced to negligible levels by shooting bundles of rays through the BVH (coherent raytracing). This gives the speed of a coherency‐based raytracer combined with substantial memory savings.

A method is described for texturing surfaces using decals , images placed on the surface using local parameterizations. Decal parameterizations are generated with a novel O ( N log N ) discrete approximation to the exponential map which requires only a single additional step in Dijkstra's graph-distance algorithm. Decals are dynamically composited in an interface that addresses many limitations of previous work. Tools for image processing, deformation/feature-matching, and vector graphics are implemented using direct surface interaction. Exponential map decals can contain holes and can also be combined with conformal parameterization to reduce distortion. The exponential map approximation can be computed on any point set, including meshes and sampled implicit surfaces, and is relatively stable under resampling. The decals stick to the surface as it is interactively deformed, allowing the texture to be preserved even if the surface changes topology. These properties make exponential map decals a suitable approach for texturing animated implicit surfaces.

Complex implicit CSG models can be represented hierarchically as a tree of nodes (the BlobTree) . However, current methods cannot be used to visualize changes made to these models at interactive rates due to the large number of potential field evaluations required. A hierarchical spatial caching technique is presented which accelerates evaluations of the potential function. This method introduces the concept of a caching node inserted into the implicit model tree. Caching nodes store exact potential field values at the vertices of a voxel grid and rely on tri-linear and tri-quadratic reconstruction filters to locally approximate the potential field of a sub-tree. A lazy evaluation scheme is used to avoid expensive pre-computation. Polygonization timings with and without caching are compared for a complex model undergoing manipulation in an interactive modeling tool. An order-of-magnitude improvement in visualization time is achieved for complex implicit models containing thousands of primitives.

We present new techniques for rendering hierarchical, skeletal implicit models in several pen-and-ink styles. Our approach extracts silhouette strokes and lines following local shape features, such as those caused by CSG junc-tions. To this end, it uses particle systems to find interesting areas on the surface and perform stroke stylization guided by local shape features. Also, it removes hidden lines either by applying a surfel technique for rapid proto-typing, or more accurately by using ray tracing. Examples from simple to complex models illustrate the capabilities of our system.

In recent years several methods for modeling botanical trees have been proposed. The geometry and topology of tree skeletons can be well described by L-systems; however, there are several approaches to modeling smooth surfaces to represent branches, and not all of the observed phenomena can be represented by current methods. Many tree types exhibit nonsmooth features such as branch bark ridges and collars. In this research a hierarchical implicit modeling system is used to produce models of branching structures that capture smooth branching, branch collars and branch bark ridges. The BlobTree provides several techniques to control the combination of primitives, allowing both smooth and nonsmooth effects to be intuitively combined in a single blend volume. Irregular effects are implemented using precise contact modeling, constructive solid geometry and space warping. We show that smooth blends can be obtained, without noticeable bulging, using summation of distance based implicit surfaces. L-systems are used to create the branching structure allowing botanically based simulations to be used as input

Abstract A method is proposed for photo‐realistic modeling and visualization of a growing tree. Recent visualization methods have focused on producing smoothly blending branching structures, however, these methods fail to account for the inclusion of non‐smooth features such as branch bark ridges and bud scale scars. These features constitute an important visual aspect of a living tree, and are also observed to vary over time. The proposed method incorporates these features by using an hierarchical implicit modeling system, which provides a variety of tools for combining surface components in both smooth and non smooth configurations. A procedural interface to this system supports the use of inverse modeling, which is a global‐to‐local methodology, where the local properties of plant organs are described in terms of their global position within the tree architecture. Inverse modeling is used to define both the tree structure at any time, and a continuous developmental sequence for the tree from a seedling. These techniques provide an intuitive paradigm for the definition of complex tree growth sequences and their subsequent visualization, based solely on observed phenomena. Thus, a key advantage is that they do not require any knowledge of, or simulation of, the underlying biological processes. Categories and Subject Descriptors (according to ACM CCS): I.3.5 [Computer Graphics]: Curve, surface, solid, and object representations I.3.7 [Computer Graphics]: Animation

Abstract Current methods for building models using implicit volume techniques present problems defining accurate and controllable blend shapes between implicit primitives. We present new methods to extend the freedom and controllability of implicit volume modeling. The main idea is to use a free‐form curve to define the profile of the blend region between implicit primitives. The use of a free‐form implicit curve, controlled point‐by‐point in the Euclidean user space, allows us to group boolean composition operators with sharp transitions or smooth free‐form transitions in a single modeling metaphor. This idea is generalized for the creation, sculpting and manipulation of volume objects, while providing the user with simplicity, controllability and freedom in implicit modeling. ACM CSS: I.3.5 Computational Gemoetry and Object Modeling—Curve, surface, solid, and object representations

Abstract Drawings made with precise pen strokes accurately reveal the geometric forms that give subjects their characteristicshape. We present a system for non‐photorealistic rendering of precise drawing strokes over dense 3Dtriangle meshes with arbitrary topology. During an automatic pre‐process, we construct an extended version ofthe edge‐buffer data structure to allow the calculation of shape measures at each mesh edge, by adapting numericalmethods used in geomorphology. At runtime, feature edges related to shape measures are extracted andrendered as strokes with varying thickness and pen marking styles. Stroke thickness is automatically adjusted byconsidering surface curvature. Pen marking styles and visual effects of ink distribution are both controlled by theuser. We demonstrate precise drawing strokes over complex meshes revealing a variety of shape characteristics.

A novel method of hierarchical implicit modeling is presented in which an implicit object is modeled using a hierarchy of implicit surfaces. The hierarchy provides both layered local refinement and global deformation. Local refinement allows the introduction of higher-level detailed surfaces. Global deformation changes the overall shape of the surface while maintaining the integrity of surface details. The model is gradually refined by introducing appropriate new primitives in specified surface areas. Refinement constraints, such as a local area constraint and a level constraint, are designed to be applied to the implicit object so as to achieve finer control of the local surface. The method provides a dynamic representation of implicit surfaces and can be used in modeling complex implicit objects, animating the surfaces, and simulating the deformations of various objects.

Many of the most interesting simulations in the biological world have to do with interactions between species. The predator-prey interactions among aquatic organisms are an interesting part of the natural world which has not been seen much in computer animation. This paper explores the interaction between various sea anemones and the starfish Dermasterias imbricata. Although a simulation between a specific sea anemone, Stomphia coccinea to Dermasterias imbricata was created, an approach was taken such that different anemones with minor parameter changes can be used to replace Stomphia coccinea. The animation was created using a parametric key-frame approach using tracks and a hierarchical procedural implicit modeling method. The anemone and starfish were modeled using the Blob-Tree. Using a hierarchical construction, the model is refined locally and deformed globally at arbitrary layers while maintaining the consistency and integrity of surface details. A hierarchy of tracks was used to control the object's motion.

The paper presents a new method for modeling the structure of sea anemones and sea stars. Two specific invertebrates, the sea anemone, Stomphia coccinea and the sea star, Dermasterias imbricata were modeled using hierarchical implicit surfaces based on the BlobTree. The hierarchy provides both local refinement and global deformation. Local refinement allows the introduction of details on the base surface and global deformations change the overall shape of the model while maintaining the integrity of the surface details. Using a new implicit surface phyllotactic method, we obtain a visually pleasing arrangement of the sea anemone's tentacles. The hierarchical representation of the model provides an easy and efficient way for modeling the many different shape changes of sea anemones.

One of the major applications of implicit surface modeling systems has been the generation of cartoon-like characters. Recently, additional modeling methods have been combined with implicit surfaces to create much more complex models. These methods include constructive solid geometry (CSG), warping, and two-dimensional texture mapping (among others). The BlobTree has been introduced to organize all of these elements into a single structure which allows both local and global applications of each of these techniques in a general and intuitive fashion. The BlobTree lends itself well to rapid and direct specification of complex models, however current implementations of the BlobTree have not been engineered for efficiency, and perform poorly when attempting to render large models. In this work we apply established techniques, such as spatial subdivision and tree optimization, to the BlobTree. The objective is to increase efficiency during rendering without restricting the functionality of the BlobTree as a modeling tool.

We present an algorithm for generating a piecewise G1 circular spline curve from an arbitrary given control polygon. For every corner, a circular biarc is generated with each piece being parameterized by its arc length. This is the first subdivision scheme that produces a piecewise biarc curve that can interpolate an arbitrary set of points. It is easily adopted in a recursive subdivision surface scheme to generate surfaces with circular boundaries with pieces parameterized by arc length, a property not previously available. As an application, a modified version of Doo–Sabin subdivision algorithm is outlined making it possible to blend a subdivision surface with other surfaces having circular boundaries such as cylinders.

Implicit surface modeling systems have been used since the mid-1980's for the generation of cartoon like characters. Recently implicit models combined with constructive solid geometry (CSG) have been used to build engineering models with automatic blending. This work is built on a structured implicit modeling system which includes CSG, warping, 2D texture mapping and operations based on the BlobTree, and its application to the generation of a complex and visually accurate biological model of the sea shell Murex cabritii. Since the model is purely procedurally defined and does not rely on polygon mesh operations, it is resolution independent and can be rendered directly using ray tracing. An interface has been built to the BlobTree using an interpreted programming language (Python). The language interface readily allows a user to procedurally describe the shell based on numeric data taken from the actual object.

Addresses the problem of texture mapping implicit surfaces. Recent work in providing 2D mappings for implicit surfaces maps points from an auxiliary parametric (support) surface to the implicit surface. In this work, we extend this method by observing that all commonly used skeletal elements are easily parameterized and can be used as their own support surfaces. In areas of a surface defined by the combination of multiple skeletal primitives, we compute a mapping through relations found with the zero-level surface of a primitive by using the gradient field.

Automatic blending has characterized the major advantage of implicit surface modeling systems. Recently, the introduction of deformations based on space warping and Boolean operations between primitives has increased the usefulness of such systems. We propose a further enhancement which will extend the range of models that can be easily and intuitively defined with a skeletal implicit surface system. We describe a hierarchical method which allows arbitrary compositions of models that make use of blending, warping and Boolean operations. We call this structure the BlobTree. Blending and space warping are treated in the same way as union, difference and intersection, i.e. as nodes in the BlobTree. The traversal of the BlobTree is described along with two rendering algorithms; a polygonizer and a ray tracer. We present some examples of interesting models which can be made easily using our approach that would be very difficult to represent with conventional systems.

Modelling, simulation, and visualization of porous media have practical applications in the petroleum and chemical industries. Advances in modelling and simulation of porous media can help in the understanding of processes in petroleum rocks. The paper presents new algorithms for modelling and visualizing fluid interfaces within porous media. These algorithms allow the creation and nondestructive testing of porous samples in a virtual laboratory of porous media. The visualization process is one of the main elements in such a laboratory. Results of these simulated processes can be visualized as 3D or 2D images, where colour and shading emphasize fluid saturations and interfaces between two interacting fluids as a function of varying pressure. These algorithms are based on the octree data structure. The idea is to create a porous media sample with a realistic structure and at a level of complexity commensurate with actual samples. Simulations are then run on this model. This method contrasts with traditional porous media modelling where a mathematical model (lattice) is simulated using sets of equations.

We present a framework for behavioural simulation. A uniform voxel space representation is used to implement the environment mechanism of the framework. An example environment is presented where actors with olfactory sensors are able to direct their motions according to a scent of the chemicals in the voxel space based on mass transfer theory. Objects in the environment are scan converted to the voxel representation to facilitate collision detection. An example of using the framework to simulate the behaviour of a group of artificial butterflies is used to demonstrate the ideas of this research.

In order to achieve the impression of a smooth surface while rendering a polygon mesh, normal vector vectors may be provided in the vertices of the mesh that are the average of the surface normals of the adjacent polygons. Interpolation of these normal vectors while rendering of the polygons in the mesh, and using the interpolated normal vectors in the shading computations, yields a smoothly varying intensity distribution. There is an inherent mismatch, however, between the smoothness of the shading thus achieved and the non-smoothness of the geometry which is particularly visible at silhouettes, showing as straight edges and non-smooth edge junctions at the silhouette vertices. A remedy for these artefacts is suggested. The remedy consists of subdividing each input polygon into a mesh of polygons prior to rendering. The shape of this resulting polygon mesh is controlled by the normal vectors that are provided in the vertices of the original polygon, unlike other subdivision schemes that make use of adjacent polygons. With the method, polygons equipped with vertex normal vectors can therefore be processed without further knowledge of neighbour polygons. This makes the method well-suited in the context of graphics libraries, such as OpenGl, that treat polygons typically on a per-polygon basis. So the proposed computation of the mesh which replaces the original polygon can be viewed as a filter which may operate as a process in front of a traditional polygon rendering pipeline.

Freeform deformations are useful for describing a class of complex motions within an animation system. Such deformations have been described using a generalization of parametric surfaces and their application to modeling is well documented. We present a method that can be applied to implicit surfaces which are defined as an iso surface around a set of skeletal elements. The resulting surface is approximated by a polygon mesh. Shape distortions, such as "squash and stretch" are applied automatically to models in motion by warping the space in which the models exist. A model will change its shape as the function defining the warped space can change over time or the model will deform as it moves through the warped space. Our system also treats groups of skeletal implicit primitives as CSG primitives. Warping can also be applied to these primitives. Different warp functions, for example bend, taper and twist can be applied locally or globally, the contribution from each primitive is calculated using a set of warp functions associated with that primitive. The interesting shapes, and possibly nonlinear motion obtained from space warping, would be difficult to reproduce using other techniques.

A method for the extrusion of arbitrary polygon meshes is introduced. This method can be applied to model a large class of complex 3-D closed surfaces. It consists of defining a (typically small) set of connected polygons in 3-D that form a skeleton of the final object, and assigning extrusion distances to all polygons. The two sides of a polygon may have different extrusion distances. An automatic extrusion algorithm constructs a closed 3-D polygon mesh around the skeleton, making use of the indicated extrusion distances. We call this process inflating the polygons of the skeleton. Unlike traditional extrusion, the method works for non-planar skeleton configurations, and it also supports branching skeleton structures (i.e. edges with more than two incident polygons). © 1997 by John Wiley & Sons, Ltd.

Phong shading is one of the best known, and at the same time simplest techniques to arrive at realistic images whem rendering 3D geometric models. However, despite (or maybe due to) its success and its widespread use, some aspects remain to be clarified with respect to its validity and robustness. This might be caused by the fact that the Phong method is based on geometric arguments, illumination models, and clever heuristics. In this article we address some of the fundamentals that underlie Phong shading, such as the computation of vertex normals for nonmanifold models and the adequacy of linear interpolation and we apply a new interpolation technique to achieve an efficient and qualitatively improve result.

Abstract An interesting problem in the oil and gas industry is the visualization of the movement of oil and gas in porous media. An example of such a medium is a rock sample with some distribution of holes (pores) connected by channels (pore throats), the solid parts of the rock are called grains. In our work we have simulated the porous medium using a pointer‐based octree, representing these pores and grains. This data structure allows us to model the connectivity of the pores and thus visualize fluid penetration within the medium. Whereas earlier models represent a serious simplifications or two dimensional homogeneous layers, our model provides us with a statistically accurate distribution in three dimensions and a more accurate representation of the connectivity. In this paper we present our data structure and the techniques which were used to create models of porous media and their porous networks. Next, we present algorithms for connectivity in octrees and we show how to apply them to modelling and visualization of fluid penetration in porous media.

A method for rendering lightning using conventional raytracing techniques is discussed. The approach taken is directed at producing aesthetic images for animation, rather than providing a realistic physically based model for rendering. A particle system is used to generate the path of the lightning channel, and subsequently to animate the lightning. A technique, using implicit surfaces, is introduced for illuminating objects struck by lightning.

Abstract We describe a new method for modelling braids and certain classes of knots and links, and how they may be visualized. The method uses generalized cylinders built around a bicubic spline centre line. We also show how multi‐stranded, recursive, hawser laid ropes can be modelled using related techniques.

Recent research has demonstrated the usefulness of implicit surfaces for modeling geometric objects. The interactive design of such surfaces has not, however, received the same attention as has the design of parametric surfaces. Principally this is due to the difficulty of controlling the shape of implicit surfaces while displaying the changes quickly enough for use within an interactive design environment. This paper describes progress towards interactive control of implicit surfaces and introduces new techniques useful to the designer.

A major bottleneck in many graphics displays is the time required to scan-convert straight line segments. Most manufacturers use hardware based on Bresenham's [5] line algorithm. In this paper an algorithm is developed based on the original Bresenham scan-conversion together with the symmetry first noted by Gardner [18] and a recent double-step technique [31]. This results in a speed-up of scan-conversion by a factor of approximately 4 as compared to the original Bresenham algorithm. Hardware implementations are simple and efficient since the property of using only shift and increment operations is preserved.

Abstract A multiprocessor algorithm for ray tracing is described. The performance of the algorithm is analysed for a cubic and square array of processors with only local communication between near neighbours. Theoretical expressions for the speedup of the system as a function of the number of processors are derived. These analytic results are supported by simulations of ray tracing on a number of simple scenes with polygonal surfaces. It is found that a square network of processors generally performs better than a cubic network. Some comments are made on the construction of such a system using current (1985) microprocessor technology.