Abstract We investigate the evaluation of points and derivatives of Bézier curves and surfaces on modern architectures, focusing on performance and guided by numerical error bounds. While the de Casteljau algorithm remains the reference for numerical robustness, its linear working‐set size imposes substantial register pressure on GPUs. We introduce a linear‐time, constant‐storage evaluation framework derived from the ladder algorithm that attains de Casteljau‐level robustness and demonstrate that it outperforms other methods both on the GPU and CPU. Our analysis provides backward‐error bounds for points and derivatives and it is also supported by empirical tests across degrees commonly used in rendering of curves and surfaces. Moreover, we show that fused multiply‐add (FMA) instructions, now ubiquitous in hardware, can improve robustness even for linear interpolation. We advocate a nested FMA formulation that reconstructs endpoints exactly, in contrast to the subtraction‐and‐FMA pattern prevalent in shader compilers. Together, these results yield reduced memory bandwidth and register pressure, and improved performance.

Creating maps of the world around us is paramount to many applications, including those related to robotics, such as navigation and inspection. Given the computational re-source limitations typical of robotic platforms, there is a pressing need for lightweight 3D representations that capture detailed texture and geometric information with min-imal storage. Traditional voxel-based approaches require substantial memory resources. On the other hand, neural implicit and 3D Gaussian splatting representations require sig-nificant computational power (GPUs) and can hardly run in real time. In this paper, we introduce a novel scene representation, Multi-HexPlanes, that divides 3D environments into large boxes and utilizes the faces of the boxes to encapsulate texture and geometric information. This representation re-duces the memory requirement to store the map, making our approach especially suitable for systems with limited memory. Through extensive evaluations on large-scale datasets, we find that our method achieves better performance on rendering and more complete 3D reconstruction. We also demonstrate that our map representation can output dense feature points with rich geometric information for down-stream tasks, such as training 3D Gaussian splats. The proposed technique promises substantial improvements in real-time 3D mapping applications, particularly for devices constrained by processing power and storage.

Abstract We present a versatile and robust framework to render implicit surfaces defined by black‐box functions that only provide function value queries. We assume that the input function is locally Lipschitz continuous; however, we presume no prior knowledge of its Lipschitz constants. Our pre‐processing step generates a discrete acceleration structure, a Lipschitz field, that provides data to infer local and directional Lipschitz upper bounds. These bounds are used to compute safe step sizes along rays during rendering. The Lipschitz field is constructed by generating local polynomial approximations to the input function, then bounding the derivatives of the approximating polynomials. The accuracy of the approximation is controlled by the polynomial degree and the granularity of the spatial resolution used during fitting, which is independent from the resolution of the Lipschitz field. We demonstrate that our process can be implemented in a massively parallel way, enabling straightforward integration into interactive and real‐time modelling workflows. Since the construction only requires function value evaluations, the input surface may be represented either procedurally or as an arbitrarily filtered grid of function samples. We query the original implicit representation upon ray trace, as such, we preserve the geometric and topological details of the input as long as the Lipschitz field supplies conservative estimates. We demonstrate our method on both procedural and discrete implicit surfaces and compare its exact and approximate variants.

This paper presents a new method for the computation of the generalized Voronoi diagram of planar polygons. First, we show that the vertices of the cut locus can be computed efficiently. This is achieved by enumerating the tripoints of the polygon, a superset of the cut locus vertices. This is the set of all points that are of equal distance to three distinct topological entities. Then our algorithm identifies and connects the appropriate tripoints to form the cut locus vertex connectivity graph, where edges define linear or parabolic boundary segments between the Voronoi regions, resulting in the generalized Voronoi diagram. Our proposed method is validated on complex polygon soups. We apply the algorithm to represent the exact signed distance function of the polygon by augmenting the Voronoi regions with linear and radial functions, calculating the cut locus both inside and outside. • Efficient algorithm for computing generalized Voronoi diagrams for polygon soups. • Our method constructs tripoints by embedding the polygon in a Delaunay triangulation. • Algorithm correctness is argued with a number of geometric theorems and a conjecture. • Exact algorithm utilizes closed-form geometric formulas and graph transformations. • Our robust Matlab implementation performs in O(n log(n)) time for most inputs.