mtk

package module
v0.1.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 5, 2024 License: MIT Imports: 15 Imported by: 0

README

Mesh Tool Kit (mtk)

Mesh tool kit for polygonal mesh processing.

Go Reference

Quickstart

mtk is primarily intended for reading/writing polygonal surface meshes as well as performing minor modifications (like zipping open edges and orienting faces). Additionally, the library supports spatial indexing for fast retrieval of intersecting entities.

While a minimal polygon soup mesh is implemented, it is recommended to use the half edge mesh data structure HEMesh. The half edge mesh data structure only supports manifold surface meshes and will return an error upon import if a non-manifold mesh is provided. Below is an example of some common use cases of a half edge mesh.

package main

import (
  "fmt"

  "github.com/ajcurley/mtk"
)

func main() {
  path := "/some/path/to/model.obj" // also supports .obj.gz
  mesh, err := mtk.NewHEMeshFromOBJFile(path)

  if err != nil {
    panic(err)
  }

  // Print out a basic summary of the contents
  fmt.Printf("Mesh summary:\n")
  fmt.Printf("Number of vertices:   %d", mesh.GetNumberOfVertices())
  fmt.Printf("Number of faces:      %d", mesh.GetNumberOfFaces())
  fmt.Printf("Number of half edges: %d", mesh.GetNumberOfHalfEdges())
  fmt.Printf("Number of patches:    %d", mesh.GetNumberOfPatches())

  // Check if the mesh has any open edges
  if !mesh.IsClosed() {
    fmt.Println("Open edges found! Fixing them now.")

    // Zip any open edges. This may result in a non-manifold mesh if three faces
    // with open edges collapse into a single edge.
    if err := mesh.ZipEdges(); err != nil {
      panic(err)
    }
  }

  // Check if the mesh has any inconsistently oriented faces
  if !mesh.IsConsistent() {
    fmt.Println("Inconsistent faces found! Fixing them now.")

    // Orient the mesh such that the faces of each connected component are the
    // same. Note: for meshes with multiple independent components, the orientation
    // of each component may be different.
    mesh.Orient()
  }

  // Extract a subset of the mesh. In this case, we subset using patch names; however,
  // we could subset by a list of face IDs.
  patchNames := []string{"patch1", "patch2"}
  submesh := mesh.ExtractPatchNames(patchNames)

  // Write the submesh to an OBJ file (also supports .obj.gz)
  submesh.ExportOBJFile("/path/to/some/output.obj")
}

Spatial Indexing

mtk supports spatial indexing using a linear octree data structure. The Octree type implements three main methods: Insert, Query, and QueryMany among other helpful methods. QueryMany uses the available number of CPU by default.

One or more geometries types may be inserted into a single octree. When performing a query, only the types implementing the appropriate interface for the query geometry can be returned.

Example: Index a triangle mesh from OBJ in an octree

func main() {
  // Import the mesh. This supports both `.obj` and `.obj.gz` extensions.
  mesh, _ := NewHEMeshFromOBJFile("./some_mesh.obj.gz")

  // Create the bounded octree
  bounds := mesh.GetBounds()
  octree := NewOctree(bounds)

  // Insert each face into the octree
  for i := 0; i < mesh.GetNumberOfFaces(); i++ {
    vertices := mesh.GetFaceVertices(i)

    // Check that the face is a triangle since the HEMesh supports polygon elements
    // but collision detection is only implemented for triangles.
    if len(vertices) != 3 {
      triangle := NewTriangle(vertices[0].Origin, vertices[1].Origin, vertices[2].Origin)
      octree.Insert(triangle)
    }
  }

  // Query for all faces intersecting the AABB. In this case, the AABB is centered
  // at the origin (0, 0, 0) and ranges from (-0.5, -0.5, -0.5) to (0.5, 0.5, 0.5)
  center := NewVector3(0, 0, 0)
  halfSize := NewVector3(0.5, 0.5, 0.5)
  query := NewAABB(center, halfSize)

  // Get the list of item IDs intersecting the AABB
  results := octree.Query(query) 
}

Example: Find all points within a radius

func findPointsInside(octree *mtk.Octree, loc Vector3) []Vector3 {
  // Given an octree indexing many Vector3 items, search for all points within
  // 1e-3 distance of the a query location.
  query := NewSphere(loc, 1e-3)
  items := make([]Vector3)

  for i, index := range octree.Query(query) {
    // Cast the item to the appropriate type
    if item, ok := octree.GetItem(index).(Vector3) {
      items = append(items, item)
    }
  }

  return items
}

