path: root/indra/llprimitive/llprimlinkinfo.h

/**
 * @file llprimlinkinfo.h
 * @author andrew@lindenlab.com
 * @brief A template for determining which prims in a set are linkable
 *
 * $LicenseInfo:firstyear=2007&license=viewerlgpl$
 * Second Life Viewer Source Code
 * Copyright (C) 2010, Linden Research, Inc.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation;
 * version 2.1 of the License only.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
 *
 * Linden Research, Inc., 945 Battery Street, San Francisco, CA  94111  USA
 * $/LicenseInfo$
 */


#ifndef LL_PRIM_LINK_INFO_H
#define LL_PRIM_LINK_INFO_H

// system includes
#include <iostream>
#include <map>
#include <list>
#include <vector>

// common includes
#include "stdtypes.h"
#include "v3math.h"
#include "llquaternion.h"
#include "llsphere.h"


const F32 MAX_OBJECT_SPAN = 54.f;       // max distance from outside edge of an object to the farthest edge
const F32 OBJECT_SPAN_BONUS = 2.f;      // infinitesimally small prims can always link up to this distance
const S32 MAX_PRIMS_PER_OBJECT = 256;


template < typename DATA_TYPE >
class LLPrimLinkInfo
{
public:
    LLPrimLinkInfo();
    LLPrimLinkInfo( DATA_TYPE data, const LLSphere& sphere );
    ~LLPrimLinkInfo();

    void set( DATA_TYPE data, const LLSphere& sphere );
    void append( DATA_TYPE data, const LLSphere& sphere );
    void getData( std::list< DATA_TYPE >& data_list ) const;
    F32 getDiameter() const;
    LLVector3 getCenter() const;

    // returns 'true' if this info can link with other_info
    bool canLink( const LLPrimLinkInfo< DATA_TYPE >& other_info );

    S32 getPrimCount() const { return mDataMap.size(); }

    void mergeLinkableSet( typename std::list< LLPrimLinkInfo < DATA_TYPE > >& unlinked );

    void transform(const LLVector3& position, const LLQuaternion& rotation);

private:
    // returns number of merges made
    S32 merge(LLPrimLinkInfo< DATA_TYPE >& other_info);

    // returns number of collapses made
    static S32 collapse(typename std::list< LLPrimLinkInfo < DATA_TYPE > >& unlinked );

    void computeBoundingSphere();

    // Internal utility to encapsulate the link rules
    F32 get_max_linkable_span(const LLSphere& first, const LLSphere& second);
    F32 get_span(const LLSphere& first, const LLSphere& second);

private:
    std::map< DATA_TYPE, LLSphere > mDataMap;
    LLSphere mBoundingSphere;
};



template < typename DATA_TYPE >
LLPrimLinkInfo< DATA_TYPE >::LLPrimLinkInfo()
:   mBoundingSphere( LLVector3(0.f, 0.f, 0.f), 0.f )
{
}

template < typename DATA_TYPE >
LLPrimLinkInfo< DATA_TYPE >::LLPrimLinkInfo( DATA_TYPE data, const LLSphere& sphere)
:   mBoundingSphere(sphere)
{
    mDataMap[data] = sphere;
}

template < typename DATA_TYPE >
LLPrimLinkInfo< DATA_TYPE >::~LLPrimLinkInfo()
{
    mDataMap.clear();
}

template < typename DATA_TYPE >
void LLPrimLinkInfo< DATA_TYPE>::set( DATA_TYPE data, const LLSphere& sphere )
{
    if (!mDataMap.empty())
    {
        mDataMap.clear();
    }
    mDataMap[data] = sphere;
    mBoundingSphere = sphere;
}

template < typename DATA_TYPE >
void LLPrimLinkInfo< DATA_TYPE>::append( DATA_TYPE data, const LLSphere& sphere )
{
    mDataMap[data] = sphere;
    if (!mBoundingSphere.contains(sphere))
    {
        computeBoundingSphere();
    }
}

template < typename DATA_TYPE >
void LLPrimLinkInfo< DATA_TYPE >::getData( std::list< DATA_TYPE >& data_list) const
{
    typename std::map< DATA_TYPE, LLSphere >::const_iterator map_itr;
    for (map_itr = mDataMap.begin(); map_itr != mDataMap.end(); ++map_itr)
    {
        data_list.push_back(map_itr->first);
    }
}

