程序代写代做代考 algorithm Visible Surfaces Determination

Visible Surfaces Determination

􏸭 Goal
􏸮visibility from a view point
HLHSR
􏸭 Assumptions
􏸮objects are made of polygonal patches 􏸮all patches are opaque
Computer Graphics

OpenGL
􏸭 Very simple, you need to do only two things 􏸮 Prepare buffer
􏸯 glutInitDisplay(GLUT_DEPTH | …); 􏸰 distance to the view point is recorded 􏸯 glClear(GL_DEPTH_BUFFER_BIT);
􏸰 clear to the far clipping plan distance (1.0) 􏸮􏸮 Enable depth comparison
􏸯 glEnable(GL_DEPTH_TEST);
􏸮 Tell OpenGL how to do the depth comparison
􏸯 glDepthFunc(); default is GL_LESS (in front of the far clipping plane)
􏸯 Visible z values are negative, but distance (depth) is positive
Computer Graphics

Depth comparison
􏸭 at 3D
􏸭 before projection
􏸭 after modeling, normalization, etc. transform
􏸭Parallel
􏸭Perspective YY
ZZ XX
if(X==X&&Y==Y) 1212
XXYY if(1== 2&&1==2)
compare Z1 and Z2
Z1 Z2 Z1 Z2 compare Z1 and Z2
Computer Graphics

General Approaches
􏸭 Image Space
for (each pixel in the image) {
determine the object closest to the viewer draw the object at that particular pixel }
􏸭􏸭 Object Space
for (each object in the scene) {
􏸭 Hybrid
determine which parts of the object whose views are unobstructed
draw those parts of the object }
Computer Graphics

Useful techniques
􏸭 Coherence
􏸮 parts of an object or an environment exhibit local
similarity
􏸭 Bounding volumes
􏸮 simplifies intersection tests 􏸭􏸭 Hierarchy
􏸮 e.g., hierarchical bounding volumes 􏸭 Spatial partitioning
􏸮 exploit spatial coherency 􏸭 Back face culling
􏸮 e.g. convex objects viewing from outside Computer Graphics

􏸭 Image space
Scan-line Algorithm
􏸭 Exploit scan-line coherency
􏸭 Image is generated one scan line at a time
􏸮keep all active polygons (edges) 􏸮􏸮determine their Z-ordering
􏸮ordering can change when cross edges
Computer Graphics

􏸭 Edge table
􏸭Polygon table
– sorted by smallbest y into buckets (scan lines) – x coor at smallest y
– y coor at largest y
– x increment
– coefficients of plane equation – shading and color info
– IN/OUT flag
– polygon ID
􏸭Active Edge table
– At each scan line
– delete edges no long intersect current scan – update x coordinates of active edges
– add new edges from the current bucket
– sort x coordinates of all active edges
Computer Graphics

Y
􏸭 Scan in none – background 􏸭 Scan in one – paint
􏸭 Scan in multiple – order test
Computer Graphics
X

ZZ
􏸭 Non-intersecting polygons – order change at edges
􏸭 Intersecting polygons
– order change at edges & intersections
– re-compute when scan leaving occluding polygons
– splitting polygons may be necessary
Don’t care
XX
Computer Graphics

