2D decimation

decimate.go

func DecimateMesh(m *model2d.Mesh, maxVertices int) *model2d.Mesh {
	m = model2d.NewMeshSegments(m.SegmentsSlice())
	areas := map[model2d.Coord]float64{}
	for _, v := range m.VertexSlice() {
		areas[v] = VertexArea(m, v)
	}

	for len(areas) > maxVertices {
		var next model2d.Coord
		nextArea := math.Inf(1)
		for v, a := range areas {
			if a < nextArea {
				nextArea = a
				next = v
			}
		}
		delete(areas, next)
		n1, n2 := VertexNeighbors(m, next)
		for _, s := range m.Find(next) {
			m.Remove(s)
		}
		// TODO: easier way to preserve normal here.
		m.Add(&model2d.Segment{n1, n2})
		areas[n1] = VertexArea(m, n1)
		areas[n2] = VertexArea(m, n2)
	}

	m, _ = m.RepairNormals(1e-5)
	return m
}

func VertexArea(m *model2d.Mesh, c model2d.Coord) float64 {
	n1, n2 := VertexNeighbors(m, c)
	mat := model2d.NewMatrix2Columns(n2.Sub(c), n1.Sub(c))
	return math.Abs(mat.Det() / 2)
}

func VertexNeighbors(m *model2d.Mesh, c model2d.Coord) (n1, n2 model2d.Coord) {
	neighbors := m.Find(c)
	if len(neighbors) != 2 {
		panic("non-manifold mesh")
	}
	n1 = neighbors[0][0]
	if n1 == c {
		n1 = neighbors[0][1]
	}
	n2 = neighbors[1][0]
	if n2 == c {
		n2 = neighbors[1][1]
	}
	return
}