Shading AlgorithmsRon GoldmanDepartment of Computer ScienceRice UniversityIllumination and ShadingStandard Assumptions• Curved surfaces are approximated by planar polygons.• All light sources are point light sources (at infinity).Illumination Models• Ambient Light• Diffuse Reflection (Scattering)• Specular ReflectionShading Models• Uniform (Flat)• Gouraud• PhongShadingAlgorithms• Uniform -- constant intensity for each polygon (Flat)• Gouraud -- linear interpolation of intensity for each polygon along scan lines• Phong -- linear interpolation of normal vectors (non-linear interpolation of intensity) for each polygon along scan linesUniform ShadingAssumptions1. The surfaces really are polygonal.• N = surface normal = constant2. Light source at infinity• L = vector to light source = constant•L • N = constant•R = 2( L • N)N − L = constant3. Eye at infinity• V = vector to eye = constant•N •V = constant•R• V = constantUniform Shading (continued)Intensity• Iuniform= Iakaambient{+ Ipkd(L • N)diffuse1 2 4 3 4 + Ipks(R •V )nspecular1 2 4 4 3 4 4 •N, L, R, V constant ⇒ Iuniform constant along each polygonθNLSurfaceθαRVMach Bands• Discontinuities in intensity along polygon edges.• Individual polygons highly visible.• Heightened by physiological effects of the eye.Gouraud ShadingPurpose• To Reduce Mach BandsMethod• Linear Interpolation of IntensitiesStrategy1. Compute intensity at vertices, using an average unit normal vector.•€ Nvertex=Npolygonvertex∈Polygon∑Npolygonvertex∈Polygon∑ (Normalized Average)2. Interpolate intensity along edges.3. Interpolate intensity along scan lines.Observation• Polygon intensities agree along common edges.• Integrates well with hidden surface scan line algorithm.PolygonScan Line€ •€ •VertexVertexEdge€ •€ •€ •€ •VertexVertexVertexVertexEdgeEdgeEdgeEdgeEdgeScan LineLinear InterpolationPoints IntensitiesL(t) = (1− t)P1+ tP2I(t) = (1− t)I1+ tI2L(t) = P1+ t(P2− P1)I(t) = I1+ t(I2− I1)L(t + Δt) = P1+(t + Δt)(P2− P1)I(t + Δt) = I1+(t + Δt)(I2− I1)_______________________________________________________________ΔL = Δt(P2− P1)ΔI = Δt(I2− I1)•Δx = Δt(x2− x1)Inew= Iold+ ΔI•Δy = Δt(y2− y1)•Δz = Δt(z2− z1)Observation: If we know Δt, then we can compute ΔI.Incremental Intensity ComputationAlong a Scan LineP1= (x1, y1,z1)P2= ( x2, y2, z2)(x, y, z)(x + Δx, y + Δy, z + Δz)••••Δx = 1 }I1I2Δx = 1 ⇒ Δt = 1/(x2− x1)ΔI = ( I2− I1)Δt = (I2− I1)/(x2− x1)Next Scan LineP1= (x1, y1,z1)P2= ( x2, y2, z2)(x, y, z)(x + Δx, y + Δy, z + Δz)•••• {Δy =1I2I1Δy =1 ⇒ Δt = 1 /(y2− y1)ΔI = ( I2− I1)Δt = (I2− I1)/(y2− y1)Orientation Dependence and IndependenceProblem• Gouraud (Phong) Shading is Orientation DependentSolution• Subdivide the Polygons into Triangles• Gouraud (Phong) Shading for Triangles is Orientation IndependentNote• Shading Algorithm Depends on the Particular Triangular Subdivision• Shading Algorithm Gives Different Results for Different SubdivisionsCoordinate DependenceWhiteWhiteWhiteWhiteWhiteWhiteBlackBlackAll WhiteGrey NotAll White••••••••Barycentric Coordinates and Coordinate Independence€ (1−t)I1+tI2€ I1€ I2€ I3€ •€ •€ •€ •€ I€ (1− s)I1+ sI3€ •€ •€ I1€ I2€ I3€ •€ •€ •€ •€ I€ β1€ β2€ β3€ I = (1− u) (1− t)I1+tI2( )+u (1− s)I1+ sI3( )€ I =β1I1+β2I2+β3I3 € I = (1− u)(1−t) +u(1− s)( )β11 2 4 4 4 3 4 4 4 I1+ (1− u)t( )β21 2 4 3 4 I2+(us)β3{I3Barycentric Coordinates•€ β1+β2+β3=1•€ P =β1P1+β2P2+β3P3= P1+β2(P2− P1)+β3(P3− P1)•€ β1,β2,β3 uniquePhong ShadingPurpose• To Reduce Mach Bands• To Mimic Curved SurfacesMethod• Linear Interpolation of Normal VectorsStrategy1. Compute unit normals at vertices by averaging the unit normals of the polygons to which the vertex belongs.•€ Nvertex=Npolygonvertex∈Polygon∑Npolygonvertex∈Polygon∑ (Normalized Average)2. Interpolate normals along edges. (Renormalize)3. Interpolate normals along scan lines. (Renormalize)4. Use normals to calculate intensities.Linear InterpolationPoints NormalsL(t) = (1− t)P1+ tP2N(t) = (1− t)N1+ tN2L(t) = P1+ t(P2− P1)N(t) = N1+ t( N2− N1)L(t + Δt) = P1+(t + Δt)(P2− P1)N(t + Δt) = N1+ (t + Δt)(N2− N1)_______________________________________________________________ΔL = Δt(P2− P1)ΔN = Δt( N2− N1)•Δx = Δt(x2− x1)Nnew=Nold+ ΔNNold+ ΔN•Δy = Δt(y2− y1)•Δz = Δt(z2− z1)Observation: If we know Δt, then we can compute ΔN.Incremental Normal ComputationAlong a Scan LineP1= (x1, y1,z1)P2= ( x2, y2, z2)(x, y, z)(x + Δx, y + Δy, z + Δz)••••Δx = 1 }N1N2Δx = 1 ⇒ Δt = 1/(x2− x1)ΔN = (N2− N1)Δt = ( N2− N1)/(x2− x1)Next Scan LineP1= (x1, y1,z1)P2= ( x2, y2, z2)(x, y, z)(x + Δx, y + Δy, z + Δz)•••• {Δy =1N2N1Δy =1 ⇒ Δt = 1 /(y2− y1)ΔN = (N2− N1)Δt = ( N2− N1)/(y2− y1)Clever Implementation -- Diffuse ReflectionDiffuse Reflection€ Idiffuse= Ipkd(L• N) = Ipkd(1−t )(L • N1)+t(L • N2)(1− t)N1+t N2• € (1−t)(L • N1)I11 2 3 4 +t(L • N2)I21 2 4 3 4 -- Similar to Gouraud (Scalars)•€ d2= (1− t )N1+t N2)2= N +ΔN2= (N + ΔN)•(N + ΔN) •€ d2= N • N + 2 N •ΔN + ΔN •ΔN =1+ 2 N •ΔN + ΔN •ΔNSquare Root by Newton’s Method•€ x2− d2= 0•€ xn+1= xn−xn2− d22xnClever Implementation -- Diffuse Reflection (continued)Length of Normal Vectors•€ D(t) = (1− t)N1+t N2)2= (1− t)N1+t N2)( )• (1− t)N1+t N2)( )• € D(t) = (1− t )2(N1• N111 2 3 )+t2(N2• N211 2 4 3 4 )+2t (1− t)(N1• N2)        •€ D(t) = (1−t)2+t2+ 2t (1−t)( N1• N2)( )•€ D(t +Δt ) = (1− t − Δt)2+(t + Δt )2+2(t + Δt)(1−t − Δt)(N1• N2)( )Change in Length•€ ΔD = 2(1−t )Δt + Δt2)+(2t Δt +Δt2)+2( Δt (1− t) −t Δt − Δt2)(N1• N2)( )--€ ΔD = 2Δt 1+ Δt +(1− 2t + Δt)( N1• N2)( )-- € ΔD = 2Δt 1+ Δt +(1+ Δt)(N1• N2)( )constant1 2 4 4 4 4 4 3 4 4 4 4 4 − 2t(N1• N2)linearin t1 2 4 3 4Clever Implementation -- Diffuse Reflection (continued)Change in D• € ΔD = 2Δt 1+ Δt +(1+ Δt)(N1• N2)( )constant1 2 4 4 4 4 4 3 4 4 4 4 4 − 2t(N1• N2)linearin t1 2 4 3 4 --€ E = 2Δt 1+ Δt +(1+Δt)(N1• N2)( )--€ F(t) = 2t(N1• N2)•€ ΔD = E −