Namespace g3

Classes

AddTrianglesMeshChange

Add triangles from mesh and store necessary data to be able to reverse the change. Vertex and Triangle IDs will be restored on Revert() Currently does not restore the same EdgeIDs

Arrangement2d constructs a planar arrangement of a set of 2D line segments. When a segment is inserted, existing edges are split, and the inserted segment becomes multiple graph edges. So, the resulting DGraph2 should not have any edges that intersect.

Calculations are performed in double-precision, so there is no guarantee of correctness.

[TODO] multi-level segment has to accelerate find_intersecting_edges() [TODO] maybe smarter handling

BaseCurve2

BezierCurve2

2D Bezier curve of arbitrary degree Ported from WildMagic5 Wm5BezierCurve2

BiArcFit2

BiGrid3<BlockType>

BiGrid3 is a two-level multiresolution grid data structure. You provide exemplar object that implements suitable interfaces, and the class automatically generates necessary data structures. Functions to act on parent/child grids are in-progress...

BinaryG3FormatReader

BinaryG3Reader

BinaryG3Writer

Bitmap2

Bitmap3

BlockSupportGenerator

BlockTimer

BoundsUtil

BSplineBasis

BufferUtil

CachingDenseGridTrilinearImplicit

[RMS] variant of DenseGridTrilinearImplicit that does lazy evaluation of Grid values.

Tri-linear interpolant for a 3D dense grid. Supports grid translation via GridOrigin, but does not support scaling or rotation. If you need those, you can wrap this in something that does the xform.

CachingMeshSDF

[RMS] this is variant of MeshSignedDistanceGrid that does lazy evaluation of actual distances, using mesh spatial data structure. This is much faster if we are doing continuation-method marching cubes as only values on surface will be computed!

Compute discretely-sampled (ie gridded) signed distance field for a mesh The basic approach is, first compute exact distances in a narrow band, and then extend out to rest of grid using fast "sweeping" (ie like a distance transform). The resulting unsigned grid is then signed using ray-intersection counting, which is also computed on the grid, so no BVH is necessary

If you set ComputeMode to NarrowBandOnly, result is a narrow-band signed distance field. This is quite a bit faster as the sweeping is the most computationally-intensive step.

Caveats:

the "narrow band" is based on triangle bounding boxes, so it is not necessarily that "narrow" if you have large triangles on a diagonal to grid axes

Potential optimizations:

Often we have a spatial data structure that would allow faster computation of the narrow-band distances (which become quite expensive if we want a wider band!) Not clear how to take advantage of this though. Perhaps we could have a binary grid that, in first pass, we set bits inside triangle bboxes to 1? Or perhaps same as current code, but we use spatial-dist, and so for each ijk we only compute once? (then have to test for computed value at each cell of each triangle...)

This code is based on the C++ implementation found at https://github.com/christopherbatty/SDFGen Original license was public domain. Permission granted by Christopher Batty to include C# port under Boost license.

CachingMeshSDFImplicit

Tri-linear interpolant for a 3D dense grid. Supports grid translation via GridOrigin, but does not support scaling or rotation. If you need those, you can wrap this in something that does the xform.

CancelFunction

CappedCylinderGenerator

Generate a Cylinder with caps. Supports sections of cylinder as well (eg wedges). Curently UV islands are overlapping for different mesh components, if NoSharedVertices Positioned along Y axis such that base-center is at Origin, and top is at Y=Height You get a cone unless BaseRadius = TopRadius No subdivisions along top/base rings or height steps. cylinder triangles have groupid = 1, top cap = 2, bottom cap = 3, wedge faces 5 and 6

CholeskyDecomposition

Computes Cholesky decomposition/factorization L of matrix A A must be symmetric and positive-definite computed lower-triangular matrix L satisfies L*L^T = A. https://en.wikipedia.org/wiki/Cholesky_decomposition

Circle2d

Circle3d

CircleProjectionTarget

ColorHSV

ColorMap

ColorMixer

CommandArgumentSet

ConeGenerator

ConstantIndexMap

ConstantItr<T>

Iterator that just returns a constant value N times

ContMinBox2

Fit minimal bounding-box to a set of 2D points. Result is in MinBox.

ContMinCircle2

Fit minimal bounding-circle to a set of 2D points

ContMinCircle2.Support

ContOrientedBox3

ConvexHull2

Construct convex hull of a set of 2D points, with various accuracy levels.

HullIndices provides ordered indices of vertices of input points that form hull.

ConvexHull2.Edge

Internal class that represents edge of hull, and neighbours

Curve3Axis3RevolveGenerator

Curve3Curve3RevolveGenerator

CurveGenerator

CurveResampler

CurveSampler2

CurveUtils

CurveUtils2

Cylinder3d

CylinderProjectionTarget

DCurve3

DCurve3 is a 3D polyline, either open or closed (via .Closed) Despite the D prefix, it is not dynamic

DCurve3BoxTree

tree of Oriented Boxes (OBB) for a DCurve3. Construction is sequential, ie pairs of segments are merged into boxes, then pairs of boxes, and so on

[TODO] is this the best strategy? is there maybe some kind of sorting/sweepline algo? [TODO] would it make more sense to have more than just 2 segments at lowest level?

DCurveProjectionTarget

DeepCopy

Collection of utility functions for one-line deep copies of lists

DenseGrid2f

2D dense grid of floating-point scalar values.

