Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I'm coding a 2D collision engine, and I need to merge adjacent axis-aligned bounding boxes depending on a direction (left, right, top, bottom).

The four cases are very similar, except for the if condition, and the push_back argument. Is there any way I can refactor this code without compromising performance?

vector<AABB> getMergedAABBSLeft(vector<AABB> mSource)
{
    vector<AABB> result;

    while(!mSource.empty())
    {
        bool merged{false}; AABB a{mSource.back()}; mSource.pop_back();

        for(auto& b : mSource)
            if(a.getRight() == b.getRight())
            {
                result.push_back(getMergedAABBVertically(a, b));
                eraseRemove(mSource, b); merged = true; break;
            }

        if(!merged) result.push_back(a);
    }

    return result;
}

vector<AABB> getMergedAABBSRight(vector<AABB> mSource)
{
    vector<AABB> result;

    while(!mSource.empty())
    {
        bool merged{false}; AABB a{mSource.back()}; mSource.pop_back();

        for(auto& b : mSource)
            if(a.getLeft() == b.getLeft())
            {
                result.push_back(getMergedAABBVertically(a, b));
                eraseRemove(mSource, b); merged = true; break;
            }

        if(!merged) result.push_back(a);
    }

    return result;
}

vector<AABB> getMergedAABBSTop(vector<AABB> mSource)
{
    vector<AABB> result;

    while(!mSource.empty())
    {
        bool merged{false}; AABB a{mSource.back()}; mSource.pop_back();

        for(auto& b : mSource)
            if(a.getBottom() == b.getBottom())
            {
                result.push_back(getMergedAABBHorizontally(a, b));
                eraseRemove(mSource, b); merged = true; break;
            }

        if(!merged) result.push_back(a);
    }

    return result;
}

vector<AABB> getMergedAABBSBottom(vector<AABB> mSource)
{
    vector<AABB> result;

    while(!mSource.empty())
    {
        bool merged{false}; AABB a{mSource.back()}; mSource.pop_back();

        for(auto& b : mSource)
            if(a.getTop() == b.getTop())
            {
                result.push_back(getMergedAABBHorizontally(a, b));
                eraseRemove(mSource, b); merged = true; break;
            }

        if(!merged) result.push_back(a);
    }

    return result;
}
share|improve this question
add comment

4 Answers

I find this line hard to read:

bool merged{false}; AABB a{mSource.back()}; mSource.pop_back();

Please split variables up 1 per line.
Yes the new syntax allows {} for list initialization. But these are not lists so it seems confusing to me (this one is more personal bias so feel free to ignore).

bool   merged(false);
AABB   a(mSource.back());
mSource.pop_back();

Pass large parameters by const reference if you can.
It saves a copy and you don't seem to need the copy (since you are not modifying the value (Note the eraseRemove() call has no effect externally and does not effect the rest of the code)).

vector<AABB> getMergedAABBSLeft(vector<AABB> const&   mSource)
                                     //     ^^^^^^^^

Since your four functions are identical apart from one method call you could write a generic version and pass that method as a parameter:

vector<AABB> getMergedAABBSLeft(vector<AABB> mSource)
{    return getMergedAABBSGeneric(mSource, &AABB::getRight);
}
share|improve this answer
    
Why isn't eraseRemove doing anything? It takes a (std::vector&) as a parameter, so I'm sure it is removing AABBs from mSource. Are you sure I can safely delete it? –  Vittorio Romeo Feb 18 '13 at 9:47
    
Its doing something locally. But mSource is not exported from this function so has no effect on anything else. The fact that you remove an element does not affect this algorithm. –  Loki Astari Feb 18 '13 at 14:38
    
