26 (2014)

Save this PDF as:
 WORD  PNG  TXT  JPG

Size: px
Start display at page:

Download "26 (2014)"

Transcription

1 26 (2014)

2 26 (2014)

3 , LOD, CAD, [ ] 3DCG 3D 3DCG 1

4 A b s t r a c t Title Author An Guangming Advisor Taichi Watanabe Key Words Mesh Simplification, LOD, CAD, Saliency [summary] In recent years, the multi-platform game content is becoming a trend in the gaming field of 3DCG. However, processing capacity of platform is very different. Content on high processing capacity platform is difficult to run smoothly on the platform of lower processing capacity. To solve this problem it emerges a technique called Mesh Simplification, which is one of the most important research themes in 3DCG. Mesh Simplification requires you to not change as much as possible the shape of polygon mesh, while to reduce the object data size to a small one. Since smaller data size requests lower processing capacity, simplified mesh can be processed faster even in low processing capacity platform. This research presents a saliency map, which considers the effect of both color information and shape information view-independent. Also, it s possible to simplify a mesh from low attentioned point while protecting the high attentioned places. When simplified the mesh model to the same number of polygons, this research method has been confirmed to produce a good result. Characteristics of high attentioned parts in mesh model are better proceed than other existing methods.

5 center-surround center-surround Metro

6 47 II

7 1.1 Surface Simplification Using Quadric Error Metrics Perceptually Driven Interactive Rendering Luebke Lee Garland Garland Lee

8 5.4 Lee Metro Metro IV

9 1

10 1.1 PC 3D 1.1 3DCG 1 2

11 Garland [1] QEM : Surface Simplification Using Quadric Error Metrics Luebke [2] Lee [3] 1.2 Luebke 1.2: Perceptually Driven Interactive Rendering - 3

12 1.3 Lee 1.3: Luebke Lee Luebke Lee 4

13

14 2

15 Hoppe [4] V 1 V : Schroeder [5] Garland [1] Popovic [6] El-Sana [7] V 1 V 2 V p : 1 7

16 2.3: 2 Hamann [8] Gieng98 [9] : [Rossignac93][10] 2.5 8

17 2.5: Schroeder [11] : [Hinker93] [12] 2.7 9

18 2.7: Floriani [13][14] A B A B : 10

19 CAD CT(Computeraided Tomography) MRI(Magnetic Resonance Imaging) 11

20 3

21 3.1 Rossignac [10] Cohen97 [15] Luebke97 [16]

22 3.1: : 2 Cohen [17] Simplification Envelopes 14

23 Ronfard [18] 3.3 (a) d b 3.3 (b) d c 3.3 (c) d b 3.3: - Garland [1] Ronfard Error Quadrics 15

24 E v = p plane(v)(p v) 2 = p ( v T p )( p T v ) = v T [ p ( pp T )] v = v T p Q p v = v T Q v v (3.1) Error Quadrics 3.2 [19] RGB Itti [20] centersurround 16

25 3.2.1 σ σ = 2, 3, 4, 5, 6, 7, σ = 2, 3, 4, 5, 6, 7, 8 σ RGB r(σ) g(σ) b(σ) i(σ) (3.2) i(σ) = r(σ) + g(σ) + b(σ) 3 (3.2) σ RGB R(σ) G(σ) B(σ) Y (σ) (3.2) σ (3.3) C R (σ) σ (3.4) C G (σ) σ (3.5) C B (σ) σ (3.6) C Y (σ) 17

26 g(σ) + b(σ) R(σ) = r(σ) 2 r(σ) + b(σ) G(σ) = g(σ) 2 r(σ) + g(σ) B(σ) = b(σ) Y (σ) = r(σ) + g(σ) 2 2 r(σ) g(σ) 2 (3.3) (3.4) (3.5) b(σ) (3.6) σ O(σ, θ) (3.7) σ (3.2) I(σ) θ = 0, 45, 90, 135 o(σ, θ) = h m h m x= h n y= h n (I(σ, m, n)ψ(θ, x m, y n)) (3.7) I(σ, m, n) I(σ) (m,n) ψ(θ) σ h m h n x y ψ(θ, x m, y n) σ ψ(θ) (x m, y n) center-surround center-surround (σ 1, σ 2 ) = (2, 5), (2, 6), (3, 6), (3, 7), (4, 7), (4, 8) 6 center-surround σ 1 σ 2 (3.8) i(σ 1, σ 2 ) = i(σ 1 ) i(σ 2 ) (3.8) 18

