Please use this identifier to cite or link to this item:
標題: 三維模型之成圖與資訊隱藏演算法
Rendering and Information Hiding Algorithms for 3D Model
作者: 張忠賢 
Chang, Chung-Hsien 
關鍵字: rendering;成圖;interactive;information hiding;3D model;互動式;資訊隱藏;三維模型
出版社: 資訊科學系所
引用: [AA03] U. Assarsson, and T. Akenine-Möller, “A Geometry-Based Soft Shadow Volume Algorithm Using Graphics Hardware,” ACM Transactions on Graphics, Vol. 22, No. 3, pp. 511-520, 2003. [ADME02] N. Aspert, E. Drelie, Y. Maret, and T. Ebrahimi, “Steganography for Three-Dimensional Polygonal Meshes,” Proceedings of SPIE 47th Annual Meeting, pp. 705-708, 2002. [ARHM00] M. Agrawala, R. Ramamoorthi, A. Heirich, and L. Moll, ”Efficient Image-Based Methods for Rendering Soft Shadows,” Proceedings of SIGGRAPH 2000, pp. 375- 384, 2000. [Arv86] J. Arvo, “Backward Ray Tracing,” Developments in Ray Tracing, ACM SIGGRAPH 1986 Course Notes 12, pp. 259-263, 1986. [Arv01] J. Arvo, “Stratified Sampling of 2-Manifolds,” State of the Art in Monte Carlo Ray Tracing for Realistic Image Synthesis, ACM SIGGRAPH 2001 Course Notes 29, pp. 41-63, 2001. [Arv95] J. Arvo, “Stratified Sampling of Spherical Triangles,” Proceeding of SIGGRAPH 1995, pp. 437-438, 1995. [Ben99] O. Benedens, “Geometry-Based Watermarking of 3D Models,” IEEE Computer Graphics and Applications, Vol. 19, No.1, pp. 46-55, 1999. [BWCG86] D. R. Baum, J. R. Wallace, M. F. Cohen, and D. P. Greenberg, “The Back-Buffer Algorithm: an Extension of the Radiosity Method to Dynamic Environments”, The Visual Computer, Vol. 2, pp. 298-306, 1986. [CG85] M. F. Cohen and D. P. Greenberg, “The Hemi-Cube: A Radiosity Solution for Complex Environments,” Proceedings of SIGGRAPH 1985, pp. 31-40, 1985. [CHCC06] N. A. Carr, J. Hoberock, K. Crane, J. C. Hart, “Fast GPU Ray Tracing of Dynamic Meshes Using Geometry Images,” to appear in the Proceedings of Graphics Interface 2006, 2006. [Che90] S. E. Chen, “Incremental Radiosity: An Extension of Progressive Radiosity to an Interactive Image Synthesis System”, Computer Graphics, Vol. 24, No. 4, pp. 135-144, 1990. [CHL04] G. Coombe, M. J. Harris, A. Lastra, “Radiosity on Graphics Hardware,” Proceedings of the 2004 Conference on Graphics interface, pp. 161-168, 2004. [CLR93] T. H. Cormen, C. E. Leiserson, and R. L. Riverst, Introduction to Algorithms, the MIT Press, Cambridge, 1993. [CM03] F. Cayre and B. Macq, “Data Hiding on 3D Triangle Meshes,” IEEE Transactions on Signal Processing, Vol. 51, pp. 939-949, 2003. [Cro77] F. C. Crow, “Shadow Algorithms for Computer Graphics,” Computer Graphics, Vol. 11, No. 3, pp. 242-248, 1977. [CW93] M. F. Cohen and J. R. Wallace, Radiosity and Realistic Image Synthesis, Academic Press Professional, San Diego, 1993. [CWPG04] D. Cotting, T. Weyrich, M. Payly, and M. Gross, “Robust Watermarking of Point-Sampled Geometry,” Proceedings of International Conference on Shape Modeling and Applications 2004, pp. 233-242, 2004. [DirectX] Microsoft Corporation , default.mspx, 2006. [FDFF96] J. D. Foley, A. van Dam, S. K. Feiner, and J. F. Hughes, Computer Graphics: Principles and Practice in C, Second Edition, Addison-Wesley, New York, 1996. [FDFH95] J. D. Foley, A. van Dam, S. K. Feiner, and J. F. Hughes, Computer Graphics: Principles and Practice in C, Addison-Wesley Publishing Company, New York, 1995. [FYT94] D. Forsyth, C. Yang, and K. Teo, Photorealistic Rendering Techniques, Springer Verlag, Heidelberg, 1994. [GKBP05] P. Gautron, J. Krivanek, K. Bouatouch, and S. Patttanaik, “Radiance Cache Splatting: A GPU-Friendly Global Illumination Algorithm,” Proceedings of Eurographics Symposium on Rendering 2005, pp. 55-64, 2005. [GSG90] D. W. George, F. Sillion, and D. P. Greenberg, “Radiosity Redistribution for Dynamic Environments”, IEEE Computer Graphics and Applications, Vol. 10, No. 4, pp. 26-34, 1990. [GTP+97] D. P. Greenberg, K. E. Torrance, P. Shirley, J. Arvo, J. A. Ferwerda, S. Pattanaik, E. P. F. Lafortune, B. Walter, S. C. Foo, and B. Trumbore, “A Framework for Realistic Image Synthesis,” Proceedings of SIGGRAPH 1997, pp. 477-494, 1997. [Hai01] E. Haines, “Soft Planar Shadows Using Plateaus,” Journal of Graphics Tools, Vol. 6, No. 1, pp. 19-27, 2001. [Hai06] E. Haines, “An Introductory Tour of Interactive Rendering,” IEEE Computer Graphics and Applications, Vol. 26, No. 1, pp. 76-87, 2006. [Hec92] P. S. Heckbert, “Introduction to Global Illumination,” ACM SIGGRAPH 1992 Course Notes 18, pp. 1-1~1-11, 1992. [Her97] M. Herf, “Efficient Generation of Soft Shadow Textures,” Technical Report CMU-CS-97-138, Carnegie Mellon University, 1997. [HLHS03] J. M. Hasenfratz, M. Lapierre, N. Holzschuch, and F. X. Sillion, “A Survey of Real-time Soft Shadows Algorithms,” EUROGRAPHICS 2003 State-of-the-Art Report, 2003. [HM99] A. Heirich and L. Moll, “Scalable Distributed Visualization Using Off-The-Shelf Components,” Proceedings of IEEE Parallel Visualization and Graphics Symposium, pp. 55-60, 1999. [Kaj86] J. T. Kajiya, “The Rendering Equation”, Computer Graphics, Vol. 20, No. 4, pp.143-150, 1986. [KHM95] C. Kolb, P. Hanrahan, and D. Mitchell, “A Realistic Camera Model for Computer Graphics,” Proceedings of SIGGRAPH 1995, pp. 317-324, 1995. [KP00] S. Katzenbeisser and F. A. P. Petitcolas, Information Hiding Techniques for Steganography and Digital Watermarking, Artech House, London, 2000. [Laf96] E. Lafortune, Mathematical Model and Monte Carlo Algorithm for Physically Based Rendering, Ph.D. Thesis, Department of Computer Science, Katholieke Universiteit Leuven, Belgium, 1996. [LC03] B. D. Larsen, N. J. Christensen, “Real-time Terrain Rendering Using Smooth Hardware Optimized Level of Detail,” Journal of Winter School of Computer Graphics, Vol. 11, No. 1, pp. 282-289, 2003. [LD97] C. Loscos and G. Drettakis, “Interactive High-Quality Soft Shadows in Scenes with Moving Objects,” Computer Graphics Forum, Vol. 16, No. 3, pp. 219-230, 1997. [LTG92] D. Lischinski, F. Tampieri, and D. P. Greenberg, “Discontinuity Meshing for Accurate Radiosity,” IEEE Computer Graphics and Applications, Vol. 12, No. 6, pp. 25-39, 1992. [ME04] Y. Maret and T. Ebrahimi, “Data Hiding on 3D Polygonal Meshes,” Proceedings of the Multimedia and Security Workshop 2004, pp. 68-74, 2004. [MGB74] A. M. Mood, F. A. Graybill, and D. C. Boes, Introduction to the Theory of Statistics, McGraw-Hill, Singapore, 1974. [Muu95] M. J. Muuss, “Towards Real-Time Ray-Tracing of Combinatorial Solid Geometric Models,” Proceedings of BRL-CAD Symposium 1995, 1995. [NVidia01] NVIDIA Corporation. NVIDIA OpenGL Extension Specifications, Available from, 2001. [OMT02] R. Ohbuchi, A. Mukaiyama, and S. Takahashi. “A Frequency-Domain Approach to Watermarking 3D Shapes,” Computer Graphics Forum, Vol. 20, No. 3, pp. 373-382, 2002. [OpenGL],, 2006. [PAK99] F. A. P. Petitcolas, R. J. Anderson, and M. G. Kuhn, “Information Hiding - A Survey,” Proceedings of the IEEE, Special Issue on Protection of Multimedia Content, Vol. 87, No. 7, pp. 1062-1078, 1999. [PDC+03] T. J. Purcell, C. Donner, M. Cammarano, H. W. Jensen, and P. Hanrahan, “Photon Mapping on Programmable Graphics Hardware,” Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware, pp. 41-50, 2003. [Pfi96] B. Pfitzmann, “Information Hiding Terminology,” Lecture Notes in Computer Science, Vol. 1174, pp. 347-349, 1996. [PM93] S. N. Pattanaik and S.P. Mudur, “Computation of Global Illumination in a Participating Medium by Monte Carlo Simulation,” The Journal of Visualization and Computer Animation, Vol. 4, No. 3, pp. 133-152, 1993. [PPD98] E. Paquette, P. Poulin, and G. Drettakis, “A Light Hierarchy for Fast Rendering of Scenes with Many Lights,” Computer Graphics Forum, Vol. 17, No. 3, pp. 63-74, 1998. [PSLHS99] S. Parker, P. Shirley, Y. Livnat, C. Hansen, and P. P. Sloan, ”Interactive Ray Tracing,” Proceedings of Interactive 3D Graphics, pp. 119-126, 1999. [Rayshade] Craig Kolb, rayshade.html, 1997. [RC00] C. Rocchini and P. Cignoni, “Generating Random Points in a Tetrahedron,” Journal of Graphics Tools, Vol. 5, pp. 9-12, 2000. [Ren02] A. C. Rencher, Methods of Multivariate Analysis, Second Edition, Wiley, New York, 2002. [Rub81] R. Y. Rubinstein, Simulation and the Monte Carlo Method, John Wiley & Sons, New York, 1981. [SC97] P. Shirley and K. Chiu, “A Low Distortion Map Between Disk and Square,” Journal of Graphics Tools, Vol. 2, No. 3, pp. 34-52, 1997. [Sha94] E. Shaw, Hierarchical Radiosity for Dynamic Environments, Master thesis, Cornell University, Ithaca, New York, 1994. [Shi91] P. Shirley, “Discrepancy as a Quality Measure for Sample Distributions,” Proceedings of EUROGRAPHICS 1991, pp. 183-193, 1991. [Shi98] P. Shirley, “Monte Carlo Methods in Rendering,” ACM SIGGRAPH 1998 Course Notes 5, pp. 9-1~9-26, 1998. [Shr96] Y. A. Shreider, The Monte Carlo Method, Pergamon Press, New York, 1996. [SS98] C. Soler and F. X. Sillion, “Fast Calculation of Soft Shadow Textures Using Convolution,” Proceedings of SIGGRAPH 1998, pp. 321-332, 1998. [SW91] P. Shirley and C. Wang, “Direct Lighting Calculation by Monte Carlo Integration,” Proceedings of the Second Eurographics Workshop on Rendering, pp. 31-40, 1991. [SW92] P. Shirley and C. Wang, “Distribution Ray Tracing: Theory and Practice,” Proceedings of the Third Eurographics Workshop on Rendering, pp. 33-43, 1992. [SWZ96] P. Shirley, C. Wang, and K. Zimmerman, “Monte Carlo Techniques for Direct Lighting Calculation,” ACM Transactions on Graphics, Vol. 15, No. 1, pp. 1-36, 1996. [TMNFY00] S. Tanaka, A. Morisaki, S. Nakata, Y. Fukuda, and H. Yamamoto, “Sampling Implicit Surfaces Based on Stochastic Differential Equations with Converging Constraint,” Computer and Graphics, Vol. 24, No. 3, pp. 419-431, 2000. [TPWG02] P. Tole, F. Pellacini, B. Walter, and D. P. Greenberg, “Interactive Global Illumination in Dynamic Scenes,” ACM Transactions on Graphics, Vol. 21, No. 3, pp.537-546, 2002. [TTOO90] A. Takage, H. Takaora, T. Oshima, and Y. Ogota, “Accurate Rendering Technique Based on Colorimetric Conception,” Proceedings of SIGGRAPH 1990, pp. 263-272, 1990. [Tur90] G. Turk, “Generating Random Points in Triangles,” Graphics Gems I, pp. 24-28, Academic Press, New York, 1990. [Ure00] C. Urena, “Computation of Irradiance from Triangles by Adaptive Sampling,” Computer Graphics Forum, Vol. 19, No. 2, pp. 165-171, 2000. [VG84] C. P. Verbeck and D. Grenberg, “A Comprehensive Light-Source Description for Computer Graphics,” IEEE Computer Graphics and Applications, Vol. 4, No. 3, pp 213-222, 1984. [VG94] E. Veach, and L. J. Guibas, “Bidirectional Estimators for Light Transport,” Proceedings of the Fifth Eurographics Workshop on Rendering, pp. 147-162, 1994. [VG97] E. Veach, L. J. Guibas, “Metropolis Light Transport,” Proceedings of SIGGRAPH 1997, pp. 65-76, 1997. [Wag00] M. Wagner, “Robust Watermarking of Polygonal Meshes,” Proceedings of Geometric Modeling and Processing 2000, pp. 201-208, 2000. [Wal04] I. Wald, Realtime Ray Tracing and Global Illumination, Ph.D. thesis, Saarland University, Germany, 2004. [Wan92] C. Y. Wang, “Physically Correct Direct Lighting for Distribution Ray Tracing,” Graphics Gems III, Academic Press, New York, 1992. [Wan93] C. Y. Wang, The Direct Lighting Computation in Global Illumination Methods, Ph.D. Thesis, Indiana University, 1993. [WC05] C. M. Wang and Y. M. Cheng, “An Efficient Information Hiding Algorithm for Polygon Models,” Computer Graphics Forum, Vol. 24, No. 3, pp. 591-600, 2005. [WDP99] B. Walter, G. Drettakis, and S. Parker, “Interactive Rendering Using The Render Cache,” Proceedings of Eurographics Rendering Workshop 1999, pp, 19-30, 1999. [Whi80] T. Whitted, “An Improved Illumination Model for Shaded Display,” Communications of the ACM, Vol. 23, No. 6, pp. 343-349, 1980. [Wil78] L. Williams, 1978, “Casting Curved Shadows on Curved Surfaces,” Computer Graphics, Vol. 12, No. 3, pp. 270-274, 1978. [WHTC04] C. M. Wang, N. C. Hwang, Y. Y. Tsai and C. H. Chang, “Ellipse Sampling for Monte Carlo Applications,” Electronics Letters, Vol. 40, No. 1, pp. 21-22, 2004. [WS01] I. Wald and P. Slusallek, “State of the Art in Interactive Ray Tracing,” EUROGRAPHICS 2001 State-of-the-Art Report, 2001. [WW06] C. M. Wang and P. C. Wang, “Steganography on Point-Sampled Geometry,” Computers & Graphics, Vol. 30, No. 2, pp. 244-254, 2006. [Zim95] K. Zimmerman, “Direct Lighting Models for Ray Tracing with Cylindrical Lamps,” Graphics Gems V, Academic Press, New York, 1995. [Zim98] K. Zimmerman, Density Prediction for Importance Sampling in Realistic Image Synthesis, Ph.D. Thesis, University of Indiana, Indiana, 1998.
電腦圖學的應用十分廣泛,從工業設計、模擬訓練到個人娛樂都有很密切的關聯。而真實地將現實世界再現於虛擬場景一直是電腦圖學的追求的目標。自從第一個電腦圖學演算法被提出來後,科技不斷進步。現今我們已經擁有超越當時數千倍以上的硬體效能,也有各式各樣不同的演算法被發展出來。真實影像的產生從需耗費數小時,甚至數天,到現在已經可以即時與虛擬場景互動。同時,因為網路的蓬勃發展,許多值得研究的問題也應蘊而生,網路資訊安全更是大家著重的焦點。隨著立體圖形在網路上的應用增加,在三維模型(3D model)上隱藏資訊便是其中的應用。
本論文提出三種不同主題的技巧,分別應用於光源取樣、互動式成圖、資訊隱藏上。第一個主題是針對圓錐型光源在其方向性空間(Directional Space)進行均勻取樣。該方法較傳統在整個光源表面上取樣更有效率,可用於直接照明或全域照明的計算上。第二個主題是提出了ㄧ個互動式直接照度成圖系統,該系統採用漸進式的方式在動態環境中達成互動的效果。這個架構使用了圖形應用程式介面(API)作為開發基礎,藉由現行硬體對圖形應用程式介面的支援,達到快速成圖的目的。該系統中亦設置了數項可以調整的參數,讓使用者能更有彈性地依需求來操作系統。第三個主題是提出了兩個技巧分別用於帶有法向量資訊與不帶有法向量資訊的三維模型。該技巧利用調整模型端點的法向量或端點與模型幾何中心形成的向量跟基準向量(Pivot Vector)的夾角來隱藏資料,並透過失真係數來控制失真率。這些技巧具有高容量、有效率、低失真、可抵抗幾何攻擊(旋轉、平移、均勻縮放)等特色。

