KrisLibrary  1.0.0
Files | Namespaces | Classes | Functions
Meshing

Classes defining operations on basic triangle meshes. More...

Files

file  MarchingCubes.h
 The marching cubes algorithm for extracting an isosurface of a 3D function.
 
file  Meshing.h
 Utilities for manipulating triangle meshes.
 
file  MeshPrimitives.h
 Constructors for basic mesh primitives.
 
file  Rasterize.h
 2D rasterization routines.
 
file  TriMeshOperators.h
 Utilities for operating on, and walking the topology of, triangle meshes.
 
file  Rasterize.h
 2D rasterization routines.
 

Namespaces

 Meshing
 The namespace for all classes/functions in the Meshing package.
 

Classes

class  Geometry::MultiVolumeGrid
 A 3D array over an axis-aligned 3D volume, containing one or more channels. More...
 
class  Geometry::SparseVolumeGrid
 A 3D array over a sparse, axis aligned 3D volume. Has a similar interface as VolumeGrid, but uses a hash grid data structure to achieve better performance in large grids with infinite domain. More...
 
struct  Meshing::AreaGridIterator< T >
 Iterator over a 2D area grid. More...
 
class  Meshing::AreaGridTemplate< T >
 A 2D array over an axis-aligned 2D box, containing Real values. More...
 
class  Meshing::ApproximateGeodesic
 Computes an approximate geodesic distance over a mesh, from a single source. More...
 
class  Meshing::LSConformalMapping
 An approximately-conformal parameterization a genus-0 mesh, found by a least-squares method. More...
 
struct  Meshing::TriSplitter
 A class that allows incremental plane-splitting of a triangle mesh. More...
 
struct  Meshing::Rasterizer2D
 A base class that allows rasterizing of 2D triangles into a grid. More...
 
struct  Meshing::FillRasterizer2D< T >
 A rasterizer that flat-fills elements of a grid. More...
 
struct  Meshing::SmoothFillRasterizer2D< T >
 A smooth-fill rasterizer. More...
 
struct  Meshing::TriMesh
 A basic triangle mesh. More...
 
struct  Meshing::TriMeshChart
 A chart maps a genus 0 triangle mesh to a 2d disk. More...
 
struct  Meshing::TriMeshAtlas
 TODO: a non-genus 0 mesh partitioned into charts. More...
 
struct  Meshing::TriMeshTraversalCallback
 A callback base class for traversing triangle mesh topology. More...
 
struct  Meshing::TriMeshWithTopology
 A triangle mesh that contains connectivity relations between vertices and triangles. More...
 
struct  Meshing::VolumeGridIterator< T >
 Iterator over a 3D volume grid. More...
 
class  Meshing::VolumeGridTemplate< T >
 A 3D array over an axis-aligned 3D volume, containing Real values. More...
 

Functions

void Meshing::MarchingCubes (ScalarFieldFunction &f, Real isoval, const AABB3D &bb, const int dims[3], TriMesh &m)
 Takes a 3D function as input, meshes the isosurface at f(x)=isoval.
 
void Meshing::MarchingCubes (Real(*f)(Real, Real, Real), Real isoval, const AABB3D &bb, const int dims[3], TriMesh &m)
 Takes a 3D function as input, meshes the isosurface at f(x)=isoval.
 
template<class T >
void Meshing::MarchingCubes (const Array3D< T > &input, T isoLevel, const AABB3D &bb, TriMesh &m)
 
void Meshing::CubeToMesh (const Real origvals[8], Real isoLevel, const AABB3D &bb, TriMesh &m)
 
int Meshing::SplitTriangle (const Triangle3D &t, const Plane3D &p, Vector3 newPts[2], IntTriple newTris[3], bool triPositive[3], Real tol)
 Splits the triangle t by the plane p. Returns the number of resulting triangles (up to 3). More...
 
int Meshing::SplitTriangle (const Triangle2D &_t, const Plane2D &p, Vector2 newPts[2], IntTriple newTris[3], bool triPositive[3], Real tol)
 
void Meshing::GetCoplanarTris (const TriMesh &mesh, int t, Real tol, vector< int > &tris)
 
void Meshing::GetConnectedCoplanarTris (const TriMeshWithTopology &mesh, int t, Real tol, vector< int > &tris)
 
