Calculating/storing transformations while traversing a graph with a depedency on parent node

Question

I've been pondering this for a week now. Hit the limit of CoPilot's use within 10 minutes (first time trying, never again). Been experimenting/drawing since. But thought it wise to see whether the community is familiar with this problem first.

I have previously written a recursive function that traverses a scenegraph (DFS), and stores the transformations matrix of every node in that scenegraph relative to the original caller's node. I actually have 2 functions (1 as a targeted search, and 1 as collect-all-of-them search). Sharing both here now.

bool AActor::GetRelativeTransformationMatrixFromGraphOld(const AActor* a_pTarget, glm::mat4& a_matrix, const AActor* a_pPrevious) const
{
    if (this == a_pTarget)
        return true;

    for (auto pChild : Graph.Children)
    {
        if (nullptr == pChild)
            continue;

        if (a_pPrevious == pChild)
            continue;

        if (pChild != a_pTarget && !pChild->HasChildIndirectly(a_pTarget))
            continue;

        glm::mat4 ctm(1);
        pChild->GetTransformationMatrix(ctm);
        a_matrix = a_matrix * ctm;
        return pChild->GetRelativeTransformationMatrixFromGraphOld(a_pTarget, a_matrix, this);
    }

    if (nullptr == Graph.Parent.GetPtr())
        return false;

    if (a_pPrevious == Graph.Parent.GetPtr())
        return false;

    glm::mat4 mtm(1);
    GetTransformationMatrix(mtm);
    a_matrix = a_matrix * glm::inverse(mtm);
    return Graph.Parent->GetRelativeTransformationMatrixFromGraphOld(a_pTarget, a_matrix, this);
}

void AActor::GetRelativeTransformationMatricesFromGraphOld(ActorTransformationMatrixMap& a_matrices, const glm::mat4& a_matrixCurrent, const AActor* a_pPrevious)
{
    a_matrices[this] = a_matrixCurrent;

    for (auto pChild : Graph.Children)
    {
        if (nullptr == pChild)
            continue;

        if (a_pPrevious == pChild)
            continue;

        glm::mat4 ctm(1);
        pChild->GetTransformationMatrix(ctm);
        pChild->GetRelativeTransformationMatricesFromGraphOld(a_matrices, a_matrixCurrent * ctm, this);
    }

    if (nullptr == Graph.Parent.GetPtr())
        return;

    if (a_pPrevious == Graph.Parent.GetPtr())
        return;

    glm::mat4 mtm(1);
    GetTransformationMatrix(mtm);
    Graph.Parent->GetRelativeTransformationMatricesFromGraphOld(a_matrices, a_matrixCurrent * glm::inverse(mtm), this);
}

Now there is a new element to the search I'd like to introduce. I want for every node to be able to ignore the parent's rotation if they wish to. Imagine modeling a solar system. If you have a node "Moon", and a building is on top of that moon, that building WILL rotate with the Moon. But if you have a satellite orbiting that moon, that satellite WON'T rotate with the moon.

I have come up with an implementation, but upon rendering it turns out to be wrong. I'm sharing the result here. I think the issue I have is that to traverse UP the scenegraph, I don't know the relationship between the node I am traversing into, and it's parent node.

Here is my test code that visualizes it. It shows construction of nodes.

    core::REngine engine;
    auto pRoot = engine.GetRoot();

    auto pResidenceGrandParent = new core::actors::AResidence(pRoot);
    pResidenceParent = new core::actors::AResidence(pResidenceGrandParent);
    auto pResidenceChild1 = new core::actors::AResidence(pResidenceParent);
    auto pResidenceChild2 = new core::actors::AResidence(pResidenceParent);
    auto pResidenceChild3 = new core::actors::AResidence(pResidenceParent);

    auto pResidenceGrandChild3A = new core::actors::AResidence(pResidenceChild3);
    auto pResidenceGrandChild3B = new core::actors::AResidence(pResidenceChild3);
    auto pResidenceGrandChild3C = new core::actors::AResidence(pResidenceChild3);

    pResidenceParent->Dynamic.Position.SetValue({ 0.0f, -24.0f, 0.0f });
    pResidenceChild1->Dynamic.Position.SetValue({ -32.0f, -24.0f, 0.0f });
    pResidenceChild2->Dynamic.Position.SetValue({ 0.0f, -24.0f, 0.0f });
    pResidenceChild3->Dynamic.Position.SetValue({ +32.0f, -24.0f, 0.0f });
    pResidenceGrandChild3A->Dynamic.Position.SetValue({ -24.0f, -16.0f, 0.0f });
    pResidenceGrandChild3B->Dynamic.Position.SetValue({ 0.0f, -16.0f, 0.0f });
    pResidenceGrandChild3C->Dynamic.Position.SetValue({ +24.0f, -16.0f, 0.0f });

    pResidenceChild2->Dynamic.RotateWithParent = false;
    pResidenceChild3->Dynamic.RotateWithParent = false;

    auto pCamera = new core::actors::ACamera(pResidenceGrandParent);
    pCamera->Camera.LookAtTarget = pResidenceGrandParent;

It is node "pResidenceParent" that gets rotated as a function of time (notice how it is not locally declared, because it is also called somewhere else to apply the rotation on).