@Loki Astari: You discourage the use of the {} because you say it is used for C++11's list initialization. This recommendation isn't correct, it's called the new C++11 "Uniform initialization" ( en.wikipedia.org/wiki/C%2B%2B11#Uniform_initialization ). It is encouraged for any type of initialization now, as it avoids problems from type narrowing, or the notorious Most Vexing Parse ( en.wikipedia.org/wiki/Most_vexing_parse ). –  Piotr99 Feb 28 '13 at 19:00
    
@Piotr99: Thanks for the extra information. That was a personal one for me (I am still learning C++11) and nothing I would have rejected code from a code review on. It would be helpful if you had a reference for "encouraged for any type of initialization now". –  Loki Astari Mar 1 '13 at 19:08
    
The most authoritative source for C++ always is Bjarne Stroustrup ;) stroustrup.com/C++11FAQ.html#uniform-init . OK, in this case he points out which problems uniform initialization solves, but he doesn't provide a clear recommendation (I still believe his statement is an implicit recommendation). Herb Sutter (also involved in the C++ standardization committee) states regarding uniform initialization "Use {} unless you have a reason not to." See his talk (and slides) advocating the new C++11 here: channel9.msdn.com/Events/GoingNative/GoingNative-2012/… –  Piotr99 Mar 1 '13 at 19:27
show 2 more comments

Without knowing much about the AABB type, I'm assuming it has the operations getBottom(), and it's top-left-right couterparts.

What you could do is set up functions which returns the appropiate result and pass it as an argument to the general function. I only show the process for the top/left/right/bottom. The horizontally/vertically part goes the same way. Something like:

    typedef elem_type (*selector)(AABB*);
    elem_type getRightSelector(AABB* obj)
    {
        return obj->getRight(); // Return value is of elem_type
    }
    // Same for the others (left, top...)

vector<AABB> getMergedAABBS(vector<AABB> mSource, selector sel )
{
     (...)
        for(auto& b : mSource)
            if(sel(a) == sel(b))
            {
                // We'd need another pointer here
                result.push_back(getMergedAABBHorizontally(a, b));
                eraseRemove(mSource, b); merged = true; break;
            }

     (...)
    return result;
}

    // Any particular one:
    vector<AABB> getMergedAABBSRight(vector<AABB> mSource )
{
         return getMergedAABBS(mSource, getRightSelector);
}

Then you'd call the general function from each suffixed function (ie. getMergedAABBTop, etc.) passing the appropriate selector function.

Note this may be achieved in a cleaner way with C++11 features, what I'm not so certain about is the performance impact. Here you are adding one function call with respect to your code inside the loop, plus one function call from the specialized functions to the general one. Consider inlining, too.

share|improve this answer
add comment

This looks like a perfect opportunity for templates, maybe something like this:

template<typename C, typename T, T(C::*Selector)() const, C(*MergeFn)(C, C)> struct static_merger {

    std::vector<C> run(std::vector<C> mSource) {
        std::vector<C> result;
        while(!mSource.empty())
        {
            bool merged = false;
            AABB a = mSource.back();
            mSource.pop_back();

            for(auto & b : mSource) {
                if((a.*Selector)() == (b.*Selector)())
                {
                    result.push_back((*MergeFn)(a, b));
                    eraseRemove(mSource, b);
                    merged = true;
                    break;
                }
            }
            if(!merged) {
                result.push_back(a);
            }
        }
        return result;
    }
};

Usage is simple:

std::vector<AABB> orig / * = ... */;
static_merger<AABB, int, &AABB::getLeft, &mergeVertically> mergl;
static_merger<AABB, int, &AABB::getRight, &mergeVertically> mergr;
static_merger<AABB, int, &AABB::getTop, &mergeHorizontally> mergt;
static_merger<AABB, int, &AABB::getBottom, &mergeHorizontally> mergb;
std::vector<AABB> mergedl = mergl.run(orig);
std::vector<AABB> mergedr = mergr.run(orig);
std::vector<AABB> mergedt = mergt.run(orig);
std::vector<AABB> mergedb = mergb.run(orig);

