CURDIS:A template for incremental curve discretization algorithms and its application to conics  

作　　者：Philippe LATOUR Marc VAN DROOGENBROECK 

机构地区：[1]Montefiore Institute,University of Liège,Quartier Polytech 1,Allée de la découverte 10,4000 Liège,Belgium

出　　处：《虚拟现实与智能硬件（中英文）》2024年第5期358-382,共25页Virtual Reality & Intelligent Hardware

摘　　要：We introduce CURDIS,a template for algorithms to discretize arcs of regular curves by incrementally producing a list of support pixels covering the arc.In this template,algorithms proceed by finding the tangent quadrant at each point of the arc and determining which side the curve exits the pixel according to a tailored criterion.These two elements can be adapted for any type of curve,leading to algorithms dedicated to the shape of specific curves.While the calculation of the tangent quadrant for various curves,such as lines,conics,or cubics,is simple,it is more complex to analyze how pixels are traversed by the curve.In the case of conic arcs,we found a criterion for determining the pixel exit side.This leads us to present a new algorithm,called CURDIS-C,specific to the discretization of conics,for which we provide all the details.Surprisingly,the criterion for conics requires between one and three sign tests and four additions per pixel,making the algorithm efficient for resource-constrained systems and feasible for fixed-point or integer arithmetic implementations.Our algorithm also perfectly handles the pathological cases in which the conic intersects a pixel twice or changes quadrants multiple times within this pixel,achieving this generality at the cost of potentially computing up to two square roots per arc.We illustrate the use of CURDIS for the discretization of different curves,such as ellipses,hyperbolas,and parabolas,even when they degenerate into lines or corners.

关 键 词：Computer graphics Curve discretization CONICS RASTERIZATION Ellipse drawing Conic spline Conic pencil 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]