27 σ 1 σ 2 (3.9) (3.10) RG(c, s) = (R(c) G(c)) (G(s) R(s)) (3.9) BY (c, s) = (B(c) Y (c)) (Y (s) B(s)) (3.10) σ 1 σ 2 (3.11) θ = 0, 45, 90, 135 O(c, s, θ) = O(c, θ) O(s, θ) (3.11) center-surround M M

28 3.4: Luebke [2] 3.5 Luebke 3.5: Luebke 20

29 Itti Lee [3] Lee Lee Lee center-surround Schneider [21] Moreton [22] PDE Taubin [23] Mayer [24] Desbrun [25] Laplace-Beltrami Meyer [26] Dyn [27] Cohen-Steiner [28] Alliez [29] Normal cycle Taubin [30] Lee Taubin 21

30 c v c(v) v σ N(v, σ) N(v, σ) = {x x v < σ} x G(c(v), σ) G(c(v), σ) = x N(v,2σ) c(x)exp[ x v 2 /(2σ 2 )] x N(v,2σ) exp[ x v 2 /(2σ 2 )] (3.12) center-surround center-surround Lee (3.13) σ v c i (v) = G(c(v), σ) G(c(v), 2σ) (3.13) σ σ σ σ Lee 22

31 σ i 2ε, 3ε, 4ε, 5ε, 6ε ε 0.3% Lee (3.14) M s (v) = M(v)(M M M m ) (3.14) M M m M M M s (3.15) S M = S(M(v i)) (3.15) i 3.6 Lee (a)(b)(c)(d)(e) (f) (a)(b)(c)(d)(e) 23

32 3.6: Lee

33 3.4.1 Taubin C 25

34 1.4 (3.16) x = x m + R sin(α i ) cos(β i ) y = y m + R sin(α i ) sin(β i ) z = z m + R cos(α i ) α i { 2n 1π N 1 ; n 1 = 0, 1, 2,, N 1 1} β i { 2n 2π N 2 ; n 2 = 0, 1, 2,, N 2 1} (3.16) (x m, y m, z m ) x y z N 1 N 2 N 1 N A 5 A 15 A B B B 26

35 A B C D E 27

36 :

37 3.8: 3.9: 29

38 4

39 2 3 QEM QEM Garland QEM Luebke [31] 6 (4.1) C(e) = Q(e) H(e); (4.1) C(e) e Q(e) e QEM H(e) e e e QEM e 31

40 (4.2) (4.3) H(V r ) = (H(V 1 ) + H(V 2 ))/2.0 (4.2) Q(V r ) = (Q(V 1 ) + Q(V 2 ))/2.0 (4.3) V r V 1 V 2 H(V r ) H(V 1 ) H(V 2 ) Q(V r ) QEM Q(V 1 ) Q(V 2 ) QEM API OpenGL[32] 3DCG Fine Kernel Toolkit System[33][34] 4.1,4.2,4.3, Armadillo 32

41 4.1: 1 4.2: 1 33

42 4.3: 2 4.4: 2 34

43 5

44 Metro 5.1 Garland Lee Garland Garland Lee Lee 36

45 5.1: Garland 5.2: Garland 37

46 5.3: Lee 5.4: Lee

47 : 39

48 5.6: 5.7: 5.3 Metro metro metro 40

49 metro : Metro 41

50 5.9: Metro : 42

51 6

52 44

53

54 46

55

56 [1] Michael Garland and Paul S. Heckbert. Surface simplification using quadric error metrics. In SIGGRAPH, pp , [2] David P. Luebke and Benjamin Hallen. Perceptually-driven simplification for interactive rendering. In Steven J. Gortler and Karol Myszkowski, editors, Proceedings of the 12th Eurographics Workshop on Rendering Techniques, London, UK, June 25-27, 2001, pp Springer, [3] Chang Ha Lee, Amitabh Varshney, and David W. Jacobs. Mesh saliency. ACM Trans. Graph., Vol. 24, No. 3, pp , [4] Hugues Hoppe, Tony DeRose, Tom Duchamp, John Alan McDonald, and Werner Stuetzle. Mesh optimization. In Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1993, pp ACM, [5] William J. Schroeder. A topology modifying progressive decimation algorithm. In IEEE Visualization, pp , [6] Jovan Popovic and Hugues Hoppe. Progressive simplicial complexes. In SIG- GRAPH, pp , [7] Jihad El-Sana and Amitabh Varshney. Generalized view-dependent simplification. Comput. Graph. Forum, Vol. 18, No. 3, pp , [8] Bernd Hamann. A data reduction scheme for triangulated surfaces. Computer Aided Geometric Design, Vol. 11, No. 2, pp , [9] Tran S. Gieng, Bernd Hamann, Kenneth I. Joy, Gregory L. Schussman, and Issac J. Trotts. Constructing hierarchies for triangle meshes. IEEE Trans. Vis. Comput. Graph., Vol. 4, No. 2, pp ,

