Ray-triangular Bézier patch intersection using hybrid clipping algorithm

Yan-hong LIU; Juan CAO; Zhong-gui CHEN; Xiao-ming ZENG

doi:10.1631/FITEE.1500390

Your Location：

Home >

Browse articles >

Ray-triangular Bézier patch intersection using hybrid clipping algorithm

Regular Papers | Updated：2022-05-19

- Ray-triangular Bézier patch intersection using hybrid clipping algorithm
- 射线与三角Bézier曲面交点的混合裁剪算法
- Frontiers of Information Technology & Electronic Engineering Vol. 17, Issue 10, Pages: 1018-1030(2016)
- Affiliations：
  
  1School of Mathematical Sciences, Xiamen University, Xiamen 361005, China
  2Fujian Provincial Key Laboratory of Mathematical Modeling and High-Performance Scientific Computation, Xiamen University, Xiamen 361005, China
  3School of Information Science and Engineering, Xiamen University, Xiamen 361005, China
- Author bio：
  
  E-mail: juancao@xmu.edu.cn
- Funds：
- DOI：10.1631/FITEE.1500390
  CLC： TP391.7
- Received：10 November 2015，
  
  Accepted：28 March 2016，
  
  Published：2016-10
- Accepted：
Scan QR Code
Yan-hong LIU, Juan CAO, Zhong-gui CHEN, et al. Ray-triangular Bézier patch intersection using hybrid clipping algorithm[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(10): 1018-1030.
DOI：

Yan-hong LIU, Juan CAO, Zhong-gui CHEN, et al. Ray-triangular Bézier patch intersection using hybrid clipping algorithm[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(10): 1018-1030. DOI： 10.1631/FITEE.1500390.

摘要

本文提出了一种快速、稳定的几何算法来求解射线与三角Bézier曲面的交点，我们把这种新方法称为混合裁剪算法（简称HC（hybrid clipping）算法）。若射线只穿过曲面一次，通过降阶逼近算法，我们得到参数域上的一对直线和一对二次曲线，进而可将交点的参数范围限定在一个比原参数域更小的三角域上。结合细分算法，原三角域可以被反复剪裁，直到参数域的直径小于给定的阈值。当射线与曲面的交点个数大于1时，本文利用Descartes符号法则和细分算法将参数域分割成一些子区域，使得每个子区域只包含一个交点。本文从理论上证明了，经过适当的预处理，HC算法在单根的情况下具有三阶的收敛速度。此外，HC算法具有许多优良的性质，如无需初始值以及对初始问题扰动不敏感等。数值实验也表明了HC算法在解决射线与三角Bézier曲面求交问题的有效性。

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.

关键词

Keywords

references

W Barth , , , W Stürzlinger . . Efficient ray tracing for Bézier and B-spline surfaces . . Comput. Graph. , , 1993 . . 17 ( ( 4 ): ): 423 - - 430 . . DOI: 10.1016/0097-8493(93)90031-4 http://doi.org/10.1016/0097-8493(93)90031-4 . .

M Bartoň , , , B Jüttler . . Computing roots of polynomials by quadratic clipping . . Comput. Aided Geom. Des. , , 2007a . . 24 ( ( 3 ): ): 125 - - 141 . . DOI: 10.1016/j.cagd.2007.01.003 http://doi.org/10.1016/j.cagd.2007.01.003 . .

M Bartoň , , , B Jüttler . . Computing Roots of Systems of Polynomials by Linear Clipping . . 2007b . . SFB F013 Technical Report . . . .

J Garloff , , , A.P Smith . . Investigation of a subdivision based algorithm for solving systems of polynomial equations . . Nonl. Anal. Theory Methods Appl. , , 2001 . . 47 ( ( 1 ): ): 167 - - 178 . . DOI: 10.1016/S0362-546X(01)00166-3 http://doi.org/10.1016/S0362-546X(01)00166-3 . .

E Haines , , , P Hanrahan , , , R.L Cook , , , 等 . . An Introduction to Ray Tracing . . 1989 . . Academic Press, London, UK . . . .

P Hanrahan . . Ray tracing algebraic surfaces . . ACM SIGGRAPH Comput. Graph. , , 1983 . . 17 ( ( 3 ): ): 83 - - 90 . . DOI: 10.1145/964967.801136 http://doi.org/10.1145/964967.801136 . .

K.I Joy , , , C.W Grant , , , N.L Max , , , 等 . . Tutorial: Computer Graphics, Image Synthesis . . 1989 . . IEEE Computer Society Press, Los Alamitos, CA, USA . . . .

B Jüttler , , , B Moore . . A quadratic clipping step with superquadratic convergence for bivariate polynomial systems . . Math. Comput. Sci. , , 2011 . . 5 ( ( 2 ): ): 223 - - 235 . . DOI: 10.1007/s11786-011-0091-4 http://doi.org/10.1007/s11786-011-0091-4 . .

L Liu , , , L Zhang , , , B Lin , , , 等 . . Fast approach for computing roots of polynomials using cubic clipping . . Comput. Aided Geom. Des. , , 2009 . . 26 ( ( 5 ): ): 547 - - 559 . . DOI: 10.1016/j.cagd.2009.02.003 http://doi.org/10.1016/j.cagd.2009.02.003 . .

Q Lou , , , L Liu . . Curve intersection using hybrid clipping . . Comput. Graph. , , 2012 . . 36 ( ( 5 ): ): 309 - - 320 . . DOI: 10.1016/j.cag.2012.03.021 http://doi.org/10.1016/j.cag.2012.03.021 . .

L Lu , , , G Wang . . Multi-degree reduction of triangular Bézier surfaces with boundary constraints . . Comput.- Aided Des. , , 2006 . . 38 ( ( 12 ): ): 1215 - - 1223 . . DOI: 10.1016/j.cad.2006.07.004 http://doi.org/10.1016/j.cad.2006.07.004 . .

G Markus , , , A Oliver . . Interactive ray tracing of trimmed bicubic Bézier surfaces without triangulation . . 2005 . . Proc. 13th Int. Conf. in Central Europe on Computer Graphics, Visualization and Computer Vision . . 71 - - 78 . . . .

W Martin , , , E Cohen , , , R Fish , , , 等 . . Practical ray tracing of trimmed NURBS surfaces . . J. Graph. Tools , , 2000 . . 5 ( ( 1 ): ): 27 - - 52 . . DOI: 10.1080/10867651.2000.10487519 http://doi.org/10.1080/10867651.2000.10487519 . .

R.E Moore , , , S.T Jones . . Safe starting regions for iterative methods . . SIAM J. Numer. Anal. , , 1977 . . 14 ( ( 6 ): ): 1051 - - 1065 . . DOI: 10.1137/0714072 http://doi.org/10.1137/0714072 . .

T Nishita , , , T.W Sederberg , , , M Kakimoto . . Ray tracing trimmed rational surface patches . . ACM SIGGRAPH Comput. Graph. , , 1990 . . 24 ( ( 4 ): ): 337 - - 345 . . DOI: 10.1145/97880.97916 http://doi.org/10.1145/97880.97916 . .

S.H.M Roth , , , P Diezi , , , M.H Gross . . Triangular Bézier clipping. Proc. 8th Pacific Conf. on Computer Graphics and Applications . . 2000 . . 413 - - 414 . . DOI: 10.1109/PCCGA.2000.883971 http://doi.org/10.1109/PCCGA.2000.883971 . .

F Rouillier , , , P Zimmermann . . Efficient isolation of polynomial’s real roots . . J. Comput. Appl. Math. , , 2004 . . 162 ( ( 1 ): ): 33 - - 50 . . DOI: 10.1016/j.cam.2003.08.015 http://doi.org/10.1016/j.cam.2003.08.015 . .

C Schulz . . Bézier clipping is quadratically convergent . . Comput. Aided Geom. Des. , , 2009 . . 26 ( ( 1 ): ): 61 - - 74 . . DOI: 10.1016/j.cagd.2007.12.006 http://doi.org/10.1016/j.cagd.2007.12.006 . .

T.W Sederberg , , , T Nishita . . Curve intersection using Bézier clipping . . Comput.-Aided Des. , , 1990 . . 22 ( ( 9 ): ): 538 - - 549 . . DOI: 10.1016/0010-4485(90)90039-F http://doi.org/10.1016/0010-4485(90)90039-F . .

W Stürzlinger . . Ray-tracing triangular trimmed freeform surfaces . . IEEE Trans. Vis. Comput. Graph. , , 1998 . . 4 ( ( 3 ): ): 202 - - 214 . . DOI: 10.1109/2945.722295 http://doi.org/10.1109/2945.722295 . .

M.A.J Sweeney , , , R.H Bartels . . Ray tracing free-form B-spline surfaces . . IEEE Comput. Graph. Appl. , , 1986 . . 6 ( ( 2 ): ): 41 - - 49 . . DOI: 10.1109/MCG.1986.276691 http://doi.org/10.1109/MCG.1986.276691 . .

D.L Toth . . On ray tracing parametric surfaces . . ACM SIGGRAPH Comput. Graph. , , 1985 . . 19 ( ( 3 ): ): 171 - - 179 . . DOI: 10.1145/325334.325233 http://doi.org/10.1145/325334.325233 . .

C Woodward . . Ray tracing parametric surfaces by subdivision in viewing plane. In: Stra?er, W., Seidel, H.P. (Eds.), Theory and Practice of Geometric Modeling. Springer Berlin Heidelberg . . 1989 . . Germany . . 273 - - 287 . . DOI: 10.1007/978-3-642-61542-9_18 http://doi.org/10.1007/978-3-642-61542-9_18 . .

J Yen , , , S Spach , , , M.T Smith , , , 等 . . Parallel boxing in B-spline intersection . . IEEE Comput. Graph. Appl. , , 1991 . . 11 ( ( 1 ): ): 72 - - 79 . . DOI: 10.1109/38.67703 http://doi.org/10.1109/38.67703 . .

R.J Zhang , , , G Wang . . Constrained Bézier curves’ best multi-degree reduction in the L2-norm . . Progr. Nat. Sci. , , 2005 . . 15 ( ( 9 ): ): 843 - - 850 . . DOI: 10.1080/10020070512331343010 http://doi.org/10.1080/10020070512331343010 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