Some Solutions

Use relative coordinates. The origin in your universe is in a fixed position, but you can perform all your calculations in a space relative to an origin closer to the action, such as the camera viewpoint. Positions themselves can be stored as floats relative to some other local origin, whose position relative to the universe origin is defined in a more accurate manner.

Use fixed points. If it's important to your game that everything look and act the same whether near the origin or far away from it, then you can use fixed-point numbers to store your positions.

Essentially, it's like using integers but with a sufficiently small unit, so for example 1 could represent 0.1mm, or whatever works for your situation. This can be extended to use 64-bit fixed points for even greater range and accuracy.

Use doubles. For defining points that are a long way from the origin, you can use double precision floating point numbers. You can either define all positions as doubles and then convert to a local space for manipulation as floats, or define a remote region's position using doubles and use relative positions within that space using floats.

Boundary Conditions

We often think of polygons and their edges as pure mathematical planes and lines, which is useful when formulating algorithms to solve certain problems. Consider a simple 2D problem: deciding which side of a line a point is on.

This kind of test is often used when determining if a point is inside a triangle or other similar tasks. So, we specify it mathematically: Given a line formed by two points A and B, and a third point P, we calculate the Z component of the cross product of AP and AB, Z, such that Z=((P-A)x(B-A)).z.

If Z is negative, then C is on the left, and if Z is positive, it's on the right of the line. This relationship is purely mathematical.

To see if a point is inside a 2D triangle, a simple method is to traverse the points of the triangle in a clockwise order and use the same test to see if the point is to the right of each of the three edges of the triangle.

This test can also be used for 3D line-triangle collision detection by first transforming the triangle's points into the space of the collision line (using the transform that would make the line parallel to the z-axis, reducing the problem to two dimensions).

Figure 2: The line from A=(0,0) to B=(5000,5000) separates all points P in this region into two triangles based on the sign of z of the cross product APxAB.

 If we have two triangles that share an edge (as most triangles do in video games), and we apply the above tests to them, we should be able to accurately determine which triangle a line lays on. Figure 2 shows two triangles and the results of the test (Z<0) on the line AB that defines the edge they share. What a nice, clean, mathematical split.

Of course, the obvious problem with this test is for points that lay on the line between the polygons, where Z=0. In our pure mathematical world, a line is an infinitely thin region between the polygons. But in the practical world of floating points, the reality is rather different.

If you zoom in on the line, down to the level of the individual float regions I described earlier, you will see the line defined by Z=0 is composed of a series of regions (see Figure 3). What's more, if you zoom in on the same line, but go farther from the origin, you see that the size of these regions increases (as Figure 4 illustrates).