Scene Graphs Modeling Transformations COS 426 3D Object Representations Points Range image Point cloud Surfaces Polygonal mesh Subdivision Parametric Implicit Solids Voxels BSP tree CSG Sweep High level structures Scene graph Application specific 3D Object Representations What object representation is best for this 3D Object Representations Desirable properties of an object representation Easy to acquire Accurate Concise Intuitive editing Efficient editing Efficient display Efficient intersections Guaranteed validity Guaranteed smoothness etc CS Building Princeton University Overview Scene graphs Geometry attributes Transformations Bounding volumes Transformations Basic 2D transformations Matrix representation Matrix composition 3D transformations Scene Graphs Building Floor 1 Floor 2 Floor 3 Floor 4 Floor5 Floor Furniture Office 1 Office N Instances Office Furniture Bookshelf 1 Desk 1 Desk 2 Bookshelf Desk Chair 1 Chair Chair K Definitions Scene Graphs Hierarchy DAG of nodes where each may have Geometry representation Modeling transformation Parents and or children Bounding volume Base M1 Upper Arm M2 Lower Arm M3 Robot Arm Angel Figures 8 8 8 9 Scene Graphs Advantages Allows definitions of objects in own coordinate systems y z x Scene Graphs Advantages Allows definitions of objects in own coordinate systems Allows use of object definition multiple times in a scene Scene Instance 1 Instance 4 Level A Instance 1 Instance 4 Level B H B Figure 109 Instance 1 Instance 4 Instances Definitions Cube Tetrahedron Octahedron Dodecahedron Icosahedron Scene Graphs Advantages Allows definitions of objects in own coordinate systems Allows use of object definition multiple times in a scene Allows hierarchical processing e g intersections Haverkort Scene Graphs Advantages Allows definitions of objects in own coordinate systems Allows use of object definition multiple times in a scene Allows hierarchical processing e g intersections Allows articulated animation Base M1 Upper Arm M2 Lower Arm M3 Robot Arm Angel Figures 8 8 8 9 Scene Graph Example Pixar Overview Scene graphs Geometry attributes Transformations Bounding volumes Transformations Basic 2D transformations Matrix representation Matrix composition 3D transformations 2D Modeling Transformations Modeling Coordinates y Scale Translate x Scale Rotate Translate World Coordinates 2D Modeling Transformations Modeling Coordinates y x Let s look at this in detail World Coordinates 2D Modeling Transformations Modeling Coordinates y x 2D Modeling Transformations Modeling Coordinates y x Scale 3 3 Rotate 90 Translate 5 3 2D Modeling Transformations Modeling Coordinates y x Scale 3 3 Rotate 90 Translate 5 3 2D Modeling Transformations Modeling Coordinates y x Scale 3 3 Rotate 90 Translate 5 3 World Coordinates Basic 2D Transformations Translation x x tx y y ty Scale x x sx y y sy Shear x x hx y y y hy x Rotation x x cosQ y sinQ y x sinQ y cosQ Transformations can be combined with simple algebra Basic 2D Transformations Translation x x tx y y ty Scale x x sx y y sy Shear x x hx y y y hy x Rotation x x cosQ y sinQ y x sinQ y cosQ Basic 2D Transformations Translation x x tx y y ty Scale x x sx y y sy x y x y Shear x x hx y y y hy x x x sx y y sy Rotation x x cosQ y sinQ y x sinQ y cosQ Basic 2D Transformations Translation x x tx y y ty Scale x x sx y y sy Shear x x hx y y y hy x x y x x sx cosQ y sy sinQ y x sx sinQ y sy cosQ Rotation x x cosQ y sinQ y x sinQ y cosQ Basic 2D Transformations Translation x x tx y y ty Scale x x sx y y sy x y Shear x x hx y y y hy x x x sx cosQ y sy sinQ tx y x sx sinQ y sy cosQ ty Rotation x x cosQ y sinQ y x sinQ y cosQ Basic 2D Transformations Translation x x tx y y ty Scale x x sx y y sy Shear x x hx y y y hy x x x sx cosQ y sy sinQ tx y x sx sinQ y sy cosQ ty Rotation x x cosQ y sinQ y x sinQ y cosQ Overview Scene graphs Geometry attributes Transformations Bounding volumes Transformations Basic 2D transformations Matrix representation Matrix composition 3D transformations Matrix Representation Represent 2D transformation by a matrix a b c d Multiply matrix by column vector apply transformation to point x a b x y c d y x ax by y cx dy Matrix Representation Transformations combined by multiplication x a b e y c d g f i h k j x l y Matrices are a convenient and efficient way to represent a sequence of transformations 2x2 Matrices What types of transformations can be represented with a 2x2 matrix 2D Identity x x y y 0 x x a1 b y c0 d1 y 2D Scale around 0 0 x sx x y sy y x asx b0 x x y c0 dsy y y 2x2 Matrices What types of transformations can be represented with a 2x2 matrix 2D Rotate around 0 0 x cos Q x sin Q y y sin Q x cos Q y a Qb xsin x cos Q x c Qd ycos y sin Q y 2D Shear x x shx y y shy x y xx a1 b shx x x c d 1y y yy shy 2x2 Matrices What types of transformations can be represented with a 2x2 matrix 2D Mirror over Y axis x x y y x a 1 y c0 b0 xx d1 yy 2D Mirror over 0 0 x x y y x x xx a1 b 0 yy c0 d 1 y y 2x2 Matrices What types of transformations can be represented with a 2x2 matrix 2D Translation x x tx y y ty a b x xNO y c d y Only linear 2D transformations can be represented with a 2 2 matrix Linear Transformations 2D linear transformations are combinations of Scale Rotation Shear and Mirror x a b x y c d y Properties of linear transformations Satisfies T s1p1 s2p 2 s1T p1 s2T p 2 Origin maps to origin Points at infinity stay at infinity Lines map to lines Parallel lines remain parallel Ratios are preserved Closed under composition 2D Translation 2D translation represented by a 3x3 matrix Point represented with homogeneous coordinates x x tx y y ty x 1 0 tx x y 0 1 ty y 1 0 0 1 1 Homogeneous Coordinates Add a 3rd coordinate to every 2D point x y w represents a point at location x w y w x y 0 represents a point at infinity 0 0 0 is not allowed y 2 2 1 1 or 4 2 2 or 6 3 3 1 1 2 x Convenient coordinate system to represent many useful transformations Basic 2D Transformations Basic 2D transformations as 3x3 matrices x 1 y 0 1 0 tx x ty y 1 1 0 1 0 Translate x cos Q y sin Q 1 0 sin Q cos Q 0 Rotate x sx y 0 1 0 0 x 0 y 1 1 0 …
View Full Document
Unlocking...