All Packages  This Package  Class Hierarchy  Class Search  Index

java.lang.Object
   |
   +----jkp.geometry.mesh.BasicMesh
           |
           +----jkp.geometry.mesh.BuildableMesh
                   |
                   +----jkp.geometry.mesh.FixableMesh
                           |
                           +----jkp.geometry.mesh.Mesh

Summary

public class  Mesh
     extends jkp.geometry.mesh.FixableMesh
{
          // Constructors 4
     public Mesh();
     public Mesh(Grid);
     public Mesh(Grid, double, int, int, int, int, int);
     public Mesh(Mesh);

          // Methods 1
     public static Mesh newMesh(Grid, double);

}

Given a NxN grid of terrain elevation data (where N = 1 + 2^k), construct a triangulation of the grid represented as a quadtree. This algorithm starts be recursively dividing the grid into diamonds until the lowest level (subdivided grid is a single point). At this lowest level, it constructs a pseuodo-Steiner triangulation (simply assigns triangles to sets of five points) and then combines triangles (in a locally greedy fashion) as it comes back up the recursion stack.

I believe the recurrance relationship boils down to (with M = NxN):

        { O(1) for M == 1                }
 T(M) = { O(1) for M == 4                }
        { 4T(M/4) + O(1) for all other M }
 

The last line is more accurately written as 4T(((M-1)/4)+1) + O(1), which is 4T((M+3)/4) + O(1), however, since the Master Thereom applies for floor(n/b) and ceiling(n/b) in addition to n/b this isn't a problem (I think) in the analysis since floor((M+3)/4) = M/4.

So, given T(n) = aT(n/b) + f(n), where a = 4, b = 4 and f(n) is O(1).

Consider (a rather large) epsilon = a - 1 = 3 (a constant).

log base b of (a - epslion) equals log base 4 of 1

log base anything of 1 is zero.

Using the Master Thereom:

1. If f(n) = O(log base b of (a - episilon)) for some constant epsilon > 0, then T(n) = theta(n^log b of a).

log b of a is log 4 of 4 which is 1.

T(n) = theta(n^1)

QED?

See the constructor for this class, Mesh(), to verify the recurrance (4T(M/4). See BuildableMesh.refine(), BuildableMesh.refineChildren() and BuildableMesh.pointMoved() to verify the O(1) term.

Version:

0.001a 4 Jul 1998

Author:

Jack Perdue j-perdue@tamu.edu si_slick@cy-net.net

See Also: refine, refineChildren, pointMoved

Cross Reference

Returned By:

Mesh.newMesh(), MeshDisplayPanel.getMesh(), MeshInfoPanel.getDisplayMesh(), MeshPanel.getMesh()

   public Mesh() 

Constructs a default (empty) Mesh.

   public Mesh(Grid meshgrid) 

Constructs a Mesh using the given grid.

Parameter	Description
meshgrid	The grid to mesh/triangulate.

   public Mesh(Grid terrain, 
               double tolerance, 
               int ilo, 
               int ihi, 
               int jlo, 
               int jhi, 
               int direction) 

Constructs the Mesh using the specified rows and columns of the grid. This is the heart of the entire algorithm. Given a terrain, a tolerance, row and column indices defining this mesh's diamond and a direction from the parent mesh divide the given region until down to a point and then combine triangles while coming back up the recurrance stack. Because of the local greediness at each level of the recursion, the resulting mesh sometimes has "seams" where neighboring meshes were unable to make similar triangle combinations. There are two solutions to this. The first is to simply ignore the seams and count them as additional (vertical) triangles. Better yet, after creating the mesh make another bottom up sweep to detect seams and undo triangle combinations from before to eliminate the seams. That is what fixMesh() attempts to do (in linear time as well).

This is a recursive constructor. I could not figure out how to extend a class with a recursive constructor and have the objects it created have the methods/properties of the extended class. The simple fix was to move the recursive constructor to the top (bottom?) most layer of the hierarchy (here).

Parameter	Description
terrain	The terrain to triangulate/mesh.
tolerance	The terrain deviation tolerance (allowable error).
ilo	The leftmost column in the grid for this mesh.
ihi	The rightmost column in the grid for this mesh.
jlo	The bottom row in the grid for this mesh.
jhi	The top row in the grid for this mesh.
direction	The direction from our parent mesh.

See Also: refine, refineChildren, pointMoved, fixMesh

   public Mesh(Mesh m) 

Consructs a new Mesh given a preexisting Mesh.

Parameter	Description
m	The mesh to copy.

   public static Mesh newMesh(Grid grid, 
                              double tolerance) 

Static constructor for a new Mesh given a grid and a terrain tolerance.

Parameter	Description
grid	The grid to mesh.
tolerance	The terrain tolerance.

Returns:

The mesh generated from the grid.

All Packages  This Package  Class Hierarchy  Class Search  Index