Geometry Simplification in Engineering and Science

Washington University in St. Louis, School of Engineering and Applied Science CSE 554 Lecture 7: Simplification Fall 2016 CSE554 Simplification Slide 1

Washington University in St. Louis, School of Engineering and Applied Science 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

Washington University in St. Louis, School of Engineering and Applied Science Why do we care? Polygon count is a major performance factor Animation (deformation), rendering, simulation, interaction ratatouille_remy_01 Space shuttle aerodynamics (NASA) Character animation (Pixar) Ray tracing rendering (POV-Ray) CSE554 Simplification Slide 3

Washington University in St. Louis, School of Engineering and Applied Science Simplification (2D) Replacing a 2D polygon by another with fewer vertices Preserves the shape and topology of the input polygon CSE554 Simplification Slide 4

Washington University in St. Louis, School of Engineering and Applied Science Simplification (2D) An optimization problem: Given an input polygon and a target vertex count N Find the coordinates of N vertices that minimize the distance from the new polygon formed by these vertices and the input polygon 200 vertices 50 vertices CSE554 Simplification Slide 5

Washington University in St. Louis, School of Engineering and Applied Science Simplification (2D) A greedy heuristic: Iteratively merges two neighboring vertices into one, until the target vertex count is reached Each merging minimizes the error to the original polygon 200 vertices 50 vertices CSE554 Simplification Slide 6

Washington University in St. Louis, School of Engineering and Applied Science Simplification (2D) If I want to replace two vertices with one, where should it be? After replacement: CSE554 Simplification Slide 7

Washington University in St. Louis, School of Engineering and Applied Science 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 8

Washington University in St. Louis, School of Engineering and Applied Science Points and Vectors Same representation Y p 1, 2 p 2, 2 2 x, y or x, y, z 1, 2 1, 2 v v x Different meaning: 1 2 Point: a fixed location (relative to {0,0} or {0,0,0}) Vector: a direction and magnitude No location (any location is possible) CSE554 Simplification Slide 9

Washington University in St. Louis, School of Engineering and Applied Science Point Operations Subtraction p2 Result is a vector p2 p1 v p2x p1x, p2y p1y v Addition with a vector Result is a point p1 p1 v p2 p1x vx, p1y vy Can points add? CSE554 Simplification Slide 10

Washington University in St. Louis, School of Engineering and Applied Science Adding Points Affine combinations Weighted addition of points where all weights sum to 1 p2 v2 n n p1 wipi p, where wi 1 i 1 i 1 Result is another point v3 v4 p Same as adding scaled vectors to a point p3 n n n p4 wipi wi pi p1 wip1 i 1 i 1 i 1 n wivi p1 i 1 CSE554 Simplification Slide 11

Washington University in St. Louis, School of Engineering and Applied Science Adding Points Affine combinations: examples Mid-point of two points p2 p p1 p2 p1 p 2 p2 Linear interpolation of two points p p1 1 p 1 p1 p2 p2 Centroid of multiple points p1 n pi n p p i 1 p3 p4 CSE554 Simplification Slide 12

Washington University in St. Louis, School of Engineering and Applied Science Vector Operations Addition/Subtraction v2 Result is a vector v1 v1 v2 v1x v2x, v1y v2y v2 v2 v1 Scaling by a scalar v1 v1 v2 Result is a vector s v s vx, s vy Magnitude s v v Result is a scalar vx2 vy2 v A unit vector: v 1 v To make a unit vector (normalization): v CSE554 Simplification Slide 13

Washington University in St. Louis, School of Engineering and Applied Science More Vector Operations Dot product (in both 2D and 3D) Result is a scalar v1 v2 v1 v2 Cos v1 In coordinates (simple!) v2 2D: v1 v2 v1x v2x v1y v2y 3D: v1 v2 v1x v2x v1y v2y v1z v2z Matrix product between a row and a column vector CSE554 Simplification Slide 14

Washington University in St. Louis, School of Engineering and Applied Science More Vector Operations Uses of dot products Angle between vectors: v1 v2 ArcCos v1 v1 v2 Orthogonal test: v1 v2 0 v2 Projected length of onto : v2 v1 v1 v2 v1 h v2 h v2 CSE554 Simplification Slide 15

Washington University in St. Louis, School of Engineering and Applied Science 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 Sin In coordinates: v2 v1 v1 v2 v2 v1yv2z v1zv2y, v1zv2x v1xv2z, v1xv2y v1yv2x v1 CSE554 Simplification Slide 16

Washington University in St. Louis, School of Engineering and Applied Science More Vector Operations Uses of cross products Getting the normal vector of the plane E.g., the normal of a triangle formed by v1v2 v2 Computing area of the triangle formed by v1v2 v1 v1 v2 v2 Area 2 Testing if vectors are parallel: v1 v2 0 v1 CSE554 Simplification Slide 17

