In most layered additive manufacturing processes, a tool solidifies or deposits material while following pre-planned trajectories to form solid beads. Many interesting problems arise in this context, among which one concerns the planning of trajectories for filling a planar shape as densely as possible. This is the problem we tackle in the present paper. Recent works have shown that allowing the bead width to vary along the trajectories helps increase the filling density. We present a novel technique that, given a deposition width range, constructs a set of closed beads whose width varies within the prescribed range and fill the input shape. The technique outperforms the state of the art in important metrics: filling density (while still guaranteeing the absence of bead overlap) and trajectories smoothness. We give a detailed geometric description of our algorithm, explore its behavior on example inputs and provide a statistical comparison with the state of the art. We show that it is possible to obtain high quality fabricated layers on commodity FDM printers.

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.

We present a method for designing mechanical metamaterials based on the novel concept of Voronoi diagrams induced by star-shaped metrics. As one of its central advantages, our approach supports interpolation between arbitrary metrics. This capability opens up a rich space of structures with interesting aesthetics and a wide range of mechanical properties, including isotropic, tetragonal, orthotropic, as well as smoothly graded materials. We evaluate our method by creating large sets of example structures, provided as accompanying material. We validate the mechanical properties predicted by simulation through tensile tests on a set of physical prototypes.

A critical advantage of additive manufacturing is its ability to fabricate complex small-scale structures. These microstructures can be understood as a metamaterial : they exist at a much smaller scale than the volume they fill, and are collectively responsible for an average elastic behavior different from that of the base printing material making the fabricated object lighter and/or flexible along specific directions. In addition, the average behavior can be graded spatially by progressively modifying the micro structure geometry. The definition of a microstructure is a careful trade-off between the geometric requirements of manufacturing and the properties one seeks to obtain within a shape: in our case a wide range of elastic behaviors. Most existing microstructures are designed for stereolithography (SLA) and laser sintering (SLS) processes. The requirements are however different than those of continuous deposition systems such as fused filament fabrication (FFF), for which there is currently a lack of microstructures enabling graded elastic behaviors. In this work we introduce a novel type of microstructures that strictly enforce all the requirements of FFF-like processes: continuity, self-support and overhang angles. They offer a range of orthotropic elastic responses that can be graded spatially. This allows to fabricate parts usually reserved to the most advanced technologies on widely available inexpensive printers that also benefit from a continuously expanding range of materials.

Recent spatial hashing schemes hash millions of keys in parallel, compacting sparse spatial data in small hash tables while still allowing for fast access from the GPU. Unfortunately, available schemes suffer from two drawbacks: Multiple runs of the construction process are often required before success, and the random nature of the hash functions decreases access performance. We introduce a new parallel hashing scheme which reaches high load factor with a very low failure rate. In addition our scheme has the unique advantage to exploit coherence in the data and the access patterns for faster performance. Compared to existing approaches, it exhibits much greater locality of memory accesses and consistent execution paths within groups of threads. This is especially well suited to Computer Graphics applications, where spatial coherence is common. In absence of coherence our scheme performs similarly to previous methods, but does not suffer from construction failures. Our scheme is based on the Robin Hood scheme modified to quickly abort queries of keys that are not in the table, and to preserve coherence. We demonstrate our scheme on a variety of data sets. We analyze construction and access performance, as well as cache and threads behavior.

Textures are often reused on different surfaces in large virtual environments. This leads to unpleasing stretch and cropping of features when textures contain architectural elements. Existing retargeting methods could adapt each texture to the size of their support surface, but this would imply storing a different image for each and every surface, saturating memory. Our new texture synthesis approach casts synthesis as a shortest path problem in a graph describing the space of images that can be synthesized. Each path in the graph describes how to form a new image by cutting strips of the source image and reassembling them in a different order. Only the paths describing the result need to be stored in memory: synthesized textures are reconstructed at rendering time. The user can control repetition of features, and may specify positional constraints. We demonstrate our approach on a variety of textures, from facades for large city rendering to structured textures commonly used in video games.

We describe a new implementation of the well-known incremental algorithm for constructing Delaunay triangulations in any dimension. Our implementation follows the exact computing paradigm and is fully robust. Extensive comparisons show that our implementation outperforms the best currently available codes for exact convex hulls and Delaunay triangulations, compares very well to the fast non-exact QHull implementation and can be used for quite big input sets in spaces of dimensions up to 6. To circumvent prohibitive memory usage, we also propose a modification of the algorithm that uses and stores only the Delaunay graph (the edges of the full triangulation). We show that a careful implementation of the modified algorithm performs only 6 to 8 times slower than the original algorithm while drastically reducing memory usage in dimension 4 or above.

We present a novel algorithm for the rendering of hard shadows cast by a point light source. The well-known Z-pass method for rasterizing shadow volumes is not always correct. Our algorithm, which we call ZP+, elegantly corrects Z-pass defects. ZP+ takes advantage of triangle strips and the fast culling capabilities of graphics hardware not available to conventional robust methods like Z-fail. While Z-fail can be up to 80% slower than Z-pass, our new method ZP+ is typically less than 10% slower than Z-pass. Finally, we compare the three methods. When a scene is geometry-bound, ZP+ is always faster than Z-fail. We also explain why, in some situations, Z-pass (hence ZP+) is surprisingly slower than Z-fail on more recent graphics hardware.

We present a new interactive method to texture complex geometries at very high resolution, while using little memory and without the need for a global planar parameterization. We rely on small texture elements, the texture sprites, locally splatted onto the surface to define a composite texture. The sprites can be arbitrarily blended to create complex surface appearances. Their attributes (position, size, texture id) can be dynamically updated, thus providing a convenient framework for interactive editing and animated textures. We demonstrate the flexibility of our method by creating new surface aspects difficult to achieve with other methods.Each sprite is described by a small set of attributes which is stored in a hierarchical structure surrounding the object's surface. The patterns supported by the sprites are stored only once. The whole data structure is compactly encoded into GPU memory. At run time, it is accessed by a fragment program which computes the final appearance of a surface point from all the sprites covering it. The overall memory cost of the structure is very low compared to the resulting texturing resolutions. Rendering is done in real-time. The resulting texture is linearly interpolated and filtered.

To remain an attractive model, skeleton-based implicit surfaces have to allow the design and display of shapes at interactive rates. We focus on surfaces whose skeletons are graphs of interconnected curves. We present subdivision-curve primitives that rely on convolution for generating bulge-free and crease-free implicit surfaces. These surfaces are efficiently yet correctly displayed using local meshes around each curve that locally overlap in blending regions. Subdivision-curve primitives offer a practical solution to the unwanted-blending problem that ensures C/sup 1/ continuity everywhere. Moreover, they can be used to generate representations at different levels of detail, enabling the interactive display of at least a coarse version of the objects, whatever the performance of the workstation.