Search

This paper presents an efficient algorithm for voxelizing the surface of triangular meshes in a single compute pass. The algorithm uses parallel equidistant lines to traverse the interior of triangles, minimizing costly memory operations and avoiding visiting the same voxels multiple times. By detecting and visiting only the voxels in each line operation, the proposed method achieves better performance results. This method incorporates a gap detection step, targeting areas where scanline‐based voxelization methods might fail. By selectively addressing these gaps, our method attains superior performance outcomes. Additionally, the algorithm is written entirely in a single compute GLSL shader, which makes it highly portable and vendor independent. Its simplicity also makes it easy to adapt and extend for various applications. The paper compares the results of this algorithm with other modern methods, comprehensibly comparing the time performance and resources used. Additionally, we introduce a novel metric, the 'Slope Consistency Value', which quantifies triangle orientation's impact on voxelization accuracy for scanline‐based approaches. The results show that the proposed solution outperforms existing, modern ones and obtains better results, especially in densely populated scenes with homogeneous triangle sizes and at higher resolutions. [ABSTRACT FROM AUTHOR]

Evaluations—encompassing computational evaluations, benchmarks and user studies—are essential tools for validating the performance and applicability of graph and network layout algorithms (also known as graph drawing). These evaluations not only offer significant insights into an algorithm's performance and capabilities, but also assist the reader in determining if the algorithm is suitable for a specific purpose, such as handling graphs with a high volume of nodes or dense graphs. Unfortunately, there is no standard approach for evaluating layout algorithms. Prior work holds a 'Wild West' of diverse benchmark datasets and data characteristics, as well as varied evaluation metrics and ways to report results. It is often difficult to compare layout algorithms without first implementing them and then running your own evaluation. In this systematic review, we delve into the myriad of methodologies employed to conduct evaluations—the utilized techniques, reported outcomes and the pros and cons of choosing one approach over another. Our examination extends beyond computational evaluations, encompassing user‐centric evaluations, thus presenting a comprehensive understanding of algorithm validation. This systematic review—and its accompanying website—guides readers through evaluation types, the types of results reported, and the available benchmark datasets and their data characteristics. Our objective is to provide a valuable resource for readers to understand and effectively apply various evaluation methods for graph layout algorithms. A free copy of this paper and all supplemental material is available at osf.io, and the categorized papers are accessible on our website at https://visdunneright.github.io/gd‐comp‐eval/. [ABSTRACT FROM AUTHOR]

Maintaining the maximum stiffness of components with as little material as possible is an overarching objective in computational design and engineering. It is well‐established that in stiffness‐optimal designs, material is aligned with orthogonal principal stress directions. In the limit of material volume, this alignment forms micro‐structures resembling quads or hexahedra. Achieving a globally consistent layout of such orthogonal micro‐structures presents a significant challenge, particularly in three‐dimensional settings. In this paper, we propose a novel geometric algorithm for compiling stress‐aligned hexahedral lattice structures. Our method involves deforming an input mesh under load to align the resulting stress field along an orthogonal basis. The deformed object is filled with a hexahedral grid, and the deformation is reverted to recover the original shape. The resulting stress‐aligned mesh is used as basis for a final hollowing procedure, generating a volume‐reduced stiff infill composed of hexahedral micro‐structures. We perform quantitative comparisons with structural optimization and hexahedral meshing approaches and demonstrate the superior mechanical performance of our designs with finite element simulation experiments. [ABSTRACT FROM AUTHOR]

Due to the widespread applications of 2‐dimensional spherical designs, there has been an increasing requirement of modeling on the 핊2 manifold in recent years. Due to the non‐Euclidean nature of the sphere, it has some challenges to find a method to represent 2D regions on 핊2 manifold. In this paper, a skeleton‐based representation method of regions on 핊2, disk B‐spline(DBSC) on 핊2 is proposed. Firstly, we give the definition and basic algorithms of DBSC on 핊2. Then we provide the calculation method of DBSC on 핊2, which includes calculating the boundary points, internal points and their corresponding derivatives. Based on that, we give some modeling methods of DBSC on 핊2, including approximation, deformation. In the end, some stunning application examples of DBSC on 핊2 are shown. This work lays a theoretical foundation for further applications of DBSC on 핊2. [ABSTRACT FROM AUTHOR]

This paper presents an efficient environment map sampling algorithm designed to render high‐quality, low‐noise images with only a few light samples, making it ideal for real‐time applications. We observe that bright pixels in the environment map produce high‐frequency shading effects, such as sharp shadows and shading, while the rest influence the overall tone of the scene. Building on this insight, our approach differs from existing techniques by categorizing the pixels in an environment map into emissive and non‐emissive regions and developing specialized algorithms tailored to the distinct properties of each region. By decomposing the environment lighting, we ensure that light sources are deposited on bright pixels, leading to more accurate shadows and specular highlights. Additionally, this strategy allows us to exploit the smoothness in the low‐frequency component by rendering a smaller image with more lights, thereby enhancing shading accuracy. Extensive experiments demonstrate that our method significantly reduces shadow artefacts and image noise compared to previous techniques, while also achieving lower numerical errors across a range of illumination types, particularly under limited sample conditions. [ABSTRACT FROM AUTHOR]

The smoothing of surface curves is an essential tool in mesh processing, important to applications that require segmenting and cutting surfaces such as surgical planning. Surface curves are typically designed by professionals to match certain surface features. For this reason, the smoothed curves should be close to the original and easily adjustable by the user in interactive tools. Previous methods achieve this desired behavior, e.g., by utilizing energy‐minimizing splines or generalizations of Bézier splines, which require a significant number of control points and may not provide interactive frame rates or numerical stability. This paper presents a new algorithm for robust smoothing of discrete surface curves on triangular surface meshes. By using a scalar penalty potential as the fourth coordinate, the given surface mesh is embedded into the 4D Euclidean space. Our method is based on finding geodesics in this lifted surface, which are then projected back onto the original 3D surface. The benefits of this approach include guaranteed convergence and good approximation of the initial curve. We propose a family of penalty potentials with one single parameter for adjusting the trade‐off between smoothness and similarity. The implementation of our method is straightforward as we rely on existing methods for computing geodesics and penalty fields. We evaluate our implementation and confirm its robustness and efficiency. [ABSTRACT FROM AUTHOR]

