[Bug report] Incorrect Ray Query Results for terrain (TSM)

[Beauty]

The last few days I got a headache, because I recognized that I have wrong (very incorrect) results for ray queries related to terrain (using the Terrain Scene Manager).
I thought, it's a calculation problem of my own code.
After some tests I found out that the problem is Ogre related.

My test results:

• Vertical rays always return the correct result.
• Non-vertical rays often return wrong values.

The hit points I calculated by this:

Code: Select all

position = rayOrigin + rayDirection * distance_of_rayQueryResultEntity

The resulting height differences are up to 1 Ogre Unit (for my test cases).
Even when the ray origin is close to the terrain surface, the incorrectness of the returned distance is huge. But only if the ray is not vertical.

This behaviour is very bad for my simulation application, because I need more precision than +/-1 Ogre Unit.

Here is an image which shows different rays and "detected" positions (red pixels).
Click image for full size.

Ogre problem - wrong RAY results for terrain.png

Has anybody an idea what's the problem?
Great would be a bugfix. (Although I think nearly nobody is interested in improving the dropped Terrain Scene Manager.)

On the other hand:
If the problem is also related to ray queries with other terrain systems, then it would be important for many other Ogre users, too.

[CABAListic]

The new Terrain component's ray queries have been completely rewritten and work very differently. The TSM queries are not particularly good because they are estimates and can get worse depending on your scaling, I think. Basically, as you already noted, the algorithm just rides along the ray in 1 unit steps and checks if it's over or under the terrain. It stops in the latter case. Now, if 1 unit is large in your scaling, then that's very inaccurate.
I can only encourage you to switch to the new terrain as the ray query algorithm I wrote for it should be accurate independent of scaling or anything else.

[Beauty]

Can somebody do tests with the new Terrain Component of Ogre?
It would be interesting to know if there is the same problem with ray queries.

To be more precise:
The wrong results come from a very incorrect distance value of RaySceneQueryResultEntry->worldFragment->distance

Also I found out more additional facts:

• The hit points are always below the terrain surface, never above.
  (So the returned distance value is always to large. If the distance would be "just" imprecise, there would also be hit points above the surface.)
• The incorrectness seems to be independent of the distance from 'ray origin' to 'terrain hit position'.

If the origin is close to the terrain the deviation is as large as for large distances of terrain.
The returned distance is like:

Code: Select all

resulting_distance = real_distance + random(0, 1)

I had the idea that the reason could be a "simplified" terrain surface for fast ray query calculation.
But when I look to the test picture and connect the single hit points (in mind) then it doesn't look like a "simplified" terrain surface.
It's more looking like constant lengths for neighboured direction angles.
Maybe a formula uses a cos/sin/tan lookup table with very imprecise values?


Source code search

Now I looked to the source files of directory
Ogre 1.7.3 source\PlugIns\OctreeSceneManager\src\. (As I read, the TerrainSceneManger is based on the OctreeSceneManager.)
There are the terrain related files, but in none of all files (in this directory) I found related distance calculations.
Only in file OgreOctreeSceneManager.cpp I found a distance calculation.
But Intersection intersect( const Sphere &one, const AxisAlignedBox &two ) is to check how a AABB intersects with a cone.

In OgreMain I found only one file with "ray" in the file name:
Ogre 1.7.3 source\OgreMain\include\OgreRay.h
There are some intersection calculations, but I don't see any connection with terrain.

Now I have no further idea where to search for the related formulas.

[Beauty]

Thanks for sharing your professional knowledge.

the algorithm just rides along the ray in 1 unit steps and checks if it's over or under the terrain.

Oh, this sounds like a good explanation for the results.
Now I know how it works internally and can write my own search function, which performs further ray queries (in the last stage (Ogre Unit) of the ray) to get the real distance. (This I can do, because vertical rays seems to return correct results.)

Are you shure that the distance increase steps are exactly 1 Ogre Unit?

I can only encourage you to switch to the new terrain.

Unfortunately I can't do that as long as there is no (finished) Mogre wrapper for the terrain component. Our last "coding master brain" has no more time for Mogre development. And people who has enough time, don't have enough knowledge about wrapping and/or Ogre internals.
It's sad, but that's the state of the art.

[Beauty]

Are you shure that the distance increase steps are exactly 1 Ogre Unit?

Well, it's exactly as you sad.
Now when I print the distances, I see it.
Before I only looked to vectors.

Code: Select all

TERRAIN DISTANCE:  2.000027
TERRAIN DISTANCE:  1.999937
TERRAIN DISTANCE:  2.000182
TERRAIN DISTANCE:  2.000064
TERRAIN DISTANCE:  1.999788
TERRAIN DISTANCE:  1.999776
TERRAIN DISTANCE:  2.999843
TERRAIN DISTANCE:  1.453644   <-- vertical ray

[CABAListic]

You could, of course, just modify your Ogre source and set the step size to something smaller than 1. However, this will significantly reduce the performance of the ray query.

And yeah, as I said, this problem does not apply to the new Terrain component at all. The Terrain component uses a different approach which suffers neither from the performance nor from the inaccuracy problems mentioned here.

[Kojack]

