根据光线的空间相关性,本文提出了一种基于图像空间剖分的隐式曲面快速光线跟踪算法。首先对图像空间进行剖分,然后对剖分后的区域进行采样,根据采样结果估计未采样部分的像素值。这种方法避免了大量与曲面不相交的光线测试,而且估计的光线初始长度也减少了光线与曲面求交测

参考文献（五号，黑体）

[1] S. Muraki. Volumetric shape description of range data using blobby model [J]. Computer Graphics

SIGGRAPH’91 Proceedings. 1991, 25(4):227-235.

[2] G. Wyvill, C. Mcpheeters, and B. Wyvill. Data structure for soft objects [J]. The Visual Computer. 1986,

2(4):227-234.

[3] V. V. Savchenko, A. A. Pasko, and O. G. Okunev, et al. Function representation of solids reconstructed from

scattered surface points and contours [J]. Computer Graphics Forum. 1995,14(4):181-188.

[4] J. C. Carr, R. K. Beatson, and J. B. Cherrie, et al. Reconstruction and representation of 3D objects with radial

basis functions [A]. Proceedings of the 28th annual conference on Computer graphics and interactive techniques[C]. New York: ACM Press. 2001, 67-76.

[5] Y. Ohtake, A. Belyaev, and M. Alexa, et al. Multi-level partition of unity implicits [J]. Computer Graphics

SIGGRAPH. 2003, 463-470

[6] Y. Ohtake, A. Belyaev, and M. Alexa. Sparse Low-degree Implicit Surfaces with Applications to High Quality

Rendering, Feature Extraction, and Smoothing[A]. Processing of the third Eurographics symposium on Geometry[C]. Vienna Austria: Eurographics Association. 2005, 149-158.

[7] J. Bloomenthal. Polygonization of Implicit Surfaces [J]. Computer Aided Geometric Design. 1988, 5(4)

341-355.

[8] J. C. Hart. Sphere tracing: a geometric method for the antialiased ray tracing of implicit surfaces[A]. The

Visual Computer[C],New York: Springer Verlag,1996:527-545.

[9] 彭群生,鲍虎军,金小刚. 计算机真实感图形的算法基础[M]. 北京:科学出版社,1999,122-220.

[10] T. Duff. Interval arithmetic and recursive subdivision for implicit functions and constructive solid geometry[J].

Computer Graphics. 1992, 26 (2):131-138.

[11] L. Szirmay-Kalos , V. Havran , and B.Balazs. On the efficiency of ray-shooting acceleration schemes[A].

Proceedings of the Spring Conference on Computer Graphics[C]. Budmerice Slovakia :ACM Press.2002, 97 -106.

[12] J. Cleary, G. Wyvill, Analysis of an algorithm for fast ray tracing using uniform space subdivision [J]. Visual

Computer. 1988, 4(2), 65-83.

[13] O. Fryazinov, A. Pasko. GPU-based real time FRep ray casting [A]. GraphiCon'2007 [C]. 2007, 23-27.

[14] T. Kanai, Y. Ohtake, and H. Kawata, et al. GPU-based Rendering of Sparse Low-degree Implicit Surfaces[A].

In 4th International Conference on Computer Graphics and Interactive Techniques in Australasia and the Southeast Asia (GRAPHITE 2006)[C] . NY: ACM Press. 2006, 165-171.

[15] E. de Groot, B. Wyvill. Rayskip: Faster Ray Tracing of Implicit Surface Animations[A]. International

Conference on Computer Graphics and Interactive Techniques in Australasia and Southeast Asia[C]. Graphite: ACM Press . 2005,31-37.

[16] D. P. Mitchell. Robust ray intersection with interval arithmetic[A]. Proceedings of Graphics Interface ’90[C].

Halifax, Nova Scotia: Canadian Information Processing Society .1990, 68-74.

[17] D. Kalra, A. H. Barr. Guaranteed ray intersections with implicit surfaces [J].Computer Graphics.1989,23(3):

297-306.

[18] J. F. Blinn. A generalization of algebraic surface drawing[J]. ACM Transactions on Graphics. 1982,

1(3):235-256,.

[19] B. V. Herzen, A. H. Barr. Accurate triangulations of deformed, intersecting surfaces[J]. Computer Graphics.

1987,21(4):103-110.

Fast Ray Tracing of Implicit Surfaces Based on Image Space

Subdivision

Wu Ji-yin Pan Rong-jiang

School of Computer Science and Technology, Shandong University, Jinan 250100

Abstract

According to the spatial coherence, a fast algorithm for ray tracing is proposed for rendering implicit surfaces. The image space is subdivided into several small regions which are sampled for rendering. According to results of sampling, it avoids the computation of rays in regions without implicit surfaces and the estimated ray length reduces the computation for finding the first points of intersection between rays and implicit surfaces. Experiments show that the proposed algorithm improves the rendering speed of ray tracing for implicit surfaces without loss of quality.

Keywords: implicit Surface, ray tracing, space subdivision, local sampling