next »

[Mikademus]

So I have this 3D game. In it my ships fly around and each have a circular icon that are part of the GUI. I translate the 3D position into 2D screen coordinates though the usual projection and view matrix voodoo, this is all no problem.

What the problem is, though, is likely something really much simpler, and I feel stupid Since the icons are always kept inside the screen sticking to the edges when the models move off-frustum, they can sometimes bunch up. At these times I want them to adjust to each other and settle in.

Anyone that have an idea how to accomplish this?

I am trying to do so atm by iterating over the icons and reacting to overlap, but this results in vibrating icons...

Code:

        float x, y;

        GetScreenCoordinates( pos, x, y );

        // ...code to clamp x and y to inside the screen rectangle snipped...

        float penetr = 0.f;
        Vector2 dir = Vector2::ZERO;

        // typedef     utils::shared_ptr<IconRep>      ICON_PTR;
        // typedef     std::vector<ICON_PTR>           ICONREP_VEC;

        for (ICONREP_VEC::iterator i = rOtherIcons.begin(); i != rOtherIcons.end(); ++i)
            if (i->get() != this) // get() the raw pointer from the smart pointer
            {
                Vector2 vec = (pIcon->getPosition() - (**i).pIcon->getPosition());
                float len = vec.length();

                if (len < ICON_SIZE && len > 0)               
                    penetr = std::max<float>(penetr, ICON_SIZE-len), 
                    dir += vec;
            }

        dir.normalise();
        dir *= penetr;

        x += dir.x;
        y += dir.y;

        pIcon->setPosition( x, y );

So anyone have a good solution to what I suspect should really be an easy problem?

[Lynx]

Here's what I'd suggest:

1. Store both the 'original location' and the 'actual display location'.
2. On your first pass, detect icons that are bunched up and line them up along the edge of the screen.  Mark these icons (temporarily) as 'moved'.
3. On your second pass, detect icons that are now obscured by the newly positioned icons, and move them up as well.  Again, mark them as moved.

Repeat passes until no icons are obscured, or all icons have been moved.

[BorisTheBrave]

Not bad, but you are getting vibrations because you are not persisting anything from frame to frame. It's doing the calculations from scratch each frame, and sometimes getting different results.

So my approach would be something like:
Give each icon a position independent from where they should be.
Each frame, move that position a bit towards where it should be, and then push stuff out which intersects much like your original function does. Make sure you push away both penetrating icons.
Note this incorporates Lynx's suggestion of multiple iterations, as you can consider it the same calculation running over several frames.

Or, if you wanted something EVEN SMOOTHER looking, go second order:
Give each icon a position and velocity independent from where they should be.
Each frame, accelerate it a bit towards it's target, and accelerate it a bit away from other icons. Apply damping.