Screen Space Reflection (SSR) can reliably achieve highly efficient reflective effects, significantly enhancing users' sense of realism in real‐time applications. However, when directly applied to stereo rendering, popular SSR algorithms lead to inconsistencies due to the differing information between the left and right eyes. This inconsistency, invisible to human vision, results in visual discomfort. This paper analyzes and demonstrates how screen‐space geometries, fade boundaries, and reflection samples introduce inconsistent cues. Considering the complementary nature of screen information, we introduce a stereo‐aware SSR method to alleviate visual discomfort caused by screen space disparities. By contrasting our stereo‐aware SSR with conventional SSR and ray‐traced results, we showcase the effectiveness of our approach in mitigating the inconsistencies stemming from screen space differences while introducing affordable performance overhead for real‐time rendering. [ABSTRACT FROM AUTHOR]

Key time steps selection, i.e., selecting a subset of most representative time steps, is essential for effective and efficient scientific visualization of large time‐varying volume data. In particular, as computer simulations continue to grow in size and complexity, they often generate output that exceeds both the available storage capacity and bandwidth for transferring results to storage, making it indispensable to save only a subset of time steps. At the same time, this subset must be chosen so that it is highly representative, to facilitate post‐processing and reconstruction with high fidelity. The key time steps selection problem is especially challenging in the in situ setting, where we can only process data in one pass in an online streaming fashion, using a small amount of main memory and fast computation. In this paper, we formulate the problem as that of optimal piece‐wise linear interpolation. We first apply a method from numerical linear algebra to compute linear interpolation solutions and their errors in an online streaming fashion. Using that method as a building block, we can obtain a global optimal solution for the piece‐wise linear interpolation problem via a standard dynamic programming (DP) algorithm. However, this approach needs to process the time steps in multiple passes and is too slow for the in situ setting. To address this issue, we introduce a novel approximation algorithm, which processes time steps in one pass in an online streaming fashion, with very efficient computing time and main memory space both in theory and in practice. The algorithm is suitable for the in situ setting. Moreover, we prove that our algorithm, which is based on a greedy update rule, has strong theoretical guarantees on the approximation quality and the number of time steps stored. To the best of our knowledge, this is the first algorithm suitable for in situ key time steps selection with such theoretical guarantees, and is the main contribution of this paper. Experiments demonstrate the efficacy of our new techniques. [ABSTRACT FROM AUTHOR]

Projection algorithms such as t‐SNE or UMAP are useful for the visualization of high dimensional data, but depend on hyperparameters which must be tuned carefully. Unfortunately, iteratively recomputing projections to find the optimal hyperparameter values is computationally intensive and unintuitive due to the stochastic nature of such methods. In this paper we propose HyperNP, a scalable method that allows for real‐time interactive hyperparameter exploration of projection methods by training neural network approximations. A HyperNP model can be trained on a fraction of the total data instances and hyperparameter configurations that one would like to investigate and can compute projections for new data and hyperparameters at interactive speeds. HyperNP models are compact in size and fast to compute, thus allowing them to be embedded in lightweight visualization systems. We evaluate the performance of HyperNP across three datasets in terms of performance and speed. The results suggest that HyperNP models are accurate, scalable, interactive, and appropriate for use in real‐world settings. [ABSTRACT FROM AUTHOR]

During the last decades, anatomy has become an interesting topic in education—even for laymen or schoolchildren. As medical imaging techniques become increasingly sophisticated, virtual anatomical education applications have emerged. Still, anatomical models are often preferred, as they facilitate 3D localization of anatomical structures. Recently, data physicalizations (i.e., physical visualizations) have proven to be effective and engaging—sometimes, even more than their virtual counterparts. So far, medical data physicalizations involve mainly 3D printing, which is still expensive and cumbersome. We investigate alternative forms of physicalizations, which use readily available technologies (home printers) and inexpensive materials (paper or semi‐transparent films) to generate crafts for anatomical edutainment. To the best of our knowledge, this is the first computer‐generated crafting approach within an anatomical edutainment context. Our approach follows a cost‐effective, simple, and easy‐to‐employ workflow, resulting in assemblable data sculptures (i.e., semi‐transparent sliceforms). It primarily supports volumetric data (such as CT or MRI), but mesh data can also be imported. An octree slices the imported volume and an optimization step simplifies the slice configuration, proposing the optimal order for easy assembly. A packing algorithm places the resulting slices with their labels, annotations, and assembly instructions on a paper or transparent film of user‐selected size, to be printed, assembled into a sliceform, and explored. We conducted two user studies to assess our approach, demonstrating that it is an initial positive step towards the successful creation of interactive and engaging anatomical physicalizations. [ABSTRACT FROM AUTHOR]

This paper presents an in depth comparison of state‐of‐the‐art precise shadowing techniques for an omnidirectional point light. We chose several types of modern shadowing algorithms, starting from stencil shadow volumes, methods using traversal of acceleration structures to hardware‐accelerated ray‐traced shadows. Some methods were further improved – robustness, increased performance; we also provide the first multi‐platform implementations of some of the tested algorithms. All the methods are evaluated on several test scenes in different resolutions and on two hardware platforms – with and without dedicated hardware units for ray tracing. We conclude our findings based on speed and memory consumption. Ray‐tracing is the fastest and one of the easiest methods to implement with small memory footprint. The Omnidirectional Frustum‐Traced Shadows method has a predictable memory footprint and is the second fastest algorithm tested. Our stencil shadow volumes are faster than some newer algorithms. Per‐Triangle Shadow Volumes and Clustered Per‐Triangle Shadow Volumes are difficult to implement and require the most memory; the latter method scales well with the scene complexity and resolution. Deep Partitioned Shadow Volumes does not excel in any of the measured parameters and is suitable for smaller scenes. The source codes of the testing framework have been made publicly available. [ABSTRACT FROM AUTHOR]