DenseGrid2i

2D dense grid of integers.

DenseGrid3f

3D dense grid of floating-point scalar values.

DenseGrid3i

3D dense grid of integers.

DenseGridTrilinearImplicit

Tri-linear interpolant for a 3D dense grid. Supports grid translation via GridOrigin, but does not support scaling or rotation. If you need those, you can wrap this in something that does the xform.

DenseMatrix

Row-major dense matrix

DenseUVMesh

DenseVector

DGraph

Base class for Arbitrary-Topology Graphs. Similar structure to topology parts of DMesh3. Each vertex can be connected to an arbitrary number of edges. Each edge can have an integer GroupID. See DGraph2 and DGraph3 for 3d implementations. Use DGraphN if you would like a topology-only graph. You cannot instantiate DGraph directly.

DGraph2

Arbitrary-Topology 2D Graph. This is similar to DMesh3 but without faces. Each vertex can be connected to an arbitrary number of edges. Each vertex can have a 3-float color, and edge edge can have an integer GroupID

DGraph2Resampler

"Remesher" for DGraph2

DGraph2Util

Utility functions for DGraph2 data structure

DGraph2Util.Curves

DGraph3

Arbitrary-Topology 3D Graph. This is similar to DMesh3 but without faces. Each vertex can be connected to an arbitrary number of edges. Each vertex can have a 3-float color, and edge edge can have an integer GroupID

DGraph3Util

Utility functions for DGraph3 data structure

DGraphN

Implementation of DGraph that has no dimensionality, ie no data stored for vertieces besides indices.

DiagonalMatrix

DijkstraGraphDistance

Compute Dijkstra shortest-path algorithm on a graph. Computation is index-based, but can use sparse data structures if the index space will be sparse.

Construction is somewhat complicated, but see shortcut static methods at end of file for common construction cases:

MeshVertices(mesh) - compute on vertices of mesh
MeshVertices(mesh) - compute on vertices of mesh

DIndexArray2i

DIndexArray3i

Distance

DistanceFieldToSkeletalField

This class converts the interval [-falloff,falloff] to [0,1], Then applies Wyvill falloff function (1-t^2)^3. The result is a skeletal-primitive-like shape with the distance=0 isocontour lying just before midway in the range (at the .ZeroIsocontour constant)

DistLine2Line2

DistLine2Segment2

DistLine3Ray3

DistLine3Segment3

DistLine3Triangle3

DistPoint2Box2

DistPoint2Circle2

DistPoint3Circle3

DistPoint3Cylinder3

DistPoint3Triangle3

DistRay3Ray3

DistRay3Segment3

Distance between ray and segment ported from WildMagic5

DistSegment2Segment2

DistSegment3Triangle3

DistTriangle3Triangle3

DMesh3

DMesh3Builder

DMeshAABBTree3

Hierarchical Axis-Aligned-Bounding-Box tree for a DMesh3 mesh. This class supports a variety of spatial queries, listed below.

Various construction strategies are also available, the default is the fastest to build but if you are doing a lot of queries, you might experiment with the others (eg TopDownMedian)

Available queries:

FindNearestTriangle(point, maxdist)
FindNearestHitTriangle(ray, maxdist)
FindAllHitTriangles(ray, maxdist)
TestIntersection(triangle)
TestIntersection(mesh)
TestIntersection(otherAABBTree)
FindAllIntersections(otherAABBTree)
FindNearestTriangles(otherAABBTree, maxdist)
IsInside(point)
WindingNumber(point)
FastWindingNumber(point)
DoTraversal(generic_traversal_object)

DMeshAABBTree3.IntersectionsQueryResult

DMeshAABBTree3.TreeTraversal

Instances of this class can be passed in to the DoTraversal() function to implement your own tree-traversal queries. NextBoxF() is called for each box node. Return false from this function to halt terminate that branch of the traversal, or true to descend into that box's children (boxes or triangles). NextTriangleF() is called for each triangle.

DMeshIntersectionTarget

DPolyLine2f

Summary description for PolyLine.

DS3FormatReader

DSparseGrid3<ElemType>

Dynamic sparse 3D grid. Idea is that we have grid of some type of object and we don't want to pre-allocate full grid of them. So we allocate on-demand. This can be used to implement multi-grid schemes, eg for example the GridElement type could be Bitmap3 of a fixed dimension.

DSubmesh3

DSubmesh3Set

A set of submeshes of a base mesh. You provide a set of keys, and a Func that returns the triangle index list for a given key. The set of DSubmesh3 objects are computed on construction.

DVector<T>

DVectorArray2<T>

DVectorArray2d

DVectorArray2f

DVectorArray3<T>

DVectorArray3d

DVectorArray3f

DVectorArray3i

DynamicPriorityQueue<T>

DynamicPriorityQueueNode

To use DynamicPriorityQueue, your queue node type needs to subclass this one. However the priority and index members are for internal queue use, not yours!

EdgeLoop

Sequential set of vertices/edges in a mesh, that form a closed loop.

If all you have are the vertices, use EdgeLoop.VertexLoopToEdgeLoop() to construct an EdgeLoop

EdgeLoopRemesher

This is a custom Remesher that only affects the edges along an EdgeLoop. The edges are only split and collapsed, flipping is not permitted. The loop vertices are smoothed along the loop, ie using curve laplacian rather than one-ring laplacian.

