Overview
Quadric error simplification assigns each vertex an error metric from nearby planes and uses a priority queue to collapse low-cost edges.
ExtendedSource checked
Quadric Error Mesh Simplification
Simplifies a mesh by collapsing edges that add the least quadric error.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Geometry
- Difficulty
- Advanced
- Family
- Mesh Simplification
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 5
- Code example
- Ready
- Visualization
- Ready
Core Concepts
edge collapsequadric errorpriority queuemesh decimation
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(E log E)
Average
O(E log E)
Worst
O(E log E)
Space
O(V + E)
When to Use
- Use when collision and intersection tests needs edge collapse.
- Use when the input matches the assumptions behind mesh Simplification.
When Not to Use
- Avoid when floating-point robustness is critical and no tolerance strategy is defined.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Simplifies a mesh by collapsing edges that add the least quadric error
- Uses edge collapse and quadric error to guide the work.
- Produces geometric relation, simplified shape, or constructed geometry.
Use Cases
- Collision and intersection tests
- Shape analysis
- Geometry processing
Inputs
- Points, segments, polygons, or meshes
- Query shape or tolerance
Outputs
- Geometric relation, simplified shape, or constructed geometry
Key Formulas (1)
Quadric error
error(v) = vT Q v
error(v) = v^T Q vScores how far a candidate vertex is from accumulated local planes.
Pseudocode
- 1.Prepare the inputs and state needed for Quadric Error Mesh Simplification.
- 2.Apply the edge collapse step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return geometric relation, simplified shape, or constructed geometry.
Canonical Example
- Input
- Quadric Error Mesh Simplification input with a small representative case
- Output
- Geometric relation, simplified shape, or constructed geometry
- Explanation
- Quadric Error Mesh Simplification applies edge collapse to produce geometric relation, simplified shape, or constructed geometry.
Implementation Notes
- Use robust orientation and tolerance checks for boundary cases.
- Keep the edge collapse step separate enough to test independently.
Common Pitfalls
- Degenerate cases such as collinear points or shared edges often need explicit handling.
- Forgetting to check edge cases can make Quadric Error Mesh Simplification look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Spatial Primitive & Sweep-Line CanvasDraw the input shapes, active tests, and generated geometric result.
Step 1 of 4: Prepare the inputs and state needed for Quadric Error Mesh Simplification.
geometry-mechanismNotes
Quadric Error Mesh Simplification should be used with the assumptions and tradeoffs of mesh Simplification in mind.
Sources (1)
What each reference supports for this entry.
Garland-Heckbert QEM
PaperOriginal reference for mesh simplification using quadric error metrics.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toCatmull-Clark Subdivision
Simplification reduces mesh complexity while subdivision increases it.
Conceptual neighborRamer-Douglas-Peucker
Both reduce geometric complexity using an error criterion.
Related Algorithms
Tags
Computational GeometryMesh ProcessingCurve SimplificationGeometry