Wolfgang Knoll, Reinhard Russ, Cornelia Hasil

(1)

Mesh Resampling

Wolfgang Knoll, Reinhard Russ, Cornelia Hasil

1 Institute of Computer Graphics and Algorithms

Vienna University of Technology

(2)

! Reducing number of faces while trying to keep overall shape,

volume and boundaries

! Oversampled 3D scan data

! Fitting isosurfaces out of volume datasets

Motivation

(3)

Motivation

! Simplification useful to

! make storage

! transmission

! computation

! display more efficient

! Can reduce memory requirements and can speed network

transmission

3 Cornelia Hasil

(4)

Problem Statement

! Transform a given polygonal mesh into another with fewer faces, edges, and vertices:

(5)

Mesh Simplification Approaches

! Two basic concepts

! Vertex Clustering

! Incremental Decimation

! Example

! Incremental decimation with quadric error metric

(6)

Mesh Simplification Approaches

! Vertex Clustering

! Cluster Generation

! Computing a representative

! Fast and effective

! Poor quality

! Uniform 3D grid

Map vertices to cluster cells

! Remove degenerate triangular cells

! Computing a representative:

If P1, P2, ..., Pk are vertices in the same cell, then the representative is P = (P1 + P2 + ... + Pk)/k

(7)

Mesh Simplification Approaches

! Incremental decimation

! General

! Repeat

! pick mesh region

! apply decimation operator

! Until no further reduction possible

(8)

Example: Quadric Error Metrics

! Surface Simplification Using Quadric Error Metrics

! Iterative Pair Contraction with the Quadric Error Metric

! Works on non-manifold geometry

! Supports aggregation

! Can be implemented efficiently

! Produces high quality approximations

(9)

Surface Simplification Using Quadric Error Metrics

! Pair contraction: (v1 , v2 ) → v ̄

! A pair of vertices (v1, v2) are valid for contraction if:

! 1. (v1, v2) is an edge, or

! 2. ||v1 − v2|| < t for some threshold t

! Benefits

! Can join unconnected components

! Can result in much nicer approximations

(10)

Approximating Error With Quadrics

! For each vertex vi store a symmetric 4x4 matrix Qi

! Error (v) at v = [vx vy vz 1]^T is v^TQ_vv

! The matrices Qi are called quadrics, because the level sets of (v) = ε form quadric surfaces (usually ellipsoids)

! For a given contraction(v1 , v2 ) → v ̄ , let Q ̄ = Q1 + Q2

€

Δ

€

Δ

(11)

Performing Contractions

! To perform a contraction(v1 , v2 ) → v ̄ , we must find v ̄

! Simple scheme: select v1, v2 or (v1 + v2)/2 with lowest value for (v ̄ )

! We find minimum v ̄ by solving ∂ /∂x = ∂ /∂y = ∂ /∂z = 0 which is equivalent to

€

Δ

€

Δ

€

Δ

€

Δ

(12)

Algorithm Summary

! Compute initial quadrics for each vertex

! Select all valid pairs

! Compute optimal contraction target for each pair and let its associated error be the cost of the contraction

! Place all pairs in a keyed heap

! Iteratively remove the pair with least cost from the heap, contract the pair, and update the cost of all valid pairs involving this contracted vertex

(13)

Error Metrics in Mesh Simplification

Reinhard Russ

Institute of Computer Graphics and Algorithms Vienna University of Technology

(14)

The purpose of using Error Metrics

! Measurement for the introduced geometric error

! What is the best contraction to perform?

! What is the best position for the remaining vertices?

! Endpoint

! Optimization

(15)

Wolfgang Knoll 15

Metrics

! Simple Heuristics

! Edge length, Dihedral angle, area etc.

! Sample Distance

! Squared distance function

! Cluster distance function

! Curvature

! Valence function

! Quadratic Error Metric

! Feature Sensitive Metric

(16)

Simple Heuristics as Error Metrics

!

Edge length

!

Edge marking function

!

Dihedral angle

!

Surrounding area

(17)

Sample distance as Error Metrics

!

Squared distance function

