Network management applications require large numbers of counters in order to collect traffic characteristics for each network flow. However, these counters often barely fit into on-chip SRAM memories. Past papers have proposed using counter estimators instead, thus trading off counter precision for a lower number of bits. But these estimators do not achieve optimal estimation error, and cannot always scale to arbitrary counter values. In this paper, we introduce the CEDAR algorithm for decoupling the counter estimators from their estimation values, which are quantized into estimation levels and shared among many estimators. These decoupled and shared estimation values enable us to easily adjust them without needing to go through all the counters. We demonstrate how our CEDAR scheme achieves the min-max relative error, i.e., can guarantee the best possible relative error over the entire counter scale. We also explain how to use dynamic adaptive estimation values in order to support counter up-scaling and adjust the estimation error depending on the current maximal counter. Finally we implement CEDAR on FPGA and explain how it can run at line rate. We further analyze its performance and size requirements.

Interactively rendering solid CAD models currently relies on tessellation of the models and passing of the tessellation onto the graphics card (GPU). Direct rendering on the GPU, without a tessellation preprocess, has many advantages -- pixel-level quality, less memory requirements, and less preprocessing, to name a few. However, one of the main problems with existing solutions for rendering solid models directly is the appearance of crack/gap artifacts between faces due to the approximations of the trimming curves. This prevents the usage of direct GPU rendering in CAD systems. In this paper we present a novel solution to the gap problem. The new method combines a unique representation of the faces of the solid model, with fragment shader algorithms that utilize the representation for identifying the surface area to be rendered. This enables us to render the models with high quality in interactive speed without the crack/gap artifacts. We have implemented our method in a ray casting system for viewing CAD solid models and present our results.

We present an algorithm which robustly computes the intersection curve(s) of an under-constrained piecewise polynomial system consisting of n equations with n + 1 unknowns. The solution of such a system is typically a curve in Rn+1. This work extends the single solution test of [6] for a set of algebraic constraints from zero dimensional solutions to univariate solutions, in Rn+1. Our method exploits two tests: a no loop test (NLT) and a single component test (SCT) that together isolate and separate domains D where the solution curve consists of just one single component. For such domains, a numerical curve tracing is applied. If one of those tests fails, D is subdivided. Finally, the single components are merged together and, consequently, the topological configuration of the resulting curve is guaranteed. Several possible application of the solver, like 3D trisector curves or kinematic simulations in 3D are discussed.

Constraint-based geometric modeling is the standard modeling paradigm in current modern CAD systems. Generally, the user defines constraints on the geometric objects and a solver is applied to find a configuration of the geometry, which satisfies these constraints. Proper application of these constraints allows rapid modification of the geometry without loss of design intent.

Arrangements of planar curves are fundamental structures in computational geometry. The arrangement package of Cgal can construct and maintain arrangements of various families of curves, when provided with the representation of the curves and some basic geometric functionality on them. It employs the exact computation paradigm in order to handle all degenerate cases in a robust manner. We present the representations and algorithms needed for implementing arrangements of Bezier curves using exact arithmetic. The implementation is efficient and complete, handling all degenerate cases. In order to avoid the prohibitive running times incurred by an indiscriminate usage of exact arithmetic, we make extensive use of the geometric properties of Bezier curves for filtering. As a result, most operations are carried out using fast approximate methods, and only in degenerate (or near-degenerate) cases do we resort to the exact, and more computationally demanding, procedures. To the best of our knowledge this is the first complete implementation that can construct arrangements of Bezier curves of any degree, and handle all degenerate cases in a robust manner.

We present an algorithm for computing the Voronoi cell for a set of planes, spheres and cylinders in R3. The algorithm is based on a lower envelope computation of the bisector surfaces between these primitives, and the projection of the trisector curves onto planes bounding the object for which the Voronoi cell is computed, denoted the base object. We analyze the different bisectors and trisectors that can occur in the computation. Our analysis shows that most of the bisector surfaces are quadric surfaces and five of the ten possible trisectors are conic section curves. We have implemented our algorithm using the IRIT library and the CGAL 3D lower envelope package. All presented results are from our implementation.

Arrangements of planar curves are fundamental structures in computational geometry. The arrangement package of CGAL can construct and maintain arrangements of various families of curves, when provided with the representation of the curves and some basic geometric functionality on them. It employs the exact computation paradigm in order to handle all degenerate cases in a robust manner. We present the representations and algorithms that are needed for implementing arrangements of Bezier curves using exact arithmetic. The implementation is efficient and complete, handling all degenerate cases. In order to avoid the prohibitive running times incurred by an indiscriminate usage of exact arithmetic, we make extensive use of the geometric properties of Bezier curves for filtering. As a result, most operations are carried out using fast approximate methods, and only in degenerate (or near-degenerate) cases do we resort to the exact, and more computationally demanding, procedures. To the best of our knowledge this is the first complete implementation that can construct arrangements of Bezier curves of any degree, and handle all degenerate cases in a robust manner.

We present an algorithm for generating the Voronoi cells for a set of rational C1-continuous planar closed curves, which is precise up to machine precision. Initially, bisectors for pairs of curves, (C(t), Ci(r)), are generated symbolically and represented as implicit forms in the tr-parameter space. Then, the bisectors are properly trimmed after being split into monotone pieces. The trimming procedure uses the orientation of the original curves as well as their curvature fields, resulting in a set of trimmed-bisector segments represented as implicit curves in a parameter space. A lower-envelope algorithm is then used in the parameter space of the curve whose Voronoi cell is sought. The lower envelope represents the exact boundary of the Voronoi cell.