/*

Open Asset Import Library (assimp)

----------------------------------------------------------------------

Copyright (c) 2006-2025, assimp team

All rights reserved.

Redistribution and use of this software in source and binary forms,

with or without modification, are permitted provided that the

following conditions are met:

* Redistributions of source code must retain the above

  copyright notice, this list of conditions and the

  following disclaimer.

* Redistributions in binary form must reproduce the above

  copyright notice, this list of conditions and the

  following disclaimer in the documentation and/or other

  materials provided with the distribution.

* Neither the name of the assimp team, nor the names of its

  contributors may be used to endorse or promote products

  derived from this software without specific prior

  written permission of the assimp team.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

----------------------------------------------------------------------

*/

/** @file  LWOAnimation.cpp

 *  @brief LWOAnimationResolver utility class

 *

 *  It's a very generic implementation of LightWave's system of

 *  component-wise-animated stuff. The one and only fully free

 *  implementation of LightWave envelopes of which I know.

*/

#if (!defined ASSIMP_BUILD_NO_LWO_IMPORTER) && (!defined ASSIMP_BUILD_NO_LWS_IMPORTER)

#include <functional>

// internal headers

#include "LWOFileData.h"

#include <assimp/anim.h>

using namespace Assimp;

using namespace Assimp::LWO;

// ------------------------------------------------------------------------------------------------

// Construct an animation resolver from a given list of envelopes

AnimResolver::AnimResolver(std::list<Envelope> &_envelopes, double tick) :

        envelopes(_envelopes),

        sample_rate(0.),

        envl_x(),

        envl_y(),

        envl_z(),

        end_x(),

        end_y(),

        end_z(),

        flags(),

        sample_delta() {

    trans_x = trans_y = trans_z = nullptr;

    rotat_x = rotat_y = rotat_z = nullptr;

    scale_x = scale_y = scale_z = nullptr;

    first = last = 150392.;

    // find transformation envelopes

    for (std::list<LWO::Envelope>::iterator it = envelopes.begin(); it != envelopes.end(); ++it) {

        (*it).old_first = 0;

        (*it).old_last = (*it).keys.size() - 1;

        if ((*it).keys.empty()) {

            continue;

        }

        if ((int)(*it).type < 1 || (int)(*it).type>EnvelopeType_Unknown) {

            continue;

        }

        switch ((*it).type) {

        // translation

        case LWO::EnvelopeType_Position_X:

            trans_x = &*it;

            break;

        case LWO::EnvelopeType_Position_Y:

            trans_y = &*it;

            break;

        case LWO::EnvelopeType_Position_Z:

            trans_z = &*it;

            break;

            // rotation

        case LWO::EnvelopeType_Rotation_Heading:

            rotat_x = &*it;

            break;

        case LWO::EnvelopeType_Rotation_Pitch:

            rotat_y = &*it;

            break;

        case LWO::EnvelopeType_Rotation_Bank:

            rotat_z = &*it;

            break;

            // scaling

        case LWO::EnvelopeType_Scaling_X:

            scale_x = &*it;

            break;

        case LWO::EnvelopeType_Scaling_Y:

            scale_y = &*it;

            break;

        case LWO::EnvelopeType_Scaling_Z:

            scale_z = &*it;

            break;

        default:

            continue;

        };

        // convert from seconds to ticks

        for (std::vector<LWO::Key>::iterator d = (*it).keys.begin(); d != (*it).keys.end(); ++d)

            (*d).time *= tick;

        // set default animation range (minimum and maximum time value for which we have a keyframe)

        first = std::min(first, (*it).keys.front().time);

        last = std::max(last, (*it).keys.back().time);

    }

    // deferred setup of animation range to increase performance.

    // typically the application will want to specify its own.

    need_to_setup = true;

}

// ------------------------------------------------------------------------------------------------

// Reset all envelopes to their original contents

void AnimResolver::ClearAnimRangeSetup() {

    for (std::list<LWO::Envelope>::iterator it = envelopes.begin(); it != envelopes.end(); ++it) {

        (*it).keys.erase((*it).keys.begin(), (*it).keys.begin() + (*it).old_first);

        (*it).keys.erase((*it).keys.begin() + (*it).old_last + 1, (*it).keys.end());

    }

}

