CLC number: TP391.7
On-line Access: 2024-08-27
Received: 2023-10-17
Revision Accepted: 2024-05-08
Crosschecked: 2016-09-11
Cited: 0
Clicked: 6388
Yan-hong Liu, Juan Cao, Zhong-gui Chen, Xiao-ming Zeng. Ray-triangular Bézier patch intersection using hybrid clipping algorith[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(10): 1018-1030.
@article{title="Ray-triangular Bézier patch intersection using hybrid clipping algorith",
author="Yan-hong Liu, Juan Cao, Zhong-gui Chen, Xiao-ming Zeng",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="17",
number="10",
pages="1018-1030",
year="2016",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.1500390"
}
%0 Journal Article
%T Ray-triangular Bézier patch intersection using hybrid clipping algorith
%A Yan-hong Liu
%A Juan Cao
%A Zhong-gui Chen
%A Xiao-ming Zeng
%J Frontiers of Information Technology & Electronic Engineering
%V 17
%N 10
%P 1018-1030
%@ 2095-9184
%D 2016
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.1500390
TY - JOUR
T1 - Ray-triangular Bézier patch intersection using hybrid clipping algorith
A1 - Yan-hong Liu
A1 - Juan Cao
A1 - Zhong-gui Chen
A1 - Xiao-ming Zeng
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 17
IS - 10
SP - 1018
EP - 1030
%@ 2095-9184
Y1 - 2016
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.1500390
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.
[1]Barth, W., Stürzlinger, W., 1993. Efficient ray tracing for Bézier and B-spline surfaces.Comput. Graph., 17(4):423-430.
[2]Bartoň, M., Jüttler, B., 2007a. Computing roots of polynomials by quadratic clipping.Comput. Aided Geom. Des., 24(3):125-141.
[3]Bartoň, M., Jüttler, B., 2007b. Computing Roots of Systems of Polynomials by Linear Clipping. SFB F013 Technical Report.
[4]Garloff, J., Smith, A.P., 2001. Investigation of a subdivision based algorithm for solving systems of polynomial equations.Nonl. Anal. Theory Methods Appl., 47(1):167-178.
[5]Haines, E., Hanrahan, P., Cook, R.L., et al., 1989. An Introduction to Ray Tracing. Academic Press, London, UK.
[6]Hanrahan, P., 1983. Ray tracing algebraic surfaces.ACM SIGGRAPH Comput. Graph., 17(3):83-90.
[7]Joy, K.I., Grant, C.W., Max, N.L., et al., 1989. Tutorial: Computer Graphics, Image Synthesis. IEEE Computer Society Press, Los Alamitos, CA, USA.
[8]Jüttler, B., Moore, B., 2011. A quadratic clipping step with superquadratic convergence for bivariate polynomial systems.Math. Comput. Sci., 5(2):223-235.
[9]Liu, L., Zhang, L., Lin, B., et al., 2009. Fast approach for computing roots of polynomials using cubic clipping.Comput. Aided Geom. Des., 26(5):547-559.
[10]Lou, Q., Liu, L., 2012. Curve intersection using hybrid clipping.Comput. Graph., 36(5):309-320.
[11]Lu, L., Wang, G., 2006. Multi-degree reduction of triangular Bézier surfaces with boundary constraints.Comput.-Aided Des., 38(12):1215-1223.
[12]Markus, G., Oliver, A., 2005. Interactive ray tracing of trimmed bicubic Bézier surfaces without triangulation. Proc. 13th Int. Conf. in Central Europe on Computer Graphics, Visualization and Computer Vision, p.71-78.
[13]Martin, W., Cohen, E., Fish, R., et al., 2000. Practical ray tracing of trimmed NURBS surfaces.J. Graph. Tools, 5(1):27-52.
[14]Moore, R.E., Jones, S.T., 1977. Safe starting regions for iterative methods.SIAM J. Numer. Anal., 14(6):1051-1065.
[15]Nishita, T., Sederberg, T.W., Kakimoto, M., 1990. Ray tracing trimmed rational surface patches.ACM SIGGRAPH Comput. Graph., 24(4):337-345.
[16]Roth, S.H.M., Diezi, P., Gross, M.H., 2000. Triangular Bézier clipping. Proc. 8th Pacific Conf. on Computer Graphics and Applications, p.413-414.
[17]Rouillier, F., Zimmermann, P., 2004. Efficient isolation of polynomial's real roots.J. Comput. Appl. Math., 162(1):33-50.
[18]Schulz, C., 2009. Bézier clipping is quadratically convergent.Comput. Aided Geom. Des., 26(1):61-74.
[19]Sederberg, T.W., Nishita, T., 1990. Curve intersection using Bézier clipping.Comput.-Aided Des., 22(9):538-549.
[20]Stürzlinger, W., 1998. Ray-tracing triangular trimmed free-form surfaces.IEEE Trans. Vis. Comput. Graph., 4(3):202-214.
[21]Sweeney, M.A.J., Bartels, R.H., 1986. Ray tracing free-form B-spline surfaces.IEEE Comput. Graph. Appl., 6(2): 41-49.
[22]Toth, D.L., 1985. On ray tracing parametric surfaces.ACM SIGGRAPH Comput. Graph., 19(3):171-179.
[23]Woodward, C., 1989. 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, Germany, p.273-287.
[24]Yen, J., Spach, S., Smith, M.T., et al., 1991. Parallel boxing in B-spline intersection.IEEE Comput. Graph. Appl., 11(1):72-79.
[25]Zhang, R.J., Wang, G., 2005. Constrained Bézier curves' best multi-degree reduction in the L2-norm.Progr. Nat. Sci., 15(9):843-850.
Open peer comments: Debate/Discuss/Question/Opinion
<1>