An effective fragment merging technique is presented in this study that addresses multi‐fragment problems, including fragment overflow and z‐fighting, and provides visual effects that are beneficial for various screen‐space rendering algorithms. The proposed method merges locally adjacent fragments along the viewing direction to resolve the aforementioned problems based on cost‐effective multi‐layer representation and coplanar blending. We introduce a z‐thickness model based on the radiosity spreading from the viewing z‐direction. Moreover, we present the fragment‐merging schemes and rules for determining the visibility of the merged fragments based on the proposed z‐thickness model. The proposed method is targeted at multi‐fragment rendering that handles individual fragments (e.g., k‐buffer) instead of representing the fragments as an approximated transmittance function. In addition, our method provides a smooth visibility transition across overlapping fragments, resulting in visual advantages in various visualization applications. In this paper, we demonstrate the advantages of the proposed method through several screen‐space rendering applications. [ABSTRACT FROM AUTHOR]

Existing keyframe‐based motion synthesis mainly focuses on the generation of cyclic actions or short‐term motion, such as walking, running, and transitions between close postures. However, these methods will significantly degrade the naturalness and diversity of the synthesized motion when dealing with complex and impromptu movements , e.g., dance performance and martial arts. In addition, current research lacks fine‐grained control over the generated motion, which is essential for intelligent human‐computer interaction and animation creation. In this paper, we propose a novel keyframe‐based motion generation network based on multiple constraints, which can achieve diverse dance synthesis via learned knowledge. Specifically, the algorithm is mainly formulated based on the recurrent neural network (RNN) and the Transformer architecture. The backbone of our network is a hierarchical RNN module composed of two long short‐term memory (LSTM) units, in which the first LSTM is utilized to embed the posture information of the historical frames into a latent space, and the second one is employed to predict the human posture for the next frame. Moreover, our framework contains two Transformer‐based controllers, which are used to model the constraints of the root trajectory and the velocity factor respectively, so as to better utilize the temporal context of the frames and achieve fine‐grained motion control. We verify the proposed approach on a dance dataset containing a wide range of contemporary dance. The results of three quantitative analyses validate the superiority of our algorithm. The video and qualitative experimental results demonstrate that the complex motion sequences generated by our algorithm can achieve diverse and smooth motion transitions between keyframes, even for long‐term synthesis. [ABSTRACT FROM AUTHOR]

Image editing is a commonly studied problem in computer graphics. Despite the presence of many advanced editing tools, there is no satisfactory solution to controllably update the position of the sun using a single image. This problem is made complicated by the presence of clouds, complex landscapes, and the atmospheric effects that must be accounted for. In this paper, we tackle this problem starting with only a single photograph. With the user clicking on the initial position of the sun, our algorithm performs several estimation and segmentation processes for finding the horizon, scene depth, clouds, and the sky line. After this initial process, the user can make both fine‐ and large‐scale changes on the position of the sun: it can be set beneath the mountains or moved behind the clouds practically turning a midday photograph into a sunset (or vice versa). We leverage a precomputed atmospheric scattering algorithm to make all of these changes not only realistic but also in real‐time. We demonstrate our results using both clear and cloudy skies, showing how to add, remove, and relight clouds, all the while allowing for advanced effects such as scattering, shadows, light shafts, and lens flares. [ABSTRACT FROM AUTHOR]

The simulation of two‐dimensional human locomotion in a bird's eye perspective is a key technology for various domains to realistically predict walk paths. The generated trajectories, however, are frequently deviating from reality due to the usage of simplifying assumptions. For instance, common deterministic motion planning algorithms predominantly utilize a set of static steering parameters (e.g. maximum acceleration or velocity of the agent) to simulate the walking behaviour of a person. This procedure neglects important influence factors, which have a significant impact on the spatio‐temporal characteristics of the finally resulting motion—such as the operator's physical conditions or the probabilistic nature of the human locomotor system. In overcome this drawback, this paper presents an approach to derive probabilistic motion models from a database of captured human motions. Although being initially designed for industrial purposes, this method can be applied to a wide range of use cases while considering an arbitrary number of dependencies (input) and steering parameters (output). To underline its applicability, a probabilistic steering parameter model is implemented, which models velocity, angular velocity and acceleration as a function of the travel distances, path curvature and height of a respective person. Finally, the technical performance and advantages of this model are demonstrated within an evaluation. The simulation of two‐dimensional human locomotion in a bird's eye perspective is a key technology for various domains to realistically predict walk paths. The generated trajectories, however, are frequently deviating from reality due to the usage of simplifying assumptions. For instance, common deterministic motion planning algorithms predominantly utilize a set of static steering parameters (e.g. maximum acceleration or velocity of the agent) to simulate the walking behaviour of a person. This procedure neglects important influence factors, which have a significant impact on the spatio‐temporal characteristics of the finally resulting motion—such as the operator's physical conditions or the probabilistic nature of the human locomotor system. In overcome this drawback, this paper presents an approach to derive probabilistic motion models from a database of captured human motions. Although being initially designed for industrial purposes, this method can be applied to a wide range of use cases while considering an arbitrary number of dependencies (input) and steering parameters (output). [ABSTRACT FROM AUTHOR]

Abstract: This paper describes a general algorithm and a system for load balancing sparse fluid simulations. Automatically distributing sparse fluid simulations efficiently is challenging because the computational load varies across the simulation domain and time. A key challenge with load balancing is that optimal decision making requires knowing the fluid distribution across partitions for future time steps, but computing this state for an arbitrary simulation requires running the simulation itself. The key insight of this paper is that it is possible to predict future load by running a speculative low resolution simulation in parallel. We mathematically formulate the problem of load balancing over multiple time steps and present a polynomial time algorithm to compute an approximate solution to it. Our experimental results show that distributing and speculatively load balancing sparse FLIP simulations over 8 nodes speeds them up by 5.3× to 7.9×, and that speculative load balancing generates assignments that perform within 20% of optimal. [ABSTRACT FROM AUTHOR]

The global routing network is the backbone of the Internet. However, it is quite vulnerable to attacks that cause major disruptions or routing manipulations. Prior related works have visualized routing path changes with node link diagrams, but it requires strong domain expertise to understand if a routing change between autonomous systems is suspicious. Geographic visualization has an advantage over conventional node‐link diagrams by helping uncover such suspicious routes as the user can immediately see if a path is the shortest path to the target or an unreasonable detour. In this paper, we present ProBGP, a web‐based progressive approach to visually analyze BGP update routes. We created a novel progressive data processing algorithm for the geographic approximation of autonomous systems and combined it with a progressively updating visualization. While the newest log data is continuously loaded, our approach also allows querying the entire log recordings since 1999. We present the usefulness of our approach with a real use case of a major route leak from June 2019. We report on multiple interviews with domain experts throughout the development. Finally, we evaluated our algorithm quantitatively against a public peering database and qualitatively against AS network maps. [ABSTRACT FROM AUTHOR]