void Meshing::MakeTriPlane (int m, int n, TriMesh &mesh)
 makes a unit square on z=0 with m,n divisions in the x,y directions
 
void Meshing::MakeTriPlane (int m, int n, Real x, Real y, TriMesh &mesh)
 makes a square of size [x,y] with m,n divisions in the x,y directions
 
void Meshing::MakeTriCube (int m, int n, int p, TriMesh &mesh)
 makes a unit cube with m,n,p divisions in the x,y,z directions
 
void Meshing::MakeTriBox (int m, int n, int p, Real x, Real y, Real z, TriMesh &mesh)
 makes a [x,y,z] sized box with m,n,p divisions in the x,y,z directions
 
void Meshing::MakeTriCenteredCube (int m, int n, int p, TriMesh &mesh)
 makes a unit cube centered at 0 with m,n,p divisions in the x,y,z directions
 
void Meshing::MakeTriCenteredBox (int m, int n, int p, Real x, Real y, Real z, TriMesh &mesh)
 makes a [x,y,z] sized cube centered at 0 with m,n,p divisions in the x,y,z directions
 
void Meshing::MakeTriSphere (int numStacks, int numSlices, TriMesh &mesh)
 makes a unit sphere with the given stacks and slices (axis in z direction)
 
void Meshing::MakeTriSphere (int numStacks, int numSlices, Real r, TriMesh &mesh)
 makes a radius r sphere with the given stacks and slices (axis in z direction)
 
void Meshing::MakeTriCone (int numSlices, TriMesh &mesh)
 makes a unit height cone with unit base radius (base at origin, tip pointing in z direction)
 
void Meshing::MakeTriCone (int numSlices, Real h, Real rbase, TriMesh &mesh)
 makes a cone with height h, base radius rbase
 
void Meshing::MakeTriCylinder (int numSlices, TriMesh &mesh)
 makes a unit height cylinder with unit base radius (centered at origin, extending in z direction)
 
void Meshing::MakeTriCylinder (int numSlices, Real h, Real rbase, TriMesh &mesh)
 makes a cylinder with height h, base radius rbase
 
void Meshing::MakeTriMesh (const Sphere3D &geom, int numStacks, int numSlices, TriMesh &mesh)
 makes a triangle mesh from a sphere
 
void Meshing::MakeTriMesh (const Triangle3D &geom, TriMesh &mesh)
 makes a triangle mesh from a triangle
 
void Meshing::MakeTriMesh (const AABB3D &geom, TriMesh &mesh)
 makes a triangle mesh from an AABB
 
void Meshing::MakeTriMesh (const Box3D &geom, TriMesh &mesh)
 makes a triangle mesh from a box
 
void Meshing::MakeTriMesh (const Ellipsoid3D &geom, int numStacks, int numSlices, TriMesh &mesh)
 makes a triangle mesh from an ellipsoid
 
void Meshing::MakeTriMesh (const Cylinder3D &geom, int numSlices, TriMesh &mesh)
 makes a triangle mesh from a cylinder
 
void Meshing::MakeTriMesh (const Polygon3D &geom, TriMesh &mesh)
 makes a triangle mesh from a polygon (one sided) More...
 
void Meshing::MakeTriMesh (const GeometricPrimitive3D &geom, TriMesh &mesh, int numDivs)
 makes a triangle mesh from a generic geometric primitive
 
void Meshing::GetSegmentCells (const Segment2D &tri, std::vector< IntPair > &cells)
 Returns a list of cells that the segment overlaps, given an infinite unit grid.
 
void Meshing::GetTriangleCells (const Triangle2D &tri, std::vector< IntPair > &cells)
 Returns a list of cells that the triangle overlaps, given an infinite unit grid.
 
void Meshing::GetTriangleCells_Clipped (const Triangle2D &tri, std::vector< IntPair > &cells, int imin, int jmin, int imax, int jmax)
 Returns a list of cells that the triangle overlaps, in a unit grid from [imin,imax)x[jmin,jmax)
 
Real Meshing::Angle (const Vector3 &e1, const Vector3 &e2)
 Returns the angle between two vectors.
 
int Meshing::CCWNeighbor (const TriMeshWithTopology &mesh, int t, int v)
 Returns the triangle neighboring t CCW about v.
 
int Meshing::CWNeighbor (const TriMeshWithTopology &mesh, int t, int v)
 Returns the triangle neighboring t CW about v.
 