[TODO] avoid rebuild_edge_list(). requires handling various cases below... [TODO] Precompute() seems overly expensive...? [TODO] local-smoothing impl is not very efficient. Should not be necessary to rebuild nbrhood each time if we are not changing it.

EdgeSpan

An EdgeSpan is a continous set of edges in a Mesh that is not closed (that would be an EdgeLoop)

Ellipse2d

EllipseArc2d

FaceGroupOptimizer

Given input mesh with a set of face groups, optimize the face group boundaries. This involves flipping triangles between groups, and/or assigning to "background" group. Also has Dilate/Contract functions to grow/shrink groups in various ways.

FaceGroupUtil

FastPointWinding

Formulas for point-set winding number approximation

FastQuaternionSVD

Fast Approximate SVD of 3x3 matrix that returns quaternions. Implemented based on https://github.com/benjones/quatSVD/blob/master/quatSVD.hpp which was re-implemented from http://pages.cs.wisc.edu/~sifakis/project_pages/svd.html

By default, only does a small number of diagonalization iterations (4), which limits the accuracy of the solution. Results are still orthonormal but error when reconstructing matrix will be larger. This is fine for many applications. Can increase accuracy by increasing NumJacobiIterations parameter

Note: does not produce same quaternions as running SingularValueDecomposition on matrix and converting resulting U/V to quaternions. The numbers will be similar but the signs will be different

Useful properties:

quaternions are rotations, there are no mirrors like in normal SVD

TODO:

SymmetricMatrix3d currently a class, could make a struct (see comments)

FastTriWinding

Formulas for triangle winding number approximation

FileSystemUtils

GaussPointsFit3

GeneralPolygon2d

GeneralPolygon2dBoxTree

GenericMaterial

gException

gIndices

gParallel

GraphCells2d

This class extracts the set of loops bounding the "cells" of a DGraph2, ie each cell is a connected region with a polygonal boundary. Precondition: the graph has no self-intersections. Precondition: at any vertex, the edges are sortable by angle (ie no outgoing edges overlap) ** numerically this may not be 100% reliable....

Both "sides" of each edge are included in some cell boundary, ie so for a simple polygon, there are two cells, one infinitely large. The "inside" cells will be oriented clockwise, if converted to a Polygon2d.

GraphSplitter2d

This class is used to bisect an existing DGraph2 with infinite lines. This is easier than inserting new segments, which can be done using Arrangement2d.

Computations are done in double precision. Use at your own risk.

[TODO]

computation of signs for a split-line is currently O(N). If inserting many parallel lines, can improve this using standard sorting.

GraphSupportGenerator

GraphSupportGenerator.ImplicitCurve3d

Implicit tube around line segment

GraphTubeMesher

GridBox3Generator

Generate a mesh of a box that has "gridded" faces, ie grid of triangulated quads, with EdgeVertices verts along each edge. [TODO] allow varying EdgeVertices in each dimension (tricky...)

GriddedRectGenerator

Generate a mesh of a rect that has "gridded" faces, ie grid of triangulated quads, with EdgeVertices verts along each edge. [TODO] allow varying EdgeVertices in each dimension (tricky...)

gSerialization

HBitArray

HBitArray is a hierarchical variant of BitArray. Basically the idea is to make a tree of 32-bit blocks, where at level N, a '0' means that no bits are true in level N-1. This means we can more efficiently iterate over the bit set.

Uses more memory than BitArray, but each tree level is divided by 32, so it is better than NlogN

Hexagon2d

IdentityIndexMap

ImplicitAxisAlignedBox3d

Implicit axis-aligned box

ImplicitBlend2d

ImplicitBlend3d

Blend of two implicit surfaces. Assumes surface is at zero iscontour. Uses Pasko blend from http://www.hyperfun.org/F-rep.pdf

ImplicitBox3d

Implicit oriented box

ImplicitDifference2d

ImplicitDifference3d

Boolean Difference/Subtraction of two implicit functions A-B = A AND (NOT B) Assumption is that both have surface at zero isocontour and negative is inside.

ImplicitFieldSampler3d

Sample implicit fields into a dense grid

ImplicitHalfSpace3d

Implicit half-space. "Inside" is opposite of Normal direction.

ImplicitIntersection2d

ImplicitIntersection3d

Boolean Intersection of two implicit functions, A AND B Assumption is that both have surface at zero isocontour and negative is inside.

ImplicitLine3d

Implicit tube around line segment

ImplicitNaryDifference3d

Boolean Difference of N implicit functions, A - Union(B1..BN) Assumption is that both have surface at zero isocontour and negative is inside.

ImplicitNaryIntersection3d

Boolean Intersection of N implicit functions, A AND B. Assumption is that both have surface at zero isocontour and negative is inside.

ImplicitNAryOp2d

ImplicitNaryUnion3d

Boolean Union of N implicit functions, A OR B. Assumption is that both have surface at zero isocontour and negative is inside.

ImplicitOffset3d

Offset the zero-isocontour of an implicit function. Assumes that negative is inside, if not, reverse offset.

ImplicitPoint2d

ImplicitShell3d

remaps values so that values within given interval are negative, and values outside this interval are positive. So, for a distance field, this converts single isocontour into two nested isocontours with zeros at interval a and b, with 'inside' in interval

ImplicitSmoothDifference3d

