Week 7 - OnCanvas Alignment Guides

Fixing Minor Bugs

Most of this week, I spent my time fixing minor bugs and improving code quality of Distribution Snapping. One of the most noticeable bugs that somehow crept in was during bidirectional distribution snapping. If you were moving an selection of multiple objects and trying to “equidistant snap” in both X and Y directions, the snapping would happen relative to the overall bounding box of the selection and not the object that was actually being moved. Fortunately this was an easy-fix!

Distribution and Alignment snapping will now be turned ON by default when you open inkscape. Also, instead of having a separate “Intelligent Snapping” heading in the preferences, the setting to disable snap distances are now included in an overall heading called “Snap”

Also replaced raw pointers with smart-pointers wherever possible, this makes code cleaner and less error-prone. It’s also a nice modern C++ paradigm to adopt into the codebase.

But one of the major but not very visible bugs that needed fixing was caused due to the poor implementation of _addBBoxforIntersectionBBoxes. I should have known this earlier, but given the idiot I am, I forgot how std::vector::iterators behave.

Iterator Invalidation

In case we have overlapping objects, it is useful that apart from probing them individually, we also consider them to be a single object. This can be achieved with a simple hack.

This involves, looking at each of the 4 lists, and add to them, the overall bounding boxes of objects that overlap. It is important that these new bounding boxes are inserted in such a way that the overall list remains sorted. The function _addBBoxforIntersectingBBoxes takes care of this.

The problem arises, when you insert an element into a std::vector. vectors are supposed to be contiguous storage, it’s what makes them so fast. When you insert and element in between somewhere in a vector, you invalidate all of the iterators that come after that position. Not only that, incase in the process of insertion, your vector needs to resize itself, it will invalidate all of the iterators before and after that position. So, in essence any iterator that you had stored earlier will be useless. This causes unaligned memory tcache chunk errors. These are unpredictable and can happen at anytime, especially when you have to insert a lot of elements.

So, now that you know what the problem was, it is apparant that things crashed randomly. Interestingly though, if I was testing with relatively small number of elements, there were no errors, but if I hade about a 1000 elements in the view port, it seemed like hell broke loose!

Fix

The easiest fix would be to not use std::vector but to use a std::list instead. Lists are not contiguous and it’s iterators do not invalidate so easily. But because Lists are not contiguous, they are also slower than std::vectors. So to fix the issue and still be able to use vectors, I needed to make some changes to the algorithm.

• first calculate the insertion positions of the new bounding boxes and store this data somewhere; I used std::pair
• resize the vector to appropriate memory size.
• add new elements to the vector and use relative positions instead of absolute pointers.

here is the code for the function that is currently in the build.

void Inkscape::DistributionSnapper::_addBBoxForIntersectingBoxes(std::vector<Geom::Rect> *vec, Direction dir) const {
    if (vec->size() < 1) {
        return;
    }

    int count = 0;
    std::vector<std::pair<int, Geom::Rect>> insertPositions;

    for (auto it = vec->begin(); it != vec->end(); it++, count++) {
        Geom::Rect comb(*it);
        int num = 0;
        int insertPos = count;

        while (std::next(it) != vec->end() && it->intersects(*std::next(it))) {
            comb.unionWith(*std::next(it));

            if (dir == Direction::RIGHT && comb.midpoint().x() > it->midpoint().x()) {
                ++insertPos;
            } else if (dir == Direction::LEFT && comb.midpoint().x() < it->midpoint().x()){
                ++insertPos;
            } else if (dir == Direction::UP && comb.midpoint().y() > it->midpoint().y()){
                ++insertPos;
            } else if (dir == Direction::DOWN && comb.midpoint().y() < it->midpoint().y()){
                ++insertPos;
            }

            ++it;
            ++num;
            ++count;
        }

        if (num > 0) {
            insertPositions.emplace_back(insertPos, comb);
        }
    }
    
    if (insertPositions.size() != 0) {
        // TODO: Does this improve performance?
        vec->reserve(vec->size() + insertPositions.size());

        count = 0;
        for (auto pair : insertPositions) {
            vec->insert(vec->begin() + pair.first + count, pair.second);
            ++count;
        }
    }
}