IntPair Meshing::Neighbors (const TriMeshWithTopology &mesh, int t, int v)
 Returns the (CCW neighbor,CW neighbor) of t about v.
 
int Meshing::CCWAdjacentVertex (const TriMeshWithTopology &mesh, int t, int v)
 Returns the vertex adjacent to v on the CCW side of t.
 
int Meshing::CWAdjacentVertex (const TriMeshWithTopology &mesh, int t, int v)
 Returns the vertex adjacent to v on the CCW side of t.
 
IntPair Meshing::AdjacentVertices (const TriMeshWithTopology &mesh, int t, int v)
 Returns the vertices on t adjacent to v in (CCW,CW) order.
 
bool Meshing::FloatingVertex (const TriMeshWithTopology &mesh, int v)
 Returns true if the vertex is "floating".
 
bool Meshing::BoundaryVertex (const TriMeshWithTopology &mesh, int v)
 Returns true if the vertex is a boundary vertex.
 
Real Meshing::IncidentTriangleArea (const TriMeshWithTopology &mesh, int v)
 
bool Meshing::IncidentTriangleOrdering (const TriMeshWithTopology &mesh, int v, vector< list< int > > &triStrips)
 Returns true if the vertex is a boundary vertex. More...
 
Real Meshing::VertexGaussianCurvature (const TriMeshWithTopology &mesh, int v)
 
Real Meshing::VertexAbsMeanCurvature (const TriMeshWithTopology &mesh, int v)
 
void Meshing::MergeVertices (TriMesh &mesh, Real tolerance, bool dropDegenerate)
 
int Meshing::ApproximateShrink (TriMeshWithTopology &mesh, Real amount, bool mergeFirst)
 
void Meshing::GetSegmentCells (const Segment3D &s, vector< IntTriple > &cells, vector< Real > *params=NULL)
 Returns a list of cells that the segment overlaps, given an infinite unit grid. More...
 
void Meshing::GetSegmentCells (const Segment3D &s, int m, int n, int p, const AABB3D &bb, vector< IntTriple > &cells, vector< Real > *params=NULL)
 Returns a list of cells that the segment overlaps, given a grid of size m,n,p over range bb. More...
 
void Meshing::GetTriangleCells (const Triangle3D &tri, vector< IntTriple > &cells)
 Returns a list of cells that the triangle overlaps, given an infinite unit grid.
 
void Meshing::GetTriangleCells (const Triangle3D &tri, int m, int n, int p, const AABB3D &bb, vector< IntTriple > &cells)
 Returns a list of cells that the triangle overlaps, given a grid of size m,n,p over range bb.
 
void Meshing::SurfaceOccupancyGrid (const TriMesh &m, Array3D< bool > &occupied, AABB3D &bb)
 Sets cells of a boolean 3D grid (occupied,bb) that overlap the surface of m to true. More...
 
void Meshing::VolumeOccupancyGrid_FloodFill (const TriMesh &m, Array3D< bool > &occupied, AABB3D &bb, const IntTriple &seed, bool seedOccupied)
 Sets cells of a boolean 3D grid (occupied,bb) to true if the cell's center is in the interior of the mesh, and false otherwise. Occupancy is determined by a flood-fill algorithm starting from the seed point.
 
void Meshing::VolumeOccupancyGrid_CenterShooting (const TriMesh &m, Array3D< bool > &occupied, AABB3D &bb, int shootDirection=0)
 Sets cells of a boolean 3D grid (occupied,bb) to true if the cell's center is in the interior of the mesh, and false otherwise. Occupancy is determined by sweeping a ray through the mesh.
 
void Meshing::SweepVisibilityGrid (const TriMesh &m, int direction, Array3D< bool > &visible, AABB3D &bb, bool singleSided=true)
 From one "visible" side of the grid, sweeps the visibility across the volume until a mesh surface is hit. After that, visible is marked as false. More...
 
void Meshing::FastMarchingMethod (const TriMeshWithTopology &m, Array3D< Real > &distance, Array3D< Vector3 > &gradient, AABB3D &bb, vector< IntTriple > &surfaceCells)
 Fills in a distance field on a 3D grid (occupied,bb) using the fast marching method initialized at the surface m. More...
 