Collision Detection

The following interfaces are used for collision detection between geometric types. The table below shows which interfaces are currently implemented by each geometric type.

  • IntersectsVector3(Vector3) bool
  • IntersectsRay(Ray) bool
  • IntersectsSphere(Sphere) bool
  • IntersectsAABB(AABB) bool
  • IntersectsTriangle(Triangle) bool
Vector3 Ray Sphere AABB Triangle
Vector3 ✔ ✔
Ray ✔ ✔
Sphere ✔ ✔
AABB ✔ ✔ ✔ ✔ ✔
Triangle ✔ ✔

Issues

Help improve this library by reporting issues

License

mtk is licensed under the MIT License

Documentation

Index

Constants

View Source 
const (
	OctreeMaxDepth        int = 21
	OctreeMaxItemsPerNode int = 100
)
View Source 
const (
	GeometricTolerance float64 = 1e-8
)

Variables

View Source 
var (
	ErrNonManifoldMesh = errors.New("non-manifold mesh")
	ErrOpenMesh        = errors.New("mesh must be closed")
)
View Source 
var (
	ErrInvalidVertex = errors.New("invalid vertex")
	ErrInvalidFace   = errors.New("invalid face")
)

Functions

This section is empty.

Types

type AABB 

type AABB struct {
	Center   Vector3
	HalfSize Vector3
}

Three dimensional Cartesian axis-aligned bounding box

func NewAABB 

func NewAABB(center, halfSize Vector3) AABB

Construct an AABB from its min/max bounds

func (AABB) Buffer 

func (a AABB) Buffer(r float64) AABB

Get the buffered AABB

func (AABB) IntersectsAABB 

func (a AABB) IntersectsAABB(b AABB) bool

Check for an intersection with an AABB

func (AABB) IntersectsRay 

func (a AABB) IntersectsRay(r Ray) bool

Check for an intersection with a Ray

func (AABB) IntersectsSphere 

func (a AABB) IntersectsSphere(s Sphere) bool

Check for an intersection with a Sphere

func (AABB) IntersectsTriangle 

func (a AABB) IntersectsTriangle(t Triangle) bool

Check for an intersection with a Triangle

func (AABB) IntersectsVector3 

func (a AABB) IntersectsVector3(v Vector3) bool

Check for an intersection with a Vector3

func (AABB) Max 

func (a AABB) Max() Vector3

Get the max bound

func (AABB) Min 

func (a AABB) Min() Vector3

Get the min bounds

func (AABB) Octant 

func (a AABB) Octant(octant int) AABB

Get the AABB representing the octant

type HEFace 

type HEFace struct {
	HalfEdge int
	Patch    int
}

Half edge mesh face

type HEHalfEdge 

type HEHalfEdge struct {
	Origin int
	Face   int
	Prev   int
	Next   int
	Twin   int
}

Half edge mesh half edge

func (HEHalfEdge) IsBoundary 

func (e HEHalfEdge) IsBoundary() bool

Get if the half edge is a boundary (no twin)

type HEMesh 

type HEMesh struct {
	// contains filtered or unexported fields
}

func NewHEMeshFromOBJ 

func NewHEMeshFromOBJ(reader io.Reader) (*HEMesh, error)

Construct a half edge mesh from an OBJ file reader

func NewHEMeshFromOBJFile 

func NewHEMeshFromOBJFile(path string) (*HEMesh, error)

Construct a half edge mesh from an OBJ file

func NewHEMeshFromPolygonSoup 

func NewHEMeshFromPolygonSoup(soup *PolygonSoup) (*HEMesh, error)

Construct a half edge mesh from a PolygonSoup

func (*HEMesh) ExportOBJ 

func (m *HEMesh) ExportOBJ(w io.Writer) error

Export the mesh to OBJ

func (*HEMesh) ExportOBJFile 

func (m *HEMesh) ExportOBJFile(path string) error

Export the mesh to an OBJ file

func (*HEMesh) ExtractFaces 

func (m *HEMesh) ExtractFaces(ids []int) (*HEMesh, error)

Extract a subset of the mesh by face IDs

func (*HEMesh) ExtractPatchNames 

func (m *HEMesh) ExtractPatchNames(names []string) (*HEMesh, error)

Extract a subset of the mesh by patch names

func (*HEMesh) ExtractPatches 

func (m *HEMesh) ExtractPatches(ids []int) (*HEMesh, error)

