# HG changeset patch # User Sascha L. Teichmann # Date 1708363660 -3600 # Node ID a68e8eae72730493e6acdc3eb11e4015343301e6 # Parent d2ccf6bb69401d4cfe2c9e6922d394939e75b609 Dont store bounding boxes in v2 meshes. diff -r d2ccf6bb6940 -r a68e8eae7273 pkg/mesh/meshserialize_v2.go --- a/pkg/mesh/meshserialize_v2.go Mon Feb 19 17:48:13 2024 +0100 +++ b/pkg/mesh/meshserialize_v2.go Mon Feb 19 18:27:40 2024 +0100 @@ -36,7 +36,6 @@ (*STRTree).serializeTinV2, (*STRTree).serializeEntries, (*STRTree).serializeIndexV2, - (*STRTree).serializeBBoxesV2, ) } @@ -121,39 +120,17 @@ return nil } -func (s *STRTree) serializeBBoxesV2(w io.Writer) error { - boxes := s.bboxes - if err := binary.Write(w, binary.LittleEndian, uint32(len(boxes))); err != nil { - return err - } - var ( - m = s.Min() - x1 = func(b Box2D) int64 { return quant(b.X1 - m.X) } - y1 = func(b Box2D) int64 { return quant(b.Y1 - m.Y) } - width = func(b Box2D) int64 { return quant(b.X2 - b.X1) } - height = func(b Box2D) int64 { return quant(b.Y2 - b.Y1) } - buf = make([]byte, binary.MaxVarintLen64) - ) - for _, proj := range []func(Box2D) int64{x1, y1, width, height} { - delta := common.Delta() - for _, b := range boxes { - v := delta(proj(b)) - if err := zigZag(buf, w, v); err != nil { - return err - } - } - } - return nil -} - func (s *STRTree) deserializeV2(r *bufio.Reader) error { // The header is already skipped here. - return serializer(r, s, + if err := serializer(r, s, (*STRTree).deserializeTinV2, (*STRTree).deserializeEntries, (*STRTree).deserializeIndexV2, - (*STRTree).deserializeBBoxesV2, - ) + ); err != nil { + return err + } + s.rebuildBBoxes() + return nil } func (s *STRTree) deserializeTinV2(r *bufio.Reader) error { @@ -161,33 +138,6 @@ return s.tin.deserializeV2(r) } -func (s *STRTree) deserializeBBoxesV2(r *bufio.Reader) error { - var numBoxes uint32 - if err := binary.Read(r, binary.LittleEndian, &numBoxes); err != nil { - return err - } - boxes := make([]Box2D, numBoxes) - s.bboxes = boxes - var ( - m = s.Min() - x1 = func(b *Box2D, v float64) { b.X1 = v + m.X } - y1 = func(b *Box2D, v float64) { b.Y1 = v + m.Y } - width = func(b *Box2D, v float64) { b.X2 = b.X1 + v } - height = func(b *Box2D, v float64) { b.Y2 = b.Y1 + v } - ) - for _, unproj := range []func(*Box2D, float64){x1, y1, width, height} { - invDelta := common.InvDelta() - for i := range boxes { - v, err := binary.ReadVarint(r) - if err != nil { - return err - } - unproj(&boxes[i], unquant(invDelta(v))) - } - } - return nil -} - func (s *STRTree) deserializeIndexV2(r *bufio.Reader) error { var numIndices uint32 if err := binary.Read(r, binary.LittleEndian, &numIndices); err != nil { diff -r d2ccf6bb6940 -r a68e8eae7273 pkg/mesh/strtree.go --- a/pkg/mesh/strtree.go Mon Feb 19 17:48:13 2024 +0100 +++ b/pkg/mesh/strtree.go Mon Feb 19 18:27:40 2024 +0100 @@ -16,7 +16,9 @@ import ( "cmp" "math" + "runtime" "slices" + "sync" ) // STRTreeDefaultEntries is the default number of children per node and leaf. @@ -164,6 +166,134 @@ s.index[0] = root } +// countNodes returns the number of nodes for a given index. +func (s *STRTree) countNodes() int { + if len(s.index) == 0 { + return 0 + } + count := 0 + stack := []int32{s.index[0]} + for len(stack) > 0 { + top := stack[len(stack)-1] + stack = stack[:len(stack)-1] + count++ + if top > 0 { // node + n := s.index[top+1] + stack = append(stack, s.index[top+2:top+2+n]...) + } + } + return count +} + +// rebuildBBoxes rebuilds the bounding boxes for a given index and triangles. +func (s *STRTree) rebuildBBoxes() { + + num := s.countNodes() + if num == 0 { + return + } + bboxes := make([]Box2D, num) + s.bboxes = bboxes + + var recurse func(int32, int32) Box2D + recurse = func(top, depth int32) Box2D { + var box Box2D + if top > 0 { // node + n := s.index[top+1] + for i, child := range s.index[top+2 : top+2+n] { + if i == 0 { + box = recurse(child, depth+1) + } else { + box = box.Union(recurse(child, depth+1)) + } + } + } else { // leaf + top = -top - 1 + n := s.index[top+1] + for i, idx := range s.index[top+2 : top+2+n] { + ti := s.tin.Triangles[idx] + t := Triangle{ + s.tin.Vertices[ti[2]], + s.tin.Vertices[ti[0]], + s.tin.Vertices[ti[1]], + } + if i == 0 { + box = t.BBox() + } else { + box = box.Union(t.BBox()) + } + } + } + bboxes[s.index[top]] = box + return box + } + + // Check if we can boost re-building with some extra CPU cores. + cpus := max(1, runtime.NumCPU()/2) + if cpus == 1 { + recurse(s.index[0], 0) + return + } + + type job struct { + top int32 + depth int32 + store func(Box2D) + } + + jobs := make(chan job) + var wg sync.WaitGroup + + singleThreaded := recurse + + for i := 0; i < cpus; i++ { + wg.Add(1) + go func() { + defer wg.Done() + for j := range jobs { + j.store(singleThreaded(j.top, j.depth)) + } + }() + } + + recurse = func(top, depth int32) Box2D { + // Only handle nodes at level 1. + if depth != 1 || top <= 0 { + return singleThreaded(top, depth) + } + var ( + first = true + box Box2D + done = make(chan struct{}) + n = s.index[top+1] + count = int32(0) + mu sync.Mutex + ) + store := func(b Box2D) { + mu.Lock() + defer mu.Unlock() + if first { + first = false + box = b + } else { + box = box.Union(b) + } + if count++; count >= n { + close(done) + } + } + for _, child := range s.index[top+2 : top+2+n] { + jobs <- job{top: child, depth: depth + 1, store: store} + } + <-done + bboxes[s.index[top]] = box + return box + } + recurse(s.index[0], 0) + close(jobs) + wg.Wait() +} + // BuildWithout builds a tree for a given TIN ignoring the triangles // with the indices given in the remove map. func (s *STRTree) BuildWithout(t *Tin, remove map[int32]struct{}) {