Hanging in updateShadowVolumes - 1.8

[robmar]

With all SVN´s up to latest of 1.8 release I´m getting a hang in updateShadowVolumes:-

Line 275:-

// recalculate adjacency if necessary
if (oldVertexCount != VertexCount || oldIndexCount != IndexCount)
calculateAdjacency();

It gets stuck in the for-loop of the call to calculateAdjacency.

[CuteAlien]

Would be great if you had some test-case for us.

[robmar]

Working on it! The test code is the TKOceanScene sample (reflective water) with an animated mesh above the ocean rotating.

Under 1.7.3, with the same code, the scene shows a messed up shadow on the animatedmesh, with black lines between parts of the animated mesh object, some single black line etc.

Will post more details and sample.

[robmar]

Digging a bit further the problem, the "hang", seems to be caused in the procedure below, which runs two for-loops that iterate exponentially the number of faces in a mesh.

If IndexCount = 36, i.e. 36 faces, then it will do 36 loops of 36 inner loops, i.e. 1,296 / 9 iterations.

But if an animated mesh has a 1000 faces, it will run a million / 9 loops.

If it has 10,000 faces, a more complex mesh, it will run 100 million / 9 loops.. well lots of calculations, and then everything starts to grind to a halt.

There are also some calculation errors on shadows caused at certain angles that blank the whole scene, and with the TKOceanScene sample, for some reason the ocean texture get set to the shadow color all the time.

Code: Select all

 
//! Generates adjacency information based on mesh indices.
void CShadowVolumeSceneNode::calculateAdjacency()
{
    Adjacency.set_used(IndexCount);
 
    // go through all faces and fetch their three neighbours
    for (u32 f=0; f<IndexCount; f+=3)
    {
        for (u32 edge = 0; edge<3; ++edge)
        {
            const core::vector3df& v1 = Vertices[Indices[f+edge]];
            const core::vector3df& v2 = Vertices[Indices[f+((edge+1)%3)]];
 
            // now we search an_O_ther _F_ace with these two
            // vertices, which is not the current face.
            u32 of;
 
            for (of=0; of<IndexCount; of+=3)
            {
                // only other faces
                if (of != f)
                {
                    bool cnt1 = false;
                    bool cnt2 = false;
 
                    for (s32 e=0; e<3; ++e)
                    {
                        if (v1.equals(Vertices[Indices[of+e]]))
                            cnt1=true;
 
                        if (v2.equals(Vertices[Indices[of+e]]))
                            cnt2=true;
                    }
                    // one match for each vertex, i.e. edge is the same
                    if (cnt1 && cnt2)
                        break;
                }
            }
 
            // no adjacent edges -> store face number, else store adjacent face
            if (of >= IndexCount)
                Adjacency[f + edge] = f/3;
            else
                Adjacency[f + edge] = of/3;
        }
    }
}
 

[robmar]

Just retested with Irrlicht 1.7.3 and the issue seems to be that calculateAdjacency() is getting called at all by the 1.8 release!

Under 1.7.3 the test isn´t passing, so calculateAdjacency doesn´t get called. If it was called, the system would slow down as is happening under 1.8

void CShadowVolumeSceneNode::updateShadowVolumes()
{
...
// recalculate adjacency if necessary
if (oldVertexCount != VertexCount && oldIndexCount != IndexCount && UseZFailMethod)
calculateAdjacency();

[robmar]

Okay so if the mesh is reasonably còmplex, say contains 12 text characters, and UseZFailMethod is set, its incredibly slow!!!

i had thought shadows might be handled in GPU hardware... is there anyway this can be speeded up?

[robmar]

Checking the differences in shadow handling between irrlicht 1.7.3 and 1.8, as shown below, version 1.8 has the ZFail control removed, which hits performance when reasonably complex meshes are used.

I´ve modified Irrlicht 1.8 as below to avoid the problem:

void CShadowVolumeSceneNode::updateShadowVolumes()
{
...
// recalculate adjacency if necessary
//if (oldVertexCount != VertexCount || oldIndexCount != IndexCount) // 1.8 version
//if (oldVertexCount != VertexCount && oldIndexCount != IndexCount && UseZFailMethod) // 1.7.3 version
if ((oldVertexCount != VertexCount || oldIndexCount != IndexCount) && UseZFailMethod) // Suggested version
calculateAdjacency();

[hybrid]

No, adjacency information is used in both versions, and the old comparison with && was simply wrong.

[robmar]

Well, I´ve extensively tested shadows with complex meshes in 1.7.3 and 1.8, and the 1.7.3 version doesn´t end up in that adjacency routine with 1 minute + delay yet the shadow works just as well.

Any reasonably complex mesh with shadows in 1.8 now slows startup by minutes while all the faces are checked.

Any ideas what can be done?

[hendu]

Yes, invent a better algorithm than the existing O(n^2) and post a patch

[CuteAlien]

The simpler solution is having simpler shadow-model. So the real model is ignored while the shadows are calculated from a simplified model at the same position (the model itself is invisible).

[robmar]

yes okay hendu... shadow handling in shaders is the answer I would imagine, unload the cpu.

Tried testing 1.8 with adjacency disabled but there was an exception when the code accessed an index array that hadn´t been initialized... must have missed something somewhere!

[Kuzy]

Idea to fasten it up:
pre-sorting of all vertices by their hash code with bubble sort (or something faster)
and checking afterwards only the "neighbors" in the list...

[robmar]

There is also a problem with shadows going through "hills" on the terrain meshes. How can that be adjusted?

Is it possible to revert to 1.7.3 shadows, as that version does not call calculateAdjacency() and works well, apart from not having occlusion on the hills.

I turned off adjacency defines but am getting a crash as the index arrays aren´t initialised but are still referenced in at least one place.

[CuteAlien]

Still would be great to have a test-case... maybe we can improve things.