stuv_test.go

Documentation: github.com/golang/geo/s2

     1  // Copyright 2014 Google Inc. All rights reserved.
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  package s2
    16  
    17  import (
    18  	"math"
    19  	"testing"
    20  
    21  	"github.com/golang/geo/r3"
    22  )
    23  
    24  func TestSTUV(t *testing.T) {
    25  	if x := stToUV(uvToST(.125)); x != .125 {
    26  		t.Error("stToUV(uvToST(.125) == ", x)
    27  	}
    28  	if x := uvToST(stToUV(.125)); x != .125 {
    29  		t.Error("uvToST(stToUV(.125) == ", x)
    30  	}
    31  }
    32  
    33  func TestUVNorms(t *testing.T) {
    34  	step := 1 / 1024.0
    35  	for face := 0; face < 6; face++ {
    36  		for x := -1.0; x <= 1; x += step {
    37  			if !float64Eq(float64(faceUVToXYZ(face, x, -1).Cross(faceUVToXYZ(face, x, 1)).Angle(uNorm(face, x))), 0.0) {
    38  				t.Errorf("UNorm not orthogonal to the face(%d)", face)
    39  			}
    40  			if !float64Eq(float64(faceUVToXYZ(face, -1, x).Cross(faceUVToXYZ(face, 1, x)).Angle(vNorm(face, x))), 0.0) {
    41  				t.Errorf("VNorm not orthogonal to the face(%d)", face)
    42  			}
    43  		}
    44  	}
    45  }
    46  
    47  func TestFaceUVToXYZ(t *testing.T) {
    48  	// Check that each face appears exactly once.
    49  	var sum r3.Vector
    50  	for face := 0; face < 6; face++ {
    51  		center := faceUVToXYZ(face, 0, 0)
    52  		if !center.ApproxEqual(unitNorm(face).Vector) {
    53  			t.Errorf("faceUVToXYZ(%d, 0, 0) != unitNorm(%d), should be equal", face, face)
    54  		}
    55  		switch center.LargestComponent() {
    56  		case r3.XAxis:
    57  			if math.Abs(center.X) != 1 {
    58  				t.Errorf("%v.X = %v, want %v", center, math.Abs(center.X), 1)
    59  			}
    60  		case r3.YAxis:
    61  			if math.Abs(center.Y) != 1 {
    62  				t.Errorf("%v.Y = %v, want %v", center, math.Abs(center.Y), 1)
    63  			}
    64  		default:
    65  			if math.Abs(center.Z) != 1 {
    66  				t.Errorf("%v.Z = %v, want %v", center, math.Abs(center.Z), 1)
    67  			}
    68  		}
    69  		sum = sum.Add(center.Abs())
    70  
    71  		// Check that each face has a right-handed coordinate system.
    72  		if got := uAxis(face).Vector.Cross(vAxis(face).Vector).Dot(unitNorm(face).Vector); got != 1 {
    73  			t.Errorf("right-handed check failed. uAxis(%d).Cross(vAxis(%d)).Dot(unitNorm%v) = %f, want 1", face, face, face, got)
    74  		}
    75  
    76  		// Check that the Hilbert curves on each face combine to form a
    77  		// continuous curve over the entire cube.
    78  		// The Hilbert curve on each face starts at (-1,-1) and terminates
    79  		// at either (1,-1) (if axes not swapped) or (-1,1) (if swapped).
    80  		var sign float64 = 1
    81  		if face&swapMask == 1 {
    82  			sign = -1
    83  		}
    84  		if faceUVToXYZ(face, sign, -sign) != faceUVToXYZ((face+1)%6, -1, -1) {
    85  			t.Errorf("faceUVToXYZ(%v, %v, %v) != faceUVToXYZ(%v, -1, -1)", face, sign, -sign, (face+1)%6)
    86  		}
    87  	}
    88  
    89  	// Adding up the absolute value all all the face normals should equal 2 on each axis.
    90  	if !sum.ApproxEqual(r3.Vector{2, 2, 2}) {
    91  		t.Errorf("sum of the abs of the 6 face norms should = %v, got %v", r3.Vector{2, 2, 2}, sum)
    92  	}
    93  }
    94  
    95  func TestFaceXYZToUV(t *testing.T) {
    96  	var (
    97  		point    = Point{r3.Vector{1.1, 1.2, 1.3}}
    98  		pointNeg = Point{r3.Vector{-1.1, -1.2, -1.3}}
    99  	)
   100  
   101  	tests := []struct {
   102  		face  int
   103  		point Point
   104  		u     float64
   105  		v     float64
   106  		ok    bool
   107  	}{
   108  		{0, point, 1 + (1.0 / 11), 1 + (2.0 / 11), true},
   109  		{0, pointNeg, 0, 0, false},
   110  		{1, point, -11.0 / 12, 1 + (1.0 / 12), true},
   111  		{1, pointNeg, 0, 0, false},
   112  		{2, point, -11.0 / 13, -12.0 / 13, true},
   113  		{2, pointNeg, 0, 0, false},
   114  		{3, point, 0, 0, false},
   115  		{3, pointNeg, 1 + (2.0 / 11), 1 + (1.0 / 11), true},
   116  		{4, point, 0, 0, false},
   117  		{4, pointNeg, 1 + (1.0 / 12), -(11.0 / 12), true},
   118  		{5, point, 0, 0, false},
   119  		{5, pointNeg, -12.0 / 13, -11.0 / 13, true},
   120  	}
   121  
   122  	for _, test := range tests {
   123  		if u, v, ok := faceXYZToUV(test.face, test.point); !float64Eq(u, test.u) || !float64Eq(v, test.v) || ok != test.ok {
   124  			t.Errorf("faceXYZToUV(%d, %v) = %f, %f, %t, want %f, %f, %t", test.face, test.point, u, v, ok, test.u, test.v, test.ok)
   125  		}
   126  	}
   127  }
   128  
   129  func TestFaceXYZtoUVW(t *testing.T) {
   130  	var (
   131  		origin = Point{r3.Vector{0, 0, 0}}
   132  		posX   = Point{r3.Vector{1, 0, 0}}
   133  		negX   = Point{r3.Vector{-1, 0, 0}}
   134  		posY   = Point{r3.Vector{0, 1, 0}}
   135  		negY   = Point{r3.Vector{0, -1, 0}}
   136  		posZ   = Point{r3.Vector{0, 0, 1}}
   137  		negZ   = Point{r3.Vector{0, 0, -1}}
   138  	)
   139  
   140  	for face := 0; face < 6; face++ {
   141  		if got := faceXYZtoUVW(face, origin); got != origin {
   142  			t.Errorf("faceXYZtoUVW(%d, %v) = %v, want %v", face, origin, got, origin)
   143  		}
   144  
   145  		if got := faceXYZtoUVW(face, uAxis(face)); got != posX {
   146  			t.Errorf("faceXYZtoUVW(%d, %v) = %v, want %v", face, uAxis(face), got, posX)
   147  		}
   148  
   149  		if got := faceXYZtoUVW(face, Point{uAxis(face).Mul(-1)}); got != negX {
   150  			t.Errorf("faceXYZtoUVW(%d, %v) = %v, want %v", face, uAxis(face).Mul(-1), got, negX)
   151  		}
   152  
   153  		if got := faceXYZtoUVW(face, vAxis(face)); got != posY {
   154  			t.Errorf("faceXYZtoUVW(%d, %v) = %v, want %v", face, vAxis(face), got, posY)
   155  		}
   156  
   157  		if got := faceXYZtoUVW(face, Point{vAxis(face).Mul(-1)}); got != negY {
   158  			t.Errorf("faceXYZtoUVW(%d, %v) = %v, want %v", face, vAxis(face).Mul(-1), got, negY)
   159  		}
   160  
   161  		if got := faceXYZtoUVW(face, unitNorm(face)); got != posZ {
   162  			t.Errorf("faceXYZtoUVW(%d, %v) = %v, want %v", face, unitNorm(face), got, posZ)
   163  		}
   164  
   165  		if got := faceXYZtoUVW(face, Point{unitNorm(face).Mul(-1)}); got != negZ {
   166  			t.Errorf("faceXYZtoUVW(%d, %v) = %v, want %v", face, unitNorm(face).Mul(-1), got, negZ)
   167  		}
   168  	}
   169  }
   170  
   171  func TestUVWAxis(t *testing.T) {
   172  	for face := 0; face < 6; face++ {
   173  		// Check that the axes are consistent with faceUVtoXYZ.
   174  		if faceUVToXYZ(face, 1, 0).Sub(faceUVToXYZ(face, 0, 0)) != uAxis(face).Vector {
   175  			t.Errorf("face 1,0 - face 0,0 should equal uAxis")
   176  		}
   177  		if faceUVToXYZ(face, 0, 1).Sub(faceUVToXYZ(face, 0, 0)) != vAxis(face).Vector {
   178  			t.Errorf("faceUVToXYZ(%d, 0, 1).Sub(faceUVToXYZ(%d, 0, 0)) != vAxis(%d), should be equal.", face, face, face)
   179  		}
   180  		if faceUVToXYZ(face, 0, 0) != unitNorm(face).Vector {
   181  			t.Errorf("faceUVToXYZ(%d, 0, 0) != unitNorm(%d), should be equal", face, face)
   182  		}
   183  
   184  		// Check that every face coordinate frame is right-handed.
   185  		if got := uAxis(face).Vector.Cross(vAxis(face).Vector).Dot(unitNorm(face).Vector); got != 1 {
   186  			t.Errorf("right-handed check failed. got %f, want 1", got)
   187  		}
   188  
   189  		// Check that GetUVWAxis is consistent with GetUAxis, GetVAxis, GetNorm.
   190  		if uAxis(face) != uvwAxis(face, 0) {
   191  			t.Errorf("uAxis(%d) != uvwAxis(%d, 0), should be equal", face, face)
   192  		}
   193  		if vAxis(face) != uvwAxis(face, 1) {
   194  			t.Errorf("vAxis(%d) != uvwAxis(%d, 1), should be equal", face, face)
   195  		}
   196  		if unitNorm(face) != uvwAxis(face, 2) {
   197  			t.Errorf("unitNorm(%d) != uvwAxis(%d, 2), should be equal", face, face)
   198  		}
   199  	}
   200  }
   201  
   202  func TestSiTiSTRoundtrip(t *testing.T) {
   203  	// test int -> float -> int direction.
   204  	for i := 0; i < 1000; i++ {
   205  		si := uint32(randomUniformInt(maxSiTi))
   206  		if got := stToSiTi(siTiToST(si)); got != si {
   207  			t.Errorf("stToSiTi(siTiToST(%v)) = %v, want %v", si, got, si)
   208  		}
   209  	}
   210  	// test float -> int -> float direction.
   211  	for i := 0; i < 1000; i++ {
   212  		st := randomUniformFloat64(0, 1.0)
   213  		// this uses near not exact because there is some loss in precision
   214  		// when scaling down to the nearest 1/MaxLevel and back.
   215  		if got := siTiToST(stToSiTi(st)); !float64Near(got, st, 1e-8) {
   216  			t.Errorf("siTiToST(stToSiTi(%v)) = %v, want %v", st, got, st)
   217  		}
   218  	}
   219  }
   220  
   221  func TestUVWFace(t *testing.T) {
   222  	// Check that uvwFace is consistent with uvwAxis.
   223  	for f := 0; f < 6; f++ {
   224  		for axis := 0; axis < 3; axis++ {
   225  			if got, want := face(uvwAxis(f, axis).Mul(-1)), uvwFace(f, axis, 0); got != want {
   226  				t.Errorf("face(%v) in positive direction = %v, want %v", uvwAxis(f, axis).Mul(-1), got, want)
   227  			}
   228  			if got, want := face(uvwAxis(f, axis).Vector), uvwFace(f, axis, 1); got != want {
   229  				t.Errorf("face(%v) in negative direction = %v, want %v", uvwAxis(f, axis), got, want)
   230  			}
   231  		}
   232  	}
   233  }
   234  
   235  func TestXYZToFaceSiTi(t *testing.T) {
   236  	for level := 0; level < MaxLevel; level++ {
   237  		for i := 0; i < 1000; i++ {
   238  			ci := randomCellIDForLevel(level)
   239  			f, si, ti, gotLevel := xyzToFaceSiTi(ci.Point())
   240  			if gotLevel != level {
   241  				t.Errorf("level of CellID %v = %v, want %v", ci, gotLevel, level)
   242  			}
   243  			gotID := cellIDFromFaceIJ(f, int(si/2), int(ti/2)).Parent(level)
   244  			if gotID != ci {
   245  				t.Errorf("CellID = %b, want %b", gotID, ci)
   246  			}
   247  
   248  			// Test a point near the cell center but not equal to it.
   249  			pMoved := ci.Point().Add(r3.Vector{1e-13, 1e-13, 1e-13})
   250  			fMoved, siMoved, tiMoved, gotLevel := xyzToFaceSiTi(Point{pMoved})
   251  
   252  			if gotLevel != -1 {
   253  				t.Errorf("level of %v = %v, want %v", pMoved, gotLevel, -1)
   254  			}
   255  
   256  			if f != fMoved {
   257  				t.Errorf("face of %v = %v, want %v", pMoved, fMoved, f)
   258  			}
   259  
   260  			if si != siMoved {
   261  				t.Errorf("si of %v = %v, want %v", pMoved, siMoved, si)
   262  			}
   263  
   264  			if ti != tiMoved {
   265  				t.Errorf("ti of %v = %v, want %v", pMoved, tiMoved, ti)
   266  			}
   267  
   268  			// Finally, test some random (si,ti) values that may be at different
   269  			// levels, or not at a valid level at all (for example, si == 0).
   270  			faceRandom := randomUniformInt(NumFaces)
   271  			mask := -1 << uint32(MaxLevel-level)
   272  			siRandom := randomUint32() & uint32(mask)
   273  			tiRandom := randomUint32() & uint32(mask)
   274  			for siRandom > maxSiTi || tiRandom > maxSiTi {
   275  				siRandom = randomUint32() & uint32(mask)
   276  				tiRandom = randomUint32() & uint32(mask)
   277  			}
   278  
   279  			pRandom := faceSiTiToXYZ(faceRandom, siRandom, tiRandom)
   280  			f, si, ti, gotLevel = xyzToFaceSiTi(pRandom)
   281  
   282  			// The chosen point is on the edge of a top-level face cell.
   283  			if f != faceRandom {
   284  				if gotLevel != -1 {
   285  					t.Errorf("level of random CellID = %v, want %v", gotLevel, -1)
   286  				}
   287  				if !(si == 0 || si == maxSiTi || ti == 0 || ti == maxSiTi) {
   288  					t.Errorf("face %d, si = %v, ti = %v, want 0 or %v for both", f, si, ti, maxSiTi)
   289  				}
   290  				continue
   291  			}
   292  
   293  			if siRandom != si {
   294  				t.Errorf("xyzToFaceSiTi(%v).si = %v, want %v", pRandom, siRandom, si)
   295  			}
   296  			if tiRandom != ti {
   297  				t.Errorf("xyzToFaceSiTi(%v).ti = %v, want %v", pRandom, tiRandom, ti)
   298  			}
   299  			if gotLevel >= 0 {
   300  				if got := cellIDFromFaceIJ(f, int(si/2), int(ti/2)).Parent(gotLevel).Point(); !pRandom.ApproxEqual(got) {
   301  					t.Errorf("cellIDFromFaceIJ(%d, %d, %d).Parent(%d) = %v, want %v", f, si/2, ti/2, gotLevel, got, pRandom)
   302  				}
   303  			}
   304  		}
   305  	}
   306  }
   307  
   308  func TestXYZFaceSiTiRoundtrip(t *testing.T) {
   309  	for level := 0; level < MaxLevel; level++ {
   310  		for i := 0; i < 1000; i++ {
   311  			ci := randomCellIDForLevel(level)
   312  			f, si, ti, _ := xyzToFaceSiTi(ci.Point())
   313  			op := faceSiTiToXYZ(f, si, ti)
   314  			if !ci.Point().ApproxEqual(op) {
   315  				t.Errorf("faceSiTiToXYZ(xyzToFaceSiTi(%v)) = %v, want %v", ci.Point(), op, ci.Point())
   316  			}
   317  		}
   318  	}
   319  }
   320  
   321  func TestSTUVFace(t *testing.T) {
   322  	tests := []struct {
   323  		v    r3.Vector
   324  		want int
   325  	}{
   326  		{r3.Vector{-1, -1, -1}, 5},
   327  		{r3.Vector{-1, -1, 0}, 4},
   328  		{r3.Vector{-1, -1, 1}, 2},
   329  		{r3.Vector{-1, 0, -1}, 5},
   330  		{r3.Vector{-1, 0, 0}, 3},
   331  		{r3.Vector{-1, 0, 1}, 2},
   332  		{r3.Vector{-1, 1, -1}, 5},
   333  		{r3.Vector{-1, 1, 0}, 1},
   334  		{r3.Vector{-1, 1, 1}, 2},
   335  		{r3.Vector{0, -1, -1}, 5},
   336  		{r3.Vector{0, -1, 0}, 4},
   337  		{r3.Vector{0, -1, 1}, 2},
   338  		{r3.Vector{0, 0, -1}, 5},
   339  		{r3.Vector{0, 0, 0}, 2},
   340  		{r3.Vector{0, 0, 1}, 2},
   341  		{r3.Vector{0, 1, -1}, 5},
   342  		{r3.Vector{0, 1, 0}, 1},
   343  		{r3.Vector{0, 1, 1}, 2},
   344  		{r3.Vector{1, -1, -1}, 5},
   345  		{r3.Vector{1, -1, 0}, 4},
   346  		{r3.Vector{1, -1, 1}, 2},
   347  		{r3.Vector{1, 0, -1}, 5},
   348  		{r3.Vector{1, 0, 0}, 0},
   349  		{r3.Vector{1, 0, 1}, 2},
   350  		{r3.Vector{1, 1, -1}, 5},
   351  		{r3.Vector{1, 1, 0}, 1},
   352  		{r3.Vector{1, 1, 1}, 2},
   353  	}
   354  
   355  	for _, test := range tests {
   356  		if got := face(test.v); got != test.want {
   357  			t.Errorf("face(%v) = %d, want %d", test.v, got, test.want)
   358  		}
   359  	}
   360  }
   361
View as plain text