In either case, you will need to carefully tune such that
a) Icons never drift too far from their intended position.
b) Icons can be dragged through each other if there is enough pull to do so (i.e. so icons cannot end up trapped far away from the intended position by being blocked off.

Even if you don't go for this approach, I think you need to think carefully about pathological cases for where icons can and should be.

[Mikademus]

Though still not perfect (there are more problems to solve) I got rid of the vibrations be dividing the updating into two steps as was suggested. I'd agree with that the vibrations were due to multiple re-updates.

So I first simply project the 3D to screen coordinates:

Code:

    void IconRep::update()
    {
        // Note that we have to invert the Z-axis of the source Ship's 
        // look vector since it uses left-handed coordinates while 
        // OGRE uses right-handed.
        //
        Ogre::Vector3 pos = *reinterpret_cast<ogre::Vector3 const *>( &rShip.world.pos() );

        float x, y;

        ogre::GetScreenCoordinates( pos, x, y );

        x = -HALF_SIZE + ogre::pWindow->getWidth()/2 - x;
        y = -(ICON_SIZE+HALF_SIZE) + ogre::pWindow->getHeight()/2 - y;

        x = std::min<float>( x, ogre::pWindow->getWidth()-ICON_SIZE );     x = std::max<float>( 0, x );   
        y = std::min<float>( y, ogre::pWindow->getHeight()-ICON_SIZE );    y = std::max<float>( 0, y );   


        pIcon->setPosition( CEGUI::UVector2(CEGUI::UDim(0, x), CEGUI::UDim(0, y)) );
    }

I then moved the unbunching into its own method. DO NOT COPY THIS, it is WIP and experimental, and very buggy!!!

Code:

    void IconRep::alignIcons()
    {
        using namespace Ogre;

        float   x = pIcon->getXPosition().d_offset, 
                y = pIcon->getYPosition().d_offset;

        float penetr = 0.f;
        Vector2 dir = Vector2::ZERO;
        unsigned start = 0;

        for (ICONREP_VEC::iterator i = rOtherIcons.begin(); i != rOtherIcons.end(); ++i, ++start)
            if (i->get() == this)
                break;

        struct Shift
        {
            CEGUI::Window  *pIcon;
            float           p;
            Vector2         dir;
        };

        std::vector<Shift> adjustments;

        for (ICONREP_VEC::iterator i = rOtherIcons.begin() + start+1; i < rOtherIcons.end(); ++i)
            {
                CEGUI::UVector2 gv;
                Vector2 ov = Vector2::ZERO;

                CEGUI::UVector2 p1 = pIcon->getPosition(),
                                p2 = (**i).pIcon->getPosition();

                if (p1.d_x == p2.d_x) p1.d_x.d_offset += 5;
                if (p1.d_y == p2.d_y) p1.d_y.d_offset += 5;

                gv = (p1 - p2);
                ov.x = gv.d_x.d_offset, ov.y = gv.d_y.d_offset;

                float len = ov.length();

                if (len < ICON_SIZE && len > 0)               
                {
                    penetr = std::max<float>(penetr, ICON_SIZE-len), 
                        dir += ov;

                    Shift s;
                    s.pIcon = (**i).pIcon;
                    s.dir = ov.normalisedCopy();
                    s.p = len;

                    adjustments.push_back( s );
                }

            }

        dir.normalise();
        dir *= penetr;

        x += dir.x;
        y += dir.y;

        pIcon->setPosition( CEGUI::UVector2(CEGUI::UDim(0, x), CEGUI::UDim(0, y)) );


        for (std::vector<Shift>::iterator i = adjustments.begin(); i != adjustments.end(); ++i)
        {
            Vector2 nv( i->pIcon->getXPosition().d_offset, y = i->pIcon->getYPosition().d_offset );
            nv -= i->dir * i->p;
            i->pIcon->setPosition( CEGUI::UVector2(CEGUI::UDim(0, nv.x), CEGUI::UDim(0, nv.y)) );
        }
    }

Finally, everything is updated outside of these methods:

Code:

    void Session::updateRepresentations()
    {
        for (SHIPREP_VEC::iterator i = ship_reps.begin(); i != ship_reps.end(); ++i)
            (*i)->update();

        for (ICONREP_VEC::iterator i = icons_reps.begin(); i != icons_reps.end(); ++i)
            if ((*i)->active)
                (*i)->update();

        for (ICONREP_VEC::iterator i = icons_reps.begin(); i != icons_reps.end(); ++i)
            if ((*i)->active)
                (*i)->alignIcons();
    }

This is much more efficient and solves the vibrations. Still, icons can shove each other out of the screen, and the mutual shoving I'm implementing (it looks much better than one icon being completely solid and the other doing all the dodging) is extremely rudimentary and the icons do not align nicely alongside sides and in corners when all in a bunch. Anyway, it is a good start, I hope...

[Lynx]

IMO what you do is:

1. Record icons which overlap each other
2. Designate the highest one as the anchor and align it to the side of the screen
3. Align other icons under it, each one's top being at the previous one's bottom

For second iteration you just line the new icons up under bottommost one of those that were previously aligned.  If it goes off the screen, move it over to the right instead.

[Mikademus]

I have gotten some good feedback in this thread so I will do more tests based on your suggestions and get back to you. Thanks for your replies