!

Cluster distance function

17 Reinhard Russ

(18)

Cluster distance function

(19)

Sample distance as Error Metrics

!

Projection to closest point

!

Restricted projection

(20)

Error Metric based on Curvature

!

Curvature

(21)

Error Metric based on Curvature

! Curvature Tensor Field

! How many lines should be traced on the surface?

! Compute local density

! Spacing between two lines of curvature

! Cross section of the surface (normal to the lines)

(22)

Error Metric based on Valence function

!

Valence function

(23)

Quadric Error Metric

! Quadric Error Metric

! Based on point-to-plane distance (instead of point-to-point distance)

! Minimize sum of squared distance to all planes at vertex

(24)

Quadric Error Metric

! Quadric Error Metric

! Construct a quadric Q for every vertex

! Compute error of collapsing

! Compute quadric for new vertex

(25)

Quadric Error Metric Adaptations

! Originally for ECP-based algorithms

! Adaptations for VDP-based and FCP-based algorithms

! Originally for Polygonal Models

! Adaptations for Point Clouds

(26)

Feature Sensitive Metric

! Consider the field of unit normal vectors as a vector- valued image

(27)

Metric Classification

Wolfgang Knoll

Institute of Computer Graphics and Algorithms Vienna University of Technology

(28)

Groupings

! Goal

! Simplification/Minimization

! Quality Improvement

! Topology/Feature Preservation

! Application Area

! Approach

(29)

Simplification/Minimization

! Less vertices, triangles, faces etc. than before

→ Smaller Mesh

! Either:

! Given amount

! Minimal under error boundary

! Combinable with other goals

(30)

Simplification/Minimization

!

Use of metrics depending on the methods.

(31)

Simplification/Minimization

!

Use of metrics depending on the methods.

!

But:

Almost every metric can be used for

Minimization...

(32)

Simplification/Minimization

! Edge/Vertex/Region decimation based on simple Heuristics

! Clustering in regards with Energy minimization

! Etc...

(33)

Quality Improvement

! Improvement in regards with:

! Vertex/Face distribution

! Connectivity

! Triangle shape

! Keeping Quality in regards with:

! Error-Metric

! Topology/Feature Preservation

(34)

Quality Improvement

! Not always quantizable!

! Metrics:

! Curvature based metrics

! QEM, squared distance function and other metrics for minimizing error/energy

(taking the best choice)

! Valence function

(35)

Quality Improvement

! Example: Redistribution

(36)

Topology/Feature Preservation

! Not necessary error minimization

! Goal is to keep topology intact and/or maintain important features

! More triangles at feature-areas

! Rules for Topology preservation

! Used metrics are often curvature-based

(37)

Topology/Feature Preservation

! Example: Feature preservation

(38)

Application Area

! Dependent on:

! Operational area

! Local

! Global

! Geometrical Element

! Vertex

! Edge

! Face

(39)

Application Area

! Local approaches are often based on decimation approaches with simple heuristics

! Global approaches:

! (Iterative) Energy minimization

! Clustering

! → both often use distance metrics

! Feature Sensitive Metric

(40)

Application Area

! Distance metrics (obviously) use mostly the distance between vertices/points

! Clustering additionally can be extended with the Curvature around vertices and in an area/face

(41)

Application Area

! Example: global method

(42)

Approach

! Decimation Approaches

! Energy minimization

! Clustering

! Other Approaches:

Particle Simulation, Retiling etc.

(43)

Comparison Measures

! Used to analyze and compare a method

! Often tightly tied with the method goal

! Usually no direct comparison between proposed methods due to different measures & models

(44)

Comparison Measures

! Quantitative Goal:

! Size: vertex/face number, # Bytes

! Speed: computational performance

! Qualitative Goal:

! Error: max, avg

! Triangle-angle

(45)

Comparison Measures

! Quality improvement often lowers performance

! Size reduction often lowers quality

(46)

Conclusion

! Main goal is minimization!

→ reducing the numbers

! Clustering and Decimation approaches

! Curvature often used for quality improvement

! Performance often goal dependent