Issues with floating origin

Started by
58 comments, last by dragonmagi 2 years, 2 months ago

So, I've got this big top-down 2D space and in this space I have a space ship, and a few planets. These planets are separated by huge distances (e.g. one is ~800,000 units away).

I'm aware of floating point issues when you start to deal with objects that far away. Particularly object jitter.

So, to tackle this I implemented a floating origin (more specifically, a continuous floating origin... I think... there's actually precious little about continuous floating origin). This worked fine for a bit.

That is until I decided I wanted to be able to "jump" to the location I want. By jump, I mean that I shift the world around me by the number of units needed to get to my destination. However, when I translate the world so that the destination point is 0x0, the object at that position is off by a noticeable amount (it should be at 0x0, but ends up in slightly different locations each time).

Is there a special way to deal with just repositioning and floating origins that I'm missing? Is there a better way to do this?

Thanks in advance.

For reference, this is the code I'm using for my floating origin:

		/// <summary>
        /// Function to assign the origin offset used to readjust the entities.
        /// </summary>
        public void MoveWorld(Vector2 offset) => _offset = offset;

        /// <summary>
        /// Function to make the specified entity's position the origin of the map.
        /// </summary>
        /// <param name="entity">Entity to use.</param>
        public void MakeOrigin(Entity entity)
        {
            _offset = entity.Transform.Position.ToVector2();
            Update(entity);

            // Reset the transform to 0 because we are now the origin.
            entity.Transform.LocalPosition = new Vector3(Vector2.Zero, entity.Transform.LocalPosition.Z);
        }

        /// <summary>Function to update the world around the primary entity.</summary>
        /// <param name="originEntity">The entity considered the origin of the scene.</param>
        /// <remarks>
        /// <para>
        /// This should be called during the <see cref="CodeBehindComponent.FinalUpdate(float)"/> method.
        /// </para>
        /// </remarks>
        public void Update(Entity originEntity)
        {
            foreach (Entity entity in _map.Entities)
            {
                if ((entity == originEntity) || (entity.Transform.Parent is not null) || (entity is MapLayer))
                {
                    continue;
                }

                entity.Transform.LocalPosition = new Vector3(entity.Transform.LocalPosition.X - _offset.X, entity.Transform.LocalPosition.Y - _offset.Y, entity.Transform.LocalPosition.Z);
            }

            _x = (decimal)-_offset.X;
            _y = (decimal)-_offset.X;
            Distance += -_offset;            
        }
Advertisement

Never heard about “continuous origin”, but your “Vector2.Zero” looks weird. I mean, everything in the world is at a non-precise position, so all your translations won't be exact. And then you discard all non-precise data of this one entity.

So I wonder what would happen if you translate this one entity in the same way as all the other entities?

The way I do it is I don't actually have an single origin per se. That means there is no “world space", I have a tree of objects. For example the sun, the planets which are children of the sun, down the a character, which is a child of the planet he's standing on or near. Between a parent and a child there is a “reference” object. Some kinds of references allow for movement. For instance there is an orbit reference for planets (both Circular and Kepler), and a walking reafference which is a character controller. References have matrices for transformations in both directions. Each object has it's own origin of course.

I use double precision, but that's mainly because I'm in 3D and have large planets and distances. If your scale is smaller, you might be able to get away with float. Keep in mind on the CPU double is almost as fast as float. In any case you will convert to float before going to the GPU regardless, so when rendering you will still have a float matrix. Usually that's what your base graphics system expects.

Now the camera is also an object and it has various kinds of references for using it. For example there is a follow reference for following other objects that move, such as a character. When I render I always start at the position of the camera in the tree. It's typically at the bottom somewhere. When I go up a from one object to the next I apply the transformation for going up (like the inverse), and the opposite going down. I render objects when I traverse them in the tree. So basically I never go to world space (since there is none). I always go straight to view spaces which means you don't have the precision issue to begin with since things close to the camera are by default near the origin.

So in short I'm not doing anything specifically to move the origin. It's just kind of naturally moves on every frame. Not sure if this is applicable to what your trying to do, but maybe you can glean something from it.

@Alberth The idea behind continuous origin is that you are always at 0x0, you never translate your view. This is unlike most other floating origin setups which tend to use a threshold and then shift everything back. Also, this specific function is only called once at startup and never called again, it just resets the entity to 0 and sets the origin offset to whatever used to be in the position transform.

@Gnollrunner I tried using doubles, that ended badly (it kinda fixed things, but it broke other things). Beyond that I really don't want to have to build up a math library based on doubles if I don't have to. I'm not trying to simulate actual distances, just big enough that it'll take time to get there. I'm looking into seeing if I can use some kind of spatial grid to give each cell its own, smaller, coordinate system that will fit within single float range. Unfortunately this is giving me grief because I'm using parallax levels. Regardless, I'm not familiar with spatial partitioning schemes like quadtrees or spatial grids. Most of the stuff I've found is about collision and not really about avoiding precision issues.

Tape_Worm said:

@Gnollrunner I tried using doubles, that ended badly (it kinda fixed things, but it broke other things). Beyond that I really don't want to have to build up a math library based on doubles if I don't have to. I'm not trying to simulate actual distances, just big enough that it'll take time to get there. I'm looking into seeing if I can use some kind of spatial grid to give each cell its own, smaller, coordinate system that will fit within single float range. Unfortunately this is giving me grief because I'm using parallax levels. Regardless, I'm not familiar with spatial partitioning schemes like quadtrees or spatial grids. Most of the stuff I've found is about collision and not really about avoiding precision issues.

Well you don't need double everywhere. For instance your models can still be in float if they are small enough. You mostly just need the matrix operations. That really isn't hard at all. I wrote the basics stuff in a couple days years ago, and I have slowly added bits here and there. It's basically a template library you can give it either float or double. It's probably not so optimized since I wrote it before SIMD but it actually works well enough for now and the compiler does some SIMD optimization itself.

Frankly I'm surprised more people doesn't just use double. There is really nothing tricky about it. IMHO there is no real reason to jump through hoops to avoid it, but suit yourself.

Tape_Worm said:
Is there a special way to deal with just repositioning and floating origins that I'm missing? Is there a better way to do this?

I think your issue is: All your data is represented by single precision floats(?). So that's not enough precision to represent your larger world to begin with.
Then you constantly transform it, introducing error each time.

For a robust floating origin, you'd need to represent your objects with doubles, transform to a local double-origin, only after that convert to float for further processing, update the double data as well on changes.
Obviously that sucks a bit, which is why most people end up using just doubles for everything.
But it depends. In many cases the floating origin surely remains the faster way, and the extra complexity can be worth it.

Gnollrunner said:
Frankly I'm surprised more people doesn't just use double.

My reason is the same: It's hard to switch your math lib, which often is some SIMD optimized stuff restricted to floats.

And i don't want to write a templated replacement, because it would be slower a bit. Even less i want to learn about SIMD intrinsics.

If anyone knows a linear math lib supporting both float and doubles, let me know…

JoeJ said:

Gnollrunner said:
Frankly I'm surprised more people doesn't just use double.

My reason is the same: It's hard to switch your math lib, which often is some SIMD optimized stuff restricted to floats.

And i don't want to write a templated replacement, because it would be slower a bit. Even less i want to learn about SIMD intrinsics.

If anyone knows a linear math lib supporting both float and doubles, let me know…

I've written plenty of SIMD floating point routines. Even if you have to have a something SIMD optimized it's not that hard and in a 2D game it's probably not even that important. With AVX2 it's easily doable and you could even do something with plain AVX.

On the flip side by not using double, you spend a huge amount of time trying to get around the precision problem which is otherwise easily solved. If you are using a game engine there is certainly an argument for sticking to float. If you aren't however, I think it's a no brainer to go to double.

Gnollrunner said:
I've written plenty of SIMD floating point routines.

I have some questions… (actually it seems so much of a dilemma, i tend to ignore / postpone it)

If we use it for our most common data type vec3, we'll waste one of 4 slots on doing nothing, plus the memory lost as well.
If we try to do better, using SOA layout, our data scatters across memory like crazy, leading to mostly cache misses when accessing it.
We can counteract that by processing things in sequence, but that's possible only for brute force workloads, which in general we do not want.

So what should we do? There seems no general answer. It always depends on the case. So SIMD is doomed to be a close to the metal optimization we can only use at some bottlenecks. Otherwise it's almost useless. Is it worth the die area then?

It would be much nicer to have more general purpose registers and cores instead. Like GPUs do, with their scalar architecture treating a vec3 as 3 individual numbers, which works for vec2 and vec4 just as well.

The issue with those high performance fixed function HW blocks is always the same: They lack flexibility and dictate brute force.
Maybe Intel even does us a favor by literally destroying their AVX512 blocks on their current lineup. Just that we still pay for it regardless.

Tape_Worm said:
I'm not trying to simulate actual distances, just big enough that it'll take time to get there.

In this case, could you perhaps fake it by translating and scaling objects, combined with a very slow movement speed, to give the impression of distance without actually having distance…?

MWAHAHAHAHAHAHA!!!

My Twitter Account: @EbornIan

This topic is closed to new replies.

Advertisement