This paper presents a scalable online occlusion culling algorithm, which significantly improves the previous raster occlusion culling using object‐level bounding volume hierarchy. Given occluders found with temporal coherence, we find and rasterize coarse groups of potential occludees in the hierarchy. Within the rasterized bounds, per‐pixel ray casting tests fine‐grained visibilities of every individual occludees. We further propose acceleration techniques including the read‐back of counters for tightly‐packed multidrawing and occluder filtering. Our solution requires only constant draw calls for batch occlusion tests, while avoiding costly iteration for hierarchy traversal. Our experiments prove our solution outperforms the existing solutions in terms of scalability, culling efficiency, and occlusion‐query performance. [ABSTRACT FROM AUTHOR]

Abstract: This paper surveys mesh segmentation techniques and algorithms, with a focus on part‐based segmentation, that is, segmentation that divides a mesh (featuring a 3D object) into meaningful parts. Part‐based segmentation applies to a single object and also to a family of objects (i.e. co‐segmentation). However, we shall not address here chart‐based segmentation, though some mesh co‐segmentation methods employ such chart‐based segmentation in the initial step of their pipeline. Finally, the taxonomy proposed in this paper is new in the sense that one classifies each segmentation algorithm regarding the dimension (i.e. 1D, 2D and 3D) of the representation of object parts. The leading idea behind this survey is to identify the properties and limitations of the state‐of‐the‐art algorithms to shed light on the challenges for future work. [ABSTRACT FROM AUTHOR]

In physics‐based character animation, Proportional‐Derivative (PD) controllers are commonly used for tracking reference motions in motor control tasks. Stable PD (SPD) controllers significantly improve the numerical stability of traditional PD controllers and support large gains and large integration time steps during simulation [TLT11]. For an articulated rigid body system with n degrees of freedom, all SPD implementations to date, however, use an O(n3) dense matrix factorization based method. In this paper, we propose a linear time algorithm for SPD computation, which is based on Featherstone's forward dynamics formulation for articulated rigid body systems in generalized coordinates [Fea14]. We demonstrate the performance advantage of our algorithm by comparing with both the conventional dense matrix factorization based method and an alternative sparse matrix factorization based method. We show that the proposed algorithm provides superior stability when controlling complex models at large time steps. We further demonstrate that our algorithm can improve the learning speed and quality of a Deep Reinforcement Learning (DRL) system for physics‐based character animation. [ABSTRACT FROM AUTHOR]

The "procedural" approach to animating ocean waves is the dominant algorithm for animating larger bodies of water in interactive applications as well as in off‐line productions — it provides high visual quality with a low computational demand. In this paper, we widen the applicability of procedural water wave animation with an extension that guarantees the satisfaction of boundary conditions imposed by terrain while still approximating physical wave behavior. In combination with a particle system that models wave breaking, foam, and spray, this allows us to naturally model waves interacting with beaches and rocks. Our system is able to animate waves at large scales at interactive frame rates on a commodity PC. [ABSTRACT FROM AUTHOR]

Salient object detection is to identify objects or regions with maximum visual recognition in an image, which brings significant help and improvement to many computer visual processing tasks. Although lots of methods have occurred for salient object detection, the problem is still not perfectly solved especially when the background scene is complex or the salient object is small. In this paper, we propose a novel Weak Feature Boosting Network (WFBNet) for the salient object detection task. In the WFBNet, we extract the unpredictable regions (low confidence regions) of the image via a polynomial function and enhance the features of these regions through a well‐designed weak feature boosting module (WFBM). Starting from a coarse saliency map, we gradually refine it according to the boosted features to obtain the final saliency map, and our network does not need any post‐processing step. We conduct extensive experiments on five benchmark datasets using comprehensive evaluation metrics. The results show that our algorithm has considerable advantages over the existing state‐of‐the‐art methods. [ABSTRACT FROM AUTHOR]

3D acquisition of archaeological artefacts has become an essential part of cultural heritage research for preservation or restoration purpose. Statues, in particular, have been at the center of many projects. In this paper, we introduce a way to improve the understanding of acquired statues representing real or imaginary creatures by registering a simple and pliable articulated model to the raw point set data. Our approach performs a Forward And bacKward Iterative Registration (FAKIR) which proceeds joint by joint, needing only a few iterations to converge. We are thus able to detect the pose and elementary anatomy of sculptures, with possibly non realistic body proportions. By adapting our simple skeleton, our method can work on animals and imaginary creatures. [ABSTRACT FROM AUTHOR]

3D shape recognition has been actively investigated in the field of computer graphics. With the rapid development of deep learning, various deep models have been introduced and achieved remarkable results. Most 3D shape recognition methods are supervised and learn only from the large amount of labeled shapes. However, it is expensive and time consuming to obtain such a large training set. In contrast to these methods, this paper studies a semi‐supervised learning framework to train a deep model for 3D shape recognition by using both labeled and unlabeled shapes. Inspired by the co‐training algorithm, our method iterates between model training and pseudo‐label generation phases. In the model training phase, we train two deep networks based on the point cloud and multi‐view representation simultaneously. In the pseudo‐label generation phase, we generate the pseudo‐labels of the unlabeled shapes using the joint prediction of two networks, which augments the labeled set for the next iteration. To extract more reliable consensus information from multiple representations, we propose an uncertainty‐aware consistency loss function to combine the two networks into a multimodal network. This not only encourages the two networks to give similar predictions on the unlabeled set, but also eliminates the negative influence of the large performance gap between the two networks. Experiments on the benchmark ModelNet40 demonstrate that, with only 10% labeled training data, our approach achieves competitive performance to the results reported by supervised methods. [ABSTRACT FROM AUTHOR]

