What do people think of a 48-bit integer coordinate space?

What I am proposing here is to rebase the overarching client-side coordinate system in Vircadia to 48 bit integers, rather than the current 32-bit IEEE floats. Only client-side, though.

Note: This is NOT a proposition to change the graphics system to integer/fixed-point

Summary

(that would be an awfully big job of no benefit in the context of currently common GPU hardware!)

.

Also note: I would be able to put some time (several hours per week, indefinitely) into working on these ideas myself (ie, I’m not asking others to do it for me), but would only be interested in doing so if the community feels it is a worthwhile direction for Vircadia! Also keeping in mind that I am not a professionally-trained programmer - I’m self taught, mostly in C on micro-controller-class devices. I am happy to try to learn as I go, but would require some support via answering of probably-stupid questions in the forums! :grinning_face_with_smiling_eyes:

So this is primarily intended a question on if it is worthwhile (to the community) for me to pursue this idea. Details below are provided for clarity, and for opportunity for others to point out any flaws in my idea (and any mistaken assumptions I have made in formulating it!).

…

Anyway…

The current Vircadia system has an object-placement coordinate system based on 32-bit IEEE floating-point numbers. Though in theory, this allows a server-administrator to choose world-extent vs object-placement-resolution, at present it seems to be fixed to a 1mm granularity and 16km extent for practical purposes, in the user-side UI at least.

I am proposing an alternative in-world coordinate system (predominantly expressed client-side) using 48-bit integers with a fixed granularity of 10Îźm* (ie: 1 unit = 10Îźm).

Summary

*Declaration of conflict-of-interest: I have chosen the 10μm value for entirely personal reasons. Specifically, it is a usefully-fine-grained value occurring at a ‘sweet-spot’ intersecting the base-10 metric system closely enough (97.6%) with my own preferred measurement units (base-8 multiples of the plank-length) that I can fiddle the UI to use either base+unit just by adding/subtracting zeros from the numbers displayed/input in a marginally-modified UI!

This would give a coordinate system with an extent of 2.8 million!! km. Rather large, being big enough to very comfortably fit a Jovian-moon-system-sized ‘world’ inside its bounds! (

Summary

64-bit would get you out to solar-system scale, which could be an option, but keeping those high 16-bits reserved can potentially help with keeping integer/fixed-point maths within the range of a 64-bit CPU register while calculations are in-flight!

Summary

Also, to mash up Arthur C. Clarke and Bill Gates* “All the worlds of Jupiter ought to be enough for anyone!” :smiley:

Summary

*To be fair on Mr Gates, in context his statement should be more like: 640k ought to be enough for anyone using MS-DOS for anything it could reasonably be expected to be used for.!

)

To properly utilise this additional coordinate space, a server would have to supply the client with the following additional data about itself:

1) Base scale - an indicator of the ‘unit’ size of the server.

At present the scale of a Vircadia appears to be assumed fixed at 1mm object placement resolution across an approximately 16km extent, per axis (before resolution granularity starts to noticeably suffer the effects of floating-point-format non-linearity).

Instead, I suggest the server should be able to specify its preferred optimal FP range explicitly to the client, so the server-operator can choose to reduce the maximum extent to gain higher object placement-resolution or vice-versa, and the client UI can set its input limits accordingly (it is, I believe, mainly a UI issue, as the nature of floats already allow this to be done as long as the user manually avoids exceeding the preferred bounds - this mostly just makes it explicit it in the UI presented to the user).

Summary

Personal note: I originally was going to suggest switching server-coordinates to 32-bit integers to better use a smaller fixed resolution over a greater extent, but after typing out my ideas on that realised that being able to actually choose the trade-off in extent-vs-resolution is sort of what IEEE floating point is all about in the first place, so why not use the existing format’s strength!

2) Origin offset - a 32-bit-per-axis offset in 48-bit coordinate space (added to the 32 MSB of the 48-bit coordinates of the server’s objects to get absolute location in 48-bit space).

