CS代考计算机代写 flex algorithm Computer Graphics CSI4130 – Winter 2019

Computer Graphics CSI4130 – Winter 2019
Jochen Lang
EECS, University of Ottawa Canada

Summary: Representations for Curves and Surfaces
– Parametric curves and surfaces
– Implicit curves in 2D and implicit surfaces in 3D
– Gradient
– Line equations
CSI4130 – Computer Graphics

This Lecture
• Triangles and Rasterization – Textbook: Chapter 2
– Triangles
– Baricentric coordinates
– Triangle rasterization – Simple Anti-Aliasing
CSI4130 – Computer Graphics

Triangles
• Fundamental modeling primitive
– OpenGL pipeline is optimized for triangles as geometric
primitive
– A triangle is in a plane defined by its 3 vertices
– Triangles interpolate their endpoints linearly along their edges and in the plane
– Trianglesdefinebaricentriccoordinates(non-orthogonal axes)
• Triangle area (2D) is the determinant – Vertices a,b,c in rhs
CSI4130 – Computer Graphics

Triangles 2D
• Baricentric coordinates
– Anypointinthetrianglecanbedescribedasthesumoftwo
edge vectors plus an origin.
CSI4130 – Computer Graphics

Baricentric Coordinates
• Given a point find its baricentric coordinates w.r.t. the triangle a,b,c
CSI4130 – Computer Graphics

Reminder: Distance of a Point from a Line
• Use implicit formulation
• Signed distance d
0
CSI4130 – Computer Graphics

Baricentric Coordinates via Implicit Line Equations
• Given a point find its baricentric coordinates w.r.t. the triangle a,b,c
CSI4130 – Computer Graphics

Baricentric Coordinates via Triangle Area
• Given a point find its baricentric coordinates w.r.t. the triangle a,b,c
CSI4130 – Computer Graphics

Triangles 3D
• Baricentric coordinates carry over
• Normal via cross products
• Area via length of normal
• Baricentric coordinates require signed area – Calculate dot product between normals
– Same side +1 other side -1
CSI4130 – Computer Graphics