Apollonius diagrams, also known as additively weighted Voronoi diagrams, are an extension of Voronoi diagrams, where the weighted distance is defined by the Euclidean distance minus the weight. The bisectors of Apollonius diagrams have a hyperbolic form, which is fundamentally different from traditional Voronoi diagrams and power diagrams. Though robust solvers are available for computing 2D Apollonius diagrams, there is no practical approach for the 3D counterpart. In this paper, we systematically analyze the structural features of 3D Apollonius diagrams, and then develop a fast algorithm for robustly computing Apollonius diagrams in 3D. Our algorithm consists of vertex location, edge tracing and face extraction, among which the key step is to adaptively subdivide the initial large box into a set of sufficiently small boxes such that each box contains at most one Apollonius vertex. Finally, we use centroidal Voronoi tessellation (CVT) to discretize the curved bisectors with well‐tessellated triangle meshes. We validate the effectiveness and robustness of our algorithm through extensive evaluation and experiments. We also demonstrate an application on computing centroidal Apollonius diagram. [ABSTRACT FROM AUTHOR]

It is still challenging to render directional but non‐specular reflections in complex scenes. The SG‐based (Spherical Gaussian) many‐light framework provides a scalable solution but still requires a large number of glossy virtual lights to avoid spikes as well as reduce clamping errors. Directly gathering contributions from these glossy virtual lights to each pixel in a pairwise way is very inefficient. In this paper, we propose an adaptive algorithm with tighter error bounds to efficiently compute glossy interreflections from glossy virtual lights. This approach is an extension of the Lightcuts that builds hierarchies on both lights and pixels with new error bounds and new GPU‐based traversal methods between light and pixel hierarchies. Results demonstrate that our method is able to faithfully and efficiently compute glossy interreflections in scenes with highly glossy and spatial varying reflectance. Compared with the conventional Lightcuts method, our approach generates lightcuts with only one‐fourth to one‐fifth light nodes therefore exhibits better scalability. Additionally, after being implemented on GPU, our algorithms achieve a magnitude of faster performance than the previous method. [ABSTRACT FROM AUTHOR]

Quad meshes as a surface representation have many conceptual advantages over triangle meshes. Their edges can naturally be aligned to principal curvatures of the underlying surface and they have the flexibility to create strongly anisotropic cells without causing excessively small inner angles. While in recent years a lot of progress has been made towards generating high quality uniform quad meshes for arbitrary shapes, their adaptive and anisotropic refinement remains difficult since a single edge split might propagate across the entire surface in order to maintain consistency. In this paper we present a novel refinement technique which finds the optimal trade‐off between number of resulting elements and inserted singularities according to a user prescribed weighting. Our algorithm takes as input a quad mesh with those edges tagged that are prescribed to be refined. It then formulates a binary optimization problem that minimizes the number of additional edges which need to be split in order to maintain consistency. Valence 3 and 5 singularities have to be introduced in the transition region between refined and unrefined regions of the mesh. The optimization hence computes the optimal trade‐off and places singularities strategically in order to minimize the number of consistency splits — or avoids singularities where this causes only a small number of additional splits. When applying the refinement scheme iteratively, we extend our binary optimization formulation such that previous splits can be undone if this prevents degenerate cells with small inner angles that otherwise might occur in anisotropic regions or in the vicinity of singularities. We demonstrate on a number of challenging examples that the algorithm performs well in practice. [ABSTRACT FROM AUTHOR]

In this paper, we propose an algorithm for fully automatic neural face swapping in images and videos. To the best of our knowledge, this is the first method capable of rendering photo‐realistic and temporally coherent results at megapixel resolution. To this end, we introduce a progressively trained multi‐way comb network and a light‐ and contrast‐preserving blending method. We also show that while progressive training enables generation of high‐resolution images, extending the architecture and training data beyond two people allows us to achieve higher fidelity in generated expressions. When compositing the generated expression onto the target face, we show how to adapt the blending strategy to preserve contrast and low‐frequency lighting. Finally, we incorporate a refinement strategy into the face landmark stabilization algorithm to achieve temporal stability, which is crucial for working with high‐resolution videos. We conduct an extensive ablation study to show the influence of our design choices on the quality of the swap and compare our work with popular state‐of‐the‐art methods. [ABSTRACT FROM AUTHOR]

In this paper, we present a new framework for sublinear time force computation for visualization of big complex graphs. Our algorithm is based on the sampling of vertices for computing repulsion forces and edge sparsification for attraction force computation. More specifically, for vertex sampling, we present three types of sampling algorithms, including random sampling, geometric sampling, and combinatorial sampling, to reduce the repulsion force computation to sublinear in the number of vertices. We utilize a spectral sparsification approach to reduce the number of attraction force computations to sublinear in the number of edges for dense graphs. We also present a smart initialization method based on radial tree drawing of the BFS spanning tree rooted at the center. Experiments show that our new sublinear time force computation algorithms run quite fast, while producing good visualization of large and complex networks, with significant improvements in quality metrics such as shape‐based and edge crossing metrics. [ABSTRACT FROM AUTHOR]

An application may have to load an unknown 3D model and, for enhanced realistic rendering, precompute values over the surface domain, such as light maps, ambient occlusion, or other global‐illumination parameters. High‐quality uv‐unwrapping has several problems, such as seams, distortions, and wasted texture space. Additionally, procedurally generated scene content, perhaps on the fly, can make manual uv unwrapping impossible. Even when artist manipulation is feasible, good uv layouts can require expertise and be highly labor intensive. This paper investigates how to use Sparse Voxel DAGs (or DAGs for short) as one alternative to avoid uv mapping. The result is an algorithm enabling high compression ratios of both voxel structure and colors, which can be important for a baked scene to fit in GPU memory. Specifically, we enable practical usage for an automatic system by targeting efficient real‐time mipmap filtering using compressed textures and adding support for individual mesh voxelizations and resolutions in the same DAG. Furthermore, the latter increases the texture‐compression ratios by up to 32% compared to using one global voxelization, DAG compression by 10 – 15% compared to using a DAG per mesh, and reduces color‐bleeding problems for large mipmap filter sizes. The voxel‐filtering is more costly than standard hardware 2D‐texture filtering. However, for full HD with deferred shading, it is optimized down to 2.5 ± 0.5 ms for a custom multisampling filtering (e.g., targeted for minification of low‐frequency textures) and 5 ± 2 ms for quad‐linear mipmap filtering (e.g., for high‐frequency textures). Multiple textures sharing voxelization can amortize the majority of this cost. Hence, these numbers involve 1–3 textures per pixel (Fig. 1c). [ABSTRACT FROM AUTHOR]