Continuous R-Function Boolean Difference of two implicit functions, A AND B Assumption is that both have surface at zero isocontour and negative is inside.

ImplicitSmoothIntersection3d

Continuous R-Function Boolean Intersection of two implicit functions, A-B = A AND (NOT B) Assumption is that both have surface at zero isocontour and negative is inside.

ImplicitSmoothUnion3d

Continuous R-Function Boolean Union of two implicit functions, A OR B. Assumption is that both have surface at zero isocontour and negative is inside.

ImplicitSphere3d

Implicit sphere, where zero isocontour is at Radius

ImplicitUnion2d

ImplicitUnion3d

Boolean Union of two implicit functions, A OR B. Assumption is that both have surface at zero isocontour and negative is inside.

IndexArray2i

IndexArray3i

IndexArray4i

IndexFlagSet

This class provides a similar interface to BitArray, but can optionally use a HashSet (or perhaps some other DS) if the fraction of the index space required is small

IndexHashSet

IndexMap

IndexPriorityQueue

This is a min-heap priority queue class that does not use an object for each queue node. Integer IDs must be provided by the user to identify unique nodes. Internally an array is used to keep track of the mapping from ids to internal indices, so the max ID must also be provided.

See DijkstraGraphDistance for example usage.

conceptually based on https://github.com/BlueRaja/High-Speed-Priority-Queue-for-C-Sharp

IndexRangeEnumerator

IndexUtil

InPlaceIterativeCurveSmooth

Integrate1d

IntersectionUtil

Intersector1

IntrLine2Line2

IntrLine2Segment2

IntrLine2Triangle2

IntrLine3AxisAlignedBox3

IntrLine3Box3

IntrRay3AxisAlignedBox3

IntrRay3Box3

IntrRay3Triangle3

IntrSegment2Segment2

IntrSegment2Triangle2

IntrSegment3Box3

IntrTriangle2Triangle2

IntrTriangle3Triangle3

IntTagSet<T>

Basic object->integer mapping

IWrappedCurve3d

Simple sampled-curve wrapper type

LaplacianCurveDeformer

Variant of LaplacianMeshDeformer that can be applied to 3D curve.

Solve in each dimension can be disabled using .SolveX/Y/Z

Currently only supports uniform weights (in Initialize)

LaplacianMeshDeformer

LaplacianMeshSmoother

LineGenerator

LocalProfiler

LockingQueue<T>

MappedList

IList wrapper that remaps values via a Func (eg for index maps)

MarchingCubes

Basic implementation of marching cubes mesh generation, which can be applied to arbitrary Implicit function. Multi-threading enabled by default.

[TODO] support locking on Implicit.Value()? May not be thread-safe!! [TODO] extension that tracks set of triangles in each cube, so we can do partial updates? [TODO] is hash table on vertex x/y/z the best idea? [TODO] hash table for edge vtx-indices instead, like old polygonizer? (how did we index edges?!?)

MarchingQuads

2D MarchingQuads polyline extraction from scalar field [TODO] this is very, very old code. Should at minimum rewrite using current vector classes/etc.

MathUtil

Matrix2d

Matrix2f

MatrixUtil

MemoryPool<T>

Very basic object pool class.

MeshBoolean

MeshBoundaryEdgeMidpoints

Present mesh boundary-edge midpoints as a point set

MeshBoundaryLoops

Extract boundary EdgeLoops from Mesh. Can also extract EdgeSpans for open areas, however default behavior is to ignore these. Set .SpanBehavior to configure.

MeshBoundaryLoopsException

MeshConnectedComponents

MeshConstraints

MeshConstraintUtil

MeshDecomposition

MeshEdgeMidpoints

Present mesh edge midpoints as a point set

MeshEdgeSelection

MeshEditor

MeshExtrudeFaces

Extrude a subset of faces of Mesh. Steps are: 1) separate subset from neighbouring triangles 2) offset them 3) connect original and offset edges (now boundary edges) with a triangle strip

Caveats:

not sure it works for multiple regions?
boundary vertices are currently attached to offset region, rather than also duplicated and then connected w/ strip [TODO] implement this behavior

MeshExtrudeLoop

Assumption is that Loop is a boundary loop on Mesh. Operation makes a duplicate loop of vertices, at location defind by PositionF, then stitches input and new loops together with a ring of triangles.

MeshExtrudeMesh

Extrude all faces of a mesh, and stitch together any boundary loops. Steps are: 1) make a copy of all triangles in mesh 2) offset copy vertices 3) connect up loops with triangle strips

MeshFaceSelection

MeshFacesFromLoop

Find mesh triangles enclosed by a curve embedded in the mesh If a seed triangle in the enclosed region is not provided, then the smaller of the two largest connected-components is chosen as the "inside".

MeshGenerator

MeshICP

MeshIndexUtil

Utility functions for manipulating sets/lists of mesh indices

MeshInsertPolygon

Insert Polygon into Mesh. Assumption is that Mesh has 3D coordinates (u,v,0). This is basically a helper/wrapper around MeshInsertUVPolyCurve. Inserted edge set is avaliable as .InsertedPolygonEdges, and triangles inside polygon as .InteriorTriangles

MeshInsertUVPolyCurve

Cut mesh with a path of 2D line segments Assumptions:

mesh vertex x/y coordinates are 2D coordinates we want to use. Replace PointF if this is not the case.
segments of Curve lie entirely within UV-triangles

Limitations:

currently not robust to near-parallel line segments that are within epsilon-band of the input loop. In this case, we will include all such segments in the 'cut' set, but we will probably not be able to find a connected path through them.
not robust to degenerate geometry. Strongly recommend that you use Validate() and/or preprocess the input mesh to remove degenerate faces/edges

MeshIOUtil

MeshIsoCurves

MeshIterativeSmooth

MeshIterators

MeshLocalParam

MeshLoopClosure

MeshLoopSmooth

MeshMeasurements

MeshMeshCut

TODO:

track descendant triangles of each input face
for missing segments, can resolve in 2D in plane of face

MeshNormals

MeshOps

MeshPlaneCut

MeshProjectionTarget

MeshProjectionTarget provides an IProjectionTarget interface to a mesh + spatial data structure. Use to project points to mesh surface.

MeshQueries

MeshRefinerBase

MeshRegionBoundaryLoops

Extract boundary EdgeLoops for subregions of Mesh

MeshSignedDistanceGrid

If you set ComputeMode to NarrowBandOnly, result is a narrow-band signed distance field. This is quite a bit faster as the sweeping is the most computationally-intensive step.

Caveats:

the "narrow band" is based on triangle bounding boxes, so it is not necessarily that "narrow" if you have large triangles on a diagonal to grid axes

Potential optimizations:

Often we have a spatial data structure that would allow faster computation of the narrow-band distances (which become quite expensive if we want a wider band!) Not clear how to take advantage of this though. Perhaps we could have a binary grid that, in first pass, we set bits inside triangle bboxes to 1? Or perhaps same as current code, but we use spatial-dist, and so for each ijk we only compute once? (then have to test for computed value at each cell of each triangle...)

MeshTransforms

MeshTriInfoCache

MeshTrimLoop

Delete triangles inside on/near-surface trimming curve, and then adapt the new boundary loop to conform to the loop.

[DANGER] To use this class, we require a spatial data structure we can project onto. Currently we assume that this is a DMesh3AABBTree because if you don't provide a seed triangle, we use FindNearestTriangle() to find this index on the input mesh. So, it must be a tree for the exact same mesh (!). However we then delete a bunch of triangles and use this spatial DS only for reprojection. Possibly these should be two separate things? Or force caller to provide seed triangle for trim loop, instead of solving this problem for them? (But basically there is no way around having a full mesh copy...)

TODO:

output boundary EdgeLoop that has been aligned w/ trim curve
handle cases where input mesh has open borders

MeshUtil

MeshValidation

MeshVertexSelection

MeshWeights

ModifyVerticesMeshChange

Mesh change for vertex deformations. Currently minimal support for initializing buffers. AppendNewVertex() can be used to accumulate modified vertices and their initial positions.

NormalHistogram

Construct spherical histogram of normals of mesh. Binning is done using a Spherical Fibonacci point set.

NTMesh3

NURBSCurve2

OBJFormatReader

OBJMaterial

OBJReader

OBJWriter

gradientspace OBJ writer

[TODO] if mesh has groups, usemtl lines will not be written (see TODO below) [TODO] options to preserve vertex and triangle indices

OFFFormatReader

OFFWriter

OpenCylinderGenerator

OrthogonalPlaneFit3

PackedSparseMatrix

This is a sparse matrix where each row is an array of (column,value) pairs This is more efficient for Matrix*Vector multiply.

ParallelStream<V, T>

ParametricCurveSequence2

PlanarComplex

PlanarComplex.ClosedLoopsInfo

PlanarComplex.Element

PlanarComplex.GeneralSolid

PlanarComplex.OpenCurvesInfo

PlanarComplex.SmoothCurveElement

PlanarComplex.SmoothLoopElement

PlanarComplex.SolidRegionInfo

PlanarHoleFiller

Try to fill planar holes in a mesh. The fill is computed by mapping the hole boundary into 2D, filling using 2D algorithms, and then mapping back to 3D. This allows us to properly handle cases like nested holes (eg from slicing a torus in half).

PlanarComplex is used to sort the input 2D polyons.

MeshInsertUVPolyCurve is used to insert each 2D polygon into a generated planar mesh. The resolution of the generated mesh is controlled by .FillTargetEdgeLen

In theory this approach can handle more geometric degeneracies than Delaunay triangluation. However, the current code requires that MeshInsertUVPolyCurve produce output boundary loops that have a 1-1 correspondence with the input polygons. This is not always possible.

Currently these failure cases are not handled properly. In that case the loops will not be stitched.

PlanarSolid2d

PlanarSpansFiller

This class fills an ordered sequence of planar spans. The 2D polygon is formed by chaining the spans.

Current issues:

connectors have a single segment, so when simplified, they become a single edge. should subsample them instead.
currently mapping from inserted edges back to span edges is not calculated, so we have no way to merge them (ie MergeFillBoundary not implemented)
fill triangles not returned?

PlaneIntersectionTarget

Compute ray-intersection with plane

PlaneProjectionTarget

PointAABBTree3

Hierarchical Axis-Aligned-Bounding-Box tree for an IPointSet

TODO: no timestamp support right now...

PointAABBTree3.TreeTraversal

PointHashGrid2d<T>

Hash Grid for 2D points. You provide the 'point' type. If you have an indexable set of points this can just be int, or can be more complex point data structure (but be careful w/ structs...)