void Meshing::FastMarchingMethod_Fill (const TriMeshWithTopology &m, Array3D< Real > &distance, Array3D< Vector3 > &gradient, AABB3D &bb, vector< IntTriple > &surfaceCells)
 Same as FastMarchingMethod but constrains start points to the exterior of the mesh (sometimes avoids artifacts from internal structures)
 
void Meshing::DensityEstimate_CenterShooting (const TriMesh &m, Array3D< Real > &density, AABB3D &bb, int shootDirection=0)
 Estimates the object's density filling the grid using a shooting method.
 
void Meshing::DensityEstimate_RandomShooting (const TriMesh &m, Array3D< Real > &density, AABB3D &bb, int numSamples, int shootDirection=0)
 Estimates the object's density filling the grid using a shooting method.
 
void Meshing::DensityEstimate_FloodFill (const TriMeshWithTopology &m, Array3D< Real > &density, AABB3D &bb, const IntTriple &seed)
 Fills in a density estimate on a 3D grid (occupied,bb) using a flood fill to determine inside/outside, more accurate calculation for density. More...
 
void Meshing::DensityEstimate_FMM (const TriMeshWithTopology &m, Array3D< Real > &density, AABB3D &bb)
 Fills in a density estimate on a 3D grid (occupied,bb) using the FMM distance measurement.
 
void Meshing::DensityEstimate_FMM (const Array3D< Real > &distance, const Array3D< Vector3 > &gradient, const AABB3D &bb, Array3D< Real > &density)
 Fills in a density estimate on a 3D grid (occupied,bb) using the density, gradient output from running FMM.
 

Detailed Description

Classes defining operations on basic triangle meshes.

Function Documentation

int Meshing::ApproximateShrink ( TriMeshWithTopology mesh,
Real  amount,
bool  mergeFirst = true 
)

Shifts the mesh's vertices by an amount that causes each adjacent triangle to be shifted along its normal by the given amount. This is a local, approximate erosion operator that is much quicker to compute, but the approximation degrades with larger amounts of erosion.

If mergeFirst = true, then the points are first merged. This helps with some exploded triangle meshes. If you know your mesh is not exploded, then you can save some overhead by setting this to false.

Returns 0 if there were no local interpenetrations caused by the shrinking, otherwise it returns the number of detected local interpenetrations.

References Math::dot(), Meshing::TriMeshWithTopology::incidentTris, MergeVertices(), Math3D::Matrix2::setInverse(), and Meshing::TriMesh::TriangleNormal().

Referenced by BoundaryVertex().

void Meshing::CubeToMesh ( const Real  vals[8],
Real  isoval,
const AABB3D bb,
TriMesh m 
)

Takes values of a function f at a cube's vertices as input, meshes the isosurface at f(x)=isoval cube vertex indices are given by the index's last 3 bits in xyz order, i.e., 0 = 000b = (0,0,0), 1 = 001b = (0,0,+x), 3 = 011b = (0,+y,+x), etc.

References Math3D::SegmentCrossing().

void Meshing::DensityEstimate_FloodFill ( const TriMeshWithTopology m,
Array3D< Real > &  density,
AABB3D bb,
const IntTriple seed 
)

Fills in a density estimate on a 3D grid (occupied,bb) using a flood fill to determine inside/outside, more accurate calculation for density.

The seed point is assumed to be empty.

References Meshing::TriMesh::GetTriangle().

void Meshing::FastMarchingMethod ( const TriMeshWithTopology m,
Array3D< Real > &  distance,
Array3D< Vector3 > &  gradient,
AABB3D bb,
vector< IntTriple > &  surfaceCells 
)

Fills in a distance field on a 3D grid (occupied,bb) using the fast marching method initialized at the surface m.

O(n^3 log n) for a grid of size n x n x n

If bb is empty, automatically fits the bounding box to contain the mesh in the non-border cells of the grid.

References ArrayUtils::copy(), and Meshing::TriMesh::GetTriangle().

Referenced by DensityEstimate_FMM().

void Meshing::GetSegmentCells ( const Segment3D s,
vector< IntTriple > &  cells,
vector< Real > *  params = NULL 
)

Returns a list of cells that the segment overlaps, given an infinite unit grid.

If params is not null, the segment parameters that indicate the beginnings / endings of each overlap are output in params.

void Meshing::GetSegmentCells ( const Segment3D s,
int  m,
int  n,
int  p,
const AABB3D bb,
vector< IntTriple > &  cells,
vector< Real > *  params = NULL 
)

