Class QEMDecimateHalfEdge

  extended by org.jcae.mesh.amibe.algos3d.AbstractAlgoHalfEdge
      extended by org.jcae.mesh.amibe.algos3d.QEMDecimateHalfEdge

public class QEMDecimateHalfEdge
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:

  1. Quadrics are computed for all vertices.
  2. For each edge, compute the optimal placement and its cost.
  3. 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:

  1. Some checks must be performed to make sure that edge contraction does not modify the topology of the mesh.
  2. Optimal placement strategy can be chosen at run time among several choices.
  3. 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.
  4. Weights are added to compute quadrics, as described in Garland's dissertation.
  5. 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( out)
protected  void appendRestoreState( 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


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

m - the Mesh instance to refine.
options - map containing key-value pairs to modify algorithm behaviour. Valid keys are size, placement and maxtriangles.
Method Detail


public java.util.logging.Logger thisLogger()
Specified by:
thisLogger in class AbstractAlgoHalfEdge


public void preProcessAllHalfEdges()
Specified by:
preProcessAllHalfEdges in class AbstractAlgoHalfEdge


protected void postComputeTree()
postComputeTree in class AbstractAlgoHalfEdge


protected void appendDumpState( out)
appendDumpState in class AbstractAlgoHalfEdge


protected void appendRestoreState( q)
appendRestoreState in class AbstractAlgoHalfEdge


public double cost(HalfEdge e)
Specified by:
cost in class AbstractAlgoHalfEdge


public boolean canProcessEdge(HalfEdge current)
Specified by:
canProcessEdge in class AbstractAlgoHalfEdge


public void preProcessEdge()
preProcessEdge in class AbstractAlgoHalfEdge


public HalfEdge processEdge(HalfEdge current,
                            double costCurrent)
Specified by:
processEdge in class AbstractAlgoHalfEdge


public void postProcessAllHalfEdges()
Specified by:
postProcessAllHalfEdges in class AbstractAlgoHalfEdge


public static void main(java.lang.String[] args)
args - xmlDir, -t tolerance | -n triangle, brepFile, output