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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

An Adaptive \(O(n\log n)\) Algorithm for Discretizing 3D Parametric Spherical Curves

  • Hans Dulimarta,
  • William Dickinson

摘要

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.