[QUESTION] Octant Position Logic

[chris-aeviator]

Did you find out a (logical) way on how to get the correct octants of a given coordinate? the positioning seems rather random and it's nearly impossible to get an obj from an POI without trial & error or loading all (>30) octants of any given viewport on google maps into the nodejs script.

[TysonGersh]

Out of curiosity, how big were your .obj files? I just created my first one and it's 1gb. It's gonna take a long time to load - I can't imagine having to do this multiple times for the same site. Also, what model units were you using during import?

[chris-aeviator]

Mine were 50-100mb, just imported them and they were there (not in the viewport though, see blender.md)

[rastapasta]

Did you find out a (logical) way on how to get the correct octants of a given coordinate?

maybe: octree + google = variant of s2 projection?

edit: s2 geometry is a quadtree based.

[retroplasma]

Did you find out a (logical) way on how to get the correct octants of a given coordinate?

Unfortunately not. Also, no idea how to get correct sub-octants more efficiently (for OBJ export) or how to calculate visible octants from a camera via BulkMetadata, without loading all NodeData. There is BVH stuff in the NodeData and OBB stuff in BulkMetadata; not sure if that's only for collision or if it helps with this stuff.

My guess would be that BVH is used for collision here because its packed alongside the meshes. I think OBB might be usable for octant calculations, because BulkMetadata is always traversed. But again, not sure at all. Hopefully someone here will figure it out.

[chris-aeviator]

A workaround could be inputting gps coordinates, letting puppeteer open them in gmaps, and let all nodeInfo be parsed and downloaded for a given scene/position. Guess a webgl context is needed to make the calls to kh.gmaps

[erikmol]

I tried to make out some logic behind the octants, I'm not sure if this is know or not?

The earth is made up of 8 octants: 02,03,12,13,20,21,30 and 31 which represents an octant of the earth each.
These octants have three sub-octants so there is a total of 8x3=24 octants for zoom level 3 (try node index.js 20 3 to see these).
Now at level 3 there is some logic because each octant is split into four sub-octants a level deeper which continues to level 20.