Washington University in St. Louis, School of Engineering and Applied Science Properties Dot Product Cross Product v v1 v1 v2 v v v1 v1 v2 v Distributive? v v2 v v2 Commutative? v1 v2 v2 v1 v1 v2 v2 v1 (Sign change!) Associative? v1 v2 v3 v1 v2 v3 v1 v2 v3 CSE554 Simplification Slide 18

Washington University in St. Louis, School of Engineering and Applied Science 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 19

Washington University in St. Louis, School of Engineering and Applied Science Simplification (2D) Closed point to multiple lines Sum of squared distances from p to all lines (Quadratic Error Metric, QEM) Input lines: q1, n1 , ..., qm, nm m 2 QEM p p qi ni 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 0 p CSE554 Simplification Slide 20

Washington University in St. Louis, School of Engineering and Applied Science Simplification (2D) m Minimizing QEM 2 QEM p p qi ni i 1 Writing QEM in matrix form px py p Row vector Matrix transpose pT [Eq. 1] QEM p p a 2 p b c Matrix (dot) product m m m nixnix nixniy nix ni qi m i 1 i 1 i 1 2 c ni qi a b m m m nixniy niyniy niy ni qi i 1 i 1 i 1 i 1 2x2 matrix 1x2 column vector Scalar CSE554 Simplification Slide 21

Washington University in St. Louis, School of Engineering and Applied Science Simplification (2D) Minimizing QEM pT QEM p p a 2 p b c Solving the zero-derivative equation: QEM p pT 2 a 2 b 0 p pT [Eq. 2] a b m m m nixnix nixniy nix ni qi px py i 1 i 1 i 1 m m m nixniy niyniy niy ni qi i 1 i 1 i 1 A linear system with 2 equations and 2 unknowns (px,py) Using Gaussian elimination, or matrix inversion: pT a1b CSE554 Simplification Slide 22

Washington University in St. Louis, School of Engineering and Applied Science Simplification (2D) What vertices to merge first? Pick the ones whose replacement vertex introduces least QEM error (usually lies in flat areas) CSE554 Simplification Slide 23

Washington University in St. Louis, School of Engineering and Applied Science 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 24

Washington University in St. Louis, School of Engineering and Applied Science 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 25

Washington University in St. Louis, School of Engineering and Applied Science 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 26

Washington University in St. Louis, School of Engineering and Applied Science 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 27

Washington University in St. Louis, School of Engineering and Applied Science 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 28

Washington University in St. Louis, School of Engineering and Applied Science 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 pT [Eq. 1] QEM p p a 2 p b c CSE554 Simplification Slide 29

Washington University in St. Louis, School of Engineering and Applied Science Simplification (2D) a, b, c, p, QEM p Step 2: Collapses and updates a2, b2, c2, p2, QEM p2 a1, b1, c1, p1, QEM p1 Remove the edge and its vertices 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 a b c p2, QEM p2 p2, QEM p2 a2, b2, c2, c2, a b c a2, b2, a b c a1, b1, a b c p1, QEM p1 p1, QEM p1 a1, b1, c1, c1, The coefficients are additive! p Re-compute its minimizer and QEM p1, p2 : new minimizer locations computed from the updated coefficients CSE554 Simplification Slide 30

Washington University in St. Louis, School of Engineering and Applied Science 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 31

Washington University in St. Louis, School of Engineering and Applied Science 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 p above or below the plane We use its square q CSE554 Simplification Slide 32

Washington University in St. Louis, School of Engineering and Applied Science Simplification (3D) Closest point to multiple planes m m m nixnix nixniy nixniz i 1 i 1 i 1 Input planes: m m m niynix niyniy niyniz q1, n1 , ..., qm, nm a i 1 i 1 i 1 m m m niznix nizniy nizniz QEM (same as in 2D) i 1 i 1 i 1 3x3 matrix m m nix ni qi 2 QEM p p qi ni i 1 m niy ni qi b i 1 1x3 column vector i 1 m niz ni qi In matrix form: px py pz p i 1 pT m QEM p p a 2 p b c 2 c ni qi Scalar i 1 pT Find p that minimizes QEM: a b A linear system with 3 equations and 3 unknowns (px,py,pz) CSE554 Simplification Slide 33

Washington University in St. Louis, School of Engineering and Applied Science 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 34

Washington University in St. Louis, School of Engineering and Applied Science Simplification (3D) Degenerate triangles after collapse Step 2: Collapsing an edge Remove the edge with least QEM Re-connect neighbor triangles and edges to the minimizer of the removed edge Duplicate edges after collapse Remove degenerate triangles Collapse Remove duplicate edges For each re-connected edge: Increment its coefficients by that of the removed edge Re-compute its minimizer and QEM CSE554 Simplification Slide 35

Washington University in St. Louis, School of Engineering and Applied Science Simplification (3D) Example: 5600 vertices 500 vertices CSE554 Simplification Slide 36

Washington University in St. Louis, School of Engineering and Applied Science 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 37