An Adaptive \(O(n\log n)\) Algorithm for Discretizing 3D Parametric Spherical Curves
摘要
We present an adaptive \(O(n\log {n})\) algorithm for discretizing three-dimensional parametric curves. The goal is to generate a minimal set of sample points for polyline rendering while maintaining visual fidelity under arbitrary rotations and projections. Unlike traditional subtractive algorithms such as Ramer–Douglas–Peucker or Visvalingam–Whyatt, our method is additive and curvature-driven. Starting from a small set of temporally equidistant seed points, the algorithm iteratively refines the curve by inserting new points in regions of high curvature. The curvature is approximated using the area of the triangle formed by adjacent sample points, allowing for a computationally simple curvature proxy. The resulting approach adaptively balances visual aesthetic and computational efficiency, making it suitable for real-time rendering of spherical curves and other applications requiring smooth low-sample curve representations.