Extract a subset of the mesh by patch IDs

func (*HEMesh) GetBounds 

func (m *HEMesh) GetBounds() AABB

Compute the axis-aligned bounding box

func (*HEMesh) GetComponents 

func (m *HEMesh) GetComponents() [][]int

Get the distinct components (connected faces). Each component is defined by the indices of the faces.

func (*HEMesh) GetFace 

func (m *HEMesh) GetFace(id int) HEFace

Get the face by ID

func (*HEMesh) GetFaceHalfEdges 

func (m *HEMesh) GetFaceHalfEdges(id int) []int

Get the half edges of the face by ID

func (*HEMesh) GetFaceNeighbors 

func (m *HEMesh) GetFaceNeighbors(id int) []int

Get the neighboring faces for a face by ID

func (*HEMesh) GetFaceNormal 

func (m *HEMesh) GetFaceNormal(id int) Vector3

Get the unit normal vector of the face by ID

func (*HEMesh) GetFaceVertices 

func (m *HEMesh) GetFaceVertices(id int) []int

Get the vertices defining the face by ID

func (*HEMesh) GetHalfEdge 

func (m *HEMesh) GetHalfEdge(id int) HEHalfEdge

Get the half edge by ID

func (*HEMesh) GetNumberOfFaces 

func (m *HEMesh) GetNumberOfFaces() int

Get the number of faces

func (*HEMesh) GetNumberOfHalfEdges 

func (m *HEMesh) GetNumberOfHalfEdges() int

Get the number of half edges

func (*HEMesh) GetNumberOfPatches 

func (m *HEMesh) GetNumberOfPatches() int

Get the number of patches

func (*HEMesh) GetNumberOfVertices 

func (m *HEMesh) GetNumberOfVertices() int

Get the number of vertices

func (*HEMesh) GetPatch 

func (m *HEMesh) GetPatch(id int) HEPatch

Get the patch by ID

func (*HEMesh) GetPatchFaces 

func (m *HEMesh) GetPatchFaces(id int) []int

Get the faces assigned to the patch by ID

func (*HEMesh) GetPatchNames 

func (m *HEMesh) GetPatchNames() []string

Get the list of patch names

func (*HEMesh) GetVertex 

func (m *HEMesh) GetVertex(id int) HEVertex

Get the vertex by ID

func (*HEMesh) GetVertexCurvature 

func (m *HEMesh) GetVertexCurvature(id int) (float64, error)

Get the Gaussian curvature at the vertex by ID. This assumes the mesh is composed of strictly triangular elements and is oriented.

func (*HEMesh) GetVertexFaces 

func (m *HEMesh) GetVertexFaces(id int) []int

Get the faces using the vertex by ID

func (*HEMesh) GetVertexNeighbors 

func (m *HEMesh) GetVertexNeighbors(id int) []int

Get the neighboring vertices for a vertex by ID

func (*HEMesh) IsClosed 

func (m *HEMesh) IsClosed() bool

Check if the half edge mesh is closed (no open boundaries)

func (*HEMesh) IsConsistent 

func (m *HEMesh) IsConsistent() bool

Check if the half edge mesh has consistently oriented faces

func (*HEMesh) IsVertexOnBoundary 

func (m *HEMesh) IsVertexOnBoundary(id int) bool

Get if the vertex is on a boundary. This assumes the mesh is consistently oriented. For inconsistent meshes, this may yield incorrect results.

func (*HEMesh) Merge 

func (m *HEMesh) Merge(other *HEMesh)

Naively copy another half edge mesh into the current. This does not merge any duplicate vertices or faces.

func (*HEMesh) Orient 

func (m *HEMesh) Orient()

Orient the mesh such that the faces of each distinct component share the same normal vector orientaton. This does not guarantee that all components will have the same orientation.

func (*HEMesh) ZipEdges 

func (m *HEMesh) ZipEdges() error

Zip open edges by merging vertices within the geometric tolerance and are on edges without a twin.

type HEPatch 

type HEPatch struct {
	Name string
}

Half edge mesh patch

type HEVertex 

type HEVertex struct {
	Origin   Vector3
	HalfEdge int
}

Half edge mesh vertex

type IntersectsAABB 

type IntersectsAABB interface {
	IntersectsAABB(AABB) bool
}

Interface for an AABB intersection test

type IntersectsRay 

type IntersectsRay interface {
	IntersectsRay(Ray) bool
}

Interface for a Ray intersection test

type IntersectsSphere 