This allows multiple servers to inhabit the same coordinate space seamlessly, with the avatar moving between them simply by changing location in 48-bit integer space.
It is assumed the client is tracking which objects in its 48-bit space are being served from which server and unioning them in its local scene-graph.

Note that the server placement-resolution provided will be about 0.66m, or 2ft (10um*2^16), which allows fairly fine-grained placement of server-origins (for example, it is sufficiently fine for fitting an apartment-sized ‘world’ into a level of a sky-scraper-shell with other ‘apartment-servers’ filling other levels of the same shell; or being able to place 1/4-acre housing blocks along a non-strait road. ie, not forcing a Second-Life-style fixed-sized-grid-layout to such worlds).

Rather than each server individually advising its ‘origin offset’, it might be more efficient and secure to for any server sharing physical space with others to send a link to a new type of server (and a null-type address if not space-sharing)…

3) Federation Server

An additional server type would handle federated sets of worlds, one server per federation, managing the origins and bounds of all its contained worlds.
Note that this is not one central server for all federated worlds, but one server per federated set, of which there could be any number. We are not centralising here at a general level, only between server-operators that want to share a space, with as many shared spaces as desired. A user would still ‘teleport’ between individual federations, but now can move spatially between servers within a federation sharing a single coordinate system.

…

Notes for consideration:

  • Spatially-overlapping servers probably don’t need to be aware of each other except in special cases.

  • Avatars will need to interact with multiple servers where objects of said servers are occupying the same space.

  • Would OR-ing collision boundaries between multiple space-concurrent* servers (ie, a collision on any server blocks the avatar) be manageable? … Probably reasonable to no expect more than 4 concurrently geographically-overlapping servers: eg: over-world, sub-world, local-world, closest-local-neighbour at the extreme.

  • Server-controlled physics-controlled objects would be bounded by their server spatial extent (probably mostly a good thing as it stops inadvertent - or deliberate - object-spamming between non-overlapping servers - ie: I can’t stuff my physical-neighbours’ space full of tribbles hosted from my own server!)

  • A special object type/attribute for NPCs, Vehicles and such, that explicitly forces multi-server physics interaction might be enough to cover cases where generic inter-server physical interaction is useful/desired, so cases where this extra load is present are explicitly set up, with the lighter-weight no-interaction being default for most objects. Servers could also explicitly handle inter-server-object interaction via custom back-end programming, with an appropriate API, where the general explicitly-via-physics interaction described is not sufficient.

The client-side object-location calculation would likely go something like…
_For each axis (X,Y,Z)
__Convert object location float32 to int64 (normalised via server_base_scale to 10um units)
__Add (32-bit_server_origin_offset << 16)
__Subtract current 48-bit-space avatar location
__Convert back to float32 for graphics subsystem (assuming things far away from avatar won’t miss any loss in precision from this conversion - or are far-clipped out anyway)

A bit of extra work there, but the avatar-location-subtract, at least, is presumably already happening somewhere in he graphics stack.

Also, this calculation is just needed once per object in the scene-graph - calculations on all sub-vertexes, etc. shouldn’t need to change, just use the above final float32 origin result instead of the raw server-origin-relative one they presently use. That is to say, I wouldn’t expect this to noticeably impact performance as it is a relatively tiny part of the entire graphics pipeline.

…

