-
Notifications
You must be signed in to change notification settings - Fork 3
/
convex_hull.go
93 lines (79 loc) · 2.42 KB
/
convex_hull.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
package quickhull
import (
"github.com/golang/geo/r3"
)
type ConvexHull struct {
optimizedVertexBuffer []r3.Vector
Vertices []r3.Vector
Indices []int
}
func (hull ConvexHull) Triangles() [][3]r3.Vector {
triangles := make([][3]r3.Vector, len(hull.Indices)/3)
for i, idx := range hull.Indices {
triangles[i/3][i%3] = hull.Vertices[idx]
}
return triangles
}
func newConvexHull(mesh meshBuilder, pointCloud []r3.Vector, ccw bool, useOriginalIndices bool) ConvexHull {
var hull ConvexHull
faceProcessed := make([]bool, len(mesh.faces))
var faceStack []int
for i, f := range mesh.faces {
if !f.isDisabled() {
faceStack = append(faceStack, i)
break
}
}
if len(faceStack) == 0 {
return hull
}
finalMeshFaceCount := len(mesh.faces) - len(mesh.disabledFaces)
hull.Indices = make([]int, 0, finalMeshFaceCount*3)
vertexIndexMapping := make(map[int]int) // Map vertex indices from original point cloud to the new mesh vertex indices
for len(faceStack) > 0 {
lastFaceIndex := len(faceStack) - 1
var top int
top, faceStack = faceStack[lastFaceIndex], faceStack[:lastFaceIndex]
topFace := mesh.faces[top]
assertTrue(!topFace.isDisabled())
if faceProcessed[top] {
continue
}
faceProcessed[top] = true
halfEdges := mesh.halfEdgeIndicesOfFace(topFace)
adjacent := []int{mesh.halfEdges[mesh.halfEdges[halfEdges[0]].Opp].Face, mesh.halfEdges[mesh.halfEdges[halfEdges[1]].Opp].Face, mesh.halfEdges[mesh.halfEdges[halfEdges[2]].Opp].Face}
for _, a := range adjacent {
if !faceProcessed[a] && !mesh.faces[a].isDisabled() {
faceStack = append(faceStack, a)
}
}
vertices := mesh.vertexIndicesOfFace(topFace)
if !useOriginalIndices {
for i, v := range vertices {
it, found := vertexIndexMapping[v]
if !found {
hull.optimizedVertexBuffer = append(hull.optimizedVertexBuffer, pointCloud[v])
addedIdx := len(hull.optimizedVertexBuffer) - 1
vertexIndexMapping[v] = addedIdx
vertices[i] = addedIdx
} else {
vertices[i] = it
}
}
}
hull.Indices = append(hull.Indices, vertices[0])
if ccw {
hull.Indices = append(hull.Indices, vertices[2])
hull.Indices = append(hull.Indices, vertices[1])
} else {
hull.Indices = append(hull.Indices, vertices[1])
hull.Indices = append(hull.Indices, vertices[2])
}
}
if useOriginalIndices {
hull.Vertices = pointCloud
} else {
hull.Vertices = hull.optimizedVertexBuffer
}
return hull
}