Does not actually store 2D points. So, to remove a point you must also know it's 2D coordinate, so we can look up the cell coordinates. Hence, to 'update' a point, you need to know both it's old and new 2D coordinates.

PointHashGrid3d<T>

Hash Grid for 3D points. You provide the 'point' type. If you have an indexable set of points this can just be int, or can be more complex point data structure (but be careful w/ structs...)

Does not actually store 3D points. So, to remove a point you must also know it's 3D coordinate, so we can look up the cell coordinates. Hence, to 'update' a point, you need to know both it's old and new 3D coordinates.

TODO: if a lot of points are in the same spot, this is still a disaster. What if we had a second level of hashing, where once a list at a level gets too big, we build a sub-hash there?

PointSplatsGenerator

Create a mesh that contains a planar element for each point and normal (currently only triangles)

Polygon2d

Polygon2dBoxTree

tree of Oriented Boxes (OBB) for a Polygon2d. Construction is sequential, ie pairs of segments are merged into boxes, then pairs of boxes, and so on

[TODO] is this the best strategy? is there maybe some kind of sorting/sweepline algo? [TODO] would it make more sense to have more than just 2 segments at lowest level?

Polygon2DCurve

Wrapper for a Polygon2d that provides minimal IParametricCurve2D interface

PolygonFont2d

This class represents an outline font, where the outline is composed of polygons. Each font is a list of GeneralPolygon2D objects, so each outline may have 1 or more holes. (In fact, the mapping is [string,list_of_gpolygons], so you can actually keep entire strings together if desired)

PolygonFont2d.CharacterInfo

PolyLine2d

PolyLine2DCurve

Wrapper for a PolyLine2d that provides minimal IParametricCurve2D interface

PolyLine3d

PolySimplification2

2D Polyline/Polygon simplification.

This is a more complex approach than Polygon.Simplify(), which uses sequential vtx clustering and then runs douglas-peucker algorithm. That method can end up modifying long straight segments, which is not ideal in many contexts (eg manufacturing).

Strategy here is : 1) find runs of vertices that are very close to straight lines (default 0.01mm deviation tol) 2) find all straight segments longer than threshold distance (default 2mm) 3) discard vertices that deviate less than tolerance (default = 0.2mm) from sequential-points-segment, unless they are required to preserve straight segments

[TODO] currently doing greedy search in 1,3. Could do more optimal search. [TODO] currently measuring deviation of p1...pN-1 from line [p0,pN] for points [p0,p1,...pN]. could alternately fit best segment to p1...pN (p0 is already fixed). [TODO] 2d variant of variational shape segmentation?

ProgressCancel

This class is intended to be passed to long-running computes to 1) provide progress info back to caller (not implemented yet) 2) allow caller to cancel the computation

PuncturedDiscGenerator

QuadraticFit2

Query2d

Query2Int64

2D queries for integer coordinates. Note that input Vector2d values are directly cast to int64 - you must scale them to suitable coordinates yourself!

QueryBase

Port of WildMagic5 Query class

QueryTuple2d

Radial3DArrowGenerator

RayIntersection

ReadOptions

Reducer

RefCountVector

RefCountedVector is used to keep track of which indices in a linear index list are in use/referenced. A free list is tracked so that unreferenced indices can be re-used.

The enumerator iterates over valid indices (ie where refcount > 0)

refcounts are shorts so the maximum count is 65536. No overflow checking is done in release builds.

RegionOperator

This class automatically extracts a submesh from a mesh, and can re-insert it after you have edited it, as long as you have not messed up the boundary

[TODO] Nearly all the code here is duplicated from RegionRemesher. Maybe this could be a base class for that? [TODO] ReinsertSubToBaseMapT is not returned by the MeshEditor.ReinsertSubmesh, instead we are trying to guess it here, by making some assumptions about what happens. It works for now, but it would better if MeshEditor returned this information.

RegionRemesher

RemapItr<T, T2>

Iterator that re-maps iterated values via a Func

Remesher

RemoveTrianglesMeshChange

Remove triangles from mesh and store necessary data to be able to reverse the change. Vertex and Triangle IDs will be restored on Revert() Currently does not restore the same EdgeIDs

RoundRectGenerator

SafeListBuilder<T>

SampledArcLengthParam

SampledArcLengthParam2d

ScalarMap

Scalar version of a ColorMap (ie interpolate between sample points) [TODO] could we make this a template?

SculptCurveDeformation

Base-class for DCurve3 spatial deformations. Subclasses must implement abstract Apply() method.

SculptCurveMove

SculptCurveSmooth

Segment2dBox

SegmentHashGrid2d<T>

Hash Grid for 2D segments. You provide the 'segment' type. If you have an indexable set of segments this can just be int, or can be more complex segment data structure (but be careful w/ structs...)

Segments are stored in the grid cell that contains the segment center. We keep track of the extent of the longest segment that has been added. The search radius for distance queries is expanded by this extent.

So, distance queries ARE NOT EFFICIENT if you even one very long segment. [TODO] make a multi-level hash

Does not actually store 2D segments. So, to remove a segment you must also know it's 2D center, so we can look up the cell coordinates. Hence, to 'update' a segment, you need to know both it's old and new 2D centers.

SegmentSet2d

SequentialProjectionTarget

SetVerticesMeshChange

Mesh change for full-mesh vertex deformations - more efficient than ModifyVerticesMeshChange. Note that this does not enforce that vertex count does not change!