// ------------------------------------------------------------------------------------------------

// Insert additional keys to match LWO's pre& post behaviors.

void AnimResolver::UpdateAnimRangeSetup() {

    // XXX doesn't work yet (hangs if more than one envelope channels needs to be interpolated)

    for (std::list<LWO::Envelope>::iterator it = envelopes.begin(); it != envelopes.end(); ++it) {

        if ((*it).keys.empty()) continue;

        const double my_first = (*it).keys.front().time;

        const double my_last = (*it).keys.back().time;

        const double delta = my_last - my_first;

        if (delta == 0.0) {

            continue;

        }

        const size_t old_size = (*it).keys.size();

        const float value_delta = (*it).keys.back().value - (*it).keys.front().value;

        // NOTE: We won't handle reset, linear and constant here.

        // See DoInterpolation() for their implementation.

        // process pre behavior

        switch ((*it).pre) {

        case LWO::PrePostBehaviour_OffsetRepeat:

        case LWO::PrePostBehaviour_Repeat:

        case LWO::PrePostBehaviour_Oscillate: {

            const double start_time = delta - std::fmod(my_first - first, delta);

            std::vector<LWO::Key>::iterator n = std::find_if((*it).keys.begin(), (*it).keys.end(),

                                                    [start_time](double t) { return start_time > t; }), m;

            size_t ofs = 0;

            if (n != (*it).keys.end()) {

                // copy from here - don't use iterators, insert() would invalidate them

                ofs = (*it).keys.end() - n;

                (*it).keys.insert((*it).keys.begin(), ofs, LWO::Key());

                std::copy((*it).keys.end() - ofs, (*it).keys.end(), (*it).keys.begin());

            }

            // do full copies. again, no iterators

            const unsigned int num = (unsigned int)((my_first - first) / delta);

            (*it).keys.resize((*it).keys.size() + num * old_size);

            n = (*it).keys.begin() + ofs;

            bool reverse = false;

            for (unsigned int i = 0; i < num; ++i) {

                m = n + old_size * (i + 1);

                std::copy(n, n + old_size, m);

                const bool res = ((*it).pre == LWO::PrePostBehaviour_Oscillate);

                reverse = !reverse;

                if (res && reverse) {

                    std::reverse(m, m + old_size - 1);

                }

            }

            // update time values

            n = (*it).keys.end() - (old_size + 1);

            double cur_minus = delta;

            unsigned int tt = 1;

            for (const double tmp = delta * (num + 1); cur_minus <= tmp; cur_minus += delta, ++tt) {

                m = (delta == tmp ? (*it).keys.begin() : n - (old_size + 1));

                for (; m < n; --n) {

                    (*n).time -= cur_minus;

                    // offset repeat? add delta offset to key value

                    if ((*it).pre == LWO::PrePostBehaviour_OffsetRepeat) {

                        (*n).value += tt * value_delta;

                    }

                }

            }

            break;

        }

        default:

            // silence compiler warning

            break;

        }

        // process post behavior

        switch ((*it).post) {

        case LWO::PrePostBehaviour_OffsetRepeat:

        case LWO::PrePostBehaviour_Repeat:

        case LWO::PrePostBehaviour_Oscillate:

            break;

        default:

            // silence compiler warning

            break;

        }

    }

}

// ------------------------------------------------------------------------------------------------

// Extract bind pose matrix

void AnimResolver::ExtractBindPose(aiMatrix4x4 &out) {

    // If we have no envelopes, return identity

    if (envelopes.empty()) {

        out = aiMatrix4x4();

        return;

    }

    aiVector3D angles, scaling(1.f, 1.f, 1.f), translation;

    if (trans_x) translation.x = trans_x->keys[0].value;

    if (trans_y) translation.y = trans_y->keys[0].value;

    if (trans_z) translation.z = trans_z->keys[0].value;

    if (rotat_x) angles.x = rotat_x->keys[0].value;

    if (rotat_y) angles.y = rotat_y->keys[0].value;

    if (rotat_z) angles.z = rotat_z->keys[0].value;

    if (scale_x) scaling.x = scale_x->keys[0].value;

    if (scale_y) scaling.y = scale_y->keys[0].value;

    if (scale_z) scaling.z = scale_z->keys[0].value;

    // build the final matrix

    aiMatrix4x4 s, rx, ry, rz, t;

    aiMatrix4x4::RotationZ(angles.z, rz);

    aiMatrix4x4::RotationX(angles.y, rx);

    aiMatrix4x4::RotationY(angles.x, ry);

    aiMatrix4x4::Translation(translation, t);

    aiMatrix4x4::Scaling(scaling, s);

    out = t * ry * rx * rz * s;

}

