Welding vertices

Monday April 27, 2009

To summarise the problem – welding vertices means you want to find all pairs of vertices with N distance of each other, and join them into one. There’s many uses for this kind of stuff.

The trouble is you often see it implemented using a O(n^2) algorithm, like such –

void WeldVerticesSlow(vertex *verts, int vertCount)
{
    for (int a=0;a<vertCount;a++)
    {
        for (int b=0;b<vertCount;b++)
        {
            if (Distance(verts[a], verts[b]) < THRESHOLD)
                Join(a, b);
        }      
    }
}

Now I’m not claiming that this is the faster algorithm, but it’s kind of somewhere around O(nlogn) I think.

void WeldVerticesFast(vertex *verts, int vertCount)
{
    SortAlongXAxis(verts, vertCount);
   
    for (int a=0;a<vertCount;a++)
    {
        int b = a;
        while(b--)
        {
            if (verts[b].x < verts[a].x - THRESHOLD)
                break;

            if (Distance(verts[a], verts[b]) < THRESHOLD)
                Join(a, b);
        }      
    }
}

It tends to do massively better than the naive algorithm in the real world, as the slow way can thrash the cache like mad – if your full vertex set doesn’t fit in the L2 cache, you’ll basically get a cache miss on every iteration.

So stop using n^2 !

— Kayamon
---

Monday April 27, 2009

  1. Alternatively, you can try hash-based approach, as shown here: http://codesuppository.blogspot.com/2006/04/welding.html

    — MaciejS
    ---

    · Apr 27, 22:48 · #

  2. Well the hash based approach is fine, except it doesn’t use a tolerance.

    It’s very rare for floating-point values to exactly match up – usually you need to specify a distance to search around.

    — Kayamon
    ---

    · Apr 27, 22:55 · #

  3. Now we’ll probably get tons of better solutions, so I’ll add my input too: first store the vertices in a grid, then go through the grid.

    — Roel
    ---

    · Apr 28, 03:57 · #

  4. I’ve ended up using std::multiset<> and for the tolerance I was just summing X+Y+Z and then was looking for lower_bound … upper_bound.

    const float xyz_sum = model.verts[index].offset[0] + model.verts[index].offset[1] + model.verts[index].offset[2];
    std::multiset<ValueIndex>::const_iterator lowerBound = surf->vertsIndex->lower_bound( ValueIndex( xyz_sum – 0.5f ) );
    const std::multiset<ValueIndex>::const_iterator upperBound = surf->vertsIndex->upper_bound( ValueIndex( xyz_sum + 0.5f ) );

    Works pretty good, and also works in cases where you don’t have the vertices in advance (e.g. the way the pipeline is structured, is that every vertex when it’s being added it’s welded).

    It speeded up 10 times certain ops, but multiset<> is still not the most optimal there is (but haven’t bother with something else for now).

    Tip – check -fastvert in your favourite converter tool :)

    — Dimiter "malkia" Stanev
    ---

    · Apr 29, 10:44 · #

  5. Richard, you CAN do welding upto a tolerance in O(n) using hashing, which is as fast as it gets. For details, see this old usenet post of mine:

    http://groups.google.com/group/comp.games.development.programming.algorithms/msg/d6d2a2b98209e013

    I think it should be pretty clear. If not, I describe the approach in more detail (with code) in my book (section 12.1).

    — Christer Ericson
    ---

    · May 1, 22:21 · #

  6. Oh I see, that’s kinda cool. I haven’t bought your book yet, it’s on my Amazon wish list but no-one will buy it for me :-(

    But yes, a naive hashing will ignore the tolerance, so you need to hash 4 times and check up to 4 lists I guess. (8 in 3D?)

    I still think mine wins for being like 4 extra lines of code. :-)

    To be quite honest, I’m happy to just see anything that isn’t O(n^2).

    — Kayamon
    ---

    · May 1, 23:35 · #