ShiftIndexMap

SimpleHoleFiller

SimpleMesh

SimpleMeshBuilder

SimpleQuadMesh

SimpleTriangleMesh but for quads. Data packed into buffers, no dynamics. Supports Per-Vertex Normals, Colors, UV, and Per-Quad Facegroup.

use static WriteOBJ() to save. No loading, for now.

SimpleStore

Utility class that is intended to support things like writing and reading test cases, etc. You can write out a test case in a single line, eg SimpleStore.Store(path, new object[] { TestMesh, VertexList, PlaneNormal, ... }) The object list will be binned into the relevant sublists automatically. Then you can load this data via: SimpleStore s = SimpleStore.Restore(path)

SingularValueDecomposition

Singular Value Decomposition of arbitrary matrix A Computes U/S/V of A = U * S * V^T

Useful Properties: S = square-roots of eigenvalues of A U = eigenvectors of A * A^T V = eigenvectors of A^T * A U * V^T = rotation matrix closest to A V * Inv(S) * U^T = psuedoinverse of A

U and/or V are rotation matrices but may also contain reflections Detection: det(U) or det(v) == -1 Removal: if ( det(U) == -1 ) { U *= -1; S *= -1 } if ( det(V) == -1 ) { V *= -1; S *= -1 } (right? seems to work)

SkeletalBlend3d

sum-blend

SkeletalRicciBlend3d

Ricci blend

SkeletalRicciNaryBlend3d

Boolean Union of N implicit functions, A OR B. Assumption is that both have surface at zero isocontour and negative is inside.

SmallListSet

SmallListSet stores a set of short integer-valued variable-size lists. The lists are encoded into a few large DVector buffers, with internal pooling, so adding/removing lists usually does not involve any new or delete ops.

The lists are stored in two parts. The first N elements are stored in a linear subset of a dvector. If the list spills past these N elements, the extra elements are stored in a linked list (which is also stored in a flat array).

Each list stores its count, so list-size operations are constant time. All the internal "pointers" are 32-bit.

Snapping

SparseList<T>

SparseObjectList<T>

variant of SparseList for class objects, then "zero" is null

TODO: can we combine these classes somehow?

SparseSymmetricCG

SparseSymmetricCGMultipleRHS

[RMS] this is a variant of SparseSymmetricCG that supports multiple right-hand-sides. Makes quite a big difference as matrix gets bigger, because MultiplyF can unroll inner loops (as long as you actually do that)

However, if this is done then it is not really possible to do different numbers of iterations for different RHS's. We will not update that RHS once it has converged, however we still have to do the multiplies!

SpatialFunctions

SpatialFunctions.NormalOffset

Sphere3Generator_NormalizedCube

Generate a mesh of a sphere by first generating a mesh of a cube, and then normalizing the vertices and moving them to sphere of desired radius.

SphericalFibonacciPointSet

A Spherical Fibonacci Point Set is a set of points that are roughly evenly distributed on a sphere. Basically the points lie on a spiral, see pdf below. The i-th SF point of an N-point set can be calculated directly. For a given (normalized) point P, finding the nearest SF point (ie mapping back to i) can be done in constant time.

math from http://lgdv.cs.fau.de/uploads/publications/spherical_fibonacci_mapping_opt.pdf

StandardMeshReader

StandardMeshWriter

Writes various mesh file formats. Format is determined from extension. Currently supports:

.obj : Wavefront OBJ Format https://en.wikipedia.org/wiki/Wavefront_.obj_file
.stl : ascii and binary STL formats https://en.wikipedia.org/wiki/STL_(file_format)
.off : OFF format https://en.wikipedia.org/wiki/OFF_(file_format)
.g3mesh : internal binary format for packed DMesh3 objects

Each of these is implemented in a separate Writer class, eg OBJWriter, STLWriter, etc

StandardSculptCurveDeformation

STLFormatReader

STLReader

STLReader.STLSolid

STLWriter

StringTagSet<T>

Basic object->string mapping

SVGWriter

SymmetricEigenSolver

SymmetricSparseMatrix

Basic sparse-symmetric-matrix class. Stores upper-triangular portion. Uses Dictionary as sparsifying data structure, which is probably not a good option. But it is easy.

TilingUtil

TransformedIntersectionTarget

TransformedMeshProjectionTarget

Extension of MeshProjectionTarget that allows the target to have a transformation relative to it's internal space. Call SetTransform(), or initialize the transforms yourself

TransformSequence

TransformSequence stores an ordered list of basic transformations. This can be useful if you need to construct some modifications and want to use the same set later. For example, if you have a hierarchy of objects with relative transformations and want to "save" the nested transform sequence without having to hold references to the original objects.

Use the Append() functions to add different transform types, and the TransformX() to apply the sequence

TransformSequence2

Use the Append() functions to add different transform types, and the TransformX() to apply the sequence

TriangleBinsGrid2d

This class is a spatial data structure for 2D triangles. It is intended for point-containment and box-overlap queries. It does not store the triangles, only indices, so you must pass in the triangle vertices to add/remove functions, similar to PointHashGrid2d.

However, unlike the hash classes, this one is based on a grid of "bins" which has a fixed size, so you must provide a bounding box on construction. Each triangle is inserted into every bin that it overlaps.

[TODO] currently each triangle is inserted into every bin that it's bounding box overlaps. Need conservative rasterization to improve this. Can implement by testing each bin bbox for intersection w/ triangle