// ------------------------------------------------------------------------------------------------

// Do a single interpolation on a channel

void AnimResolver::DoInterpolation(std::vector<LWO::Key>::const_iterator cur,

        LWO::Envelope *envl, double time, float &fill) {

    if (envl->keys.size() == 1) {

        fill = envl->keys[0].value;

        return;

    }

    // check whether we're at the beginning of the animation track

    if (cur == envl->keys.begin()) {

        // ok ... this depends on pre behaviour now

        // we don't need to handle repeat&offset repeat&oszillate here, see UpdateAnimRangeSetup()

        switch (envl->pre) {

        case LWO::PrePostBehaviour_Linear:

            DoInterpolation2(cur, cur + 1, time, fill);

            return;

        case LWO::PrePostBehaviour_Reset:

            fill = 0.f;

            return;

        default: //case LWO::PrePostBehaviour_Constant:

            fill = (*cur).value;

            return;

        }

    }

    // check whether we're at the end of the animation track

    else if (cur == envl->keys.end() - 1 && time > envl->keys.rbegin()->time) {

        // ok ... this depends on post behaviour now

        switch (envl->post) {

        case LWO::PrePostBehaviour_Linear:

            DoInterpolation2(cur, cur - 1, time, fill);

            return;

        case LWO::PrePostBehaviour_Reset:

            fill = 0.f;

            return;

        default: //case LWO::PrePostBehaviour_Constant:

            fill = (*cur).value;

            return;

        }

    }

    // Otherwise do a simple interpolation

    DoInterpolation2(cur - 1, cur, time, fill);

}

// ------------------------------------------------------------------------------------------------

// Almost the same, except we won't handle pre/post conditions here

void AnimResolver::DoInterpolation2(std::vector<LWO::Key>::const_iterator beg,

        std::vector<LWO::Key>::const_iterator end, double time, float &fill) {

    switch ((*end).inter) {

    case LWO::IT_STEP:

        // no interpolation at all - take the value of the last key

        fill = (*beg).value;

        return;

    default:

        // silence compiler warning

        break;

    }

    // linear interpolation - default

    double duration = (*end).time - (*beg).time;

    if (duration > 0.0) {

        fill = (*beg).value + ((*end).value - (*beg).value) * (float)(((time - (*beg).time) / duration));

    } else {

        fill = (*beg).value;

    }

}

// ------------------------------------------------------------------------------------------------

// Subsample animation track by given key values

void AnimResolver::SubsampleAnimTrack(std::vector<aiVectorKey> & /*out*/,

        double /*time*/, double /*sample_delta*/) {

    //ai_assert(out.empty() && sample_delta);

    //const double time_start = out.back().mTime;

    //  for ()

}

// ------------------------------------------------------------------------------------------------

// Track interpolation

void AnimResolver::InterpolateTrack(std::vector<aiVectorKey> &out, aiVectorKey &fill, double time) {

    // subsample animation track?

    if (flags & AI_LWO_ANIM_FLAG_SAMPLE_ANIMS) {

        SubsampleAnimTrack(out, time, sample_delta);

    }

    fill.mTime = time;

    // get x

    if ((*cur_x).time == time) {

        fill.mValue.x = (*cur_x).value;

        if (cur_x != envl_x->keys.end() - 1) /* increment x */

            ++cur_x;

        else

            end_x = true;

    } else

        DoInterpolation(cur_x, envl_x, time, (float &)fill.mValue.x);

    // get y

    if ((*cur_y).time == time) {

        fill.mValue.y = (*cur_y).value;

        if (cur_y != envl_y->keys.end() - 1) /* increment y */

            ++cur_y;

        else

            end_y = true;

    } else

        DoInterpolation(cur_y, envl_y, time, (float &)fill.mValue.y);

    // get z

    if ((*cur_z).time == time) {

        fill.mValue.z = (*cur_z).value;

        if (cur_z != envl_z->keys.end() - 1) /* increment z */

            ++cur_z;

        else

            end_x = true;

    } else

        DoInterpolation(cur_z, envl_z, time, (float &)fill.mValue.z);

}