Notice that with this approach, you need to create 4 different instances of our static_merger since the callbacks are being passed as template arguments.

If you want to be able to decide at runtime which callbacks to use, you can use this one:

template<typename C, typename T> struct dynamic_merger {

    std::vector<C> run(std::vector<C> const & mSource, T(C::*selector)() const, C(*merge_fn)(C, C)) {
        std::vector<C> result;
        while(!mSource.empty())
        {
            bool merged = false;
            AABB a = mSource.back();
            mSource.pop_back();

            for(auto & b : mSource) {
                if((a.*selector)() == (b.*selector)())
                {
                    result.push_back((*merge_fn)(a, b));
                    eraseRemove(mSource, b);
                    merged = true;
                    break;
                }
            }
            if(!merged) {
                result.push_back(a);
            }
        }
        return result;
    }
};

Usage is also simple:

std::vector<AABB> orig / * = ... */;
dynamic_merger<AABB, int> merg;
std::vector<AABB> mergedl = merg.run(orig, &AABB::getLeft, &mergeVertically);
std::vector<AABB> mergedr = merg.run(orig, &AABB::getRight, &mergeVertically);
std::vector<AABB> mergedt = merg.run(orig, &AABB::getTop, &mergeHorizontally);
std::vector<AABB> mergedb = merg.run(orig, &AABB::getBottom, &mergeHorizontally);

One last thing, as Loki Astari suggested you should pass your original data by (const) reference instead of by value, this avoids expensive copying, resulting in (possibly) faster execution times.

share|improve this answer
add comment
up vote 0 down vote accepted

I used trait classes, which gives me the exact same performance as before (the compiler inlines it).

I still don't understand why some answers wanted me to pass mSource as a const std::vector<AABB>, since I believe eraseRemove actually changes the vector. Can you explain?

Anyway, here's my solution. I got it from a reply to a reddit post I made in r/reviewmycode.

template<typename TMergeTraits> std::vector<AABB> getMergedAABBs(std::vector<AABB> mSource)
{
    std::vector<AABB> result;

    while(!mSource.empty())
    {
        bool merged{false}; AABB a{mSource.back()}; mSource.pop_back();

        for(auto& b : mSource)
        {
            if(TMergeTraits::side(a) == TMergeTraits::side(b))
            {
                result.push_back(TMergeTraits::merge(a, b));
                eraseRemove(mSource, b); merged = true; break;
            }
        }

        if(!merged) result.push_back(a);
    }

    return result;
}

struct Left
{
    static int side(const AABB& mAABB) { return mAABB.getRight(); }
    static AABB merge(const AABB& mA, const AABB& mB) { return getMergedAABBVertically(mA, mB); }
};

struct Right
{
    static int side(const AABB& mAABB) { return mAABB.getLeft(); }
    static AABB merge(const AABB& mA, const AABB& mB) { return getMergedAABBVertically(mA, mB); }
};

struct Top
{
    static int side(const AABB& mAABB) { return mAABB.getBottom(); }
    static AABB merge(const AABB& mA, const AABB& mB) { return getMergedAABBHorizontally(mA, mB); }
};

struct Bottom
{
    static int side(const AABB& mAABB) { return mAABB.getTop(); }
    static AABB merge(const AABB& mA, const AABB& mB) { return getMergedAABBHorizontally(mA, mB); }
};

You call it like this:

getMergedAABBs<Left>(vectorOfAABBs);

Seems elegant - any suggestion?

share|improve this answer
    
Doing it like that causes function overhead. Please have a look at the static_merger in my answer, which doesn't suffer from function overhead. –  Tom Knapen Feb 18 '13 at 10:28
    
Testing in -O3 didn't show any overhead. –  Vittorio Romeo Feb 18 '13 at 10:41
    
That may be because O3 is a rather high level of optimization. But without (or with low) optimizations my previous comment stands. –  Tom Knapen Feb 18 '13 at 19:06
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.