Triangle Rasterization
• How to decide if pixels belong to a triangle?
– Triangle defined by 3 points
– Assume2Dcoordinates,otherwise
apply orthographic and perspective
projection first
– Utilize baricentric coordinates
for all x do
for all y do
compute ( alpha, beta, gamma ) of (x,y)
if 0<=alpha<=1 and 0<=beta<=1 and 0<=gamma<=1 c = alpha c_a + beta c_b + gamma c_c drawpixel(x,y,c) CSI4130 - Computer Graphics Smooth Shading of Triangle • Color defined at vertices CSI4130 - Computer Graphics
  12 Aside: Setting the Drawing Color in OpenGL • OpenGL Immediate Mode – Drawing color is a state. The current vertex is drawn with the current color. – Example: glColor3f( 1.0f, 0.0f, 0.0f ); • WebGL and Modern OpenGL – Need to look at buffers for data transfer – Example will be for WebGL 2 (using a Vertex Array Object VAO) or for OpenGL 3.3+ CSI4130 - Computer Graphics Data Transfer to WebGL/OpenGL • Uniforms – Variablesthatstayconstantforoneexecutionofthebuffer • Buffer objects hold data in WebGL/OpenGL (GL) – AbufferobjecttoholdvertexdataiscalledaVertexBuffer Object (VBO) • Vertex Array Objects (VAO) – Organizeoneorseveralvertexarraybuffersintoacommon object – VAOstoresstateincluding: • Parametersofthecalltogl.VertexAttribPointer (size, type, stride, and offset) • gl.ARRAY_BUFFER in use when gl.VertexAttribPointer was called. CSI4130 - Computer Graphics Program Structure with VAO/VBO • Set-up in initialization routine – generate and bind VAO – generate, bind and fill (multiple) VBO for storing vertices and their attributes (e.g., colors, normals, texture coordinates) – unbind VAO and possibly go the next set-up • Drawing routine – bind the desired VAO – call draw using data stored in the VBOs of the VAO – unbind the VAO • Clean-up – If there is lot of data in GL, free up the space taken up by the VAO/VBO (see gl.deleteVertexArrays) CSI4130 Computer Graphics Vertex Shader Program • • Vertex shader program is flexible to use (many) different buffers We have used so far – 1VBOatlocation0forthevertexpositionsoftypevec2or vec4. – 2 uniforms for the modelview and projection matrices. #version 300 es layout (location=0) in vec4 position; uniform mat4 ModelViewMatrix; uniform mat4 ProjectionMatrix; CSI4130 - Computer Graphics Buffer Memory Allocation – Buffers are identified by name (an unsigned integer number). – Need to perform the following steps 1. ask WebGL for a buffer name 2. bind the name to a binding point – here use the gl.ARRAY_BUFFER binding point 3. Tell WebGL how big the buffer needs to be and optionally fill it with data // Generate an array of handles to VBO const vertBuf = gl.createBuffer(); gl.bindBuffer(gl.ARRAY_BUFFER, vertBuf); gl.bufferData(gl.ARRAY_BUFFER, verts, gl.STATIC_DRAW); CSI4130 Computer Graphics Vertex Array Objects (VAO) – Organize one or several vertex array buffers into a common object – Available since WebGL 2.0 • OpenGL 4 always uses a VAO – Once the VAO is bound VBOs can be bound to it // Generate an VAO and bind it const vao = gl.createVertexArray(); gl.bindVertexArray( vao ); CSI4130 Computer Graphics Drawing with a VBO/VAO – LetGLknowhowthedataistobeused • index, size of a single data, data type, normalize, stride (if there are gaps in the array), offset – Enable the attribute in the buffer object for drawing // offset into the buffer and data format gl.vertexAttribPointer(0, 2, gl.FLOAT, false, 0, 0 ); gl.enableVertexAttribArray(0); – Drawing with the currently bound VAO • type of primitive, starting index and number of vertices gl.drawArrays( gl.TRIANGLES, 0, 3 ); CSI4130 Computer Graphics More Vertex Attributes • • Our models (normally) have additional vertex attributes – color, normals, texture coordinates, ... Example: Color as an additional vertex attribute – need to transfer the data to GL in a buffer – adjust our vertex program to use the data • exactly the same as for vertex coordinates ... // Additional attributes in separate buffer object const colorBuf = gl.createBuffer(); gl.bindBuffer(gl.ARRAY_BUFFER, colorBuf); gl.BufferData(gl.ARRAY_BUFFER, colors, gl.STATIC_DRAW); CSI4130 - Computer Graphics Using Additional Vertex Attributes • Adjust the shader program • Query the locations for the attributes in your initialization • Use the location layout (location=0) in vec4 position; layout (location=1) in vec4 color; locPos = gl.getAttribLocation( program, "position"); locColor = gl.getAttribLocation(program, "color"); gl.vertexAttribPointer(locColor, 4, gl.FLOAT, false, 0, 0); gl.enableVertexAttribArray(locColor); CSI4130 - Computer Graphics Format of VBO VAO VBO VBO v0 c0 v1 c1 v2 c2 • One buffer per attribute – The approach on the previous slide – Uses many buffers but independent buffer exchanges are easy • Sequential storage in one buffer – Can store position, color, normal as blocks in a single vertex buffer object – Less overhead because of fewer openGL calls and more VBO v0 v1 v2 resource conscious VAO gl.vertexAttribPointer(locColor, 3, gl.FLOAT, false, c0 0, c1 Float32Array.BYTES_PER_ELEMENT * 3 * nVerts); c2 CSI4130 - Computer Graphics Format of VBO: Interleaved • Interleaved storage in one buffer – Keep all information about a vertex together and make use of the stride parameter VBO v0 c0 v1 – Here assuming a vertex is stored as three floats gl.vertexAttribPointer(locColor, 3, gl.FLOAT, false, Float32Array.BYTES_PER_ELEMENT * 3 ) Float32Array.BYTES_PER_ELEMENT * 3 ); CSI4130 - Computer Graphics offset c1 v2 c2 VAO stride Details of Triangle Rasterization • Which pixel belongs to a triangle? Offscreen Point – triangles usually share edges 1, 1 – holes are bad – double coloring is bad because of transparency • Solution – draw pixel only if we inside of triangle – treat pixel exactly on the edge differently CSI4130 - Computer Graphics Edge Pixels determine x_min, x_max, y_min, y_max calculate f_alpha, f_beta, f_gamma for x=x_min to x_max do for y=y_min to y_max do alpha = f12(x,y)/f_alpha beta = f20(x,y)/f_beta gamma = f01(x,y)/f_gamma if alpha>=0 and beta>=0 and gamma>=0
if (alpha>0 or f_alpha * f12(-1,-1)>0) and (beta>0 or f_beta * f20(-1,-1)>0) and (gamma>0 or f_gamma * f01(-1,-1)>0)
c = alpha c_a + beta c_b + gamma c_c
drawpixel(x,y,c)
CSI4130 – Computer Graphics

Anti-Aliasing
• Box-filter: average pixel over an area
• e.g., 2x, 4x, 6x
– simple implementation
– use images 2x, 4x or 6x the size of the original image
– pixel in original image is the average of a 2×2 area, 4×4 area or 6×6 area of the enlarged image
CSI4130 – Computer Graphics

Line Drawing
– Bresenham Algorithm or
– Incremental Midpoint Algorithm
• use implicit lines
CSI4130 – Computer Graphics

Integer Line Drawing
– avoid floating point operations
– incrementalalgorithm • Key observations
– Ateachpixeldecideifpositionalongminoraxisneedstobe changed
– 4 Cases
• Line mainly along x with gradient • Line mainly along x with gradient • Line mainly along y with gradient • Line mainly along y with gradient
CSI4130 – Computer Graphics

Decide the Next Pixel
• Incremental Midpoint Algorithm
– Decision based on which side of the midpoint the line
crosses
– on the left/right of midpoint
CSI4130 – Computer Graphics

Incremental Midpoint Algorithm
// Integer start position
y=y0
// Initialize decision variable at (x0,y0+0.5)
// use 2f(x,y) = 0
d=(y0-y1)(2*x0)+(x1-x0)(2*y0+1)+2*(x0*y1-x1*y0)=x1-x0
for x=x0 to x1
draw( x, y )
if d<0 then // left of midpoint y=y+1 // next midpoint d=d+2*(x1-x0)+2*(y0-y1) else // right of midpoint -- next midpoint d=d+2*(y0-y1) CSI4130 - Computer Graphics Next • Shading – Textbook: Chapter 5.1, 5.2, 5.3 – Shading – Diffuse Shading – Blinn-Phong Shading CSI4130 - Computer Graphics