template < typename DATA_TYPE >
F32 LLPrimLinkInfo< DATA_TYPE >::getDiameter() const
{
    return 2.f * mBoundingSphere.getRadius();
}

template < typename DATA_TYPE >
LLVector3 LLPrimLinkInfo< DATA_TYPE >::getCenter() const
{
    return mBoundingSphere.getCenter();
}

template < typename DATA_TYPE >
F32 LLPrimLinkInfo< DATA_TYPE >::get_max_linkable_span(const LLSphere& first, const LLSphere& second)
{
    F32 max_span = 3.f * (first.getRadius() + second.getRadius()) + OBJECT_SPAN_BONUS;
    if (max_span > MAX_OBJECT_SPAN)
    {
        max_span = MAX_OBJECT_SPAN;
    }

    return max_span;
}

template < typename DATA_TYPE >
F32 LLPrimLinkInfo< DATA_TYPE >::get_span(const LLSphere& first, const LLSphere& second)
{
    F32 span = (first.getCenter() - second.getCenter()).length()
                + first.getRadius() + second.getRadius();
    return span;
}

// static
// returns 'true' if this info can link with any part of other_info
template < typename DATA_TYPE >
bool LLPrimLinkInfo< DATA_TYPE >::canLink(const LLPrimLinkInfo& other_info)
{
    F32 max_span = get_max_linkable_span(mBoundingSphere, other_info.mBoundingSphere);

    F32 span = get_span(mBoundingSphere, other_info.mBoundingSphere);

    if (span <= max_span)
    {
        // The entire other_info fits inside the max span.
        return TRUE;
    }
    else if (span > max_span + 2.f * other_info.mBoundingSphere.getRadius())
    {
        // there is no way any piece of other_info could link with this one
        return FALSE;
    }

    // there may be a piece of other_info that is linkable
    typename std::map< DATA_TYPE, LLSphere >::const_iterator map_itr;
    for (map_itr = other_info.mDataMap.begin(); map_itr != other_info.mDataMap.end(); ++map_itr)
    {
        const LLSphere& other_sphere = (*map_itr).second;
        max_span = get_max_linkable_span(mBoundingSphere, other_sphere);

        span = get_span(mBoundingSphere, other_sphere);

        if (span <= max_span)
        {
            // found one piece that is linkable
            return TRUE;
        }
    }
    return FALSE;
}

// merges elements of 'unlinked'
// returns number of links made (NOT final prim count, NOR linked prim count)
// and removes any linkable infos from 'unlinked'
template < typename DATA_TYPE >
void LLPrimLinkInfo< DATA_TYPE >::mergeLinkableSet(std::list< LLPrimLinkInfo< DATA_TYPE > > & unlinked)
{
    bool linked_something = true;
    while (linked_something)
    {
        linked_something = false;

        typename std::list< LLPrimLinkInfo< DATA_TYPE > >::iterator other_itr = unlinked.begin();
        while ( other_itr != unlinked.end()
               && getPrimCount() < MAX_PRIMS_PER_OBJECT )
        {
            S32 merge_count = merge(*other_itr);
            if (merge_count > 0)
            {
                linked_something = true;
            }
            if (0 == (*other_itr).getPrimCount())
            {
                unlinked.erase(other_itr++);
            }
            else
            {
                ++other_itr;
            }
        }
        if (!linked_something
            && unlinked.size() > 1)
        {
            S32 collapse_count = collapse(unlinked);
            if (collapse_count > 0)
            {
                linked_something = true;
            }
        }
    }
}

// transforms all of the spheres into a new reference frame
template < typename DATA_TYPE >
void LLPrimLinkInfo< DATA_TYPE >::transform(const LLVector3& position, const LLQuaternion& rotation)
{
    typename std::map< DATA_TYPE, LLSphere >::iterator map_itr;
    for (map_itr = mDataMap.begin(); map_itr != mDataMap.end(); ++map_itr)
    {
        (*map_itr).second.setCenter((*map_itr).second.getCenter() * rotation + position);
    }
    mBoundingSphere.setCenter(mBoundingSphere.getCenter() * rotation + position);
}

