[SOLVED] 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<=1c = alpha c_a + beta c_b + gamma c_cdrawpixel(x,y,c)CSI4130 – Computer Graphics Smooth Shading of Triangle• Color defined at verticesCSI4130 – Computer Graphics
  12Aside:Setting the Drawing Color in OpenGL• OpenGL Immediate Mode– Drawing color is a state. The current vertex is drawn with thecurrent 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)– AbufferobjecttoholdvertexdataiscalledaVertexBufferObject (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 theVAO/VBO (see gl.deleteVertexArrays) CSI4130 Computer GraphicsVertex Shader Program• •Vertex shader program is flexible to use (many) different buffersWe have used so far– 1VBOatlocation0forthevertexpositionsoftypevec2or vec4.– 2 uniforms for the modelview and projection matrices.#version 300 eslayout (location=0) in vec4 position;uniform mat4 ModelViewMatrix;uniform mat4 ProjectionMatrix;CSI4130 – Computer GraphicsBuffer Memory Allocation– Buffers are identified by name (an unsigned integer number). – Need to perform the following steps1. ask WebGL for a buffer name2. bind the name to a binding point– here use the gl.ARRAY_BUFFER binding point3. 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 GraphicsVertex 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 verticesgl.drawArrays( gl.TRIANGLES, 0, 3 );CSI4130 Computer GraphicsMore 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 GraphicsUsing Additional Vertex Attributes•Adjust the shader program•Query the locations for the attributes in your initialization•Use the locationlayout (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 VBOVAOVBO VBOv0 c0v1 c1v2 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 vertexbuffer object– Less overhead because of fewer openGL calls and moreVBO v0v1v2resource consciousVAOgl.vertexAttribPointer(locColor, 3, gl.FLOAT, false,c0 0, c1Float32Array.BYTES_PER_ELEMENT * 3 * nVerts);c2CSI4130 – Computer Graphics Format of VBO: Interleaved• Interleaved storage in one buffer– Keep all information about a vertex together and make useof the stride parameterVBO v0c0v1– Here assuming a vertex is stored as three floatsgl.vertexAttribPointer(locColor, 3, gl.FLOAT, false, Float32Array.BYTES_PER_ELEMENT * 3 ) Float32Array.BYTES_PER_ELEMENT * 3 );CSI4130 – Computer Graphicsoffsetc1 v2 c2VAOstride Details of Triangle Rasterization• Which pixel belongs to a triangle?Offscreen Point– triangles usually share edges1, 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 differentlyCSI4130 – Computer Graphics Edge Pixelsdetermine x_min, x_max, y_min, y_maxcalculate f_alpha, f_beta, f_gammafor x=x_min to x_max dofor 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 midpointy=y+1// next midpointd=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 ShadingCSI4130 – Computer Graphics