Object pCamera starts as a child of GrandParent (and looks at GrandParent), but using the mouse, it is able to be assigned to other nodes and ReParent itself under them (and set them as its lookAt target).

My first few attempts at the rewrite of the code accumulated into this:

bool AActor::GetRelativeTransformationMatrixFromGraphNew(const AActor* a_pTarget, glm::mat4& a_matrix, const AActor* a_pPrevious) const
{
    auto previousIsParent = a_pPrevious != nullptr && Graph.Parent.GetPtr() != nullptr && a_pPrevious == Graph.Parent.GetPtr();
    if (this == a_pTarget)
    {
        if (previousIsParent)
        {
            glm::mat4 tm(1);
            GetTransformationMatrix(tm, false);
            a_matrix = a_matrix * tm;
        }
        return true;
    }

    for (auto pChild : Graph.Children)
    {
        if (pChild == nullptr || pChild == a_pPrevious)
            continue;

        if (pChild == a_pTarget || pChild->HasChildIndirectly(a_pTarget))
        {
            if (!previousIsParent) // I am the local root. Reversing direction, without changing a_matrix;
                return pChild->GetRelativeTransformationMatrixFromGraphNew(a_pTarget, a_matrix, this);

            glm::mat4 tm(1);
            GetTransformationMatrix(tm, !pChild->Dynamic.RotateWithParent.GetValue());
            a_matrix = a_matrix * tm;
            return pChild->GetRelativeTransformationMatrixFromGraphNew(a_pTarget, a_matrix, this);
        }
    }

    if (Graph.Parent.GetPtr() == nullptr || a_pPrevious == nullptr || Graph.Parent.GetPtr() == a_pPrevious)
        return false;

    auto previousIsChild = std::find(Graph.Children.begin(), Graph.Children.end(), a_pPrevious) != Graph.Children.end();
    glm::mat4 tm(1);
    GetTransformationMatrix(tm, previousIsChild ? !a_pPrevious->Dynamic.RotateWithParent.GetValue() : false);
    a_matrix = a_matrix * glm::inverse(tm);
    return Graph.Parent->GetRelativeTransformationMatrixFromGraphNew(a_pTarget, a_matrix, this);
}

void AActor::GetRelativeTransformationMatricesFromGraphNew(ActorTransformationMatrixMap& a_matrices, const glm::mat4& a_matrixCurrent, const AActor* a_pPrevious)
{
    auto previousIsParent = a_pPrevious != nullptr && Graph.Parent.GetPtr() != nullptr && a_pPrevious == Graph.Parent.GetPtr();
    if (previousIsParent)
    {
        glm::mat4 tm(1);
        GetTransformationMatrix(tm, false);
        a_matrices[this] = a_matrixCurrent * tm;
    }
    else
    {
        a_matrices[this] = a_matrixCurrent;
    }

    for (auto pChild : Graph.Children)
    {
        if (pChild == nullptr || pChild == a_pPrevious)
            continue;

        if (!previousIsParent) // I am the local root. Reversing direction, without changing a_matrix;
        {
            pChild->GetRelativeTransformationMatricesFromGraphNew(a_matrices, a_matrixCurrent, this);
        }
        else
        {
            glm::mat4 tm(1);
            GetTransformationMatrix(tm, !pChild->Dynamic.RotateWithParent.GetValue());
            pChild->GetRelativeTransformationMatricesFromGraphNew(a_matrices, a_matrixCurrent * tm, this);
        }
    }

    if (Graph.Parent.GetPtr() == nullptr || a_pPrevious == nullptr || Graph.Parent.GetPtr() == a_pPrevious)
        return;

    auto previousIsChild = std::find(Graph.Children.begin(), Graph.Children.end(), a_pPrevious) != Graph.Children.end();
    glm::mat4 tm(1);
    GetTransformationMatrix(tm, previousIsChild ? !a_pPrevious->Dynamic.RotateWithParent.GetValue() : false);
    Graph.Parent->GetRelativeTransformationMatricesFromGraphNew(a_matrices, a_matrixCurrent * glm::inverse(tm), this);
}

It passed all my unit tests for non-ignored rotations. But I haven't written ones for ignored rotations yet, and already noticed the problem upon visual inspection. And it has the wrong result like this:

GIF Link

I'm kinda aware of what's going on. The problem is that when traversing the graph, you don't always know whether to ignore a rotation or not depending on the direction you're traversing. I've been hacking at it heuristically for so long now to the point where I'm wondering whether this is not a general problem with a general solution. So it would be nice to have some graph expert eyeballs on it.

I'm aware how other libraries do it. Ogre3D caches the result at every node. But it is able to do so because they render in worldspace. I always render in localspace. For several reasons relating to the underlying model and its use cases, I do not wish to do anything in global space or cache local space results. I also do not wish to find the top node and work my way down every single frame. I really prefer the more pure DFS being able to start from any node in the graph, and stop once I reach a certain distance. As you may have already guessed, I am starting my search from pCamera every time, making every object in pCamera local space.

Sorry for the long post. Not sure if I split the question correctly either.

Calculating/storing transformations while traversing a graph with a depedency on parent node

Answers (1)

Related Questions