How big is your terrain?
Because you could just load it as a normal mesh and use the raycast to triangle code you already have.
You could also cut the terrain into chunks manually, so there's some culling.
Maybe not as fast as a terrain system, but it works, and would also let you have non heightmap terrain (like the game Gothic 3, it's world is a freeform mesh, not a heightmap, so can do some great looking overhangs and stuff).

[Beauty]

set the step size to something smaller than 1.

There would be a better way than just changing the step size.
You just need the last point above terrain and the single point below.
Then you compare the height differences and can perform a linear interpolation to get the real point of intersection (with much higher precision).
I didn't find the right positions of code where to change. Also I would need to compile Ogre and Mogre (the second is harder).
So I will write a "ray correction" method by usage of 2 additional vertical rays inside my application.
It's written quickly and works, too.
I will post my solution, when it's ready.

How big is your terrain?

My defaut size is 10,000 x 10,000 Ogre units (meter).
I also use only one terrain chunk.
For each terrain I created one height map and one texture file.
It's easy, but fully enough for my needs.
Also it's quite fast for loading. (As I read terrain for the new terrain system can cause long loading times.)
I'm not shure if I can create equivalent meshes from my heightmap/texture terrains.
Also I would need to apply changes to my sensor simulation code.
So the best for myself is to stay with TSM.
And by your quick help I can improve the ray query results.

[Beauty]

just modify your Ogre source and set the step size to something smaller than 1.

I think about to apply my way of improvement directly to the TSM source code, because it's a cleaner solution. Also it would be useful for other users (because for Mogre we still can't use the new terrain component).

Unfortunately I didn't find the place for the distance/hit calculation.
You said you re-wrote the whole terrain ray query code. So I assume you know where to find the related formulas of the TSM.
Can you tell me where I find the code, please?

[Beauty]

Ok, my solution works fine.

Here is a screenshot. The red points are the hit points, based on the corrected ray distance.

Ogre problem - wrong RAY results for terrain 2 (correction).png

Here is my code (if anybody need it).
It's written in C#, but should be easy to port to C++.

Code: Select all

/// <summary>
/// Correction of imprecise ray distance queries for terrain. <br/>
/// Background: <br/>
/// Ray scene queries with the Terrain Scene Manager are very imprecise. (because of Ogre TSM internal calculation) <br/>
/// The resulting distance to the terrain hit point is upto 1 Ogre Unit (1m) larger than the real distance. <br/>
/// So the resulting hit point is at the wrong place. (somewhere below the terrain surface)
/// </summary>
/// <param name="ray">Ray which was used for the ray query</param>
/// <param name="terrainHit">Query result for terrain</param>
/// <returns>Correct distance to the terrain</returns>
Single TerrainRayCorrection(Ray ray, RaySceneQueryResultEntry terrainHit)
{
    //-------------------------------
    // Written by Beauty in 2011
    // For bug reports use this forum topic:  http://www.ogre3d.org/forums/viewtopic.php?f=1&t=67631
    // If somebody port this code to C++, please publish it in the same forum topic.
    //-------------------------------

    // skip if no terrain
    if (terrainHit.worldFragment == null)
        return terrainHit.distance; // no change

    // skip if vertical ray  (because vertical rays need no correction)
    if ((ray.Direction == Vector3.NEGATIVE_UNIT_Y) || (ray.Direction == Vector3.NEGATIVE_UNIT_Y))
        return terrainHit.distance; // no change

    Ray[] helperRays = 
    {
        new Ray(ray.Origin + ray.Direction * terrainHit.distance,         // origin under terrain surface
                Vector3.UNIT_Y),
        new Ray(ray.Origin + ray.Direction * (terrainHit.distance - 1f),  // origin above terrain surface
                Vector3.NEGATIVE_UNIT_Y)
    };

    Single[] helperDistances = { -1f, -1f };

    RaySceneQuery rsQuery = mScene.Smgr.CreateRayQuery(new Ray());  // IMPORTANT:  Set reference to your SceneManager here

    // query real terrain height for helper rays  (by vertical rays)
    for (Byte h = 0;   h <= 1;   h++)
    {
        rsQuery.Ray = helperRays[h];
        RaySceneQueryResult vResult = rsQuery.Execute();

        // search for terrain hit
        foreach (RaySceneQueryResultEntry hit in vResult)
            if (hit.worldFragment != null)
            {
                helperDistances[h] = hit.distance;
                break;
            }
    }

        // skip if helper query failed  (happens when ray origin is below terrain surface)
        if ((helperDistances[0] == -1f) || (helperDistances[1] == -1f))
        {
            if (terrainHit.distance < 1.01f)
                // ray origin is below terrain  (in this case the TerrainSceneManager returns a value around 1 for distance)
                return 0f;  
            else
                // uncommon case (could happen at outer border of whole terrain)
                return terrainHit.distance; // no change
        }


    // skip for special case  (very rare, but possible - would cause a division by zero)
    if (helperDistances[0] + helperDistances[1] == 0)
        return terrainHit.distance;

    // calculate distance correction
    Single correction = helperDistances[0] / (helperDistances[0] + helperDistances[1]);

    // apply correction
    return terrainHit.distance - correction;
} // TerrainRayCorrection()

Changelog:
2011-11-21: Improvement for origin below terrain surface (details here)

For usage just add 2 lines of code:

Code: Select all

// for all ray query results
foreach (RaySceneQueryResult resultEntry in vResult)
{
    // if terrain, APPLY DISTANCE CORRECTION
    if (resultEntry.worldFragment != null)
        resultEntry.distance = TerrainRayCorrection(vRSQuery.Ray, resultEntry);
    
    // ... user code ...
}

Calculation details as images:

Ogre problem - wrong RAY results for terrain 3a (correction).png

Ogre problem - wrong RAY results for terrain 3b (correction).png

[Beauty]

Ogre problem - wrong RAY results for terrain 3c (correction).png

Ogre problem - wrong RAY results for terrain 3d (correction).png

[Beauty]

I updated the code (in previous post).

Reason:
When ray origin is below terrain surface, the TSM returns a distance around "1".
Now my code set the distance to "0" for this case.