Scene Graphs andBarycentric CoordinatesJason LawrenceCS445: GraphicsAcknowledgment: slides by Misha Kazhdan, Allison Klein, Tom Funkhouser,Adam Finkelstein and David DobkinLast Time• 2D TransformationsBasic 2D transformationsMatrix representationMatrix composition• 3D TransformationsBasic 3D transformationsSame as 2DHomogeneous Coordinates• Add a 4th coordinate to every 3D point(x, y, z, w) represents a point at location (x/w, y/w, z/w)• Represent transformations by 4x4 matricesThe top-left 3x3 block represents the linear part of the transformationThe last column represents the translationTransformations (translations/rotations/scales) can be composed using simple matrix multiplicationOverview• 2D TransformationsBasic 2D transformationsMatrix representationMatrix composition• 3D TransformationsBasic 3D transformationsSame as 2D• Transformation HierarchiesScene graphsRay casting• Barycentric CoordinatesTransformation Example 1• An object may appear in a scene multiple timesDraw same 3D data with different transformationsTransformation Example 1BuildingFloor 4 Floor5Floor 3Floor 2Floor 1Chair KBookshelf 1DeskChairBookshelfDesk 1 Desk 2 Chair 1Floor FurnitureOffice NOffice 1Office FurnitureDefinitionsInstancesTransformation Example 2Rose et al. `96• Well-suited for humanoid charactersRootLHipLKneeLAnkleRHipRKneeRAnkleChestLCollarLShldLElbowLWristRCollarRShldRElbowRWristNeckHeadScene Graphs• Allow us to have multiple instances of a single model – providing a reduction in model storage size• Allow us to model objects in local coordinates and then place them into a global frame – particularly important for animationScene Graphs• Allow us to have multiple instances of a single model – providing a reduction in model storage size• Allow us to model objects in local coordinates and then place them into a global frame – particularly important for animation• Accelerate ray-tracing by providing a hierarchical structure that can be used for bounding volume testingRay Casting with HierarchiesRay Casting with Hierarchies• Transform the shape (M)• Compute the intersectionRay Casting with Hierarchies• Transform the ray (M-1)• Compute the intersection• Transform the intersection (M)• Transform the shape (M)• Compute the intersectionAngel Figures 8.8 & 8.9Ray Casting With Hierarchies• Transform rays, not primitivesFor each node ...» Transform ray by inverse of matrix» Intersect transformed ray with primitives» Transform hit information by matrixBase[M1]Lower Arm[M2]Upper Arm[M3]Robot ArmApplying a Transformation• Position• Direction• NormalMAffine Translate LinearMTMLApplying a Transformation• PositionoApply the full affine transformation:p’=M(p)=(MT×ML)(p)• Direction• NormalMAffine Translate LinearMTMLApplying a Transformation• Position• DirectionoApply the linear component of the transformation:p’=ML(p)• NormalMAffine Translate LinearMTMLApplying a Transformation• Position• DirectionoApply the linear component of the transformation:p’=ML(p)A direction vector v is defined as the difference between two positional vectors p and q: v=p-q.qvpApplying a Transformation• Position• DirectionoApply the linear component of the transformation:p’=ML(p)A direction vector v is defined as the difference between two positional vectors p and q: v=p-q.Applying the transformation M, we compute the transformed direction as the distance between the transformed positions: v’=M(p)-M(q).qvpv’M(p)M(q)Applying a Transformation• Position• DirectionoApply the linear component of the transformation:p’=ML(p)A direction vector v is defined as the difference between two positional vectors p and q: v=p-q.Applying the transformation M, we compute the transformed direction as the distance between the transformed positions: v’=M(p)-M(q).The translation terms cancel out!qvpv’M(p)M(q)Angel Figures 8.8 & 8.9Ray Casting With Hierarchies• Transform rays, not primitivesFor each node ...» Transform ray by inverse of matrix» Intersect transformed ray with primitives» Transform hit information by matrixBase[M1]Lower Arm[M2]Upper Arm[M3]Robot ArmTransforming a Ray• If M is the transformation mapping a scene-graph node into the global coordinate system, then we transform a ray r by:or’.start = M-1(r.start)or’.direction = ML-1(r.direction)MAffine Translate LinearMTMLApplying a Transformation• Position• Direction• Normalp’= ?MMTMLAffine Translate LinearNormal Transformation2D Example:Translate ScaleMMTMLNormal Transformation2D Example:If v is a direction in 2D, and n is a vector perpendicular to v, we want the transformed n to be perpendicular to the transformed v:Translate ScaleMMTMLNormal Transformation2D Example:Say …Translate ScaleMMTMLvNormal Transformation2D Example:Say … thenTranslate ScaleMMTMLvnNormal Transformation2D Example:Say … thenTransforming, …Translate ScaleMMTMLvnML(v)Normal Transformation2D Example:Say … thenTransforming, … and Translate ScaleMMTMLvnML(v)ML(n)Normal Transformation2D Example:Say … thenTransforming, … and Translate ScaleMMTMLvnML(v)ML(n)Simply applying the directional part of the transformation to n does not result in a vector that is perpendicular to the transformed v.RecallTransposes:• The transpose of a matrix M is the matrix Mt whose (i,j)-th coeff. is the (j,i)-th coeff. of M:RecallTransposes:• The transpose of a matrix M is the matrix Mt whose (i,j)-th coeff. is the (j,i)-th coeff. of M:• If M and N are two matrices, then the transpose of the product is the inverted product of the transposes:RecallDot-Products:•The dot product of two vectors v=(vx,vy,vz) and w=(wx,wy,wz) is obtained by summing the product of the coefficients:RecallDot-Products :•The dot product of two vectors v=(vx,vy,vz) and w=(wx,wy,wz) is obtained by summing the product of the coefficients:• Can also express as a matrix product:RecallTransposes and Dot-Products:• If M is a matrix, the dot product of v with M applied to w is the dot product of the transpose of M applied to v with w:RecallTransposes and Dot-Products:• If M is a matrix, the dot product of v with M applied to w is the dot product of the transpose of M applied to v with w:RecallTransposes and Dot-Products:• If M is a matrix, the dot product of v with M applied to w is the
View Full Document