57 [10] Jarek Rossignac and Paul Borrel. Multi-resolution 3d approximations for rendering complex scenes. In Bianca Falcidieno and Tosiyasu L. Kunii, editors, Modeling in Computer Graphics, Methods and Applications [selection of papers from the conference held at Genoa, Italy, on June 28-July 1, 1993], IFIP Series on Computer Graphics, pp Springer, [11] William J. Schroeder, Jonathan A. Zarge, and William E. Lorensen. Decimation of triangle meshes. In James J. Thomas, editor, Proceedings of the 19th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1992, pp ACM, [12] Paul A. Hinker and Charles D. Hansen. Geometric optimization. In Gregory M. Nielson and R. Daniel Bergeron, editors, Proceedings IEEE Visualization 93, San Jose, California, USA, October 25-29, 1993, pp IEEE Computer Society, [13] Leila De Floriani, Paola Magillo, and Enrico Puppo. Building and traversing a surface at variable resolution. In IEEE Visualization, pp , [14] Leila De Floriani, Paola Magillo, and Enrico Puppo. Efficient implementation of multi-triangulations. In IEEE Visualization, pp , [15] Jonathan D. Cohen, Dinesh Manocha, and Marc Olano. Simplifying polygonal models using successive mappings. In IEEE Visualization, pp , [16] David P. Luebke and Carl Erikson. View-dependent simplification of arbitrary polygonal environments. In SIGGRAPH, pp , [17] Jonathan D. Cohen, Amitabh Varshney, Dinesh Manocha, Greg Turk, Hans Weber, Pankaj K. Agarwal, Frederick P. Brooks Jr., and William V. Wright. Simplification envelopes. In SIGGRAPH, pp ,

58 [18] Rémi Ronfard and Jarek Rossignac. Full-range approximation of triangulated polyhedra. Comput. Graph. Forum, Vol. 15, No. 3, pp , [19].. :, Vol. 64, No. 12, pp , [20] Laurent Itti, Christof Koch, and Ernst Niebur. A model of saliency-based visual attention for rapid scene analysis. IEEE Trans. Pattern Anal. Mach. Intell., Vol. 20, No. 11, pp , [21] Robert Schneider and Leif Kobbelt. Geometric fairing of irregular meshes for free-form surface design. Computer Aided Geometric Design, Vol. 18, No. 4, pp , [22] Henry P. Moreton and Carlo H. Séquin. Functional optimization for fair surface design. In James J. Thomas, editor, Proceedings of the 19th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1992, pp ACM, [23] G. Taubin. Geometric Signal Processing on Polygonal Meshes. In Eurographics, [24] Uwe F. Mayer. Numerical solutions for the surface diffusion flow in three space dimensions, [25] Mathieu Desbrun, Mark Meyer, Peter Schröder, and Alan H. Barr. Implicit fairing of irregular meshes using diffusion and curvature flow. In SIGGRAPH, pp , [26] Mark Meyer, Mathieu Desbrun, Peter Schrder, and Alan H. Barr. Discrete differential-geometry operators for triangulated 2-manifolds,

59 [27] Nira Dyn, Kai Hormann, Sun jeong Kim, and David Levin. Optimizing 3d triangulations using discrete curvature analysis. In in Mathematical Methods in CAGD: Oslo 2000, T. Lyche and, pp Vanderbilt University Press, [28] David Cohen-Steiner and Jean-Marie Morvan. Restricted delaunay triangulations and normal cycle. In Steven Fortune, editor, Proceedings of the 19th ACM Symposium on Computational Geometry, San Diego, CA, USA, June 8-10, 2003, pp ACM, [29] Pierre Alliez, David Cohen-Steiner, Olivier Devillers, Bruno Lévy, and Mathieu Desbrun. Anisotropic polygonal remeshing. ACM Trans. Graph., Vol. 22, No. 3, pp , [30] Gabriel Taubin. Estimating the tensor of curvature of a surface from a polyhedral approximation. In ICCV, pp , [31] D.P. Luebke. Level of Detail for 3D Graphics. The Morgan Kaufmann Series in Computer Graphics Series. Morgan Kaufmann Publishers, [32] OpenGL.org. OpenGL. : [33] Fine Kernel Project. Fine Kernel ToolKit System. : [34]..,