Example use-cases:

  1. Sole world
  • A lone-world server would just set its origin_offset to zero and carry on indistinguishable from present.
  1. Building complex
  • A macro-server would supply the shell of the building, (and possibly enforce server-boundaries within - extra coding presumably required).
  • Individual apartment-servers are slotted into appropriate cavities within the building shell and serve internal walls, furniture, etc. to any avatar within this cavity.
  • Optionally, a apartment-server might serve a low-poly, low-frame-rate, version of its contents to anyone observing it from outside (eg, through the windows).
  • Note that the building-server and apartment-servers are identical from a codebase and functionality perspective: they just have different scale and origin settings.
  1. Township
  • A town-server supplies a terrain and some public amenities such as roads/pathways, etc.
  • House-servers occupy designated housing blocks and provide the contents of them (high-poly if on the block, or a low-poly shell if viewing from outside)
  • Additional servers may supply parks, chunks of forested areas, etc. high/low poly, as per housing blocks.
  • For visual continuity, the town-server might also cache a home-server’s low-poly building which it can substitute in if it detects home-server has gone offline.
  • Note that, again, the township-server and house-servers only differ in scale and origin settings.
  1. Country
  • A country-server hosts multiple of the above town-servers which in turn host house servers, and possibly also a few apartment servers in the capital!
  • Additional servers supply forests, deserts, fields, lakes, etc. between towns.
  • The country-server also supplies a programatically-generated terrain for all the above to sit over, and the default sky for them to sit under.
  • Some apartment-servers are providing multi-sub-server orbital-space-station-shaped structures high overhead.
  • Yep, nothing special about the different ‘levels’ of server here, only scale and origin settings.
  1. Turtles
  • All the way down! As far as you care to go. Well, down to 0.66m, anyway!
1 Like

There’s a lot here so forgive me if I only inquire about parts of it for the moment!

As an overview, you are proposing that we make the resolution of scale variable for the client and server to allow for more precision or a larger extent depending on the needs of the world.

I really like this kind of capability as it would be very helpful for VRMMO worlds in the future. However, what might be the performance impacts of such a system, specifically in the way you have proposed it?

The server also has things to process such as the entity tree and all entities and avatars within it in real-time. A large part of the allure for our server is its relatively decent scale coupled with its ultra high performance. A massive world is only as good as the things it can support within. Though, I can see the use for a much larger space even with a reduced capacity… something like Elite: Dangerous, Star Citizen, or EVE Online could be created relatively on a Vircadia Domain server.

Either way, a system like this would be a massive net positive even if capacity did not increase. The main thing we’d want to consider is to ensure that the current capacity would not be reduced.

I wouldn’t really expect any noticeable performance drop for any comparable-to-current world. Of course if you try to fill up a lot of space on a single server with massive quantities of objects, the same will happen even on the current system, just in a smaller area.

To clarify, the proposed 48-bit coordinate space doesn’t apply to servers - for that exact reason - you will hit a database+physics performance wall long before you fill a single server to any great density, so the (effective*) 24-bit integer coordinate space currently available server-side is plenty.

*using floats for a linear coordinate system is a bit of a ‘float-abuse’ no-no, but programmers who are used to using floats in all graphics operations tend to default to them everywhere, even when they really shouldn’t! (I’m biassed, though - coming from micro-controller land, I am used to having access to solid fixed-point maths in hardware!)

The proposed 48-bit space is intended to allow seamless federation of multiple servers - Performance-wise , at least if the server-spaces are kept non-overlapping, it would be rather similar on both client and server to what you get now with Alezia’s exceptionally clever super-domain, but without the need for intercepting avatar locations and inserting invisible teleports between worlds. If you start over-lapping servers, then client performance will drop off from having to manage a union of data sets, of course, but overlapping server-spaces isn’t mandatory, just an option for where it makes sense (and you have done performance testing to make sure it is reasonable!)

Personal note: Ironically, seamlessly federated worlds have turned out to be a big benefit of this, but are not actually something I am very interested in for my own use, but support for them fell out of the integer coordinate system which I do need for some of my actual future plans. I could just do a 32-bit-integer conversion (a 44km world @ 10um granularity is plenty!), but if I was to change the format anyway, I might as well go all the way in one go!

I think it’s a great idea and allows domain owners to do much more… you would have to however do more crud in the interface so that you are not holding onto things in memory as they pop in and out of view… This could easily result in run away memory issues otherwise if not managed properly…