The sub-octant is labeled according to the quadrant with respect to the parent: 0 (South West), 1 (South East), 2 (North West) or 3 (North West).
If the level is an odd number, the label number is increased by 4. (I don't know the reason behind this)

Looking at the example in the readme: 20527061605273514 we see the following stating from the 205 octant:

• 205 - Starting point, run node index.js 205 4
• 2052 - Zoomed into the North West (2)
• 20527 - Zoomed into the North East (3+4 since we're at an odd level)
• 205270 - Zoomed into the South West (0)
• 2052706 - Zoomed into the North West (2+4 odd level)

Perhaps somebody can figure out how this logic relates to coordinates.

[LexSong]

A dirty script to convert octants to lat/long bounding box:
https://gist.github.com/LexSong/e2830be220542ac637e1ce476e771f79

[retroplasma]

@LexSong Is the reverse also possible this way? Tried brute-forcing it but got duplicate midpoints for octants:

0 and 4

$ python octant_to_latlong.py 210
Midpoint: (22.5, -67.5)
Box: LatLonBox(north=45.0, south=0, west=-90, east=-45.0)
$ python octant_to_latlong.py 214
Midpoint: (22.5, -67.5)
Box: LatLonBox(north=45.0, south=0, west=-90, east=-45.0)

1 and 5

$ python octant_to_latlong.py 211
Midpoint: (22.5, -22.5)
Box: LatLonBox(north=45.0, south=0, west=-45.0, east=0)
$ python octant_to_latlong.py 215
Midpoint: (22.5, -22.5)
Box: LatLonBox(north=45.0, south=0, west=-45.0, east=0)

2, 3, 6 and 7

$ python octant_to_latlong.py 212
Midpoint: (67.5, -45.0)
Box: LatLonBox(north=90, south=45.0, west=-90, east=0)
$ python octant_to_latlong.py 213
Midpoint: (67.5, -45.0)
Box: LatLonBox(north=90, south=45.0, west=-90, east=0)
$ python octant_to_latlong.py 216
Midpoint: (67.5, -45.0)
Box: LatLonBox(north=90, south=45.0, west=-90, east=0)
$ python octant_to_latlong.py 217
Midpoint: (67.5, -45.0)
Box: LatLonBox(north=90, south=45.0, west=-90, east=0)

Btw. figured out how BulkMetadata's oriented bounding box looks like:

Script for generating this model here. I think we can use OBBs to find octants of absolute points in space by checking if a point is inside. Probably an inverse of your method is simpler. Might be useful for view frustum stuff though.

[LexSong]

I have no idea how the z-axis separation works here.

We can only assume that the block 210 and 214 both have the same latitude and longitude bounding box, but are in different height, and block 214 is higher than 210.

[retroplasma]

edit: Wrote this script to convert lat long to octants: https://gist.github.com/retroplasma/a2511c08efb73d89699985fbdc0b5278. It uses your method and brute-forces through BulkMetadata. I committed this first but then noticed that it doesn't work for some coordinates.

[retroplasma]

Method using OBB ray intersection, please test: https://github.com/retroplasma/earth-reverse-engineering/blob/443a3622ce9cb12cd4460cc6dc7999cc703ae67f/experimental_latlong_to_octant.js

Usage:

npm install
node experimental_latlong_to_octant.js 37.420806884765625 -122.08419799804688

[LexSong]

I rewrote lat_long_to_octant in my branch here:
https://github.com/LexSong/earth-reverse-engineering

I'm not familiar with javascript, however I think it may be helpful.

[LexSong]

By the way, node experimental_latlong_to_octant.js 28 87 failed to find the octant.

[retroplasma]

By the way, node experimental_latlong_to_octant.js 28 87 failed to find the octant.

damn 😄

Yours is very elegant! What is the logic behind it btw? Guess there's some fixed order (like @erikmol said? I see a +4 in there). Feel free to open a PR btw if you want.

[LexSong]

What is the logic behind it btw?

Just traverse the octree as the original dump_obj.js, but only examine possible branches by calculating the bounding box of the child octants. We don't know which octant in the z-axis may have data, so we try both octants with key and key+4.

[retroplasma]

Ah thanks! Think I got it, it works because the octants split at the proper angles. That's nice.

[retroplasma]

@LexSong please let me know if you want a PR or want me to directly implement it. planning to adapt it and add to README

[LexSong]

I will send the PR if you're OK with the current state.

I think that there should be clearer way to determine child octants. However the script is already useful now.

[retroplasma]

sure, send it. we can continue to improve it. it's very useful already

[TysonGersh]

Hey, so I'm doing my best to follow along this conversation, but it's hard for me. The first time I've ever used the terminal was to get this program/app (whatever it's called to work). From what I gather the process has changed a bit from when this was first released. I removed the original files and re-downloaded everything. I seem to be able to get the new process (using node dump instead of node index) to work, but when I enter my coordinates I get a bunch of different octants (at least I think that's what's happening?). Here's what shows up for me:
Tysons-MacBook-Pro-2:earth-reverse-engineering tysongersh$ node lat_long_to_octant.js 42.317152, -83.231428
42.317152, -83.231428

21 { n: 90, s: 0, w: -90, e: 0 }
214 { n: 45, s: 0, w: -90, e: -45 }
2142 { n: 45, s: 22.5, w: -90, e: -67.5 }
21426 { n: 45, s: 33.75, w: -90, e: -78.75 }
214263 { n: 45, s: 39.375, w: -84.375, e: -78.75 }
2142636 { n: 45, s: 42.1875, w: -84.375, e: -81.5625 }
21426360 { n: 43.59375, s: 42.1875, w: -84.375, e: -82.96875 }
214263605 { n: 42.890625, s: 42.1875, w: -83.671875, e: -82.96875 }
2142636051 { n: 42.5390625, s: 42.1875, w: -83.3203125, e: -82.96875 }
21426360514 { n: 42.36328125, s: 42.1875, w: -83.3203125, e: -83.14453125 }
214263605143 { n: 42.36328125,
s: 42.275390625,
w: -83.232421875,
e: -83.14453125 }
2142636051434 { n: 42.3193359375,
s: 42.275390625,
w: -83.232421875,
e: -83.1884765625 }
21426360514342 { n: 42.3193359375,
s: 42.29736328125,
w: -83.232421875,
e: -83.21044921875 }
214263605143426 { n: 42.3193359375,
s: 42.308349609375,
w: -83.232421875,
e: -83.221435546875 }
2142636051434262 { n: 42.3193359375,
s: 42.3138427734375,
w: -83.232421875,
e: -83.2269287109375 }
21426360514342626 { n: 42.3193359375,
s: 42.31658935546875,
w: -83.232421875,
e: -83.22967529296875 }
214263605143426264 { n: 42.317962646484375,
s: 42.31658935546875,
w: -83.232421875,
e: -83.23104858398438 }
2142636051434266 { n: 42.3193359375,
s: 42.3138427734375,
w: -83.232421875,
e: -83.2269287109375 }
21426360514342662 { n: 42.3193359375,
s: 42.31658935546875,
w: -83.232421875,
e: -83.22967529296875 }
214263605143426620 { n: 42.317962646484375,
s: 42.31658935546875,
w: -83.232421875,
e: -83.23104858398438 }
Tysons-MacBook-Pro-2:earth-reverse-engineering tysongersh$ node dump_obj.js 214263605143426620 20
found: 214263605143426620
found: 2142636051434266200
found: 21426360514342662000
found: 21426360514342662001
found: 21426360514342662002
found: 21426360514342662003
found: 2142636051434266201
found: 21426360514342662010
found: 21426360514342662011
found: 21426360514342662012
found: 21426360514342662013
found: 2142636051434266202
found: 21426360514342662020
found: 21426360514342662021
found: 21426360514342662022
found: 21426360514342662023
found: 2142636051434266203
found: 21426360514342662030
found: 21426360514342662031
found: 21426360514342662032
found: 21426360514342662033
octants: 21
Tysons-MacBook-Pro-2:earth-reverse-engineering tysongersh$

Here's the real world thing I'm trying to retrieve:

Here's what shows up in Blender:

Any suggestions for me?

BTW I wasn't sure how to use the Blender Script thing to make the fuzziness go away when rotating the object, but I found that if you go to Material view (as opposed to rendered view) it fixes the problem (maybe it creates another one though, I don't know).