Returns a list of cells that the segment overlaps, given a grid of size m,n,p over range bb.

If params is not null, the segment parameters that indicate the beginnings / endings of each overlap are output in params.

bool Meshing::IncidentTriangleOrdering ( const TriMeshWithTopology mesh,
int  v,
vector< list< int > > &  triStrips 
)

Returns true if the vertex is a boundary vertex.

Divides the triangles connected to v in lists sorted by CCW order. Returns true if the vertex is a boundary vertex

References CCWNeighbor(), CWNeighbor(), Meshing::TriMeshWithTopology::incidentTris, and Meshing::TriMeshWithTopology::triNeighbors.

Referenced by BoundaryVertex(), and VertexGaussianCurvature().

void Meshing::MakeTriMesh ( const Polygon3D geom,
TriMesh mesh 
)

makes a triangle mesh from a polygon (one sided)

makes a triangle mesh from a convex polygon (one sided)

References Math3D::Polygon3D::vertices.

template<class T >
void Meshing::MarchingCubes ( const Array3D< T > &  input,
isoval,
const AABB3D bb,
TriMesh m 
)

Takes a 3D grid as input, meshes the isosurface at f(x)=isoval. Assumes the input values are defined at the vertices of a grid with m-1 x n-1 x p-1 cells

Defined for T = char, int, float, and double

References Math3D::SegmentCrossing().

void Meshing::MergeVertices ( TriMesh mesh,
Real  tolerance,
bool  dropDegenerate = true 
)

Merges all vertices in mesh that are closer than tolerance Linf distance from each other If dropDegenerate = true, then all triangles that are now degenerate will be dropped.

Referenced by ApproximateShrink(), BoundaryVertex(), and GLDraw::GeometryAppearance::DrawGL().

int Meshing::SplitTriangle ( const Triangle3D t,
const Plane3D p,
Vector3  newPts[2],
IntTriple  newTris[3],
bool  triPositive[3],
Real  tol 
)

Splits the triangle t by the plane p. Returns the number of resulting triangles (up to 3).

The new triangles are given as a set of indices. 0,1,2 are the vertices a,b,c of the original triangle. 3,4 are newPts[0],newPts[1].

For each new triangle, triPositive marks true if it is on the positive side of the plane.

References Math::FuzzyZero(), ShiftBackward(), and ShiftForward().

void Meshing::SurfaceOccupancyGrid ( const TriMesh m,
Array3D< bool > &  occupied,
AABB3D bb 
)

Sets cells of a boolean 3D grid (occupied,bb) that overlap the surface of m to true.

If bb is empty, automatically fits the bounding box to contain the mesh in the non-border cells of the grid.

References Meshing::TriMesh::GetTriangle().

Referenced by SweepVisibilityGrid(), and VolumeOccupancyGrid_FloodFill().

void Meshing::SweepVisibilityGrid ( const TriMesh m,
int  direction,
Array3D< bool > &  visible,
AABB3D bb,
bool  singleSided = true 
)

From one "visible" side of the grid, sweeps the visibility across the volume until a mesh surface is hit. After that, visible is marked as false.

direction can be one of 1,2,3,-1,-2, or -3, corresponding to the sweep direction (+x,+y,+z,-x,-y, or -z, respectively).

If singleSided=true, then a surface is "hit" only when approaching the front side (ccw winding) of the triangle.

References SurfaceOccupancyGrid().

Real Meshing::VertexAbsMeanCurvature ( const TriMeshWithTopology mesh,
int  v 
)

Returns the abs val of the integral of the mean curvature about v assuming the mesh approximates an underlying smooth surface

References Angle(), CCWNeighbor(), Meshing::TriMeshWithTopology::incidentTris, Meshing::TriMesh::TriangleNormal(), and Meshing::TriMeshWithTopology::triNeighbors.

Referenced by BoundaryVertex().

Real Meshing::VertexGaussianCurvature ( const TriMeshWithTopology mesh,
int  v 
)

Returns the integral of the gaussian curvature about v assuming the mesh approximates an underlying smooth surface

References Angle(), CCWAdjacentVertex(), CCWNeighbor(), CWAdjacentVertex(), CWNeighbor(), IncidentTriangleOrdering(), and Meshing::TriMeshWithTopology::incidentTris.

Referenced by BoundaryVertex().