NewtonCritical Class Reference

#include <NewtonCritical.h>

Inheritance diagram for NewtonCritical:

[legend]Collaboration diagram for NewtonCritical:

[legend]List of all members.

---

Detailed Description

NewtonCritical is a class for finding critical points of an Implicit.

The class basically redefines the NewtonEquation() method to set up the system of equations for A*(Y-Xc) = b. See Newton.h for more information on the basics of how it goes about first subdiving space and then calling Newton's Method to find the roots.

The equation in NewtonEquation() comes from the SIGGRAPH 97 paper "Guaranteeing the Polygonization of an Implicit Surface Polygonization for Interactive Modeling". In that paper, we try to find the critical points of an implicit surface. A critical point is where the gradient of the implicit equation goes to zero. Skipping the details, we can do this by first using a simple subdivision technique to eliminate most of the empty space (since there really aren't that many critical points for a given implicit). Once we have a small interval to search, we can switch to Newton's method to find the critical points a little quicker.

In the context of the paper, we have the following. V(X) is the interval Hessian matrix of the implicit surface. Vc = midpts(V(X)) is a scalar matrix consisting of the midpoints of the intervals of the Hessian. Xc = midpts(X) is a scalar vector conisting of the midpoints of the interval to be searched. So our equation we are solving is:

Vc^-1 * V(X) * (Y-Xc) + Vc^-1 * grad(Xc) = 0

From this we can see that A = Vc^-1 * V(X) and b= Vc^-1 * grad(Xc). The reason for including the Vc^-1 term is to try to make the system converge faster.

For the subdivision part of the searching process, we call NewtonSubdivisionBreak() on a Box to see if we can conclude that there is no root in that Box. We do this by looking at the gradient of the Box. If this interval vector does not contain 0, then there's no roots to be found.

Definition at line 52 of file NewtonCritical.h.

Public Member Functions
	NewtonCritical ()
	Default constructor.
	NewtonCritical (Implicit *)
	Constructs an object which finds critical points for an Implicit.
virtual void	setSurface (Implicit *)
	Changes the surface to search.
virtual Implicit *	getSurface ()
	Returns the current surface being searched.
Protected Member Functions
virtual bool	NewtonEquation (Box< double > &X, IMatrix &A, Box< double > &b)
	Overridden NewtonEquation to solve A(Y-Xc) = b for critical points.
virtual bool	NewtonSubdivisionBreak (Box< double > &X)
	Overridden Newton solver method to stop subdividing.
Protected Attributes
Implicit *	surface
	Find critical points for this Implicit surface.
Private Member Functions
bool	Invert (TNT::Matrix< double > aorig, TNT::Matrix< double > &ainv)
	Using the LU decomposition solve for the inverse of a matrix.

---

Constructor & Destructor Documentation

NewtonCritical::NewtonCritical (   )

Default constructor. This method isn't very useful since it sets the surface to be NULL which means that there is no surface for which to find critical points. Definition at line 21 of file NewtonCritical.cpp. References setSurface().

NewtonCritical::NewtonCritical (  Implicit *  surf  )

Constructs an object which finds critical points for an Implicit. You MUST pass in an Implicit surface or Newton's method won't do anything. Parameters: surf  The implicit surface to be used when finding critical points. Definition at line 31 of file NewtonCritical.cpp. References setSurface(), and surf.

---

Member Function Documentation

Implicit * NewtonCritical::getSurface (   )  [virtual]

Returns the current surface being searched. This method is virtual and should be overridden (along with setSurface(Implicit*)) to keep the surface variable consistent. Returns: The Implicit surface being searched for critical points. See also: setSurface(Implicit*) Reimplemented in SearchCritical. Definition at line 56 of file NewtonCritical.cpp. References surface. Referenced by NewtonEquation(), and NewtonSubdivisionBreak().

bool NewtonCritical::Invert (  TNT::Matrix< double >  aorig, TNT::Matrix< double > &  ainv )  [private]

Using the LU decomposition solve for the inverse of a matrix.

bool NewtonCritical::NewtonEquation (  Box< double > &  X, IMatrix &  A, Box< double > &  b )  [protected, virtual]

Overridden NewtonEquation to solve A(Y-Xc) = b for critical points. In the basic finding of critical points, we look for points in the Box where the gradient is zero. To do this, we need to use the Hessian of the function so Newton's Method knows which way to go at each iteration. As stated in the SIGGRAPH 97 paper "Guaranteeing the Polygonization of an Implicit Surface Polygonization for Interactive Modeling", this comes down to solving the following equation for Y: Vc^-1 * V(X) * (Y-Xc) + Vc^-1 * grad(Xc) = 0 where V(X) is the interval Hessian matrix of the implicit surface, Vc = midpts(V(X)) is a scalar matrix consisting of the midpoints of the intervals of the Hessian, and Xc = midpts(X) is a scalar vector conisting of the midpoints of the interval to be searched. So in this case, we have A = Vc^-1 * V(X) and b = -Vc^-1 * grad(Xc). The reason for including the Vc^-1 term is to try to make the system converge faster. Reimplemented from Newton. Definition at line 83 of file NewtonCritical.cpp. References IMatrix::center(), convert(), getSurface(), Implicit::hess(), GaussJordan::Invert(), and X.

bool NewtonCritical::NewtonSubdivisionBreak (  Box< double > &  X  )  [protected, virtual]

Overridden Newton solver method to stop subdividing. If the gradient of the Box being searched does not contain 0, then there aren't any roots to be found in it and we can quit looking in this Box. Parameters: X  The Box region to check for a 0 gradient. Returns: False if the gradient of the region contains a 0 value, indicating that we should check the region for a critical point. True if we CAN quit early since the region doesn't contain a 0 gradient point. Reimplemented from Newton. Definition at line 118 of file NewtonCritical.cpp. References getSurface(), Implicit::grad(), surf, and X.

void NewtonCritical::setSurface (  Implicit *  surf  )  [virtual]

Changes the surface to search. This method is called by the constructors to set up the private surface variable. It is also virtual and should be overridden (along with getSurface()) to keep the surface variable consistent. Parameters: surf  The new Implicit surface to search for critical points. See also: getSurface() Reimplemented in SearchCritical. Definition at line 44 of file NewtonCritical.cpp. References surf, and surface. Referenced by NewtonCritical().

---

Member Data Documentation

Implicit* NewtonCritical::surface [protected]

Find critical points for this Implicit surface. Reimplemented in SearchCritical. Definition at line 55 of file NewtonCritical.h. Referenced by getSurface(), and setSurface().

---

The documentation for this class was generated from the following files:

• NewtonCritical.h
• NewtonCritical.cpp

---