103 lines
2.6 KiB
Go
103 lines
2.6 KiB
Go
// Copyright 2014, 2015, 2017 by Sascha L. Teichmann
|
|
// Use of this source code is governed by the MIT license
|
|
// that can be found in the LICENSE file.
|
|
|
|
package common
|
|
|
|
import (
|
|
"math"
|
|
)
|
|
|
|
type Area struct {
|
|
X1, Z1 int16
|
|
X2, Z2 int16
|
|
}
|
|
|
|
func (a Area) contains(x, z int16) bool {
|
|
return x >= a.X1 && x <= a.X2 && z >= a.Z1 && z <= a.Z2
|
|
}
|
|
|
|
func (a Area) higher() bool {
|
|
return a.Z2-a.Z1 > a.X2-a.X1
|
|
}
|
|
|
|
func areasContain(areas []Area, x, z int16) bool {
|
|
for _, r := range areas {
|
|
if r.contains(x, z) {
|
|
return true
|
|
}
|
|
}
|
|
return false
|
|
}
|
|
|
|
// recalculate implements a greedy algorithm to figure out
|
|
// a list of disjunct areas of free regions in the domain
|
|
// to the (x, z) block plane.
|
|
// oldAreas are searched and found free areas are appended
|
|
// to newAreas which ist return.
|
|
// This is useful to spatial query only blocks from db
|
|
// that are not below already rendered blocks.
|
|
func (area Area) recalculate(r *Renderer, nareas []Area) []Area {
|
|
yM := r.yMin
|
|
|
|
const ex = 1
|
|
const ez = 2
|
|
|
|
nas := len(nareas)
|
|
|
|
for z := area.Z1; z <= area.Z2; z++ {
|
|
row := z * int16(r.width)
|
|
for x := area.X1; x <= area.X2; x++ {
|
|
// Uncovered and not in list of new areas?
|
|
if yM[row+x] > math.MinInt32 || areasContain(nareas[nas:], x, z) {
|
|
continue
|
|
}
|
|
a := Area{X1: x, Z1: z, X2: x, Z2: z}
|
|
// Try to extend the area in x and/or z till no further extension is possible.
|
|
ext:
|
|
for extend := ex | ez; extend != 0; {
|
|
// If we extending in both directions a the current area
|
|
// is higher than wide we gain more block if extend
|
|
// in the x direction first.
|
|
if (extend == ex|ez && a.higher()) || extend&ex == ex { // check x
|
|
nx := a.X2 + 1
|
|
if nx > area.X2 { // reached border of area
|
|
extend &= ^ex
|
|
continue
|
|
}
|
|
// Check column right of the current area if its fully free.
|
|
for nz := a.Z1; nz <= a.Z2; nz++ {
|
|
if yM[nz*int16(r.width)+nx] > math.MinInt32 ||
|
|
areasContain(nareas[nas:], nx, nz) {
|
|
extend &= ^ex
|
|
continue ext
|
|
}
|
|
}
|
|
// free -> extend
|
|
a.X2 = nx
|
|
} else if extend&ez == ez { // check z
|
|
nz := a.Z2 + 1
|
|
if nz > area.Z2 {
|
|
extend &= ^ez
|
|
continue
|
|
}
|
|
// Check line right below the current area if its free.
|
|
row2 := nz * int16(r.width)
|
|
for nx := a.X1; nx <= a.X2; nx++ {
|
|
if yM[row2+nx] > math.MinInt32 ||
|
|
areasContain(nareas[nas:], nx, nz) {
|
|
extend &= ^ez
|
|
continue ext
|
|
}
|
|
}
|
|
// free -> extend
|
|
a.Z2 = nz
|
|
}
|
|
}
|
|
// At this point the area is extended to max.
|
|
nareas = append(nareas, a)
|
|
}
|
|
}
|
|
return nareas
|
|
}
|