// private
// returns number of links made
template < typename DATA_TYPE >
S32 LLPrimLinkInfo< DATA_TYPE >::merge(LLPrimLinkInfo& other_info)
{
    S32 link_count = 0;

//  F32 other_radius = other_info.mBoundingSphere.getRadius();
//  other_info.computeBoundingSphere();
//  if ( other_radius != other_info.mBoundingSphere.getRadius() )
//  {
//      LL_INFOS() << "Other bounding sphere changed!!" << LL_ENDL;
//  }

//  F32 this_radius = mBoundingSphere.getRadius();
//  computeBoundingSphere();
//  if ( this_radius != mBoundingSphere.getRadius() )
//  {
//      LL_INFOS() << "This bounding sphere changed!!" << LL_ENDL;
//  }


    F32 max_span = get_max_linkable_span(mBoundingSphere, other_info.mBoundingSphere);

    //  F32 center_dist = (mBoundingSphere.getCenter() - other_info.mBoundingSphere.getCenter()).length();
    //  LL_INFOS() << "objects are " << center_dist << "m apart" << LL_ENDL;
    F32 span = get_span(mBoundingSphere, other_info.mBoundingSphere);

    F32 span_limit = max_span + (2.f * other_info.mBoundingSphere.getRadius());
    if (span > span_limit)
    {
        // there is no way any piece of other_info could link with this one
        // LL_INFOS() << "span too large:  " << span << " vs. " << span_limit << LL_ENDL;
        return 0;
    }

    bool completely_linkable = (span <= max_span) ? true : false;

    typename std::map< DATA_TYPE, LLSphere >::iterator map_itr = other_info.mDataMap.begin();
    while (map_itr != other_info.mDataMap.end()
            && getPrimCount() < MAX_PRIMS_PER_OBJECT )
    {
        DATA_TYPE other_data = (*map_itr).first;
        LLSphere& other_sphere = (*map_itr).second;

        if (!completely_linkable)
        {
            max_span = get_max_linkable_span(mBoundingSphere, other_sphere);

            F32 span = get_span(mBoundingSphere, other_sphere);

            if (span > max_span)
            {
                ++map_itr;
                continue;
            }
        }

        mDataMap[other_data] = other_sphere;
        ++link_count;

        if (!mBoundingSphere.contains(other_sphere) )
        {
            computeBoundingSphere();
        }

        // remove from the other info
        other_info.mDataMap.erase(map_itr++);
    }

    if (link_count > 0 && other_info.getPrimCount() > 0)
    {
        other_info.computeBoundingSphere();
    }
    return link_count;
}

// links any linkable elements of unlinked
template < typename DATA_TYPE >
S32 LLPrimLinkInfo< DATA_TYPE >::collapse(std::list< LLPrimLinkInfo< DATA_TYPE > > & unlinked)
{
    S32 link_count = 0;
    bool linked_something = true;
    while (linked_something)
    {
        linked_something = false;

        typename std::list< LLPrimLinkInfo< DATA_TYPE > >::iterator this_itr = unlinked.begin();
        typename std::list< LLPrimLinkInfo< DATA_TYPE > >::iterator other_itr = this_itr;
        ++other_itr;
        while ( other_itr != unlinked.end() )

        {
            S32 merge_count = (*this_itr).merge(*other_itr);
            if (merge_count > 0)
            {
                linked_something = true;
                link_count += merge_count;
            }
            if (0 == (*other_itr).getPrimCount())
            {
                unlinked.erase(other_itr++);
            }
            else
            {
                ++other_itr;
            }
        }
    }
    return link_count;
}


template < typename DATA_TYPE >
void LLPrimLinkInfo< DATA_TYPE >::computeBoundingSphere()
{
    std::vector< LLSphere > sphere_list;
    typename std::map< DATA_TYPE, LLSphere >::const_iterator map_itr;
    for (map_itr = mDataMap.begin(); map_itr != mDataMap.end(); ++map_itr)
    {
        sphere_list.push_back(map_itr->second);
    }
    mBoundingSphere = LLSphere::getBoundingSphere(sphere_list);
}


#endif