-
Notifications
You must be signed in to change notification settings - Fork 17
/
vertex_welder.go
103 lines (91 loc) · 2.57 KB
/
vertex_welder.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
94
95
96
97
98
99
100
101
102
103
package unityai
func hash(x, y, z int, BucketCount int) int {
h1 := 0x8da6b343 // Large multiplicative constants;
h2 := 0xd8163841 // here arbitrarily chosen primes
h3 := 0xcb1ab31f
n := h1*x + h2*y + h3*z
return n & (BucketCount - 1)
}
func NewVertexWelder(BucketCount int, verts *[]Vector3f, weldThr float32) *VertexWelder {
welder := &VertexWelder{
m_weldThr: weldThr,
m_verts: verts,
m_next: nil,
m_first: make([]int, BucketCount),
BucketCount: BucketCount,
}
Assert(weldThr > 0.0)
for i := 0; i < BucketCount; i++ {
welder.m_first[i] = -1
}
return welder
}
type VertexWelder struct {
m_weldThr float32
m_verts *[]Vector3f
m_next []int
m_first []int
BucketCount int
}
func (this *VertexWelder) GetCellSize() float32 {
return this.m_weldThr * 10.0
}
func (this *VertexWelder) SetVertexArray(verts *[]Vector3f) {
Assert(len(*verts) == 0)
this.m_verts = verts
}
func (this *VertexWelder) Reset() {
for i := 0; i < this.BucketCount; i++ {
this.m_first[i] = -1
}
this.m_next = this.m_next[:0]
}
func (this *VertexWelder) Push(pt Vector3f) int {
cellSize := this.GetCellSize()
// Add vertex
x := FloorfToInt(pt.x / cellSize)
y := FloorfToInt(pt.y / cellSize)
z := FloorfToInt(pt.z / cellSize)
h := hash(int(x), int(y), int(z), this.BucketCount)
*this.m_verts = append(*this.m_verts, pt)
this.m_next = append(this.m_next, -1)
// The external array must be kept in sync with m_next.
// Only this method should add stuff to verts when using the welder.
Assert(len(*this.m_verts) == len(this.m_next))
idx := len(*this.m_verts) - 1
this.m_next[idx] = this.m_first[h]
this.m_first[h] = idx
return idx
}
func (this *VertexWelder) AddUnique(pt Vector3f) int {
verts := *this.m_verts
// Try to find vertex
weldThr := this.m_weldThr
cellSize := this.GetCellSize()
minx := FloorfToInt((pt.x - weldThr) / cellSize)
maxx := FloorfToInt((pt.x + weldThr) / cellSize)
miny := FloorfToInt((pt.y - weldThr) / cellSize)
maxy := FloorfToInt((pt.y + weldThr) / cellSize)
minz := FloorfToInt((pt.z - weldThr) / cellSize)
maxz := FloorfToInt((pt.z + weldThr) / cellSize)
bestIndex := -1
bestDistSq := weldThr * weldThr
for z := minz; z <= maxz; z++ {
for y := miny; y <= maxy; y++ {
for x := minx; x <= maxx; x++ {
h := hash(int(x), int(y), int(z), this.BucketCount)
for i := this.m_first[h]; i != -1; i = this.m_next[i] {
distSq := SqrMagnitude(verts[i].Sub(pt))
if distSq < bestDistSq {
bestDistSq = distSq
bestIndex = i
}
}
}
}
}
if bestIndex != -1 {
return bestIndex
}
return this.Push(pt)
}