基于多重增量递推和采样点分解的求交算法

A Ray Intersecting Algorithm Based on Multiple Incremental Computing and Sampled Points Decomposing

同一投射光线上相邻采样点间以及屏幕相邻像素点投射光线上的递推增量间都存在着递推关系 ,本文据此提出一种利用这些递推关系来快速计算采样点坐标的多重增量递推算法 ,使投射光线与采样平面间交点的计算完全避免了乘法运算 ,同时把采样点坐标分解为整数和浮点数两部分 ,避免了计算采样点坐标时浮点数的取整运算。综合应用多重增量递推和采样点分解技术 ,对于采用三线性插值方式和常规光线投射算法 ,渲染速度达到传统采样点计算方式的 2倍以上 ,且不需要额外的内存消耗和预处理 ,也不损失图像质量 。

Based on the following fact that coherence exists between consecutive sampled points along the same ray and incremental values between adjacent screen pixels cast from rays on them also have simple coherences,an algorithm of multiple incremental computation is presented to do fast calculation of sampled points coordinates.Using this algorithm,multiplication operation can be completely avoided and only incremental addition operation is required during computing the intersection points between a ray and the sampled plane.Meantime,coordinates of sampled points are decomposed into two components comprised of an integer and a floating-point number to avoid truncating floating-point numbers.Applying both methods together,we can improve rendering speed to at least two times of that as normal ray casting algorithm using tri-linear interpolation.Moreover,it does not require additional memory cost and pre-processing,and also does not degrade the quality of rendered images.Therefore,the proposed algorithm is quite useful in virtual endoscopy system.