(depth int)
| 126 | } |
| 127 | |
| 128 | func (node *Node) Split(depth int) { |
| 129 | if len(node.Shapes) < 8 { |
| 130 | return |
| 131 | } |
| 132 | xs := make([]float64, 0, len(node.Shapes)*2) |
| 133 | ys := make([]float64, 0, len(node.Shapes)*2) |
| 134 | zs := make([]float64, 0, len(node.Shapes)*2) |
| 135 | for _, shape := range node.Shapes { |
| 136 | box := shape.BoundingBox() |
| 137 | xs = append(xs, box.Min.X) |
| 138 | xs = append(xs, box.Max.X) |
| 139 | ys = append(ys, box.Min.Y) |
| 140 | ys = append(ys, box.Max.Y) |
| 141 | zs = append(zs, box.Min.Z) |
| 142 | zs = append(zs, box.Max.Z) |
| 143 | } |
| 144 | sort.Float64s(xs) |
| 145 | sort.Float64s(ys) |
| 146 | sort.Float64s(zs) |
| 147 | mx, my, mz := Median(xs), Median(ys), Median(zs) |
| 148 | best := int(float64(len(node.Shapes)) * 0.85) |
| 149 | bestAxis := AxisNone |
| 150 | bestPoint := 0.0 |
| 151 | sx := node.PartitionScore(AxisX, mx) |
| 152 | if sx < best { |
| 153 | best = sx |
| 154 | bestAxis = AxisX |
| 155 | bestPoint = mx |
| 156 | } |
| 157 | sy := node.PartitionScore(AxisY, my) |
| 158 | if sy < best { |
| 159 | best = sy |
| 160 | bestAxis = AxisY |
| 161 | bestPoint = my |
| 162 | } |
| 163 | sz := node.PartitionScore(AxisZ, mz) |
| 164 | if sz < best { |
| 165 | best = sz |
| 166 | bestAxis = AxisZ |
| 167 | bestPoint = mz |
| 168 | } |
| 169 | if bestAxis == AxisNone { |
| 170 | return |
| 171 | } |
| 172 | l, r := node.Partition(best, bestAxis, bestPoint) |
| 173 | node.Axis = bestAxis |
| 174 | node.Point = bestPoint |
| 175 | node.Left = NewNode(l) |
| 176 | node.Right = NewNode(r) |
| 177 | node.Left.Split(depth + 1) |
| 178 | node.Right.Split(depth + 1) |
| 179 | node.Shapes = nil // only needed at leaf nodes |
| 180 | } |
no test coverage detected