TriangulatedPolygonGenerator

Triangulate a 2D polygon-with-holes by inserting it's edges into a meshed rectangle and then removing the triangles outside the polygon.

TrivialBox3Generator

Generate a minimal box

TrivialDiscGenerator

TrivialRectGenerator

TubeGenerator

Sweep a 2D Profile Polygon along a 3D Path. Supports closed and open paths, and capping open paths. However caps are triangulated using a fan around a center vertex (which you can set using CapCenter). If Polygon is non-convex, this will have foldovers. In that case, you have to triangulate and append it yourself.

If your profile curve does not contain the polygon bbox center, set OverrideCapCenter=true and set CapCenter to a suitable center point.

The output normals are currently set to those for a circular profile. Call MeshNormals.QuickCompute() on the output DMesh to estimate proper vertex normals

Units

Util

VectorArray2<T>

VectorArray2d

VectorArray2f

VectorArray3<T>

VectorArray3d

VectorArray3f

VectorArray3i

VectorArray4<T>

VerticalGeneralizedCylinderGenerator

VoxelSurfaceGenerator

Structs

Arrangement2d.Intersection

Arrangement2d.SegmentPoint

ArrayAlias<T>

AxisAlignedBox2d

AxisAlignedBox2f

AxisAlignedBox2i

AxisAlignedBox3d

AxisAlignedBox3f

AxisAlignedBox3i

Box2d

Box2f

Box3d

Box3f

Colorb

Colorf

ComplexEndpoint2d

ComplexSegment2d

CurveSample

CurveSample2d

DGraph.EdgeCollapseInfo

DGraph.EdgeSplitInfo

DGraph3Util.Curves

DMesh3.CompactInfo

DMesh3.EdgeCollapseInfo

DMesh3.EdgeFlipInfo

DMesh3.EdgeSplitInfo

DMesh3.MergeEdgesInfo

DMesh3.PokeTriangleInfo

DMeshAABBTree3.PointIntersection

DMeshAABBTree3.SegmentIntersection

DPolyLine2f.Edge

DPolyLine2f.Vertex

DVector<T>.DBlock

EdgeConstraint

Frame3f

FrameGridIndexer3

Map to/from grid coords, where grid is relative to frame coords/axes

GridLevelIndex

GridLevelIndex2

HashBuilder

Construct hash of multiple values using FNV hash (ish) http://www.isthe.com/chongo/tech/comp/fnv/

(should probably be using uint? but standard GetHashCode() returns int...)

Index2i

Index3i

Index4i

Interval1d

Interval1i

IntSequence

IList wrapper for an Interval1i, ie sequential list of integers

IntTagPair

integer type/value pair, packed into 32 bits - 8 for type, 24 for value

IOReadResult

IOWriteResult

LaplacianCurveDeformer.SoftConstraintV

LaplacianMeshDeformer.SoftConstraintV

LaplacianMeshSmoother.SoftConstraintV

Line2d

Line2f

Line3d

Line3f

LinearIntersection

returned by linear-primitive intersection functions

matrix_entry

Matrix3d

Matrix3f

MeshConnectedComponents.Component

MeshDecomposition.Component

MeshGenerator.CircularSection

MeshIsoCurves.GraphEdgeInfo

Information about edge of the computed Graph. mesh_tri is triangle ID of crossed triangle mesh_edges depends on case. EdgeEdge is [edgeid,edgeid], EdgeVertex is [edgeid,vertexid], and OnEdge is [edgeid,-1]

MeshMeasurements.GenusResult

MultigridIndexer2

map between "outer" (ie higher-res) grid coordinates and "blocks" of those coordinates.

MultigridIndexer3

map between "outer" (ie higher-res) grid coordinates and "blocks" of those coordinates.

NewVertexInfo

NTMesh3.EdgeSplitInfo

NTMesh3.PokeTriangleInfo

NURBSCurve2.CurveDerivatives

PackedSparseMatrix.nonzero

PlanarComplex.FindSolidsOptions

Plane3d

Plane3f

QuadricError

Stores quadratic function that evaluates distance to plane, in minimal 10-coefficient form, following http://mgarland.org/files/papers/qtheory.pdf

symmetric matrix A
vector b
constant c

Quaterniond

Quaternionf

Ray3d

Ray3f

Reducer.QEdge

ScaleGridIndexer2

Map to/from grid coords

ScaleGridIndexer3

Map to/from grid coords

SculptCurveDeformation.DeformInfo

Segment2d

Segment2f

Segment3d

Segment3f

SetGroupBehavior

ShiftGridIndexer2

Map to/from grid coords, where grid is translated from origin

ShiftGridIndexer3

Map to/from grid coords, where grid is translated from origin

SVGWriter.Style

Triangle2d

Triangle2f

Triangle3d

Triangle3f

Vector2d

Vector2d.Information

Vector2dTuple2

Vector2dTuple3

Vector2dTuple4

Vector2f

Vector2i

Vector2l

Vector3d

Vector3dTuple2

Vector3dTuple3

Vector3f

Vector3fTuple3

Vector3i

3D integer vector type. This is basically the same as Index3i but with .x.y.z member names. This makes code far more readable in many places. Unfortunately I can't see a way to do this w/o so much duplication...we could have .x/.y/.z accessors but that is much less efficient...