Initialization
} }
ZB<- most distant Z; IB <- background color; for each polygon { for each pixel in polygon { compute Z(x,y); if Z(x,y) is closer then ZB(x,y) { ZB(x,y) = Z(x,y); IB(x,y) = polygon color; } Z Buffer 􏸭 Simplest (and most widely used) Object space 􏸭 Amenable to hardware implementation Computer Graphics 􏸭 Hybrid Initialization Depth-Sort (List-Priority) sort polygons in order of decreasing distance Resolve Ambiguity Pick the polygon (P) at the front (most distant) of the list and for all polygon (Q) whose Z-extent overlap that of P’s 1. Do the polygons’ x extent not overlap? 2. Do the polygons’ y extent not overlap? 3. Is P entirely on the opposite side of Q’s plane from the viewpoint? 4. Is Q entirely on the same side of P’s plane as the viewpoint? 5. Do the projections of the polygons not overlap? Switch P and Q if all above fail Scan Conversion Computer Graphics ZZ P Q Q XX ZZ R PP QQ XX Computer Graphics P BSP-Tree (Object Space) 􏸭 Based on a simple observation 􏸮 if the space is divided in half, then polygons on the side that does not contain the observer cannot obscure polygons on the same side as the observer Computer Graphics BSP Tree (cont.) 􏸭 Record the spatial adjacency info in a tree 􏸮 choose a scene polygon and use its plane to partition the space into two halves 􏸮 scene polygons are put in one half 􏸮 split polygons that straddle the partition plane 􏸮􏸮 recursively apply the algorithm until no more polygons can be used 􏸮 good for 􏸯 static scene structures 􏸯moving observer locations 􏸯 e.g. fly-through, walk-through Computer Graphics 2 1 3 3 1 5 5a 5b 3 24 5 4 Example of BSP Tree 5a 4 1 5b Computer Graphics 2 IN OUT IN OUT 1 IN OUT IN OUT 2 4 2 5 4 􏸭 Iterate through the list of vertices 􏸭 Output vertices based on IN/OUT relations Computer Graphics Original 3 3 1 6 􏸭 An in-order traversal Rendering 􏸭 At each node 􏸮 traverse the subtree not containing the observer 􏸮render polygons at the node 􏸮traverse the subtree containing the observer Computer Graphics Surrounding Area Sub-division 􏸭 Divide-and-Conquer 􏸭 Divide an image region until it is easy to decide which polygon or polygons are visible Intersecting Contained Disjoint Computer Graphics Area Sub-division 􏸭 Disjoint 􏸮 render background color 􏸭 One intersecting or contained 􏸮 render background then polygon 􏸭 One surrounding 􏸮 render polygon color 􏸭 More than one surrounding, intersecting, contained 􏸮 if the surrounding polygon is in front 􏸭 Otherwise, recursive subdivision Computer Graphics } } Visible Surface Ray Tracing for (each scan line) { for (each pixel in scan line) { compute ray direction from COP (eye) to pixel for (each object in scene) { if (intersection and closest so far) { record object and intersection point } set pixels color to that at closet object intersection } Computer Graphics Compute Intersection 􏸭 A (low-order) implicit representation (f(x,y,z) =0) can be useful 􏸭 >0 (outside), =0 (surface), <0 (inside) 􏸭 Two examples 􏸮Spheres (implicit representation) 􏸮Polygons (parametric representation) Computer Graphics sphere:(X−a)2 +(Y−b)2 +(Z−c)2 −r2 =0 X = Xo +t∆X r a y :  Y = Y o + t ∆ Y  Z = Z o + t ∆ Z X2 −2aX+a2 +Y2 −2bY+b2 +Z2 −2cZ+c2 −r2 =0 (Xo +t∆X)2 −2a(Xo +t∆X)+a2 + (Yo +t∆Y)2 −2b(Yo +t∆Y)+b2 + (Zo +t∆Z)2 −2c(Zo +t∆Z)+c2 −r2 =0 (∆X2 +∆Y2 +∆Z2)t2 + 2{∆X(Xo −a)+∆Y(Yo −b)+∆Z(Zo −c)}t+ (Xo −a)2 +(Yo −b)2 +(Zo −c)2 −r2 =0 Computer Graphics (∆X2 +∆Y2 +∆Z2)t2 + 2{∆X(X −a)+∆Y(Y −b)+∆Z(Z −c)}t+ ooo (X −a)2 +(Y −b)2 +(Z −c)2 −r2 =0 ooo At2 +Bt+C=0 ∆=B2 −4AC ∆ > 0 t∆ = 0  ∆ < 0 insersecting grazing n o n i n s e r s e c t i n g Computer Graphics plane : aX + bY + cZ + d = 0 X = Xo +t∆X r a y :  Y = Y o + t ∆ Y  Z = Z o + t ∆ Z a(Xo +t∆X)+b(Yo +t∆Y)+c(Zo +t∆Z)+d =0 t=−aXo +bYo +cZo +d a∆X + b∆Y + c∆Z 􏸭 There will be a reasonable t value, unless the denominator is zero (the line and the plane are parallel) 􏸭 But is the intersection point actually inside the polygon? Computer Graphics 􏸭 Point-in-polygon test (point must be on the inside relative to all polygon edges) 􏸭 Can be done in 2D Y X Computer Graphics Z Avoid intersection computation 􏸭 Bounding volume 􏸭 Object hierarchy 􏸭 Spatial partitioning Computer Graphics Slab : aX + bY + cZ + d = 0 X = Xo +t∆X A:perrayperslabset B:perrayperslabset D: per slab ray:Y =Yo +t∆Y  Z = Z o + t ∆ Z Bounding Volume t=−aXo +bYo +cZo +d = A+D a∆X +b∆Y +c∆Z B Computer Graphics Bounding Volume (cont.) 􏸭 All the maximum (circle) intersections must be after all the minimum (square) intersections Computer Graphics Hierarchical Bounding Volume Computer Graphics Spatial Partitioning 􏸭 Ray can be advanced from cell to cell 􏸭 Only those objects in the cells lying on the path of the ray need be considered 􏸭 First intersection terminates the search Computer Graphics