1 Like

Very much. The actual support for multi-server worlds would likely be a longer-term goal.

I can see this being broken into stages:

  1. 48-bit integer coordinate system conversion on client-side.
  2. Add world-origin-offset support to client, and ability to report this offset to server.
  3. Add client ability to support multiple non-overlapping worlds in one space.
  4. Support over-lapping-in-space worlds - the most challenging bit!
1 Like

Some miscellaneous comments / questions:

  • Current Vircadia coordinate system is 32-bit float metres. Apparent 1mm resolution is UI-imposed. Precision decreases as distance from origin increases.

  • 64-bit floats can represent 53-bit integers, I believe.

  • In C++, I imagine that 48-bit integers would be implemented as something like typedef uint64_t uint48; and masking the desired 48 bits?

  • In JavaScript, I imagine that 48-bit integers would need to be implemented using either number (i.e., 64-bit float) or BigInt (arbitrary precision integer) types.

  • Babylon.js uses the JavaScript number type (64-bit float) for its coordinate system, I believe.

  • Rotation precision also needs to be considered: a small difference in rotation at the origin translates to a large difference in position at large distances. [*]

  • I don’t have a handle on the potential impact of the multiple type conversions and calculations in the float / int48 coordinate transformation but it does make me nervous given the already high CPU load.

  • Can similar origin offset etc. be achieved using more-standard 64-bit reals rather than a custom numeric type?

  • Would changing the Vircadia coordinate system to 64-bit reals everywhere (i.e., not just an offset) achieve similar benefits without extra calculations?

[*] Exacerbating this problem, the Vircadia protocol currently compresses rotation floats (i.e., they lose precision) and the compression/decompression algorithm doesn’t preserve 0.0 - one of the reasons for not building at the extents of the nominal 32-bit float coordinate system.

2 Likes

Thanks @ctrlaltdavid, all feedback greatly appreciated.

To some of your points:

  • Vircadia’s declining-with-distance-from-origin precision is exactly why floats shouldn’t be used to represent a linear number graph (ie: float abuse!) floats do tend to get used all over the place, more often than not in inappropriate places and always end up biting someone on the bum! Unfortunately they are so readily available on modern CPUs that it is far too easy to use them inappropriately (and to a degree you are forced to in many situations by deficiencies elsewhere in the instruction set - * cough * integer/fixed trig functions * cough *). Unfortunately we are pinned to their ongoing use by decades of legacy now :-/

  • 64-bit floats can accurately represent 53-bit ints. And it is relatively easy to convert a 48-bit int into a float (no actual maths involved even - just OR it with a bit field representing a pre-calculated exponent) :grin:

  • I would probably just use 64-bit ints internally (that upper 16 bits is often good for transitory mid-calculation overflows, saving you a bunch of carry-catches … you may still have to catch overflows and do the extra multi-register-maths-shuffle in extreme cases, but incidences of this should be greatly reduced).

  • Javascript is a good catch - something that is a definite issue (I’m not a big fan of languages that lump entirely incompatible numeric concepts like ints and floats together, if you haven’t guessed!). It is another good reason to limit to 48 (or 53 at most) bit ints for the coordinate system so you can mis-use the available resources (in this case f64) without losing precision. Not ideal, but there is a point where you have to accept working with what you have!

  • The Rotation precision issue is a big reason I quickly discarded the idea of being able to arbitrarily rotate sub-worlds - also it is a lot of extra trigonometry added to EVERY vector in the scene for not enough benefit. Because I am not proposing (or wanting to, for this exact reason) increase the server-side maximum distances, all rotations within server-space are going to be relative to that server’s origin, not the client’s origin, so rotational resolution won’t be any better or worse than existing. Note that the proposal doesn’t change anything server-side other than the server sending out an extra 3 int32s of metadata when a client connects to it, namely its X,Y,Z origins in 48-bit client-side space. The server shouldn’t need to know where it is in this space for any of its internal operations - the client just takes everything the server gives it and adds the origin-offsets to that data.

  • I would expect the slow-down from those 3 extra 64-bit ads per object in the scenegraph to be measurable, but am dubious that they would be noticeable. It would also depend on if more of the stack could be integerised - there is a point were things will have to be converted to floats just to interface with libraries (and ultimately hardware), but IF it turns out to be possible to defer that point enough the efficiencies of using ints over floats would balance back. There is no way to know without actually writing the code and testing it though.

  • 64-bit floats would certainly work too (without any precision loss over 48-bit ints) but at the expense of using floats - which are inherently less efficient and slower, even with the insane transistor-counts that modern CPUs throw at them! I just don’t see any advantage in using a real over an int here, other than a long programming tradition of using reals in entirely inappropriate places!