Research in the area of collision detection permeates most of the literature on simulations, interaction and agents planning, being commonly regarded as one of the main bottlenecks for large‐scale systems. To this day, despite its importance, most subareas of collision detection lack a common ground to test and validate solutions, reference implementations and widely accepted benchmark suites. In this paper, we delve into the broad‐phase of collision detection systems, providing both an open‐source framework, named Broadmark, to test, compare and validate algorithms, and an in‐deep analysis of the main techniques used so far to tackle the broad‐phase problem. The technical challenges of building this framework from the software and hardware perspectives are also described. Within our framework, several original and state‐of‐the‐art implementations of CPU and GPU algorithms are bundled, alongside three benchmark scenes to stress algorithms under several conditions. Furthermore, the system is designed to be easily extensible. We use our framework to bring out an extensive performance comparison among assembled solutions, detailing the current CPU and GPU state‐of‐the‐art on a common ground. We believe that Broadmark encompasses the principal insights and tools to derive and evaluate novel algorithms, thus greatly facilitating discussion about successful broad‐phase collision detection solutions. [ABSTRACT FROM AUTHOR]

In this paper, we provide a smooth extension of the energy aware Gauss‐Seidel iteration to the Position‐Based Dynamics (PBD) method. This extension is inspired by the kinetic and potential energy changes equalization and uses the foundations of the recent extended version of PBD algorithm (XPBD). The proposed method is not meant to conserve the total energy of the system and modifies each position constraint based on the equality of the kinetic and potential energy changes within the Gauss‐Seidel process of the XPBD algorithm. Our extension provides an implicit solution for relatively better stiffness during the simulation of elastic objects. We apply our solution directly within each Gauss‐Seidel iteration and it is independent of both simulation step‐size and integration methods. To demonstrate the benefits of our proposed extension with higher frame rates, we develop an efficient and practical mesh coloring algorithm for the XPBD method which provides parallel processing on a GPU. During the initialization phase, all mesh primitives are grouped according to their connectivity. Afterwards, all these groups are computed simultaneously on a GPU during the simulation phase. We demonstrate the benefits of our method with many spring potential and strain‐based continuous material constraints. Our proposed algorithm is easy to implement and seamlessly fits into the existing position‐based frameworks. [ABSTRACT FROM AUTHOR]

There are many methods proposed for generating polycube polyhedrons, but it lacks the study about the possibility of generating polycube polyhedrons. In this paper, we prove a theorem for characterizing the necessary condition for the skeleton graph of a polycube polyhedron, by which Steinitz's theorem for convex polyhedra and Eppstein's theorem for simple orthogonal polyhedra are generalized to polycube polyhedra of any genus and with non‐simply connected faces. Based on our theorem, we present a faster linear algorithm to determine the dimensions of the polycube shape space for a valid graph, for all its possible polycube polyhedrons. We also propose a quadratic optimization method to generate embedding polycube polyhedrons with interactive assistance. Finally, we provide a graph‐based framework for polycube mesh generation, quadrangulation, and all‐hex meshing to demonstrate the utility and applicability of our approach. [ABSTRACT FROM AUTHOR]

Recent work has shown that distributing Monte Carlo errors as a blue noise in screen space improves the perceptual quality of rendered images. However, obtaining such distributions remains an open problem with high sample counts and high‐dimensional rendering integrals. In this paper, we introduce a temporal algorithm that aims at overcoming these limitations. Our algorithm is applicable whenever multiple frames are rendered, typically for animated sequences or interactive applications. Our algorithm locally permutes the pixel sequences (represented by their seeds) to improve the error distribution across frames. Our approach works regardless of the sample count or the dimensionality and significantly improves the images in low‐varying screen‐space regions under coherent motion. Furthermore, it adds negligible overhead compared to the rendering times. Note: our supplemental material provides more results with interactive comparisons against previous work. [ABSTRACT FROM AUTHOR]

This paper proposes a new methodology for measuring the error of unbiased physically based rendering algorithms. The current state of the art includes mean squared error (MSE) based metrics and visual comparisons of equal‐time renderings of competing algorithms. Neither is satisfying as MSE does not describe behavior and can exhibit significant variance, and visual comparisons are inherently subjective. Our contribution is two‐fold: First, we propose to compute many short renderings instead of a single long run and use the short renderings to estimate MSE expectation and variance as well as per‐pixel standard deviation. An algorithm that achieves good results in most runs, but with occasional outliers is essentially unreliable, which we wish to quantify numerically. We use per‐pixel standard deviation to identify problematic lighting effects of rendering algorithms. The second contribution is the error spectrum ensemble (ESE), a tool for measuring the distribution of error over frequencies. The ESE serves two purposes: It reveals correlation between pixels and can be used to detect outliers, which offset the amount of error substantially. [ABSTRACT FROM AUTHOR]

Process mining enables organizations to analyze data about their (business) processes. Visualization is key to gaining insight into these processes and the associated data. Process visualization requires a high‐quality graph layout that intuitively represents the semantics of the process. Process analysis additionally requires interactive filtering to explore the process data and process graph. The ideal process visualization therefore provides a high‐quality, intuitive layout and preserves the mental map of the user during the visual exploration. The current industry standard used for process visualization does not satisfy either of these requirements. In this paper, we propose a novel layout algorithm for processes based on the Sugiyama framework. Our approach consists of novel ranking and order constraint algorithms and a novel crossing minimization algorithm. These algorithms make use of the process data to compute stable, high‐quality layouts. In addition, we use phased animation to further improve mental map preservation. Quantitative and qualitative evaluations show that our approach computes layouts of higher quality and preserves the mental map better than the industry standard. Additionally, our approach is substantially faster, especially for graphs with more than 250 edges. [ABSTRACT FROM AUTHOR]