type IntersectsSphere interface {
	IntersectsSphere(Sphere) bool
}

Interface for a Sphere intersection test

type IntersectsTriangle 

type IntersectsTriangle interface {
	IntersectsTriangle(Triangle) bool
}

Interface for a Triangle intersection test

type IntersectsVector3 

type IntersectsVector3 interface {
	IntersectsVector3(Vector3) bool
}

Interface for a Vector3 intersection test

type OBJReader 

type OBJReader struct {
	// contains filtered or unexported fields
}

func NewOBJReader 

func NewOBJReader() *OBJReader

func (*OBJReader) Read 

func (r *OBJReader) Read(reader io.Reader) (*PolygonSoup, error)

Read an OBJ file from an io.Reader interface

func (*OBJReader) ReadFile 

func (r *OBJReader) ReadFile(path string) (*PolygonSoup, error)

Read an OBJ file from path

type OBJWriter 

type OBJWriter struct {
	// contains filtered or unexported fields
}

Write an OBJ file to an io.Writer interface

func NewOBJWriter 

func NewOBJWriter() *OBJWriter

func (*OBJWriter) SetFaceGroups 

func (w *OBJWriter) SetFaceGroups(faceGroups []int)

Set the groups of each face to write. This must be the same length as the faces. Any faces that are not assigned to a group must specify -1.

func (*OBJWriter) SetFaces 

func (w *OBJWriter) SetFaces(faces [][]int)

Set the faces to write

func (*OBJWriter) SetGroups 

func (w *OBJWriter) SetGroups(groups []string)

Set the groups to write

func (*OBJWriter) SetLines 

func (w *OBJWriter) SetLines(lines [][]int)

Set the lines to write

func (*OBJWriter) SetVertices 

func (w *OBJWriter) SetVertices(vertices []Vector3)

Set the vertices to write

func (*OBJWriter) Write 

func (w *OBJWriter) Write(writer io.Writer) error

Write the mesh to the io.Writer interface

type Octree 

type Octree struct {
	// contains filtered or unexported fields
}

Linear octree implementation

func NewOctree 

func NewOctree(bounds AABB) *Octree

Construct an Octree indexing items

func (*Octree) GetItem 

func (o *Octree) GetItem(id int) IntersectsAABB

Get an item by ID

func (*Octree) GetNumberOfItems 

func (o *Octree) GetNumberOfItems() int

Get the number of indexed items

func (*Octree) Insert 

func (o *Octree) Insert(item IntersectsAABB) (int, bool)

Insert an item into the octree

func (*Octree) Query 

func (o *Octree) Query(query IntersectsAABB) []int

Query the octree for intersecting items

func (*Octree) QueryMany 

func (o *Octree) QueryMany(queries []IntersectsAABB) [][]int

Query the octree for many intersecting items in parallel using the available number of processors.

func (*Octree) Split 

func (o *Octree) Split(code uint64)

Split an octree node

type PolygonSoup 

type PolygonSoup struct {
	// contains filtered or unexported fields
}

func NewPolygonSoup 

func NewPolygonSoup() *PolygonSoup

func (*PolygonSoup) GetFace 

func (m *PolygonSoup) GetFace(id int) []int

Get a face's ordered set of vertices by face ID

func (*PolygonSoup) GetFacePatch 

func (m *PolygonSoup) GetFacePatch(id int) int

Get a face's patch by face ID

func (*PolygonSoup) GetNumberOfFaces 

func (m *PolygonSoup) GetNumberOfFaces() int

Get the number of faces

func (*PolygonSoup) GetNumberOfPatches 

func (m *PolygonSoup) GetNumberOfPatches() int

Get the number of patches

func (*PolygonSoup) GetNumberOfVertices 

func (m *PolygonSoup) GetNumberOfVertices() int

Get the number of vertices

func (*PolygonSoup) GetPatch 

func (m *PolygonSoup) GetPatch(id int) string

Get a patch by ID

func (*PolygonSoup) GetVertex 

func (m *PolygonSoup) GetVertex(id int) Vector3

Get a vertex by ID

func (*PolygonSoup) InsertFace 

func (m *PolygonSoup) InsertFace(vertices []int) int

Insert a face. By default, the patch is empty.

func (*PolygonSoup) InsertFaceWithPatch 

func (m *PolygonSoup) InsertFaceWithPatch(vertices []int, patch int) int

Insert a face with a patch

func (*PolygonSoup) InsertPatch 

