Published on

31-Dec-2015View

23Download

2

DESCRIPTION

CS 430/536 Computer Graphics I Line Drawing Week 1, Lecture 2. David Breen, William Regli and Maxim Peysakhov Geometric and Intelligent Computing Laboratory Department of Computer Science Drexel University http://gicl.cs.drexel.edu. Outline. Math refresher Line drawing - PowerPoint PPT Presentation

Transcript

*CS 430/536Computer Graphics I

Line DrawingWeek 1, Lecture 2David Breen, William Regli and Maxim PeysakhovGeometric and Intelligent Computing LaboratoryDepartment of Computer ScienceDrexel Universityhttp://gicl.cs.drexel.edu

*OutlineMath refresherLine drawingDigital differential analyzerBresenhams algorithmXPM file format

*Geometric PreliminariesAffine GeometryScalars + Points + Vectors and their opsEuclidian GeometryAffine Geometry lacks angles, distanceNew op: Inner/Dot product, which givesLength, distance, normalizationAngle, Orthogonality, Orthogonal projection Projective Geometry

*Affine GeometryAffine Operations:

Affine Combinations: 1v1 + 2v2 + + nvn where v1,v2, ,vn are vectors and Example:

*Mathematical PreliminariesVector: an n-tuple of real numbersVector OperationsVector addition: u + v = wCommutative, associative, identity element (0)Scalar multiplication: cv

Note: Vectors and Points are differentCan not add pointsCan find the vector between two points

*Linear Combinations & Dot ProductsA linear combination of the vectors v1, v2, vn is any vector of the form a1v1 + a2v2 + + anvn where ai is a real number (i.e. a scalar) Dot Product:

a real value u1v1 + u2v2 + + unvn written as

*Fun with Dot ProductsEuclidian Distance from (x,y) to (0,0) in general: which is just: This is also the length of vector v: ||v|| or |v|Normalization of a vector:Orthogonal vectors:

*Projections & AnglesAngle between vectors,

Projection of vectorsPics/Math courtesy of Dave Mount @ UMD-CP

*Matrices and Matrix OperatorsA n-dimensional vector:

Matrix Operations:Addition/SubtractionIdentityMultiplicationScalarMatrix MultiplicationImplementation issue: Where does the index start? (0 or 1, its up to you)

*Matrix Multiplication[C] = [A][B] Sum over rows & columnsRecall: matrix multiplication is not commutativeIdentity Matrix: 1s on diagonal 0s everywhere else

*Matrix DeterminantsA single real numberComputed recursivelyExample:

Uses: Find vector ortho to two other vectorsDetermine the plane of a polygon

*Cross ProductGiven two non-parallel vectors, A and BA x B calculates third vector C that is orthogonal to A and BA x B = (aybz - azby, azbx - axbz, axby - aybx)

*Matrix Transpose & InverseMatrix Transpose: Swap rows and cols:Facts about the transpose:

Matrix Inverse: Given A, find B such that AB = BA = I BA-1 (only defined for square matrices)

*Line Drawing

*Scan-Conversion AlgorithmsScan-Conversion: Computing pixel coordinates for ideal line on 2D raster gridPixels best visualized as circles/dotsWhy? Monitor hardware 1994 Foley/VanDam/Finer/Huges/Phillips ICG

*Drawing a Liney = mx + Bm = y / xStart at leftmost x and increment by 1 x = 1yi = Round(mxi + B)This is expensive and inefficientSince x = 1, yi+1 = yi + y = yi + m No more multiplication!This leads to an incremental algorithm

*Digital Differential Analyzer (DDA)If |slope| is less then 1x = 1 else y = 1Check for vertical linem = Compute corresponding y (x) = m (1/m)xk+1 = xk + xyk+1 = yk + yRound (x,y) for pixel location Issue: Would like to avoid floating point operations1994 Foley/VanDam/Finer/Huges/Phillips ICGxk+1xxkyk+1yky

Generalizing DDAIf |slope| is less than or equal to 1Ending point should be right of starting point If |slope| is greater than 1Ending point should be above starting pointVertical line is a special case x = 0

*

*Bresenhams Algorithm1965 @ IBMBasic Idea:Only integer arithmeticIncremental

Consider the implicit equation for a line:1994 Foley/VanDam/Finer/Huges/Phillips ICG

*The AlgorithmAssumptions: 0 slope 1Pre-computed:Pics/Math courtesy of Dave Mount @ UMD-CP