We present visual analysis methods for the evaluation of tomographic fiber reconstruction algorithms by means of analysis, visual debugging and comparison of reconstructed fibers in materials science. The methods are integrated in a tool (FIAKER) that supports the entire workflow. It enables the analysis of various fiber reconstruction algorithms, of differently parameterized fiber reconstruction algorithms and of individual steps in iterative fiber reconstruction algorithms. Insight into the performance of fiber reconstruction algorithms is obtained by a list‐based ranking interface. A 3D view offers interactive visualization techniques to gain deeper insight, e.g., into the aggregated quality of the examined fiber reconstruction algorithms and parameterizations. The tool was designed in close collaboration with researchers who work with fiber‐reinforced polymers on a daily basis and develop algorithms for tomographic reconstruction and characterization of such materials. We evaluate the tool using synthetic datasets as well as tomograms of real materials. Five case studies certify the usefulness of the tool, showing that it significantly accelerates the analysis and provides valuable insights that make it possible to improve the fiber reconstruction algorithms. The main contribution of the paper is the well‐considered combination of methods and their seamless integration into a visual tool that supports the entire workflow. Further findings result from the analysis of (dis‐)similarity measures for fibers as well as from the discussion of design decisions. It is also shown that the generality of the analytical methods allows a wider range of applications, such as the application in pore space analysis. [ABSTRACT FROM AUTHOR]

Superpixel segmentation is a popular image pre‐processing technique in many computer vision applications. In this paper, we present a novel superpixel generation algorithm by agglomerative clustering with quadratic error minimization. We use a quadratic error metric (QEM) to measure the difference of spatial compactness and colour homogeneity between superpixels. Based on the quadratic function, we propose a bottom‐up greedy clustering algorithm to obtain higher quality superpixel segmentation. There are two steps in our algorithm: merging and swapping. First, we calculate the merging cost of two superpixels and iteratively merge the pair with the minimum cost until the termination condition is satisfied. Then, we optimize the boundary of superpixels by swapping pixels according to their swapping cost to improve the compactness. Due to the quadratic nature of the energy function, each of these atomic operations has only O(1) time complexity. We compare the new method with other state‐of‐the‐art superpixel generation algorithms on two datasets, and our algorithm demonstrates superior performance. [ABSTRACT FROM AUTHOR]

Abstract: Stroke correspondence construction is a precondition for vectorized 2D animation inbetweening and remains a challenging problem. This paper introduces the FTP‐SC, a fuzzy topology preserving stroke correspondence technique, which is accurate and provides the user more effective control on the correspondence result than previous matching approaches. The method employs a two‐stage scheme to progressively establish the stroke correspondence construction between the keyframes. In the first stage, the stroke correspondences with high confidence are constructed by enforcing the preservation of the so‐called “fuzzy topology” which encodes intrinsic connectivity among the neighboring strokes. Starting with the high‐confidence correspondences, the second stage performs a greedy matching algorithm to generate a full correspondence between the strokes. Experimental results show that the FTP‐SC outperforms the existing approaches and can establish the stroke correspondence with a reasonable amount of user interaction even for keyframes with large geometric and spatial variations between strokes. [ABSTRACT FROM AUTHOR]

This paper presents a novel system that enables a fully automatic modeling of both 3D geometry and functionality of a mechanism assembly from a single RGB image. The resulting 3D mechanism model highly resembles the one in the input image with the geometry, mechanical attributes, connectivity, and functionality of all the mechanical parts prescribed in a physically valid way. This challenging task is realized by combining various deep convolutional neural networks to provide high‐quality and automatic part detection, segmentation, camera pose estimation and mechanical attributes retrieval for each individual part component. On the top of this, we use a local/global optimization algorithm to establish geometric interdependencies among all the parts while retaining their desired spatial arrangement. We use an interaction graph to abstract the inter‐part connection in the resulting mechanism system. If an isolated component is identified in the graph, our system enumerates all the possible solutions to restore the graph connectivity, and outputs the one with the smallest residual error. We have extensively tested our system with a wide range of classic mechanism photos, and experimental results show that the proposed system is able to build high‐quality 3D mechanism models without user guidance. [ABSTRACT FROM AUTHOR]

Extracting a faithful and compact representation of an animated surface mesh is an important problem for computer graphics. However, the surface‐based methods have limited approximation power for volume preservation when the animated sequences are extremely simplified. In this paper, we introduce Deformable Medial Axis Transform (DMAT), which is deformable medial mesh composed of a set of animated spheres. Starting from extracting an accurate and compact representation of a static MAT as the template and partitioning the vertices on the input surface as the correspondences for each medial primitive, we present a correspondence‐based approximation method equipped with an As‐Rigid‐As‐Possible (ARAP) deformation energy defined on medial primitives. As a result, our algorithm produces DMAT with consistent connectivity across the whole sequence, accurately approximating the input animated surfaces. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we present Hypersliceplorer, an algorithm for generating 2D slices of multi‐dimensional shapes defined by a simplical mesh. Often, slices are generated by using a parametric form and then constraining parameters to view the slice. In our case, we developed an algorithm to slice a simplical mesh of any number of dimensions with a two‐dimensional slice. In order to get a global appreciation of the multi‐dimensional object, we show multiple slices by sampling a number of different slicing points and projecting the slices into a single view per dimension pair. These slices are shown in an interactive viewer which can switch between a global view (all slices) and a local view (single slice). We show how this method can be used to study regular polytopes, differences between spaces of polynomials, and multi‐objective optimization surfaces. [ABSTRACT FROM AUTHOR]

Abstract: Sets of multiple scalar fields can be used to model many types of variation in data, such as uncertainty in measurements and simulations or time‐dependent behavior of scalar quantities. Many structural properties of such fields can be explained by dependencies between different points in the scalar field. Although these dependencies can be of arbitrary complexity, correlation, i.e., the linear dependency, already provides significant structural information. Existing methods for correlation analysis are usually limited to positive correlation, handle only local dependencies, or use combinatorial approximations to this continuous problem. We present a new approach for computing and visualizing correlated regions in sets of 2‐dimensional scalar fields. This paper describes the following three main contributions: (i) An algorithm for hierarchical correlation clustering resulting in a dendrogram, (ii) a generalization of topological landscapes for dendrogram visualization, and (iii) a new method for incorporating negative correlation values in the clustering and visualization. All steps are designed to preserve the special properties of correlation coefficients. The results are visualized in two linked views, one showing the cluster hierarchy as 2D landscape and the other providing a spatial context in the scalar field's domain. Different coloring and texturing schemes coupled with interactive selection support an exploratory data analysis. [ABSTRACT FROM AUTHOR]