func (m *PolygonSoup) InsertPatch(name string) int

Insert a patch

func (*PolygonSoup) InsertVertex 

func (m *PolygonSoup) InsertVertex(vertex Vector3) int

Insert a vertex

type Ray 

type Ray struct {
	Origin    Vector3
	Direction Vector3
}

Three dimension Cartesian ray

func NewRay 

func NewRay(origin, direction Vector3) Ray

Construct a Ray from its origin and direction

func (Ray) IntersectsAABB 

func (r Ray) IntersectsAABB(a AABB) bool

Check for an intersection with an AABB

func (Ray) IntersectsTriangle 

func (r Ray) IntersectsTriangle(t Triangle) bool

Check for an intersection with a Triangle

type Sphere 

type Sphere struct {
	Center Vector3
	Radius float64
}

Three-dimensional Cartesian sphere

func NewSphere 

func NewSphere(center Vector3, radius float64) Sphere

Construct a Sphere from its center and radius

func (Sphere) IntersectsAABB 

func (s Sphere) IntersectsAABB(a AABB) bool

Check for an intersection with an AABB

func (Sphere) IntersectsVector3 

func (s Sphere) IntersectsVector3(v Vector3) bool

Check for an intersection with a Vector

type Triangle 

type Triangle [3]Vector3

Three dimensional Cartesian triangle

func NewTriangle 

func NewTriangle(p, q, r Vector3) Triangle

Construct a Triangle from its points

func (Triangle) Area 

func (t Triangle) Area() float64

Get the area

func (Triangle) Center 

func (t Triangle) Center() Vector3

Get the center

func (Triangle) IntersectsAABB 

func (t Triangle) IntersectsAABB(a AABB) bool

Check for an intersection with an AABB

func (Triangle) IntersectsRay 

func (t Triangle) IntersectsRay(r Ray) bool

Check for an intersection with a Ray

func (Triangle) Normal 

func (t Triangle) Normal() Vector3

Get the normal vector (not necessarily a unit vector)

func (Triangle) UnitNormal 

func (t Triangle) UnitNormal() Vector3

Get the unit normal vector

type Vector3 

type Vector3 [3]float64

Three-dimensional Cartesian vector

func NewVector3 

func NewVector3(x, y, z float64) Vector3

Construct a Vector3 from its components

func (Vector3) Add 

func (v Vector3) Add(u Vector3) Vector3

Elementwise vector addition v + u

func (Vector3) AddScalar 

func (v Vector3) AddScalar(s float64) Vector3

Elementwise vector/scalar addition v + s

func (Vector3) AngleTo 

func (v Vector3) AngleTo(u Vector3) float64

Get the angle (in radians) between the vectors

func (Vector3) Cross 

func (v Vector3) Cross(u Vector3) Vector3

Get the cross product v x

func (Vector3) Div 

func (v Vector3) Div(u Vector3) Vector3

Elementwise vector division v / u

func (Vector3) DivScalar 

func (v Vector3) DivScalar(s float64) Vector3

Elementwise vector/scalar division

func (Vector3) Dot 

func (v Vector3) Dot(u Vector3) float64

Get the dot product v * u

func (Vector3) IntersectsAABB 

func (v Vector3) IntersectsAABB(a AABB) bool

Check for an intersection with an AABB

func (Vector3) IntersectsSphere 

func (v Vector3) IntersectsSphere(s Sphere) bool

Check for an intersection with a Sphere

func (Vector3) Inv 

func (v Vector3) Inv() Vector3

Get the inverse of the vector

func (Vector3) Mag 

func (v Vector3) Mag() float64

Get the magnitude (L2-norm)

func (Vector3) Mul 

func (v Vector3) Mul(u Vector3) Vector3

Elementwise vector multiplication v * u

func (Vector3) MulScalar 

func (v Vector3) MulScalar(s float64) Vector3

Elementwise vector/scalar multiplication v * s

func (Vector3) Sub 

func (v Vector3) Sub(u Vector3) Vector3

Elementwise vector subtraction v - u

func (Vector3) SubScalar 

func (v Vector3) SubScalar(s float64) Vector3

Elementwise vector/scalar subtraction v - s

func (Vector3) Unit 

func (v Vector3) Unit() Vector3

Get the unit vector

func (Vector3) X 

func (v Vector3) X() float64

Get the x-component

func (Vector3) Y 

func (v Vector3) Y() float64

Get the y-component

func (Vector3) Z 

func (v Vector3) Z() float64

Get the z-component

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.