editor › Globals › HalfEdgeMeshImplementation
Class: HalfEdgeMeshImplementation
Implements a mesh using a half-edge data structure
Hierarchy
- HalfEdgeMeshImplementation
Implements
Index
Constructors
Properties
Methods
- _deduplicateProblematicPoints
- _findDisconnectedEdgesOnSurfaceRemoval
- _findVectorsToExistingMeshPoints
- _mapNewPositionToMeshPoint
- _replaceSurfacesWithPolygons
- clear
- getAllPoints
- getSurfaces
- hasSurface
- isEmpty
- isTwoManifold
- replaceSurfaces
- _assignTwins
- _createEdgesAndSurfaces
- _duplicateProblematicPoints
- _edgeToString
- _findOverlappingEdgesContainingPoint
- _fromPolygons
- _getHalfEdgesWithCollinearPoints
- _getNewCollinearEdge
- _mapVectorsToMeshPoints
- _traverseAroundPoint
- fromGeometricPrimitive
- fromPolygons
- splitUpUnconnectedGeometries
Constructors
constructor
+ new HalfEdgeMeshImplementation(surfaces: MeshSurface[], skipValidationChecks: boolean, mustBeManifold: boolean): HalfEdgeMeshImplementation
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:539
Constructs a half-edge mesh based on the provided surfaces.
Parameters:
| Name | Type | Default | Description |
|---|---|---|---|
surfaces |
MeshSurface[] | [] | the surfaces of the mesh representing a valid two-manifold mesh. If unsure, use HalfEdgeMeshImplementation.fromPolygons() or fromGeometricPrimitive(), as these methods already do a lot of fixing. |
skipValidationChecks |
boolean | false | if you are ABSOLUTELY sure that your surfaces are correct, you can skip the validation for increased performance. |
mustBeManifold |
boolean | true | whether or not to include a two-manifold check in the validations. |
Returns: HalfEdgeMeshImplementation
Properties
Private surfaces
• surfaces: readonly MeshSurface[] = []
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:539
Methods
Private _deduplicateProblematicPoints
▸ _deduplicateProblematicPoints(allMeshPoints: MeshPoint[]): void
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:708
Parameters:
| Name | Type |
|---|---|
allMeshPoints |
MeshPoint[] |
Returns: void
Private _findDisconnectedEdgesOnSurfaceRemoval
▸ _findDisconnectedEdgesOnSurfaceRemoval(surfaces: MeshSurface[]): MeshHalfEdge[]
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:789
Parameters:
| Name | Type |
|---|---|
surfaces |
MeshSurface[] |
Returns: MeshHalfEdge[]
Private _findVectorsToExistingMeshPoints
▸ _findVectorsToExistingMeshPoints(polygons: any): Map‹Vector3, MeshPoint›
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:738
For newly added positions in the mesh, find the corresponding meshPoint (possibly already existing or added here).
Parameters:
| Name | Type |
|---|---|
polygons |
any |
Returns: Map‹Vector3, MeshPoint›
Private _mapNewPositionToMeshPoint
▸ _mapNewPositionToMeshPoint(position: Vector3, vectorsToMeshPoints: Map‹Vector3, MeshPoint›, oldMeshPoints: MeshPoint[], positionEqualityDistance: number): void
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:749
Parameters:
| Name | Type | Default |
|---|---|---|
position |
Vector3 | - |
vectorsToMeshPoints |
Map‹Vector3, MeshPoint› | - |
oldMeshPoints |
MeshPoint[] | - |
positionEqualityDistance |
number | Config.get("modelLimits.maximumPositionEqualityDistance", 0.005) |
Returns: void
Private _replaceSurfacesWithPolygons
▸ _replaceSurfacesWithPolygons(surfacesToPolygons: Map‹MeshSurface, Vector3[][]›, polygonsToSurfaceIds: Map‹Vector3[][], string›, polygonsToEdgeIds: Map‹Vector3[][], string[][]›, allSurfacesToRemove: MeshSurface[], fixPolygons: boolean, mustBeManifold: boolean): HalfEdgeMeshImplementation[]
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:642
Parameters:
| Name | Type | Default |
|---|---|---|
surfacesToPolygons |
Map‹MeshSurface, Vector3[][]› | - |
polygonsToSurfaceIds |
Map‹Vector3[][], string› | - |
polygonsToEdgeIds |
Map‹Vector3[][], string[][]› | - |
allSurfacesToRemove |
MeshSurface[] | [] |
fixPolygons |
boolean | false |
mustBeManifold |
boolean | true |
Returns: HalfEdgeMeshImplementation[]
clear
▸ clear(): void
Implementation of IMeshImplementation
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:590
Returns: void
getAllPoints
▸ getAllPoints(): Set‹MeshPoint›
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:597
Collects all points used by surfaces
getSurfaces
▸ getSurfaces(): readonly MeshSurface[]
Implementation of IMeshImplementation
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:578
Returns: readonly MeshSurface[]
hasSurface
▸ hasSurface(surface: MeshSurface): boolean
Implementation of IMeshImplementation
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:586
Parameters:
| Name | Type |
|---|---|
surface |
MeshSurface |
Returns: boolean
isEmpty
▸ isEmpty(): boolean
Implementation of IMeshImplementation
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:582
Returns: boolean
isTwoManifold
▸ isTwoManifold(): boolean
Implementation of IMeshImplementation
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:569
Returns: boolean
replaceSurfaces
▸ replaceSurfaces(surfacesToPolygons: Map‹MeshSurface, Vector3[][]›, polygonsToSurfaceIds: Map‹Vector3[][], string›, polygonsToEdgeIds: Map‹Vector3[][], string[][]›, allSurfacesToRemove: MeshSurface[], fixPolygons: boolean, mustBeManifold: boolean): HalfEdgeMeshImplementation[]
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:614
Constructs new surfaces. For each surface there must be exactly one new polygon. Ids are kept equal, so all anchors stay.
Parameters:
| Name | Type | Default | Description |
|---|---|---|---|
surfacesToPolygons |
Map‹MeshSurface, Vector3[][]› | - | - |
polygonsToSurfaceIds |
Map‹Vector3[][], string› | new Map |
- |
polygonsToEdgeIds |
Map‹Vector3[][], string[][]› | new Map |
- |
allSurfacesToRemove |
MeshSurface[] | [] | - |
fixPolygons |
boolean | false | whether to filter degenerated polygons before constructing. If this is true, the id replacement maps will be invalid, so take care of it yourself if you want both and set it here to false |
mustBeManifold |
boolean | true | whether or not errors should be thrown for unmatched edges |
Returns: HalfEdgeMeshImplementation[]
Static Private _assignTwins
▸ _assignTwins(allHalfEdges: MeshHalfEdge[], maxCollinearTries: number, mustBeManifold: boolean): MeshHalfEdge[]
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:281
Finds and assigns matching twin HalfEdges. If there are multiple candidates (e.g. two boxels touching along a shared edge), these cases are resolved by preferring producing convex geometry.
Parameters:
| Name | Type | Default | Description |
|---|---|---|---|
allHalfEdges |
MeshHalfEdge[] | - | - |
maxCollinearTries |
number | 0 | the maximum recursion depth. One fix can create new edges which have no partner themselves. If > 0 we try to find another edge which overlaps an edge which has no partner and split this edge in two parts so that the edge has a partner. Used in CSG Server. |
mustBeManifold |
boolean | true | whether or not errors should be thrown for unmatched edges |
Returns: MeshHalfEdge[]
Static Private _createEdgesAndSurfaces
▸ _createEdgesAndSurfaces(vectorsToPoints: Map‹ReadonlyVector3, MeshPoint›, polygons: ReadonlyVectorPolygon3D[], polygonsToSurfaceIds?: Map‹ReadonlyVectorPolygon3D, string›, polygonsToEdgeIds?: Map‹ReadonlyVectorPolygon3D, string[][]›): object
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:145
Creates edges and surfaces based on the given polygons and a map of which MeshPoint to use for which vector. Does not link edge's twins yet.
Parameters:
| Name | Type |
|---|---|
vectorsToPoints |
Map‹ReadonlyVector3, MeshPoint› |
polygons |
ReadonlyVectorPolygon3D[] |
polygonsToSurfaceIds? |
Map‹ReadonlyVectorPolygon3D, string› |
polygonsToEdgeIds? |
Map‹ReadonlyVectorPolygon3D, string[][]› |
Returns: object
-
allHalfEdges: MeshHalfEdge[]
-
allSurfaces: MeshSurface[]
Static Private _duplicateProblematicPoints
▸ _duplicateProblematicPoints(allHalfEdges: MeshHalfEdge[], allPoints: MeshPoint[]): void
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:454
In some cases, geometries might share points even though they are not connected (e.g. two boxels touching at an edge will initially share the two point instances even though they are conceptually separate).
This methods duplicates those point instances to restore two-manifoldness and to allow splitting up unconnected geometries.
Parameters:
| Name | Type |
|---|---|
allHalfEdges |
MeshHalfEdge[] |
allPoints |
MeshPoint[] |
Returns: void
Static Private _edgeToString
▸ _edgeToString(halfEdge: MeshHalfEdge): string
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:535
Pretty-prints a half edge (for debug purposes)
Parameters:
| Name | Type |
|---|---|
halfEdge |
MeshHalfEdge |
Returns: string
Static Private _findOverlappingEdgesContainingPoint
▸ _findOverlappingEdgesContainingPoint(point: ReadonlyVector3, candidates: MeshHalfEdge[], direction: Vector3): MeshHalfEdge[]
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:251
Containing means in this context that the point lies somewhere in the middle and that it is explicitly not the start or end point.
Parameters:
| Name | Type | Description |
|---|---|---|
point |
ReadonlyVector3 | - |
candidates |
MeshHalfEdge[] | - |
direction |
Vector3 | the direction the overlapping edge must have. Should be exactly inverse. |
Returns: MeshHalfEdge[]
Static Private _fromPolygons
▸ _fromPolygons(polygons: ReadonlyVectorPolygon3D[], positionEqualityDistance: number, options: IFromPolygonsOptions): HalfEdgeMeshImplementation[]
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:110
Parameters:
| Name | Type |
|---|---|
polygons |
ReadonlyVectorPolygon3D[] |
positionEqualityDistance |
number |
options |
IFromPolygonsOptions |
Returns: HalfEdgeMeshImplementation[]
Static Private _getHalfEdgesWithCollinearPoints
▸ _getHalfEdgesWithCollinearPoints(unmatchedEdges: MeshHalfEdge[], allEdges: MeshHalfEdge[]): MeshHalfEdge[]
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:379
Parameters:
| Name | Type |
|---|---|
unmatchedEdges |
MeshHalfEdge[] |
allEdges |
MeshHalfEdge[] |
Returns: MeshHalfEdge[]
Static Private _getNewCollinearEdge
▸ _getNewCollinearEdge(start: MeshPoint, previousEdge: MeshHalfEdge, surface: MeshSurface): MeshHalfEdge
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:435
Construct a new collinear edge behind the overlapping edge so that the overlapping edge now either ends at the current start / end point of the unmatched edge.
Parameters:
| Name | Type |
|---|---|
start |
MeshPoint |
previousEdge |
MeshHalfEdge |
surface |
MeshSurface |
Returns: MeshHalfEdge
Static Private _mapVectorsToMeshPoints
▸ _mapVectorsToMeshPoints(polygons: ReadonlyVectorPolygon3D[], positionEqualityDistance: any): Map‹ReadonlyVector3, MeshPoint›
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:212
Parameters:
| Name | Type |
|---|---|
polygons |
ReadonlyVectorPolygon3D[] |
positionEqualityDistance |
any |
Returns: Map‹ReadonlyVector3, MeshPoint›
Static Private _traverseAroundPoint
▸ _traverseAroundPoint(edge: MeshHalfEdge): MeshHalfEdge[]
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:508
Given the origin point of the provided edge, traverses adjacent edges and returns all halfEdges that leave the given point but are interconnected via surfaces.
Traversion is counter-clockwise, meaning that for a leaving edge, it's predecessor's twin is also leaving that point and will be enumerated next.
If there exists no interconnected surface, for example if an outgoing edge is non-manifold, returns an empty array.
Parameters:
| Name | Type |
|---|---|
edge |
MeshHalfEdge |
Returns: MeshHalfEdge[]
Static fromGeometricPrimitive
▸ fromGeometricPrimitive(primitive: object, positionEqualityDistance: number, mustBeManifold: boolean): HalfEdgeMeshImplementation[]
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:30
Reconstructs a mesh from a GeometricPrimitive. Assumes that a GeoemtricPrimitive only defines one mesh with its surfaces and points.
Parameters:
▪ primitive: object
| Name | Type |
|---|---|
getSurfaces |
function |
▪Default value positionEqualityDistance: number= Config.get("modelLimits.maximumPositionEqualityDistance", 0.005)
▪Default value mustBeManifold: boolean= true
Returns: HalfEdgeMeshImplementation[]
Static fromPolygons
▸ fromPolygons(polygons: ReadonlyVectorPolygon3D[], positionEqualityDistance: number, options: IFromPolygonsOptions): HalfEdgeMeshImplementation[]
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:57
Reconstructs mesh(es) from an array of ServerCSG-styled polygons. During the process, merges points at the same position and links edges. As points are deduplicated by position, uses an additional heuristic to keep meshes two-manifold by duplicating points at the same position (e,g, if two boxels share an edge with the same point instances, but are technically unconnected, these points are duplicated for each boxel).
Parameters:
| Name | Type | Default | Description |
|---|---|---|---|
polygons |
ReadonlyVectorPolygon3D[] | - | the polygons to create the surfaces from (first array is the outline, following arrays are holes). The instance will have the surfaces ordered the same way the polygons were specified, if only one mesh is defined by the polygons. |
positionEqualityDistance |
number | Config.get("modelLimits.maximumPositionEqualityDistance", 0.005) | distance below which two points are considered equal and are represented as one MeshPoint |
options |
IFromPolygonsOptions | { | |
| maxCollinearTries: 0, | |||
| fixPolygons: false, | |||
| skipPolygonValidationChecks: false, | |||
| mustBeManifold: true, | |||
| } | - |
Returns: HalfEdgeMeshImplementation[]
all meshes reconstructed from the polygons. If there are multiple unconnected groups of surfaces, each group is exported as a separate mesh.
Static splitUpUnconnectedGeometries
▸ splitUpUnconnectedGeometries(surfaces: readonly MeshSurface[]): MeshSurface[][]
Defined in src/model/data/Concepts/Mesh/HalfEdgeMeshImplementation.ts:85
Splits up unconnected (= surfaces are not connected through any edge) geometries into individual arrays
Parameters:
| Name | Type | Description |
|---|---|---|
surfaces |
readonly MeshSurface[] | the surfaces need to be closed under the edge.getTwin() operation which leads to another surface |
Returns: MeshSurface[][]