### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# APPROXIMATION ALGORITHMS CSCI 6963

RPI

GPA 3.76

### View Full Document

## 31

## 0

## Popular in Course

## Popular in ComputerScienence

This 20 page Class Notes was uploaded by Santos Fadel on Monday October 19, 2015. The Class Notes belongs to CSCI 6963 at Rensselaer Polytechnic Institute taught by Staff in Fall. Since its upload, it has received 31 views. For similar materials see /class/224867/csci-6963-rensselaer-polytechnic-institute in ComputerScienence at Rensselaer Polytechnic Institute.

## Reviews for APPROXIMATION ALGORITHMS

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/19/15

CSCI49726963 Advanced Computer Graphics httpwwwcsrpieducutlerclassesadvancedgraphicsSO7 Professor Barb Cutler cutlercsrpiedu MRC 309A Topics for the Semester 0 Meshes Rendering 7 representation 7 my tmcing 7 simpli cation 7 appeamnce models 7 subdivision surfaces 7 shadows 7 genemtion 7 local vs global 7 volumetric modeling illumination Simulation 7 mdiosity photon mg subsurface 7 particle systems scattering etc 7 rigid body deformation cloth WindWater ows 7 collision detection 7 weathering amp more procedural modeling texture synthesis Mesh Generation amp Volumetric Modeling unanan nunan Inlm m quot r wagering K p 39 Cutler et a1 Simpli cation and Improvement of Tetmhedral Models for Simulation 2004 5 Luxo Jr Pixar Animation Studios 1986 Mesh Simpli cation 2i i mi m39vlfulslLrn mum nullx mxtmr tumw mm u Hurtw Hoppe Progressive Meshes SIGGRAPH 1996 Modeling Subdivision Surfaces Hoppe et a1 Piecese Smooth Surface Reconstruction 1994 Geri s Game Pixar 1997 6 Particle Systems Star Trek The Wrath othan 1982 Physical Simulation Rigid Body Dynamics Collision Detection Fracture Deformation Muller et al Deformations 2002 Fluid Dynamics Ray Casting Visual Simulation of Smoke Fedkiw Stam amp Jensen SIGGRAPH 2001 Foster amp Mataxas 1996 For every pixel construct a ray from the eye 7 For every object in the scene 39 Find intersection with the ray 39 Keep if closest Ray Tracing Shade interaction of light and material Secondary rays shadows re ection refraction An Improved Illumination Model for Shaded Display I Whitted 1980 Traditional Ray Tracing Ray Tracing Soft Shadows Ray Tracing Caustics Global Illumination Sub surface Scattering a Jensen et a1 A Practical Model for Subsurface Light Transport 2001 I Appearance Models Syllabus amp Course Website Li r r a I Which Version should I register for a csc1 6963 3 umts ufgraduate mean chrechMatustk 7 CSCI 4972 4 umts ufundergraduate credit same lectures assignments quizzes amp grading criteria Other Questions Introductions Who are you 39 name yeardegree graphics background if any research interests Why you are taking this class something fun interesting or unusual about yourself Outline Course Overview Classes of Transformations Representing Transformations Transformations in Modelling Combining Transformations Orthographic amp Perspective Projections Example Iterated Function Systems IF S What is a Transformation Maps points x y in one coordinate system to points x39 y3 in another coordinate system x39axbyc y39dxeyf F or example Iterated Function System IFS Simple Transformations I I I I I l Iwnullwlqc Mmhlw liurIlrhun I39iIlnllwu quotquotquotlh r quot mJlmg Can be combined Are these operations invertible Yes except scale 0 Transformations are used to Position objects in a scene Change the shape of objects Create multiple copies of objects Projection for virtual cameras Describe animations 23 RigidBody Euclidean Transforms Preserves distances Preserves angles Rigid i lidean Identity Translation Rotation Similitudes Similarity Transforms Linear Transform ations preserves angles Linear Transform ations Affine Transformations 39 LKP 9 LCP q 39 Hap aLKP preserves parallel lines Projective Transformations preserves lines General FreeForm Transformation Does not preserve lines Not as pervasive eompulallonally more involved Sederberg and Parry slggraph 1986 Outline How are Transforms Represented Course Overview Classes ofTransformations Representing Transformations Transformations in Modelling Combining Transformations Orthographic amp Perspective Projections Example Iterated Function Systems IFS l 2 1 p Mpt 1 l2 Homogeneous Coordinates Translation in homogeneous coordinates Add an extra dimension in ZD we use 3 x 3 smees In 31 we use 4 x4 matrices Each pointhas an extravalue W Nkk l m E quota H i quota x axbyc y dxeyf Af ne fur mulatmn b x a a c 42 ll 3 Mpt p Mp l bc X Bf y 01 Humugeneuus furmulatmn Homogeneous Coordinates Homogeneous Visualization Most ofthe time W 1 and We can ignore it Ifwe multiply ahomogeneous coordinate by an a me matrix W is unc anged Divide by w to normalize homogenize W 07 Pamt at m mty direction Translate Ix ty tz Translatec00 y 0 Why bother with the extra dimension Because now translations can be encoded in the matrix C x l 0 0 Ix x y 7 0 l 0 1y y z 0 0 l 2 z 1 0 0 0 l l 37 Rotation mamas y 0 About 2 axis x cos 0 Sin 9 0 0 x y 7 Sin 0 cos 0 0 0 y z I 0 0 1 0 z I 0 0 0 l l Scale Sx Sy Sz Scams5 5 y P39 Isotropic uniform scaling Sx Sy Sz x Sx 0 0 0 x y 0 Sy 0 0 y z 0 0 S2 0 z 1 0 0 0 l l 38 Rotation y Romeo 5 0 About kx ky kz a unit vector on an arbitrary axis Rodrigues Formula 39x kxkxICC kzkxICkzs kxkzICkys 0 x y 7 kykxICkzs kzkxICC kykzICkxs 0 y z 7 z k l l kzkxICkys kzkxICkxs kk1cc 0 0 0 0 l Where 66050 amp rrin0 Storage Often w is not stored always 1 0 Needs careful handling of direction vs point 7 Mathematically the simplest is to encode directions with w 0 7 In terms of storage using a 3component array for both direction and poinw is more ef cient 7 Which requires to have special operation routines for points vs directions Outline 0 Course Overview 0 Classes of Transformations Representing Transformations Transformations in Modelling Combining Transformations Orthographic amp Perspective Projections 0 Example Iterated Function Systems IFS Adding Transformations Nested Transforms To position the logical groupings ofobjects within the scene H quot4 H w u t u m m p39TSpTSp same as n Txansinm 12mm 1 n s n 12mm 1 n n Txansinm Seal 2 2 2 cale222 99m m cenlex n n n am How are transforms combined Noncommutative Composition Scale then Translate gt gt 55gt 2 U s 120 2 mum 3J um nu Use matrix multiplication p39 T S p TS P 1 0 3 2 0 0 2 0 3 TS 0 1 1 0 2 0 0 2 1 0 0 1 0 0 1 0 0 1 Caution matrix multiplication is NOT commutative 45 Scale then Translate p39 T S p TS P gt gt is I W Max 21 Imam 3J n mm Translate then Scale p39 S T p ST P gt gt rm U Mum SJ 2 sum 5 an Noncommutative Composition Outline Scale then Translate p39 T S p TS P 1 0 3 2 0 0 2 0 3 TS 0 1 1 0 2 0 0 2 1 0 0 1 0 0 1 0 0 1 Translate then Scale p39 S Tp STD Course Overview Classes of Transformations Representing Transformations Transformations in Modelling Combining Transformations Orthographic amp Perspective Projections Example Iterated Function Systems IFS Orthographic vs Perspective Simple Orthographic Projection Orthographic Perspective 3 mm v t 39 women Mano Project all points along the z axis to the z 0 plane I viii M x 1000 x y 70100 y 070000 2 1 0001 1 Simple Perspective Projection Alternate Perspective Projection I Project all points along the z axis to the z dplane eyepoint at the origin Project all points along the z axis to the z 0 plane t 7 d l 7 r X eyepoint the 00d H Tf W hm v i d y g hy n havingan quot hamogzmzz II 5 xdz x l 0 0 0 x xdzd x l 0 0 0 x ydz y 0 10 0 y ydzd y 0 10 0 y d z 0 0 l 0 z 0 0 0 0 0 0 z I zd 0 0 ld 0 l 51 l zdd 0 0 ld I 15 In the limit as d gt 00 Outline this perspective i simply h projection matrix orthographic proj ection l 0 0 0 l 0 0 0 0 l 0 0 0 l 0 0 0 0 0 0 0 0 0 0 0 0 ld l 0 0 0 l j 7 an Course Overview Classes of Transformations Representing Transformations Transformations in Modelling Combining Transformations Orthographic amp Perspective Projections Example Iterated Function Systems IFS Iterated Function Systems IFS 0 Capture selfsimilarity reduce distances An attractor is a fixed point A Ur A Contraction g 5 a I a 39E V39 g IFWik Example Sierpinski Triangle Described by a set of n affine transformations In this case n 3 7 translate amp scale by 0 5 Example Sierpinski Triangle for lots of random input points x0 yo for j0 to numiters randomly pick one of the transformations xk 1 Yk 1 fi xk Yk display xk r Yk Increasing the number of iterations Another IFS The Dragon Of 1 WWW 3D IFS in OpenGL GLPOI NT S GLQUADS A 395 stagquot I x 39 5quot i I l I Jigsr 2K Egg 39 I Assignment 1 OpenGL Warmup 0 Get familiar with C environment OpenGL Transformations simple Vector Matrix amp Image classes 0 Have Fun 0 Due Thursday Jan 25th at 1159pm 1O CSCI49726963 Advanced Computer Graphics httpwwwcsrpieducutlerclassesadvancedgraphicsSOS Professor Barb Cutler cutlercsrpiedu MRC 309A Topics for the Semester 0 Meshes Rendering 7 representation 7 my tmcing 7 simpli cation 7 appeamnce models 7 subdivision surfaces 7 shadows 7 genemtion 7 local vs global 7 volumetric modeling illumination Simulation 7 mdiosity photon mg subsurface 7 particle systems scanning etc 7 rigid body deformation cloth windwater ows 7 collision detection 7 weathering 0 hardware amp more procedural modeling 0 texture synthesis Mesh Generation amp Volumetric Modeling unanan nunan Inlm m quot l wagering p 39 Cutler et a1 Simpli cation and Improvement of Tetmhedral Models for Simulation 2004 5 Luxo Jr Pixar Animation Studios 1986 Mesh Simpli cation 2 i mt n 39vlful llrn mum nullx mxtmr tumw mm u munw Hoppe Progressive Meshes SIGGRAPH 1996 Modeling Subdivision Surfaces Hoppe et a1 Piecese Smooth Surface Reconstruction 1994 Geri s Game Pixar 1997 6 Particle Systems Star Trek The Wrath othan 1982 7 Physical Simulation Rigid Body Dynamics Collision Detection Fracture Deformation Deformations 2002 Fluid Dynamics Ray Casting Visual Simulation of Smoke Fedkiw Stam amp Jensen SIGGRAPH 2001 Foster amp Mataxas 1996 For every pixel construct a ray from the eye 7 For every object in the scene 39 Find intersection with the ray 39 Keep the closest Ray Tracing Shade interaction of light and material Secondary rays shadows re ection refraction An Improved Illumination Model for Shaded Display Whitted 1980 Subsurface Scattering 2 Jensen et al A Practical Model for Subsurface Light Transport 2001 Appearance Models Wojciech Matusik 1 lt 33 uLa Henrik Wann Jensen Syllabus amp Course Website httpwwwcs rpieducutlerclassesadvancedgraphicsS08 Which version should I register for CSCI 6963 0 3 units of graduate credit CSCI 4972 0 4 units of undergraduate credit same lectures assignments quizzes amp grading criteria Other Questions Introductions Who are you 39 name yeardegree graphics background if any researchj ob interests Why you are taking this class something fun interesting or unusual about yourself Outline Course Overview Classes of Transformations Representing Transformations Combining Transformations Orthographic amp Perspective Projections Example Iterated Function Systems IFS OpenGL Basics What is a Transformation Maps points x y in one coordinate system to points x39 33 in another coordinate system x39axbyc y39dxeyf For example Iterated Function System IFS Simple Transformations r I I l Ja n um Iuh39nlrlz lmn lu hi Hnl Iu quoti39lm mquot 39Im39 Can be combined Are these operations invertible Yes except scale 0 Transformations are used to RigidBody Euclidean Transforms position objects in ascene Changetheshapeofobjects Create multiple copies ofobjects projection for virtual cameras Describe animations preserves distances preserves angles Similitudes Similarity Transforms Linear Transform ations Preserves angles Linear Transform ations Affine Transformations 39 LKP 9 LCP q 39 Hap aLKP preserves parallel lines Projective Transformations preserves 1ines General FreeForm Transformation Does not preserve 1ines Not as pervasive computationally more involved Sederberg and Parry siggrapn 1m Outline How are Transforms Represented Course Overview c1assesof39rransfonnations Representing Transformations Combining Transformations Orthographic amp Perspective Projections Example Iterated Function Systems IFS OpenGL Basics x axbyc y39dxey f Hz 1 t p Mpt x y Homogeneous Coordinates Translation in homogeneous coordinates Add an extra dimension x abcdx y 2fghy z kaIZ w mnupw X Zaxbyc y dx2yf Af ne furmulatmn c f l l p Mptt p Mp Homogeneous furmulatmn x y Homogeneous Coordinates Homogeneous Visualization Most ofthe time W 1 and We can ignore it x abcdx y efghy z zjklz 100011 Divide by w to normalize homogenize W 0 Pamt at m mty dzrecnan extra dimension Because noW translations can be encoded in the matrix Why bother with the 39 7 Ifwe multiply ahomogeneous coordinate v v 1 v Z w by an a me matrix W is unchanged 739 L 14 Z Z 14 ha m it 3 32 Translate Ix Iy 2 Translatewo Scale 3x 3y SZ smear y y p Isotropic uniform scali g SySx 1 139 x 1 0 0 x x X XX 0 0 0 x y 0 1 0 ty y y 5y 0 0 y z 0 0 l t z z 0 0 S 0 z 1 0 0 0 l l 1 0 0 l l 33 u Rotation Rotation y hum Aboutz axis About kx ky kx aunit vector on an arbitme axis Rodrigues Formula x kxkx1cc akin was Han mm o x x 5056 41716 y g g y aha04rka 1616mm him cm 0 y y m was z akin c116 akin c1 kk1cc o z z 1 1 1 l 0 0 where 00039 amp ssm9 Storage Outline Often w is not stored always 1 Needs careful handling of direction vs point 7 Mathematically the simplest is to encode directions With w 0 7 In terms of storage using a 3component array for both direction and poinw is more ef cient 7 Which requires to have special operation routines for points vs directions 0 Course Overview 0 Classes of Transformations Representing Transformations Combining Transformations Orthographic amp Perspective Projections 0 Example Iterated Function Systems IFS OpenGL Basics How are transforms combined Noncommutative Composition Scale then Translate gt gt 5 3 l l 22 39 m Saran Transom 3V1 MI W Use matrix multiplication p39 T S p TS p l 0 3 2 0 0 2 0 3 TS 0 l I 0 2 0 0 2 I 0 0 l 0 0 l 0 0 l Caution matrix multiplication is NOT commutative aa Scale then Translate p39 T S p TS p I gt I gt I 53 m Saran 22 Tramway 11 v v Translate then Scale p39 S T p ST p gt A 2 gt ll 1V1 TranslateGJ My Saran 61 v Noncommutative Composition Outline Scale then Translate p39 T S p TS p 10 3 2 0 0 2 0 3 TS 0 l I 0 2 0 0 2 I 0 01 0 01 0 01 Translate then Scale p39 STp STp 2 0 0 10 3 2 0 6 ST 7 0 2 0 011 7 0 2 2 0 0 l 0 0 l 0 01 0 Course Overview 0 Classes of Transformations Representing Transformations Combining Transformations Orthographic amp Perspective Projections 0 Example Iterated Function Systems IFS OpenGL Basics Orthographic vs Perspective Simple Orthographic Projection Orthographic Perspective 3 mm v t 39 women Mano Project all points along the z axis to the z 0 plane I viii M x 1000 x y 70100 y 070000 2 1 0001 1 Simple Perspective Projection Alternate Perspective Projection I Project all points along the z axis to the z dplane eyepoint at the origin Project all points along the z axis to the z 0 plane t 7 d l 7 r X eyepoint the 00d H Tf W hm v i d y g hy n havingan quot hamogzmzz II 5 xdz x l 0 0 0 x xdzd x l 0 0 0 x ydz y 0 10 0 y ydzd y 0 10 0 y d z 0 0 l 0 z 0 0 0 0 0 0 z I zd 0 0 ld 0 l 65 l zdd 0 0 ld l I In the limit as d gt 00 Outline this perspective i simply h projection matrix orthographic proj ection l 0 0 0 l 0 0 0 0 l 0 0 0 l 0 0 0 0 0 0 0 0 0 0 0 0 ld l 0 0 0 l j 7 an Course Overview Classes of Transformations Representing Transformations Combining Transformations Orthographic amp Perspective Projections Example Iterated Function Systems IFS OpenGL Basics Iterated Function Systems IFS 0 Capture selfsimilarity reduce distances An attractor is a fixed point a A 39 A as iquot U f a g I a 39E V39 g IFWik Contraction g 5 a Example Sierpinski Triangle Described by a set of n affine transformations In this case n 3 7 translate amp scale by 0 5 Example Sierpinski Triangle for lots of random input points x0 yo for j0 to numiters randomly pick one of the transformations xk 1 Yk 1 fi xk Yk display xk r Yk Increasing the number of iterations Another IFS The Dragon Of 1 WWW 3D IFS in OpenGL A 395 stagquot I x 39 5quot i I l I Jigsr 2K Egg 39 I GLPOI NT S GLQUADS Assignment 0 OpenGL Warmup 0 Get familiar with C environment OpenGL Transformations simple Vector amp Matrix classes Have Fun Will not be graded but you should still do it and submit it Outline OpenGL Basics GLPOINTS Course Overview Classes of Transformations Representing Transformations Combining Transformations Orthographic amp Perspective Projections Example Iterated Function Systems IFS OpenGL Basics ngisable GLLIGHTING ngegin GLPOI ms glColorBf ooooo0 glVertexBf glEnd lighting should be disabled OpenGL Basics GLQUADS OpenGL Basics Transformations glEnable GLLI GHTING ngegin GLQUADS glNormale glColorBf 10ooo0 glVertexBf u lt m h rr m x w n glVertexSf glEnd lighting should be enabled an appropriate normal should be speci ed Useful commands glMatrixMode GLMODELVIEW 39 glPushMatrixU glPopMatrix glMultMatrixf 3 CS 5 i i E l mnup d I q p u n Inn 1 m l K j mudelview l h g 1 pmjezfuun K 39 matrix stack e d c b malle Star 39 4g 32 4x4malnces w 43 2 4X4mamces 39 II a cg e i i E l m n u I From OpenGL Reference Manual Questions For Next Time Read Hugues Hoppe Progressive Meshes SIGGRAPH 1996 Post a comment or question on the course WebCTLMS discussion by 10am on Friday 1 15 i I I V 3927 mm mm mu nu mwh um a la n munMu

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I made $350 in just two days after posting my first study guide."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.