[retroplasma]

@TysonGersh this is similar to this issue. Try going up the octant path a bit. 214263605143426 should work. You can drill down from there.

It looks like this at max-level 18:

(node dump_obj.js 214263605143426 18)

[LexSong]

@TysonGersh

I updated lat/long to octants script in my fork here: https://github.com/LexSong/earth-reverse-engineering

Currently the output is like this:

42.317152, -83.231428
-------------
Octant Level: 2
{ n: 90, s: 0, w: -90, e: 0 }
    21
Octant Level: 3
{ n: 45, s: 0, w: -90, e: -45 }
    214
Octant Level: 4
{ n: 45, s: 22.5, w: -90, e: -67.5 }
    2142
Octant Level: 5
{ n: 45, s: 33.75, w: -90, e: -78.75 }
    21426
Octant Level: 6
{ n: 45, s: 39.375, w: -84.375, e: -78.75 }
    214263
Octant Level: 7
{ n: 45, s: 42.1875, w: -84.375, e: -81.5625 }
    2142636
Octant Level: 8
{ n: 43.59375, s: 42.1875, w: -84.375, e: -82.96875 }
    21426360
Octant Level: 9
{ n: 42.890625, s: 42.1875, w: -83.671875, e: -82.96875 }
    214263605
Octant Level: 10
{ n: 42.5390625, s: 42.1875, w: -83.3203125, e: -82.96875 }
    2142636051
Octant Level: 11
{ n: 42.36328125, s: 42.1875, w: -83.3203125, e: -83.14453125 }
    21426360514
Octant Level: 12
{ n: 42.36328125,
  s: 42.275390625,
  w: -83.232421875,
  e: -83.14453125 }
    214263605143
Octant Level: 13
{ n: 42.3193359375,
  s: 42.275390625,
  w: -83.232421875,
  e: -83.1884765625 }
    2142636051434
Octant Level: 14
{ n: 42.3193359375,
  s: 42.29736328125,
  w: -83.232421875,
  e: -83.21044921875 }
    21426360514342
Octant Level: 15
{ n: 42.3193359375,
  s: 42.308349609375,
  w: -83.232421875,
  e: -83.221435546875 }
    214263605143426
Octant Level: 16
{ n: 42.3193359375,
  s: 42.3138427734375,
  w: -83.232421875,
  e: -83.2269287109375 }
    2142636051434262
    2142636051434266
Octant Level: 17
{ n: 42.3193359375,
  s: 42.31658935546875,
  w: -83.232421875,
  e: -83.22967529296875 }
    21426360514342626
    21426360514342662
Octant Level: 18
{ n: 42.317962646484375,
  s: 42.31658935546875,
  w: -83.232421875,
  e: -83.23104858398438 }
    214263605143426264
    214263605143426620

You'll get multiple octants in the same level if the level is deep and there is large height difference.
Each octant is at different height and you should get all of them.

[TysonGersh]