*Bresenhams AlgorithmGiven:implicit line equation:Let: where r and q are points on the line and dx ,dy are positive Then:Observe that all of these are integers and: for points above the line for points below the lineNow..Pics/Math courtesy of Dave Mount @ UMD-CP

*Bresenhams AlgorithmSuppose we just finished (assume 0 slope 1) other cases symmetricWhich pixel next?E or NEPics/Math courtesy of Dave Mount @ UMD-CPQ

*Assume:Q = exact y value aty midway between E and NE:Observe:If , then pick EElse pick NEIf , it doesnt matter Bresenhams AlgorithmPics/Math courtesy of Dave Mount @ UMD-CP

*Create modified implicit function (2x) Create a decision variable D to select, where D is the value of f at the midpoint:Bresenhams AlgorithmPics/Math courtesy of Dave Mount @ UMD-CP

*Bresenhams AlgorithmIf then M is below the lineNE is the closest pixelIf then M is above the lineE is the closest pixel

*Bresenhams AlgorithmIf then M is below the lineNE is the closest pixelIf then M is above the lineE is the closest pixel

Note: because we multiplied by 2x, D is now an integer---which is very good newsHow do we make this incremental??

What increment for computing a new D?Next midpoint is:

Hence, increment by:*Case I: When E is nextPics/Math courtesy of Dave Mount @ UMD-CP

*Case II: When NE is nextWhat increment for computing a new D?Next midpoint is:

Hence, increment by:Pics/Math courtesy of Dave Mount @ UMD-CP

*How to get an initial value for D?Suppose we start at:Initial midpoint is:Then: Pics/Math courtesy of Dave Mount @ UMD-CP

*The AlgorithmAssumptions: 0 slope 1Pre-computed:Pics/Math courtesy of Dave Mount @ UMD-CP

- *Generalize AlgorithmIf qx > rx, swap pointsIf slope > 1, always increment y, conditionally increment xIf -1
Generalize AlgorithmReflect line into first caseCalculate pixelsReflect pixels back into original orientation*

*Bresenhams Algorithm: Example

*Bresenhams Algorithm: Example

*Bresenhams Algorithm: Example

*Bresenhams Algorithm: Example

*Bresenhams Algorithm: Example

*Bresenhams Algorithm: Example

*Bresenhams Algorithm: Example

*Bresenhams Algorithm: Example

*Bresenhams Algorithm: Example

*Some issues with Bresenhams AlgorithmsPixel density varies based on slopestraight lines look darker, more pixels per unit lengthEndpoint orderLine from P1 to P2 should match P2 to P1Always choose E when hitting M, regardless of direction1994 Foley/VanDam/Finer/Huges/Phillips ICG

*Some issues with Bresenhams AlgorithmsHow to handle the line when it hits the clip window?Vertical intersectionsCould change line slopeNeed to change init cond.Horizontal intersectionsAgain, changes in the boundary conditionsCant just intersect the line w/ the box1994 Foley/VanDam/Finer/Huges/Phillips ICG

*XPM FormatEncoded pixelsC code ASCII Text file Viewable on Unix w/ display On Windows with IrfanVIew Translate w/ convert

*XPM BasicsX PixelMap (XPM)Native file format in X WindowsColor cursor and icon bitmapsFiles are actually C source codeRead by compiler instead of viewerSuccessor of X BitMap (XBM) B-W format

*XPM Supports Color

*XPM: Defining Grayscales and ColorsEach pixel specified by an ASCII charkey describes the context this color should be used within. You can always use c for color.Colors can be specified:color name # followed by the RGB code in hexadecimalRGB 24 bits (2 characters 0 - f) for each color.

*XPM: Specifying Color

Color NameRGBColorblack# 00 00 00white# ff ff ff# 80 80 80red# ff 00 00green# 00 ff 00blue# 00 00 ff

*XPM ExampleArray of C stringsThe XPM format assumes the origin (0,0) is in the upper left-hand corner. First string is width height ncolors cpp Then you have "ncolors" strings associating characters with colors. And last you have "height" strings of "width" * "chars_per_pixel" characters

*Arrangements for PresentationsGrad students pick datesE-mail me your preferencePriority - first come, first served

*Programming assignment 1Input PostScript-like fileOutput B/W XPMPrimary I/O formats for the courseCreate data structure to hold points and lines in memory (the world model) Implement 2D translation, rotation and scaling of the world modelImplement line drawing and clippingJanuary 20thGet started now!

*Questions?Go to Assignment 1

*************************************************