// ------------------------------------------------------------------------------------------------

// Build linearly subsampled keys from three single envelopes, one for each component (x,y,z)

void AnimResolver::GetKeys(std::vector<aiVectorKey> &out,

        LWO::Envelope *_envl_x,

        LWO::Envelope *_envl_y,

        LWO::Envelope *_envl_z,

        unsigned int _flags) {

    envl_x = _envl_x;

    envl_y = _envl_y;

    envl_z = _envl_z;

    flags = _flags;

    // generate default channels if none are given

    LWO::Envelope def_x, def_y, def_z;

    LWO::Key key_dummy;

    key_dummy.time = 0.f;

    if ((envl_x && envl_x->type == LWO::EnvelopeType_Scaling_X) ||

            (envl_y && envl_y->type == LWO::EnvelopeType_Scaling_Y) ||

            (envl_z && envl_z->type == LWO::EnvelopeType_Scaling_Z)) {

        key_dummy.value = 1.f;

    } else

        key_dummy.value = 0.f;

    if (!envl_x) {

        envl_x = &def_x;

        envl_x->keys.push_back(key_dummy);

    }

    if (!envl_y) {

        envl_y = &def_y;

        envl_y->keys.push_back(key_dummy);

    }

    if (!envl_z) {

        envl_z = &def_z;

        envl_z->keys.push_back(key_dummy);

    }

    // guess how many keys we'll get

    size_t reserve;

    double sr = 1.;

    if (flags & AI_LWO_ANIM_FLAG_SAMPLE_ANIMS) {

        if (!sample_rate)

            sr = 100.f;

        else

            sr = sample_rate;

        sample_delta = 1.f / sr;

        reserve = (size_t)(

                std::max(envl_x->keys.rbegin()->time,

                        std::max(envl_y->keys.rbegin()->time, envl_z->keys.rbegin()->time)) *

                sr);

    } else

        reserve = std::max(envl_x->keys.size(), std::max(envl_x->keys.size(), envl_z->keys.size()));

    out.reserve(reserve + (reserve >> 1));

    // Iterate through all three arrays at once - it's tricky, but

    // rather interesting to implement.

    cur_x = envl_x->keys.begin();

    cur_y = envl_y->keys.begin();

    cur_z = envl_z->keys.begin();

    end_x = end_y = end_z = false;

    while (true) {

        aiVectorKey fill;

        if ((*cur_x).time == (*cur_y).time && (*cur_x).time == (*cur_z).time) {

            // we have a keyframe for all of them defined .. this means

            // we don't need to interpolate here.

            fill.mTime = (*cur_x).time;

            fill.mValue.x = (*cur_x).value;

            fill.mValue.y = (*cur_y).value;

            fill.mValue.z = (*cur_z).value;

            // subsample animation track

            if (flags & AI_LWO_ANIM_FLAG_SAMPLE_ANIMS) {

                //SubsampleAnimTrack(out,cur_x, cur_y, cur_z, d, sample_delta);

            }

        }

        // Find key with lowest time value

        else if ((*cur_x).time <= (*cur_y).time && !end_x) {

            if ((*cur_z).time <= (*cur_x).time && !end_z) {

                InterpolateTrack(out, fill, (*cur_z).time);

            } else {

                InterpolateTrack(out, fill, (*cur_x).time);

            }

        } else if ((*cur_z).time <= (*cur_y).time && !end_y) {

            InterpolateTrack(out, fill, (*cur_y).time);

        } else if (!end_y) {

            // welcome on the server, y

            InterpolateTrack(out, fill, (*cur_y).time);

        } else {

            // we have reached the end of at least 2 channels,

            // only one is remaining. Extrapolate the 2.

            if (end_y) {

                InterpolateTrack(out, fill, (end_x ? (*cur_z) : (*cur_x)).time);

            } else if (end_x) {

                InterpolateTrack(out, fill, (end_z ? (*cur_y) : (*cur_z)).time);

            } else { // if (end_z)

                InterpolateTrack(out, fill, (end_y ? (*cur_x) : (*cur_y)).time);

            }

        }

        double lasttime = fill.mTime;

        out.push_back(fill);

        if (lasttime >= (*cur_x).time) {

            if (cur_x != envl_x->keys.end() - 1)

                ++cur_x;

            else

                end_x = true;

        }

        if (lasttime >= (*cur_y).time) {

            if (cur_y != envl_y->keys.end() - 1)

                ++cur_y;

            else

                end_y = true;

        }

        if (lasttime >= (*cur_z).time) {

            if (cur_z != envl_z->keys.end() - 1)

                ++cur_z;

            else

                end_z = true;

        }

        if (end_x && end_y && end_z) /* finished? */

            break;

    }

    if (flags & AI_LWO_ANIM_FLAG_START_AT_ZERO) {

        for (std::vector<aiVectorKey>::iterator it = out.begin(); it != out.end(); ++it)

            (*it).mTime -= first;

    }

}