Yes, I’m a being bit down on floats/reals here, but so many programs really do suffer from their mis-use. Which isn’t to say they are bad at all. They just need to be used in a way they are suited for!

They are perfect for things like compactly representing vectors of force (ie physics engine) where loss of precision as values increase is not going to be noticeable (in the context of game-physics, not science-physics … boy did a lot of early physics GPU-compute people get bitten when it turned out that while early GPUs took 32-bit floats in their documented APIs, they only processed about 12-14 bits of the significand! - I believe modern GPUs do process the entire thing - but only because they are used for so much non-graphics stuff these days - graphics rasterization generally doesn’t need such high precision).

Floats/reals are, by design, just awful at representing anything that requires an equidistant numeric representation (such as Cartesian coordinates). In these cases you basically have to ignore the exponent anyway, which is a waste of bits and CPU energy! The only valid argument for doing this is that you are stuck with language/libraries/API/hardware (any/all of) that forces you to do it that way (my major worry, and the show-stopper for my proposal, is that this might be the exact case here).

Your idea of a federation server and domains being combined in the 3D world is similar to a viewer design I’ve been kicking around. The idea of domains in the same location space being OR’ed together in 3D to create a continuous view I extended into domain “layers” which were OR’ed together . So a single domain could have a “static layer” and a “physics layer” and an “avatar layer” which all existed in the same location space and were overlaid. The different layers could even use different data formats or different protocols (like “static” layer using all HTTP while the “physical” layer using UDP or some real-time protocol).

Then, the viewer asks the Federation server “I need to view from location X,Y,Z so what do I see” and the Federation server would return a set of layers for that location.

A “layers” design could also be extended to things like audio but the general idea is that several domains/content types/resolutions/etc can be merged together in 3D when they are in the same location space.

To give the float option some luv… I echo some of @ctrlaltdavid comments and add a vote for 64 bit floats measuring meters. 64bit floats gives scaling from microscopic to galactic, have compression options (if bandwidth is a problem), have a mappings to and libraries for all languages and protocols, and, in the long run, would be easier to maintain than a custom/proprietary 48 bit-plus-scaling-factor format.

1 Like

There are a number of potentially separate ideas here, including:

  • Combining multiple domains in a single space

  • Offsetting a domain content for display in the single space

  • Scaling domain content for display in the single space

  • 48-bit integer coordinate system in the client

Some further considerations about the coordinate system:

  • Octree: This database of entities is axis-aligned so integer calculations of positions would presumably be fine.

  • Orientations: Entities can be rotated relative to the axes. Rotation values are represented as quaternions (normalized 4-vector of floats).

  • Transforms: In some places in the code, 4 x 4 transform matrices are used to scale, move, and rotate things.

  • Physics: Entities can move, rotate, and collide. The Bullet physics engine presumably works in floats.

  • Entity hierarchies: Entities can be parented to others to form a parent/child tree such that when the root entity is moved or rotated, the whole tree of entities moves and rotates accordingly to maintain their positions relative to the root. Floats will still be needed in these calculations (quaternions or possibly transforms used).