Can't for the life of me get an obj that contains all of the area outlined in red. No matter where I stick the lat/lon I keep getting huge chunks of forest and maybe one the structures I'm looking for (if I'm lucky). Since the switch from Node Index to Node Dump I don't know how to "zoom out" to get the obj to include a larger overall area. Any ideas here?

[retroplasma]

@TysonGersh Most of it is at 214263605143426 (#4 (comment))

The rest can be found using LexSong's script (https://github.com/LexSong/earth-reverse-engineering/tree/find_overlaps):
python find_overlaps.py 42.322677 42.311888 -83.241127 -83.224605

From octant level 15:
node dump_obj.js 214263605142537 214263605142715 214263605143604 214263605143426 16

Result:

How to use find_overlaps.py:
python find_overlaps.py north south west east

north, west

south, east:

[iamaflyingsquirrel]

This is perhaps related to what's been discussed already but has anyone worked out to correctly assign a spatial reference to the output NodeData dump? I've gone through 4326, 3857, and even Google's weird Mercator_2SP but no joy, they're always deep within the Earth, somewhere in the mid Atlantic.

I was thinking of forcing a false projection using the octant bounding boxes but haven't got anything to work yet.

[LexSong]

It looks like that the mesh is on an ECEF coordinate system, but on a pure sphere not an ellipsoid in usual GIS systems.

[iamaflyingsquirrel]

I think you're right!

Plugging some of the ECEF coordinates from the obj file into this https://www.oc.nps.edu/oc2902w/coord/llhxyz.htm

Produces WGS84 coordinates that are where I'd hope to find them (just north of Melbourne).

I found this page looking at converting from WGS84 into ECEF, I just need to try and work out how to reverse the process, definitely above my skill level with Python but an excuse to learn.

Looks as though the common reference for this is ECEF to LLA (Lat, Long, Altitude): https://stackoverflow.com/questions/30307311/python-pyproj-convert-ecef-to-lla

Further edit: This looks to be ideal, converting the entire obj file at once: https://github.com/TerriaJS/obj-transform although I have no idea how to use it, any ideas?

[mccann8806]

So I just fiddled my way through getting a model of the entire area I wanted. My site was always in the corner of whatever model I was getting at octant 16. It's in the bottom right of 2053736372736176 20
I tried moving the gps coordinates around, thinking that there was a problem with where the gps coordinates were centered, and I eventually figured out that the octants are static, and you locate the octant that your gps coordinates fall in to. Meaning that you might be unfortunate, like me, and have your target fall on the edge of an octant.
My octant 16 chain was
2053736372736174 in the bottom left
2053736372736175 was the octant east of that
2053736372736176 was the octant north of 6174
2053736372736177 was north east of 6174
I dumped all of these at a max level of 20.
I tried to join all of these together, but the textures weren't behaving.
So I went one octant up
205373637273617 and dumped it at a max level of 20
It's a big file, but it worked, and the resolution of the models is not much different.
This is the logic I've figure out so far.

The thing I need to figure out now is if the angle of the models is related to their position on the globe. So I'm off to get something from Australia to see if its upside down.

[desmondCTNG]

@LexSong Is the reverse also possible this way? Tried brute-forcing it but got duplicate midpoints for octants:

0 and 4

$ python octant_to_latlong.py 210
Midpoint: (22.5, -67.5)
Box: LatLonBox(north=45.0, south=0, west=-90, east=-45.0)
$ python octant_to_latlong.py 214
Midpoint: (22.5, -67.5)
Box: LatLonBox(north=45.0, south=0, west=-90, east=-45.0)

1 and 5

$ python octant_to_latlong.py 211
Midpoint: (22.5, -22.5)
Box: LatLonBox(north=45.0, south=0, west=-45.0, east=0)
$ python octant_to_latlong.py 215
Midpoint: (22.5, -22.5)
Box: LatLonBox(north=45.0, south=0, west=-45.0, east=0)

2, 3, 6 and 7

$ python octant_to_latlong.py 212
Midpoint: (67.5, -45.0)
Box: LatLonBox(north=90, south=45.0, west=-90, east=0)
$ python octant_to_latlong.py 213
Midpoint: (67.5, -45.0)
Box: LatLonBox(north=90, south=45.0, west=-90, east=0)
$ python octant_to_latlong.py 216
Midpoint: (67.5, -45.0)
Box: LatLonBox(north=90, south=45.0, west=-90, east=0)
$ python octant_to_latlong.py 217
Midpoint: (67.5, -45.0)
Box: LatLonBox(north=90, south=45.0, west=-90, east=0)

Btw. figured out how BulkMetadata's oriented bounding box looks like:

Script for generating this model here. I think we can use OBBs to find octants of absolute points in space by checking if a point is inside. Probably an inverse of your method is simpler. Might be useful for view frustum stuff though.

I understand that two octants with value difference by 4 could be at different heights, but why is it that 2, 3, 6, 7 are all having the same geographical location? I see "if n == 90 or s == -90, then stop dividing the longitude by 2" in the octant_to_latlong.py script, can someone explain the theory behind?