Frontiers of Information Technology & Electronic Engineering
>> 2016,
Volume 17,
Issue 10
doi:
10.1631/FITEE.1500390
Article
Ray-triangular Bézier patch intersection using hybrid clipping algorithm
. School of Mathematical Sciences, Xiamen University, Xiamen 361005, China.. Fujian Provincial Key Laboratory of Mathematical Modeling and High-Performance Scientific Computation, Xiamen University, Xiamen 361005, China.. School of Information Science and Engineering, Xiamen University, Xiamen 361005, China
Available online: 2016-11-04
Next
Previous
Abstract
In this paper, we present a novel geometric method for efficiently and robustly computing intersections between a ray and a triangular Bézier patch defined over a triangular domain, called the hybrid clipping (HC) algorithm. If the ray pierces the patch only once, we locate the parametric value of the intersection to a smaller triangular domain, which is determined by pairs of lines and quadratic curves, by using a multi-degree reduction method. The triangular domain is iteratively clipped into a smaller one by combining a subdivision method, until the domain size reaches a prespecified threshold. When the ray intersects the patch more than once, Descartes’ rule of signs and a split step are required to isolate the intersection points. The algorithm can be proven to clip the triangular domain with a cubic convergence rate after an appropriate preprocessing procedure. The proposed algorithm has many attractive properties, such as the absence of an initial guess and insensitivity to small changes in coefficients of the original problem. Experiments have been conducted to illustrate the efficacy of our method in solving ray-triangular Bézier patch intersection problems.
京公网安备 11010502051620号