// ------------------------------------------------------------------------------------------------

// Extract animation channel

void AnimResolver::ExtractAnimChannel(aiNodeAnim **out, unsigned int /*= 0*/) {

    *out = nullptr;

    //FIXME: crashes if more than one component is animated at different timings, to be resolved.

    // If we have no envelopes, return nullptr

    if (envelopes.empty()) {

        return;

    }

    // We won't spawn an animation channel if we don't have at least one envelope with more than one keyframe defined.

    const bool trans = ((trans_x && trans_x->keys.size() > 1) || (trans_y && trans_y->keys.size() > 1) || (trans_z && trans_z->keys.size() > 1));

    const bool rotat = ((rotat_x && rotat_x->keys.size() > 1) || (rotat_y && rotat_y->keys.size() > 1) || (rotat_z && rotat_z->keys.size() > 1));

    const bool scale = ((scale_x && scale_x->keys.size() > 1) || (scale_y && scale_y->keys.size() > 1) || (scale_z && scale_z->keys.size() > 1));

    if (!trans && !rotat && !scale)

        return;

    // Allocate the output animation

    aiNodeAnim *anim = *out = new aiNodeAnim();

    // Setup default animation setup if necessary

    if (need_to_setup) {

        UpdateAnimRangeSetup();

        need_to_setup = false;

    }

    // copy translation keys

    if (trans) {

        std::vector<aiVectorKey> keys;

        GetKeys(keys, trans_x, trans_y, trans_z, flags);

        anim->mPositionKeys = new aiVectorKey[anim->mNumPositionKeys = static_cast<unsigned int>(keys.size())];

        std::copy(keys.begin(), keys.end(), anim->mPositionKeys);

    }

    // copy rotation keys

    if (rotat) {

        std::vector<aiVectorKey> keys;

        GetKeys(keys, rotat_x, rotat_y, rotat_z, flags);

        anim->mRotationKeys = new aiQuatKey[anim->mNumRotationKeys = static_cast<unsigned int>(keys.size())];

        // convert heading, pitch, bank to quaternion

        // mValue.x=Heading=Rot(Y), mValue.y=Pitch=Rot(X), mValue.z=Bank=Rot(Z)

        // Lightwave's rotation order is ZXY

        aiVector3D X(1.0, 0.0, 0.0);

        aiVector3D Y(0.0, 1.0, 0.0);

        aiVector3D Z(0.0, 0.0, 1.0);

        for (unsigned int i = 0; i < anim->mNumRotationKeys; ++i) {

            aiQuatKey &qk = anim->mRotationKeys[i];

            qk.mTime = keys[i].mTime;

            qk.mValue = aiQuaternion(Y, keys[i].mValue.x) * aiQuaternion(X, keys[i].mValue.y) * aiQuaternion(Z, keys[i].mValue.z);

        }

    }

    // copy scaling keys

    if (scale) {

        std::vector<aiVectorKey> keys;

        GetKeys(keys, scale_x, scale_y, scale_z, flags);

        anim->mScalingKeys = new aiVectorKey[anim->mNumScalingKeys = static_cast<unsigned int>(keys.size())];

        std::copy(keys.begin(), keys.end(), anim->mScalingKeys);

    }

}

#endif // no lwo or no lws