KrisLibrary
1.0.0
|
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. | |
Classes defining operations on basic triangle meshes.
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().
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().
makes a triangle mesh from a polygon (one sided)
makes a triangle mesh from a convex polygon (one sided)
References Math3D::Polygon3D::vertices.
void Meshing::MarchingCubes | ( | const Array3D< T > & | input, |
T | 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().
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().