Please wait a minute...
FITEE
Front. Inform. Technol. Electron. Eng.  2016, Vol. 17 Issue (10): 1018-1030    DOI: 10.1631/FITEE.1500390
    
射线与三角Bézier曲面交点的混合裁剪算法
Yan-hong Liu, Juan Cao, Zhong-gui Chen, Xiao-ming Zeng
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  
Ray-triangular Bézier patch intersection using hybrid clipping algorith
Yan-hong Liu, Juan Cao, Zhong-gui Chen, Xiao-ming Zeng
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
 全文: PDF 
摘要： \n 概要：本文提出了一种快速、稳定的几何算法来求解射线与三角Bézier曲面的交点，我们把这种新方法称为混合裁剪算法（简称HC（hybrid clipping）算法）。若射线只穿过曲面一次，通过降阶逼近算法，我们得到参数域上的一对直线和一对二次曲线，进而可将交点的参数范围限定在一个比原参数域更小的三角域上。结合细分算法，原三角域可以被反复剪裁，直到参数域的直径小于给定的阈值。当射线与曲面的交点个数大于1时，本文利用Descartes符号法则和细分算法将参数域分割成一些子区域，使得每个子区域只包含一个交点。本文从理论上证明了，经过适当的预处理，HC算法在单根的情况下具有三阶的收敛速度。此外，HC算法具有许多优良的性质，如无需初始值以及对初始问题扰动不敏感等。数值实验也表明了HC算法在解决射线与三角Bézier曲面求交问题的有效性。
\n
关键词： 光线跟踪;  三角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.
Key words: Ray tracing    Triangular Bézier surface    Ray-patch intersection    Root-finding    Hybrid clipping
收稿日期: 2015-11-10 出版日期: 2016-10-08
CLC:  TP391.7  
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
Yan-hong Liu
Juan Cao
Zhong-gui Chen
Xiao-ming Zeng

引用本文:

Yan-hong Liu, Juan Cao, Zhong-gui Chen, Xiao-ming Zeng. Ray-triangular Bézier patch intersection using hybrid clipping algorith. Front. Inform. Technol. Electron. Eng., 2016, 17(10): 1018-1030.

链接本文:

http://www.zjujournals.com/xueshu/fitee/CN/10.1631/FITEE.1500390    或    http://www.zjujournals.com/xueshu/fitee/CN/Y2016/V17/I10/1018

[1] . Image meshing via hierarchical optimization[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(1): 32-40.
[2] Xiao Liu, Jia-min Liu, An-xi Cao, Zhuang-le Yao. 一种新型三维不规则排样构造算法HAPE3D[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(5): 380-390.
[3] Divya Udayan J, HyungSeok Kim, Jee-In Kim. 基于3D空间组件提取和排列的古建筑重建图像方法[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(1): 12-27.
[4] Xiao-juan Duan, Guo-zhao Wang. UE样条曲线的升阶[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(12): 1098-1105.
[5] Yong-wei Miao, Fei-xia Hu, Min-yan Chen, Zhen Liu, Hua-hao Shou. 视觉显著性引导的特征敏感形状简化[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(9): 744-753.
[6] Fei-wei Qin, Lu-ye Li, Shu-ming Gao, Xiao-ling Yang, Xiang Chen. 用于三维CAD模型分类的深度学习方法[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(2): 91-106.
[7] Lie-fu Ai, Jun-qing Yu, Yun-feng He, Tao Guan. High-dimensional indexing technologies for large scale content-based image retrieval: a review[J]. Front. Inform. Technol. Electron. Eng., 2013, 14(7): 505-520.
[8] Xiao-hong Tan, Rui-min Shen, Yan Wang. Personalized course generation and evolution based on genetic algorithms[J]. Front. Inform. Technol. Electron. Eng., 2012, 13(12): 909-917.
[9] Shi-yan Wang, Hui-min Yu. Convex relaxation for a 3D spatiotemporal segmentation model using the primal-dual method[J]. Front. Inform. Technol. Electron. Eng., 2012, 13(6): 428-439.
[10] Juan Cao, Guo-zhao Wang. Non-uniform B-spline curves with multiple shape parameters[J]. Front. Inform. Technol. Electron. Eng., 2011, 12(10): 800-808.
[11] Yu-lei Geng, Jin Wang, Guo-dong Lu, Zheng Liu, Gang Chen. Sketch based garment modeling on an arbitrary view of a 3D virtual human model[J]. Front. Inform. Technol. Electron. Eng., 2011, 12(3): 195-203.
[12] Chun-luan Zhou, Jun Xiao. Cartoon capture by key-frame based contour tracking[J]. Front. Inform. Technol. Electron. Eng., 2011, 12(1): 36-43.
[13] Jia Li, Han-nan Yu, Yong-hong Tian, Tie-jun Huang, Wen Gao. [J]. Frontiers of Information Technology & Electronic Engineering, 2010, 11(11): 850-859.
[14] Wan-qiang Shen, Guo-zhao Wang. Triangular domain extension of linear Bernstein-like trigonometric polynomial basis[J]. Front. Inform. Technol. Electron. Eng., 2010, 11(5): 356-364.
[15] Qian-qian Hu, Guo-jin Wang. Representing conics by low degree rational DP curves[J]. Front. Inform. Technol. Electron. Eng., 2010, 11(4): 278-289.