Computer graphics is applied broadly in a variety of fields, including industrial design, physical simulation, skill training and personal entertainment. One of the main goals of computer graphics is to create virtual scenes which look just like the real world. Since the first computer graphics algorithm was developed, the computing power of computers has become more and more advanced. Today, we have processing power that is thousands of times greater than before, and various algorithms have been developed. For example, in the past, it took between several hours and several days to create photorealistic images, but now we can interact with virtual scenes in real-time. Meanwhile, as the Internet continues to grow quickly, network security has become an important issue and relevant researches will be needed. With the increasing need for 3D graphics applications on the Internet, data hiding in 3D models is also becoming more important.
In this thesis, we propose several techniques for three different topics. They can be used in sampling on luminaire, interactive rendering, and information hiding. First is the technique for sampling uniformly in the directional space for a cone. It performs more efficiently than the conventional approaches that sample the entire surface of the luminaire. This technique can be used in direct lighting or global illumination algorithms. Second, we propose a progressive refinement system for rendering direct illumination at interactive rates for dynamic scenes. Our system takes advantage of graphics APIs to accelerate the visibility and illumination calculations. In our system, a user can specify several tunable parameters, and the system will run at the target frame rate, using the available time budget. Third, two techniques are proposed. One is for polygonal models whose vertices have been given normal vectors and the other is for polygonal models without normal vector and point-sampled models. These techniques embed messages, by adjusting the corresponding vector of a vertex, according to the pivot vector. This corresponding vector can be the normal vector of the vertex or formed by the vertex position and the geometric center of the cover model. A distortion coefficient is also introduced to control the distortion rate during the embedding process. Our algorithms are efficient. They can achieve high data capacity and are robust against rotation, translation, and uniform scaling attacks.
According to the experimental results, the proposed algorithms work efficiently. They can be used in the applications of sampling for conic luminaire, interactive rendering, and data hiding for 3D models.
其他識別: U0005-1408200613492500
Appears in Collections:資訊科學與工程學系所

Show full item record
TAIR Related Article

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.