### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Introduction to Computer Graphics CS 4810

UVA

GPA 3.71

### View Full Document

## 28

## 0

## Popular in Course

## Popular in ComputerScienence

This 93 page Class Notes was uploaded by Mrs. Carolyne Abbott on Monday September 21, 2015. The Class Notes belongs to CS 4810 at University of Virginia taught by Jason Lawrence in Fall. Since its upload, it has received 28 views. For similar materials see /class/209634/cs-4810-university-of-virginia in ComputerScienence at University of Virginia.

## Popular in ComputerScienence

## Reviews for Introduction to Computer Graphics

### 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: 09/21/15

Clipping and Scan Conversion Jason Lawrence CS 445 Graphics Acknowledgment slides by Misha Kazhdan Allison Klein Tom Funkhouser Adam Finkelstein and David Dobkin 3D Rendering Pipeline fordirect illumination 3D Primitives 3D Modeling Coordinates Modeling Transformation 3D World Coordinates Camera Transformation 3D Camera Coordinates Lighting 3D Camera Coordinates Pro39ection Trans ormatlon 2D Screen Coordinates Clipping 2D Screen Coordinates Viewport Transformation 2D Image Coordinates Scan Conversmn 2D Image Coordinates K Image K Transformations 3D Object Coordinates Modeling Transformation L 3D World Coordinates V Camera Transformation L 3D Camera Coordinates V Prog39ection Trans ormation L 2D Screen Coordinates WindowtoViewport Transformation 1 2D Image Coordinates IO X Y 3D World Coordinates 3 D 7 I bj ect rdinates M k 7 H V Transformations pX yiz 3D Object Coordinates Modeling Transformation 3D World Coordinates V Camera Transformation 3D World 3D Camera Coordinates Coordinates V l Pro39ection l 2 Transformation TranSfOrm M M local to world transform 2D Screen Coordinates WindowtoVieyvport Transformation 2D Image Coordinates Transformations IOXyZ 3D Object Coordinates Modeling Transformation 3D World Coordinates Camera Transformation 3D Camera Coordinates V Protjection Trans ormation 2D Screen Coordinates WindowtoViewport Transformation 2D Image Coordinates 3D Camera Coordinates 3D World Coordinates TransformM M local to world transform Transformations px y 3D Object Coordinates Modeling Transformation 3D World Coordinates Camera Transformation 3D Camera Coordinates Pro39ection Trans ormation 2D Screen Coordinates WindowtoViewport Transformation 2D Image Coordinates Camera Up TransformC391M C camera transform RxeBxEx RYUYBYEY RZUZBZEZ o 0 01 C Transformations IOXyZ 3D Object Coordinates f g g 771 WW Modeling Transformation 3D World Coordinates V Camera Transformation 3D Camera Coordinates V Progection TransformPC391M Trans ormation o P pr0Ject10n transform 10 0 0 WindowtoVieyvport 1 0 LCOS 0 Transformation 0 1 Lsinq 0 0 1 0 0 Pp0010 2D Screen Coordinates 2D Image Coordinates 0 0 0 0 0 1 0 O O 0 0 0 1 D j Transformations 3D Object Coordinates Normalized Coords Image Modeling Transformation 3D World Coordinates 7 i a k a 7 V 39Viewport Camera Transformation 3D Camera Coordinates 7 Pro39ection 1 l TranstJormation l TranSme VP C M V Vlewport transform 2D Screen Coordinates WindowtoViewport Transformation 2D Image Coordinates Transformations pXyz 3D Object Coordinates Modeling Transformation 3D World Coordinates Camera Transformation V Window 2 WY 1 Wxi Wy y W W X 2 WX Screen Coordinates 3D Camera Coordinates ection Protj Trans ormation 2D Screen Coordinates WindowtoViewport Transformation 2D Image Coordinates Viewport V 1 invy V 1lt gtVX2 Image Coordinates Transform VPCquot M V Viewport transform 100v f 1 010vy 000 0 0001 w w1 vz v 000100 010 f 3D Rendering Pipeline fordirect illumination DXyZ 1 3D Object Coordinates Modeling Transformation 3D World Coordinates Camera Transformation 3D Camera Coordinates V Projection 2D Viewport Transformation 2D Screen Coordinates WindowtoViewport Transformation 1 2D Image Coordinates t t 7 2D Screen p X y 3D Model 3D Rendering Pipeline for direct illumination 3D Primitives 3D Modeling Coordinates Moling Transfrmation 8D World Coordinates Camera 7 Transfrmation 3D Camera Coordinates Lighting 3D Camera Coordinates Pro39ection Trans rmation 2D Screen Coordinates Clipping 2D Screen Coordinates Transfrmation 2D Image Coordinates Scan Conversion 2D Image Coordinates Image Clipping Avoid drawing parts of primitives outside window Window defines part of scene being viewed Must draw geometric primitives only inside window Screen Coordinates Clipping Avoid drawing parts of primitives outside window Points Line Segmen is Polygons Point Clipping Is point xy inside the Clip window wy2 Window Point Clipping Is point xy inside the Clip window Ny2 xy inside x gt wxl x lt wx2 y gt Wyl y lt wy2 Window Clipping Avoid drawing parts of primitives outside window 0 Points Line Segments Polygons Line Segment Clipping Find the part of a line inside the Clip window Pg Before Clipping Line Segment Clipping Find the part of a line inside the Clip window After Clipping CohenSutherland Line Clipping Use simple tests to Classify easy cases first P7 CohenSutherland Line Clipping If both outcodes are 0 line segment is inside If AND of outcodes not 0 line segment is outside o Otherwise Clip and test P7 CohenSutherland Line Clipping If both outcodes are 0 line segment is inside If AND of outcodes not 0 line segment is outside o Otherwise Clip and test P7 CohenSutherland Line Clipping If both outcodes are 0 line segment is inside If AND of outcodes not 0 line segment is outside o Otherwise Clip and test P7 CohenSutherland Line Clipping If both outcodes are 0 line segment is inside If AND of outcodes not 0 line segment is outside 39 Otherwise cl p and test P7 CohenSutherland Line Clipping If both outcodes are 0 line segment is inside If AND of outcodes not 0 line segment is outside 39 Otherwise cl p and test P7 CohenSutherland Line Clipping If both outcodes are 0 line segment is inside If AND of outcodes not 0 line segment is outside 39 Otherwise cl p and test P7 CohenSutherland Line Clipping If both outcodes are 0 line segment is inside If AND of outcodes not 0 line segment is outside 39 Otherwise cl p and test P7 CohenSutherland Line Clipping If both outcodes are 0 line segment is inside If AND of outcodes not 0 line segment is outside 39 Otherwise cl p and test P7 CohenSutherland Line Clipping If both outcodes are 0 line segment is inside If AND of outcodes not 0 line segment is outside 39 Otherwise cl p and test P7 CohenSutherland Line Clipping If both outcodes are 0 line segment is inside If AND of outcodes not 0 line segment is outside 39 Otherwise cl p and test P7 CohenSutherland Line Clipping If both outcodes are 0 line segment is inside If AND of outcodes not 0 line segment is outside 39 Otherwise cl p and test P 7 CohenSutherland Line Clipping If both outcodes are 0 line segment is inside If AND of outcodes not 0 line segment is outside 39 Otherwise cl p and test CohenSutherland Line Clipping If both outcodes are 0 line segment is inside If AND of outcodes not 0 line segment is outside 39 Otherwise cl p and test P 7 CohenSutherland Line Clipping If both outcodes are 0 line segment is inside If AND of outcodes not 0 line segment is outside 39 Otherwise cl p and test P 7 CohenSutherland Line Clipping If both outcodes are 0 line segment is inside If AND of outcodes not 0 line segment is outside 39 Otherwise cl p and test P 7 CohenSutherland Line Clipping If both outcodes are 0 line segment is inside If AND of outcodes not 0 line segment is outside 39 Otherwise cl p and test Bit 4 Note both lines have the same bit codes Bit 3 CohenSutherland Line Clipping If both outcodes are 0 line segment is inside If AND of outcodes not 0 line segment is outside 39 Otherwise cl p and test P 7 CohenSutherland Line Clipping If both outcodes are 0 line segment is inside If AND of outcodes not 0 line segment is outside 39 Otherwise cl p and test P 7 CohenSutherland Line Clipping If both outcodes are 0 line segment is inside If AND of outcodes not 0 line segment is outside o Otherwise Clip and test P 7 CohenSutherland Line Clipping If both outcodes are 0 line segment is inside If AND of outcodes not 0 line segment is outside o Otherwise Clip and test P 7 CohenSutherland Line Clipping Before Clipping CohenSutherland Line Clipping After Clipping Clipping Avoid drawing parts of primitives outside window 0 Points Line Segmen is Polygons Polygon Clipping Find the part of a polygon inside the clip window A Before Clipping j Polygon Clipping Find the part of a polygon inside the clip window A After Clipping 7 SutherlandHodgeman Clipping Clip to each window boundary one at a time A j Q SutherlandHodgeman Clipping Clip to each window boundary one at a time A j Q SutherlandHodgeman Clipping Clip to each window boundary one at a time A j SutherlandHodgeman Clipping Clip to each window boundary one at a time A r j SutherlandHodgeman Clipping Clip to each window boundary one at a time A j SutherlandHodgeman Clipping How do we Clip a polygon with respect to a line Window Boundary Hnede U Eze de SutherlandHodgeman Clipping Do inside test for each point in sequence Insert new points when cross window boundary Remove points outside window boundary P2 P1 Window Boundary insde uiside SutherlandHodgeman Clipping Do inside test for each point in sequence Insert new points when cross window boundary Remove points outside window boundary P2 P1 Window Boundary insde uiside SutherlandHodgeman Clipping Do inside test for each point in sequence Insert new points when cross window boundary Remove points outside window boundary P2 P1 Window Boundary insde uiside SutherlandHodgeman Clipping Do inside test for each point in sequence Insert new points when cross window boundary Remove points outside window boundary P2 P1 Window Boundary insde uiside SutherlandHodgeman Clipping Do inside test for each point in sequence Insert new points when cross window boundary Remove points outside window boundary P2 P1 Window Boundary insde uiside P SutherlandHodgeman Clipping Do inside test for each point in sequence Insert new points when cross window boundary Remove points outside window boundary P2 P1 Window Boundary insde uiside P SutherlandHodgeman Clipping Do inside test for each point in sequence Insert new points when cross window boundary Remove points outside window boundary P2 P1 Window Boundary insde uiside P SutherlandHodgeman Clipping Do inside test for each point in sequence Insert new points when cross window boundary Remove points outside window boundary P2 P1 Window Boundary insde uiside P P P5 SutherlandHodgeman Clipping Do inside test for each point in sequence Insert new points when cross window boundary Remove points outside window boundary P2 P1 Window Boundary insde uiside P v P f 3D Rendering Pipeline fordirect illumination 3D Primitives 1 3D Modeling Coordinates Modeling Transformation 1 3D World Coordinates Camera Transformation 3D Camera Coordinates Lighting 1 3D Camera Coordinates Proljection Trans ormation 1 2D Screen Coordinates Clipping 1 2D Screen Coordinates Viewport Transformation 1 2D Image Coordinates Scan Conversron 1 2D Image Coordinates Image 3D Model 2D Window 2D Screen 2D Rendering Pipeline 2D Primitives Clipping Scan Conversion Clip pertiens Oi geemetric primitives residing utsicie the Window Fill pixels representing primitives in screen coordinates Overview Scan conversion 0 Figure out which pixels to fill Shading 0 Determine a color for each filled pixel Depth test 0 Determine when the color of a pixel should be overwritten Scan Conversion Render an image of a geometric primitive by setting pixel colors void SetPixelint x int y Color rgba Example Filling the inside of a triangle I1 Scan Conversion Render an image of a geometric primitive by setting pixel colors void SetPixelint x int y Color rgba Example Filling the inside of a triangle Triangle Scan Conversion Properties of a good algorithm 0 MUST BE FAST 0 No cracks between adjacent primitives Triangle Scan Conversion Properties of a good algorithm 0 MUST BE FAST 0 No cracks between adjacent primitives Simple Algorithm Color all pixels inside triangle void ScanTriangleTriangle T Color rgba for each pixel P at xy if InsideT P SetPixelx y rgba Line defines two halfspaces Test use implicit equation for a line 0 On line axbyc0 0 On right ax byCltO 0 On left ax byCgtO Inside Triangle Test A point is inside a triangle if it is in the positive halfspace of all three boundary lines 0 Triangle vertices are ordered counterclockwise 0 Point must be on the left side of every boundary line Inside Triangle Test Boolean InsideTriangle T Point P for each boundary line L of T Scalar d LaPx LbPy Lc if d lt 00 return FALSE return TRUE Simple Algorithm What is bad about this algorithm void ScanTriangleTriangle T Color rgba for each pixel P at xy if InsideT P SetPixelx y rgba Triangle SweepLine Algorithm Take advantage of spatial coherence 0 Compute which pixels are inside using horizontal spans 0 Process horizontal spans in scanline order Take advantage of edge linearity 0 Use edge slopes to update coordinates incrementally Triangle SweepLine Algorithm void ScanTriangleTriangle T Color rgba for both edge pairs initialize xL xR compute dedyL and dedyR for each scanline at y for int x XL x lt xR x SetPixelx y rgba XL dedyL xR dedyR Polygon Scan Conversion Will this method work for convex polygons Polygon Scan Conversion Will this method work for convex polygons 0 Yes since each scan line will only intersect the polygon at two points A l L l Polygon Scan Conversion How about these polygons Polygon Scan Conversion How about these polygons Polygon Scan Conversion Fill pixels inside a polygon Starshaped Concave Triangle Quadrilateral Selfintersecting HoleS 7 Convex What problems do we encounter with arbitrary polygons Polygon Scan Conversion Need better test for points inside polygon Triangle method works only for convex polygons Convex Polygon Concave Polygon Inside Polygon Rule What is a good rule for which pixels are inside Concave Selflntersecting lt With Holes Inside Polygon Rule Oddparity rule 0 Any ray from P to infinity crosses odd number of edges E O Concave Selflntersecting With Holes Polygon SweepLine Algorithm Incremental algorithm to find spans and determine insideness with odd parity rule 0 Takes advantage of scan line coherence Triangle Polygon Polygon SweepLine Algorithm void ScanPolygonPolygon P Color rgba sort edges by maxy make empty active edge listquot for each scanline top to bottom insertremove edges from active edge listquot update x coordinate of every active edge sort active edges by x coordinate for each pair of active edges left to right SetPixelsxi x i y rgba Hardware Scan Conversion Convert everything into triangles 0 Scan convert the triangles Scan Conversion What about pixels on edges 0 If we set them either on or off we get aliasing or jaggies Scan Conversion What about pixels on edges 0 If we set them either on or off we get aliasing or jaggies Antialiasing Techniques Display at higher resolution 0 Corresponds to increasing sampling rate 0 Not always possible fixed size monitors fixed refresh rates etc Modify pixel intensities Vary pixel intensities along primitive boundaries for antialiasing 0 Must have more than bilevel display Scan Conversion What about pixels on edges 0 If we set them either on or off we get aliasing or jaggies Vary pixel intensities along primitive boundaries for antialiasing Antialiasing Method 1Area sampling aka pretiltering 0 Calculate percent of pixel covered by primitive 0 Multiply this percentage by desired intensitycolor 0 Set resulting pixel to closest available display level P1 2 25 60 100 y P1 Antialiasing Method 2 Supersampling aka postfiltering 0 Sample as if screen were higher resolution 0 Average multiple samples to get final intensity Antialiasing Method 2 Supersampling aka postfiltering 0 Sample as if screen were higher resolution 0 Average multiple samples to get final intensity amounts to using a a bilinear interpolation lter t i t Antialiasing Method 2 Supersampling aka postfiltering 0 Sample as if screen were higher resolution 0 Average multiple samples to get final intensity This amounts to using a bilinear interpolation lte P2 Can use other lters e g 1 Gaussian for better interpolation P3 Scan Conversion Example N0 AntiAliasing 4 X AntiAliasing Images courtesy of NVIDIA

### 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 used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### 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.