Report

CSE 554 Lecture 7: Simplification Fall 2014 CSE554 Simplification Slide 1 Geometry Processing • Fairing (smoothing) – Relocating vertices to achieve a smoother appearance – Method: centroid averaging • Simplification – Reducing vertex count • Deformation – Relocating vertices guided by user interaction or to fit onto a target CSE554 Simplification Slide 2 Simplification (2D) • Representing the shape with fewer vertices (and edges) 200 vertices CSE554 50 vertices Simplification Slide 3 Simplification (2D) • If I want to replace two vertices with one, where should it be? CSE554 Simplification Slide 4 Simplification (2D) • If I want to replace two vertices with one, where should it be? – Shortest distances to the supporting lines of involved edges After replacement: CSE554 Simplification Slide 5 Points and Vectors • Same representation, but different meanings and operations Y p 1, 2 p 2, 2 1, v – Points can add with vectors – Points can add with points, only using v 1, 2 – Vectors can add, scale 2 2 1 2 x affine combination n n wi pi i 1 CSE554 p, where wi 1 i 1 Simplification Slide 6 More Vector Operations • Dot product (in both 2D and 3D) – Result is a scalar v1 v2 v1 v2 Cos v1 – In coordinates (simple!) • 2D: v1 v2 v1x • 3D: v1 v2 v1x v2x v2x v1y v1y v2 v2y v2y v1z v2z • Matrix product between a row and a column vector CSE554 Simplification Slide 7 More Vector Operations • Uses of dot products – Angle between vectors: ArcCos v1 v1 • Orthogonal: v1 – Projected length of h v1 v2 v2 v2 v1 0 v2 v1 onto v2 : v2 v1 v2 h CSE554 Simplification v2 Slide 8 More Vector Operations • Cross product (only in 3D) – Result is another 3D vector • Direction: Normal to the plane where both vectors lie (right-hand rule) • Magnitude: v1 v2 v1 v2 v1 v1 v2 – In coordinates: v2 v1 y v2 z Sin v1 z v 2 y , v 1 z v2 x v 1 x v 2 z , v1 x v 2 y v2 v1 y v2 x v1 CSE554 Simplification Slide 9 More Vector Operations • Uses of cross products – Getting the normal vector of the plane Area v1 v1 v2 v1 – Computing area of the triangle formed by v2 • E.g., the normal of a triangle formed by v1 v2 v2 v2 2 • Testing if vectors are parallel: v1 v2 0 v1 CSE554 Simplification Slide 10 Properties Dot Product Distributive? v v Commutative? Associative? CSE554 v1 v1 v1 v1 v2 v v2 v2 v2 v2 v1 v3 Simplification Cross Product v v v1 v1 v1 v2 v v2 v2 v2 v1 (Sign change!) v1 v2 v 3 v1 v2 v3 Slide 11 Simplification (2D) • Distance to a line – Line represented as a point q on the line, and a perpendicular unit vector (the normal) n • To get n: take a vector {x,y} along the line, n is {-y,x} followed by normalization – Distance from any point p to the line: p q n • Projection of vector (p-q) onto n – This distance has a sign p n • “Above” or “under” of the line • We will use the distance squared q CSE554 Simplification Slide 12 Simplification (2D) • Closed point to multiple lines – Sum of squared distances from p to all lines (Quadratic Error Metric, QEM) • Input lines: q1, n1 , ..., q m , n m m QEM p p qi ni 2 i 1 – We want to find the p with the minimum QEM • Since QEM is a convex quadratic function of p, the minimizing p is where the derivative of QEM is zero, which is a linear equation QEM p p CSE554 0 Simplification Slide 13 Simplification (2D) m • Minimizing QEM QEM p px py Row vector p a pT QEM p qi ni 2 i 1 – Writing QEM in matrix form p p Matrix transpose 2p b c [Eq. 1] Matrix (dot) product m a i 1 m i 1 n i x ni x n i x ni y m i 1 m i 1 2x2 matrix CSE554 m ni x ni y ni y ni y b i 1 m i 1 nix ni niy ni qi qi 1x2 column vector Simplification m c ni qi 2 i 1 Scalar Slide 14 Simplification (2D) • Minimizing QEM QEM p p a pT 2p b c – Solving the zero-derivative equation: QEM p 2 a pT p m i 1 m i 1 n i x ni x n i x ni y m i 1 m i 1 nix ni y niy ni y 2b 0 a pT b [Eq. 2] m px py i 1 m i 1 ni x n i qi ni y n i qi – A linear system with 2 equations and 2 unknowns (px,py) • Using Gaussian elimination, or matrix inversion: pT CSE554 Simplification a 1 b Slide 15 Simplification (2D) • What vertices to merge first? – Pick the ones that lie on “flat” regions, or whose replacing vertex introduces least QEM error. CSE554 Simplification Slide 16 Simplification (2D) • The algorithm – Step 1: For each edge, compute the best vertex location to replace that edge, and the QEM at that location. • Store that location (called minimizer) and its QEM with the edge. CSE554 Simplification Slide 17 Simplification (2D) • The algorithm – Step 1: For each edge, compute the best vertex location to replace that edge, and the QEM at that location. • Store that location (called minimizer) and its QEM with the edge. – Step 2: Pick the edge with the lowest QEM and collapse it to its minimizer. • Update the minimizers and QEMs of the re-connected edges. CSE554 Simplification Slide 18 Simplification (2D) • The algorithm – Step 1: For each edge, compute the best vertex location to replace that edge, and the QEM at that location. • Store that location (called minimizer) and its QEM with the edge. – Step 2: Pick the edge with the lowest QEM and collapse it to its minimizer. • Update the minimizers and QEMs of the re-connected edges. CSE554 Simplification Slide 19 Simplification (2D) • The algorithm – Step 1: For each edge, compute the best vertex location to replace that edge, and the QEM at that location. • Store that location (called minimizer) and its QEM with the edge. – Step 2: Pick the edge with the lowest QEM and collapse it to its minimizer. • Update the minimizers and QEMs of the re-connected edges. – Step 3: Repeat step 2, until a desired number of vertices is left. CSE554 Simplification Slide 20 Simplification (2D) • The algorithm – Step 1: For each edge, compute the best vertex location to replace that edge, and the QEM at that location. • Store that location (called minimizer) and its QEM with the edge. – Step 2: Pick the edge with the lowest QEM and collapse it to its minimizer. • Update the minimizers and QEMs of the re-connected edges. – Step 3: Repeat step 2, until a desired number of vertices is left. CSE554 Simplification Slide 21 Simplification (2D) • Step 1: Computing minimizer and QEM on an edge – Consider supporting lines of this edge and adjacent edges – Compute and store at the edge: • The minimizing location p (Eq. 2) • QEM (substitute p into Eq. 1) p – Used for edge selection in Step 2 • QEM coefficients (a, b, c) – Used for fast update in Step 2 Stored at the edge: a, b, c, p, QEM p QEM p CSE554 p a pT 2p b Simplification c [Eq. 1] Slide 22 Simplification (2D) a, b, c, p, QEM p • Step 2: Collapsing an edge – Remove the edge and its vertices a1 , b1 , c1 , p1 , QEM p1 a2 , b2 , c2 , p2 , QEM p2 – Re-connect two neighbor edges to the minimizer of the removed edge – For each re-connected edge: Collapse • Increment its coefficients by that of the removed edge – The coefficients are additive! • Re-compute its minimizer and QEM aa aa11,, bb bb11,, cc cc11,, QEM pp11 pp11,, QEM p a a22, b b22, c c22, p22, QEM p22 p1 , p2 : new minimizer locations computed from the updated coefficients CSE554 Simplification Slide 23 Simplification (3D) • The algorithm is similar to 2D – Replace two edge-adjacent vertices by one vertex • Placing new vertices closest to supporting planes of adjacent triangles – Prioritize collapses based on QEM CSE554 Simplification Slide 24 Simplification (3D) • Distance to a plane (similar to the line case) – Plane represented as a point q on the plane, and a unit normal vector n • For a triangle: n is the cross-product of two edge vectors – Distance from any point p to the plane: p q n • Projection of vector (p-q) onto n – This distance has a sign n • “above” or “below” the plane p • We use its square q CSE554 Simplification Slide 25 Simplification (3D) • Closest point to multiple planes – Input planes: m q1, n1 , ..., q m , n m a – QEM (same as in 2D) i 1 m i 1 m p qi ni 2 • In matrix form: p p a pT i 1 m b i 1 QEM p niy nix i 1 mn m QEM p nix nix i 1 nix i 1 m nix niy niy niy i 1 mn i 1 iz niy m i 1 m n ix ni z n iy ni z i 1 mn i 1 iz niz nix ni qi 3x3 matrix niy ni qi 1x3 column vector ni qi i 1 mn px py pz 2p b iz m iz m c c ni qi 2 Scalar i 1 – Find p that minimizes QEM: a pT b • A linear system with 3 equations and 3 unknowns (px,py,pz) CSE554 Simplification Slide 26 Simplification (3D) • Step 1: Computing minimizer and QEM on an edge – Consider supporting planes of all triangles adjacent to the edge – Compute and store at the edge: • The minimizing location p • QEM[p] • QEM coefficients (a, b, c) p The supporting planes for all shaded triangles should be considered when computing the minimizer of the middle edge. CSE554 Simplification Slide 27 Simplification (3D) • Step 2: Collapsing an edge Degenerate triangles after collapse – Remove the edge with least QEM – Re-connect neighbor triangles and edges to the minimizer of the removed edge • Remove “degenerate” triangles Duplicate edges after collapse • Remove “duplicate” edges Collapse – For each re-connected edge: • Increment its coefficients by that of the removed edge • Re-compute its minimizer and QEM CSE554 Simplification Slide 28 Simplification (3D) • Example: 5600 vertices CSE554 500 vertices Simplification Slide 29 Further Readings • Fairing: – “A signal processing approach to fair surface design”, by G. Taubin (1995) • No-shrinking centroid-averaging • Google citations > 1000 • Simplification: – “Surface simplification using quadric error metrics”, by M. Garland and P. Heckbert (1997) • Edge-collapse simplification • Google citations > 2000 CSE554 Simplification Slide 30