Abstract: Rendering vector maps is a key challenge for high‐quality geographic visualization systems. In this paper, we present a novel approach to visualize vector maps over detailed terrain models in a pixel‐precise way. Our method proposes a deferred line rendering technique to display vector maps directly in a screen‐space shading stage over the 3D terrain visualization. Due to the absence of traditional geometric polygonal rendering, our algorithm is able to outperform conventional vector map rendering algorithms for geographic information systems, and supports advanced line anti‐aliasing as well as slope distortion correction. Furthermore, our deferred line rendering enables interactively customizable advanced vector styling methods as well as a tool for interactive pixel‐based editing operations. [ABSTRACT FROM AUTHOR]

Compactly representing time-varying geometries is an important issue in dynamic geometry processing. This paper proposes a framework of sparse localized decomposition for given animated meshes by analyzing the variation of edge lengths and dihedral angles (LAs) of the meshes. It first computes the length and dihedral angle of each edge for poses and then evaluates the difference (residuals) between the LAs of an arbitrary pose and their counterparts in a reference one. Performing sparse localized decomposition on the residuals yields a set of components which can perfectly capture local motion of articulations. It supports intuitive articulation motion editing through manipulating the blending coefficients of these components. To robustly reconstruct poses from altered LAs, we devise a connection-map-based algorithm which consists of two steps of linear optimization. A variety of experiments show that our decomposition is truly localized with respect to rotational motions and outperforms state-of-the-art approaches in precisely capturing local articulated motion. [ABSTRACT FROM AUTHOR]

Designing realistic noise patterns from scratch is hard. To solve this problem, recent contributions have proposed involved spectral analysis algorithms that enable procedural noise models to faithfully reproduce some class of textures. The aim of this paper is to propose the simplest and most efficient noise model that allows for the reproduction of any Gaussian texture. Texton noise is a simple sparse convolution noise that sums randomly scattered copies of a small bilinear texture called texton. We introduce an automatic algorithm to compute the texton associated with an input texture image that concentrates the input frequency content into the desired texton support. One of the main features of texton noise is that its evaluation only consists to sum 30 texture fetches on average. Consequently, texton noise generates Gaussian textures with an unprecedented evaluation speed for noise by example. A second main feature of texton noise is that it allows for high-quality on-the-fly anisotropic filtering by simply invoking existing GPU hardware solutions for texture fetches. In addition, we demonstrate that texton noise can be applied on any surface using parameterization-free surface noise and that it allows for noise mixing. [ABSTRACT FROM AUTHOR]

This paper presents the evolution of a data structures and algorithms course based on a specific computer graphics problem, namely, photon mapping, as the teaching medium. The paper reports development of the course through several iterations and evaluations, dating back 5 years. The course originated as a problem-based graphics course requiring sophomore students to implement Hoppe et al.'s algorithm for surface reconstruction from unorganized points found in their SIGGRAPH '92 paper of the same title. Although the solution to this problem lends itself well to an exploration of data structures and code modularization, both of which are traditionally taught in early computer science courses, the algorithm's complexity was reflected in students' overwhelmingly negative evaluations. Subsequently, because implementation of the kd-tree was seen as the linchpin data structure, it was again featured in the problem of ray tracing trees consisting of more than 250 000 000 triangles. Eventually, because the tree rendering was thought too specific a problem, the photon mapper was chosen as the semester-long problem considered to be a suitable replacement. This paper details the resultant course description and outline, from its now three semesters of teaching. [ABSTRACT FROM AUTHOR]

Interactive rigid body simulation is an important part of many modern computer tools, which no authoring tool nor game engine can do without. Such high-performance computer tools open up new possibilities for changing how designers, engineers, modelers and animators work with their design problems. This paper is a self contained state-of-the-art report on the physics, the models, the numerical methods and the algorithms used in interactive rigid body simulation all of which have evolved and matured over the past 20 years. Furthermore, the paper communicates the mathematical and theoretical details in a pedagogical manner. This paper is not only a stake in the sand on what has been done, it also seeks to give the reader deeper insights to help guide their future research. [ABSTRACT FROM AUTHOR]

This paper presents a new preconditioning technique for large-scale geometric optimization problems, inspired by applications in mesh parameterization. Our positive (semi-)definite preconditioner acts on the gradients of optimization problems whose variables are positions of the vertices of a triangle mesh in ℝ2 or of a tetrahedral mesh in ℝ3, converting localized distortion gradients into the velocity of a globally near-rigid motion via a linear solve. We pose our preconditioning tool in terms of the Killing energy of a deformation field and provide new efficient formulas for constructing Killing operators on triangle and tetrahedral meshes. We demonstrate that our method is competitive with state-of-the-art algorithms for locally injective parameterization using a variety of optimization objectives and show applications to two- and three-dimensional mesh deformation. [ABSTRACT FROM AUTHOR]

2D Confocal Raman Microscopy (CRM) data consist of high dimensional per-pixel spectral data of 1000 bands and allows for complex spectral and spatial-spectral analysis tasks, i.e., in material discrimination, material thickness, and spatial material distributions. Currently, simple integral methods are commonly applied as visual analysis solutions to CRM data which exhibit restricted discrimination power in various regards. In this paper we present a novel approach for the visual analysis of 2D multispectral CRM data using multi-variate visualization techniques. Due to the large amount of data and the demand of an explorative approach without a-priori restriction, our system allows for arbitrary interactive (de)selection of varaibles w/o limitation and an unrestricted online definition/construction of new, combined properties. Our approach integrates CRM specific quantitative measures and handles material-related features for mixed materials in a quantitative manner. Technically, we realize the online definition/construction of new, combined properties as semi-automatic, cascaded, 1D and 2D multidimensional transfer functions (MD-TFs). By interactively incorporating new (raw or derived) properties, the dimensionality of the MD-TF space grows during the exploration procedure and is virtually unlimited. The final visualization is achieved by an enhanced color mixing step which improves saturation and contrast. [ABSTRACT FROM AUTHOR]