Unfortunately, float’s won’t actually give you the vast number range you mention in this specific case. Using solar-system-scale as the example, a float64 at below-noticable-precision would get you out to approximately the inner edge of the Oort cloud fine, but by the outer edge of the Oort cloud, you are far enough into precision-loss territory that your object placement resolution is down to meter-precision and anything that is trying to move at less than 1+meter/frame is either going to be locked in position or juddering along at said 1+meter/frame, depending on if you are rounding up or down in your calculations!

Remember floats are not magic - they are explicitly - by design - lossy compression of the number space. As such, they are perfect for situations such as (human-perceptible) physics, where by the time you are at high enough magnitude to loose precision, that precision is not worth keeping anyway, and also very good for graphics, where a minor loss in precision is going to be drowned out by the general lossyness of human perception anyway (ie, it really doesn’t matter if that line is off by 1/4 of a pixel).

Floats are excellent for any such situation.

They just suck when loss of resolution is going to bite you, and a Cartesian coordinate system is specifically such an instance.

As such, using a 64-float would work, but you would have to lock the exponent down to a very specific range, defeating any real advantage of using floats in the first place.

Having said all that, in light of the needs of the API (particularly JS compatibility), it looks like using a 64-bit float but externally clamping the range of the exponent would be better than trying to use a 48-bit int, though.

…

Float-64 server-side doesn’t appeal to me at all because you are doubling the data size for no realistic gains. A single server (not even that 28-core/112-thread Power9 system I wish I could justify buying!) is never going to be able to utilize that space anyway, and if you are spreading the load across multiple servers, you are going to need some sort of federation mixer anyway, which can bump the local coordinates to a 64-bit universal coordinate itself without dragging down individual server (and network) efficiency with unnecessarily wide data. My proposal basically puts this mixer in the client.

If I was going to fiddle with the server side (and I am not proposing that can of worms!), I would switch to 40-bit floats, but store the significand and sign in a 32-bit int and have a single byte storing the exponent common to everything on the server. You would have to munge this into a 64-bit float for calculations on normal hardware (and likely cache the 64-bit versions locally for performance), but at least your stored and transmitted data would not change in size (well, it would increase by 1 byte per log-in event per client, on the network). Bandwith (both between and inside machines) is, I expect, the major barrier to performance, so it should be conserved as much as possible!

(Yes, I am the type to agonize for weeks over how to most efficiently pack a bitfield or a struct!, for both storage and processing. In micro-controller land where memory is tight and CPU-performance tighter, these things are perceptibly important! :wink:)

…

Aside: I have been doing a bit of a deep dive into how modern FPUs do their calculations. As in down to logic-gate level, which is where I am most comfortable! … Some impressive stuff, and some even more impressive stuff in the works! It has made me a good bit more tolerant of the format* though still only when used appropriately! :sweat_smile: ie: in modern CPUs, the efficiency of FPUs is higher than I had given them credit for. In specific cases, a float calculation can even be faster and more energy efficient than the equivalent integer calculation, which is not something that is really comprehensible above logic-gate level, but makes sense once you follow the gates through!

*IEEE floats, specifically, have a few extra (though relatively minor) issues, but that is nothing to do with the concept behind floats - the IEEE had to make some difficult specification decisions with too little data back then. (Beyond undocumented reduced-size significands, the other part of why older GPUs were unsuitable for non-graphics-compute is that they dropped a lot of the edge-case catches and precision-erosion workarounds that IEEE floats mandate. This saved considerably on transistors and increased FLOPS without user-visible side-effects in the image render, but as you can guess, screwed up some real-world-physics calculations rather badly until the missing bits were compensated for in the code - and these days added back into the GPU hardware, at least the hardware rated for GPU-compute - don’t try real-world-physics on your phone GPU!).

This is an interesting subject… time permitting, have you made any progress here?