QEMDecimateHalfEdge

Overview

Package

Class

Tree

Deprecated

Index

Help

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

org.jcae.mesh.amibe.algos3d
Class QEMDecimateHalfEdge

java.lang.Object
  org.jcae.mesh.amibe.algos3d.AbstractAlgoHalfEdge
      org.jcae.mesh.amibe.algos3d.QEMDecimateHalfEdge

public class QEMDecimateHalfEdge
extends AbstractAlgoHalfEdge
extends AbstractAlgoHalfEdge

Decimates a mesh. This method is based on Michael Garland's work on quadric error metrics.

A plane is fully determined by its normal N and the signed distance d of the frame origin to this plane, or in other words the equation of this plane is tN V + d = 0. The squared distance of a point to this plane is

   D*D = (tN V + d) * (tN V + d)
       = tV (N tN) V + 2d tN V + d*d
       = tV A V + 2 tB V + c

The quadric Q=(A,B,c)=(N tN, dN, d*d) is thus naturally defined. Addition of these quadrics have a simple form: Q1(V)+Q2(V)=(Q1+Q2)(V) with Q1+Q2=(A1+A2, B1+B2, c1+c2) To compute the squared distance of a point to a set of planes, we can then compute this quadric for each plane and sum each element of these quadrics.

When an edge (V1,V2) is contracted into V3, Q1(V3)+Q2(V3) represents the deviation to the set of planes at V1 and V2. The cost of this contraction is thus defined as Q1(V3)+Q2(V3). We want to minimize this error. It can be shown that if A is non singular, the optimal placement is for V3=-inv(A) B.

The algorithm is straightforward:

Quadrics are computed for all vertices.
For each edge, compute the optimal placement and its cost.
Loop on edges: starting with the lowest cost, each edge is processed until its cost is greater than the desired tolerance, and costs of adjacent edges are updated.

The real implementation is slightly modified:

Some checks must be performed to make sure that edge contraction does not modify the topology of the mesh.
Optimal placement strategy can be chosen at run time among several choices.
Boundary edges have to be preserved, otherwise they will shrink. Virtual planes are added perpendicular to triangles at boundaries so that vertices can be decimated along those edges, but edges are stuck on their boundary. Garland's thesis dissertation contains all informations about this process.
Weights are added to compute quadrics, as described in Garland's dissertation.
Edges are swapped after being contracted to improve triangle quality, as described by Frey in About Surface Remeshing.

Field Summary

Fields inherited from class org.jcae.mesh.amibe.algos3d.AbstractAlgoHalfEdge
`maxEdgeLength, mesh, noSwapAfterProcessing, notInTree, notProcessed, nrFinal, nrTriangles, processed, swapped, tolerance, tree`

Constructor Summary
`QEMDecimateHalfEdge(Mesh m, java.util.Map<java.lang.String,java.lang.String> options)` Creates a `QEMDecimateHalfEdge` instance.

Method Summary
`protected void`	`appendDumpState(java.io.ObjectOutputStream out)`
`protected void`	`appendRestoreState(java.io.ObjectInputStream q)`
`boolean`	`canProcessEdge(HalfEdge current)`
`double`	`cost(HalfEdge e)`
`static void`	`main(java.lang.String[] args)`
`protected void`	`postComputeTree()`
`void`	`postProcessAllHalfEdges()`
`void`	`preProcessAllHalfEdges()`
`void`	`preProcessEdge()`
`HalfEdge`	`processEdge(HalfEdge current, double costCurrent)`
`java.util.logging.Logger`	`thisLogger()`

Methods inherited from class org.jcae.mesh.amibe.algos3d.AbstractAlgoHalfEdge
`addToTree, compute, countInnerTriangles, dumpState, removeFromTree, restoreState, setProgressBarStatus, uniqueOrientation`

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Constructor Detail