算法 & 数据结构——裁剪多边形

弹弹堂游戏截图.gif

'　　０９年，第一次接触到《弹弹堂》这款游戏，其独特的可破坏地形，让不少玩家都惊叹不已，你可以在此机制下，创造各种玩法，跟玩家摩擦出各种闹剧。当炮弹击中地形障碍，地形会被炸出个窟窿，这个窟窿并非贴图上不可见，而是真实的地形破坏，打穿之后，那一块障碍就彻底消失了。

'　　在很早前我就揣测过这个功能的实现原理，无奈，没想出个所以然。最近，脑细胞突然沸腾了一下，把我的思绪拉回到这个问题上。

简单分析

爆炸前.png 爆炸后.png

'　　上图标记的箭头则是地形区域，地形区域由一个多边形构成，而破坏地形就是修改这个多边形。因而，只要实现通过多边形Ａ去裁剪多边形Ｂ就可以了，多边形A是炮弹产生的爆炸范围，多边形B则是地形（虽然爆炸范围看起来是圆的，但其实完全可以用多边形模拟，从而降低算法复杂度以及算法开销）。

理解到这就可以写算法了。

//  clip_shape.h
#pragma once

#include "../base.h"
#include "../math/vec4.h"
#include "../math/polygon.h"

class ClipShape {
public:
    struct CrossPoint {
        Vec4 mPoint;        //  交点
        size_t mLinkA;      //  交点上游
        size_t mLinkB;      //  交点下游
        CrossPoint(
            const Vec4 & point = Vec4(), 
            const size_t linkA = 0, 
            const size_t linkB = 0) 
            : mPoint(point)
            , mLinkA(linkA)
            , mLinkB(linkB)
        { }
    };

    using Points = std::vector<Vec4>;

    using ClipLine = std::vector<Vec4>;

    using CrossResult = std::vector<CrossPoint>;

    using ClipResult = std::pair<ClipShape, ClipShape>;

public:
    ClipShape();

    ClipShape(ClipShape && other);

    ClipShape & operator=(ClipShape && other);

    ClipShape(const ClipShape & other) = default;

    ClipShape & operator=(const ClipShape & other) = default;
    
    void Clear();

    void Push(const Vec4 & point);

    void Init(const Points & points);

    const Points & GetPoints() const;

    bool IsBeContains(const ClipLine & clipLine) const;

    std::vector<ClipShape> Clip(ClipLine clipLine) const;

private:
    bool Max(const CrossPoint & cp1, const CrossPoint & cp2) const;

    CrossResult CheckCross(const Vec4 & a, const Vec4 & b) const;
    CrossResult CheckCross(const ClipLine & clipLine) const;
    bool CheckCross(const CrossResult & crossResult) const;

    ClipShape ClipA(const CrossResult & crossResult) const;
    ClipShape ClipB(const CrossResult & crossResult) const;

    void FlipCross(CrossResult & result) const;

    bool Roll(ClipLine & clipLine) const;

private:
    Points _points;
};

//  clip_shape.cpp
#include "clip_shape.h"
#include "../math/polygon.h"

ClipShape::ClipShape()
{ }

ClipShape::ClipShape(ClipShape && other)
{
    *this = std::move(other);
}

ClipShape & ClipShape::operator=(ClipShape && other)
{
    _points = std::move(other._points);
    return *this;
}

void ClipShape::Clear()
{
    _points.clear();
}

void ClipShape::Push(const Vec4 & point)
{
    _points.push_back(point);
}

void ClipShape::Init(const Points & points)
{
    std::copy(points.begin(), points.end(), std::back_inserter(_points));
}

const ClipShape::Points & ClipShape::GetPoints() const
{
    return _points;
}

bool ClipShape::IsBeContains(const ClipLine & clipLine) const
{
    auto fn = [&](const Vec4 & point)
    {
        return Polygon::IsContains(point, clipLine);
    };
    return std::all_of(_points.begin(), _points.end(), fn);
}

std::vector<ClipShape> ClipShape::Clip(ClipLine clipLine) const
{
    std::vector<ClipShape> result;
    if (Roll(clipLine))
    {
        auto crossResult = CheckCross(clipLine);
        if (!crossResult.empty())
        {
            FlipCross(crossResult);

            auto clipA = ClipA(crossResult);
            if (!clipA.IsBeContains(clipLine))
            {
                auto ret1 = clipA.Clip(clipLine);
                std::copy(
                    std::make_move_iterator(ret1.begin()),
                    std::make_move_iterator(ret1.end()),
                    std::back_inserter(result));
                if (ret1.empty()) { result.push_back(clipA); }
            }

            auto clipB = ClipB(crossResult);
            if (!clipB.IsBeContains(clipLine))
            {
                auto ret2 = clipB.Clip(clipLine);
                std::copy(
                    std::make_move_iterator(ret2.begin()),
                    std::make_move_iterator(ret2.end()),
                    std::back_inserter(result));
                if (ret2.empty()) { result.push_back(clipB); }
            }
        }
    }
    return std::move(result);
}

bool ClipShape::Max(const CrossPoint & cp1, const CrossPoint & cp2) const
{
    assert(cp1.mLinkA != cp1.mLinkB);
    assert(cp2.mLinkA != cp2.mLinkB);
    assert(cp1.mPoint != cp2.mPoint);
    assert(cp1.mLinkA == cp2.mLinkA && cp1.mLinkB == cp2.mLinkB ||
           cp1.mLinkA != cp2.mLinkA && cp1.mLinkB != cp2.mLinkB);
    return cp1.mLinkA != cp2.mLinkA && cp1.mLinkA < cp2.mLinkA ||
        cp1.mLinkA == cp2.mLinkA && 
        _points.at(cp1.mLinkA).Unlerp(_points.at(cp1.mLinkB), cp1.mPoint) <
        _points.at(cp2.mLinkA).Unlerp(_points.at(cp2.mLinkB), cp2.mPoint);
}

ClipShape::CrossResult ClipShape::CheckCross(const Vec4 & a, const Vec4 & b) const
{
    CrossResult result;
    auto crossA = 0.0;
    auto crossB = 0.0;
    auto size = _points.size();
    for (auto i = 0; i != size; ++i)
    {
        auto & p1 = _points.at(INDEX<0>(i, size));
        auto & p2 = _points.at(INDEX<1>(i, size));
        if (Polygon::IsCross(a, b, p1, p2, &crossA, &crossB))
        {
            result.emplace_back(
                p1.Lerp(p2, crossB), 
                INDEX<0>(i, size), 
                INDEX<1>(i, size));
        }
    }

    auto fn = [&](
        const CrossResult::value_type & cross1, 
        const CrossResult::value_type & cross2)
    {
        return (cross1.mPoint - a).LengthSqrt()
            < (cross2.mPoint - a).LengthSqrt();
    };
    std::sort(result.begin(), result.end(), fn);

    return std::move(result);
}

ClipShape::CrossResult ClipShape::CheckCross(const ClipLine & clipLine) const
{
    CrossResult result;
    auto size = clipLine.size();
    for (auto i = 0; i != size; ++i)
    {
        auto & a = clipLine.at(INDEX<0>(i, size));
        auto & b = clipLine.at(INDEX<1>(i, size));
        auto points = CheckCross(a, b);
        if (!points.empty())
        {
            for (auto & point : points)
            {
                result.push_back(point);
                if (result.size() > 1)
                { 
                    if (CheckCross(result)) { goto exit; }
                    result.erase(result.begin(), std::prev(result.end()));
                }
            }
            if (result.size() == 1 && result.back().mPoint != b)
            { result.emplace_back(b); }
        }
        else if (!result.empty())
        {
            if (result.back().mPoint != a)
            { result.emplace_back(a); }
            if (result.back().mPoint != b)
            { result.emplace_back(b); }
        }
    }
    result.clear();
exit:
    if (!result.empty() && 
        result.front().mPoint == result.back().mPoint)
    {   result.clear(); }
    return std::move(result);
}

bool ClipShape::CheckCross(const CrossResult & crossResult) const
{
    for (auto i = 0; i != crossResult.size() - 1; ++i)
    {
        auto & a = crossResult.at(i    );
        auto & b = crossResult.at(i + 1);
        if (!Polygon::IsContains(a.mPoint, b.mPoint, _points))
        { return false; }
    }
    return true;
}

ClipShape ClipShape::ClipA(const CrossResult & crossResult) const
{
    ClipShape result;
    auto & front = crossResult.front();
    auto & back = crossResult.back();

    //  points => clipLine
    if (front.mPoint != _points.front())
    {
        result.Push(_points.front());
    }
    for (auto i = 1;
        i != front.mLinkB && 
        i != _points.size(); ++i)
    {
        result.Push(_points.at(i));
    }

    //  append clipLine
    if (result.GetPoints().empty() ||
        result.GetPoints().back() != front.mPoint)
    {
        result.Push(front.mPoint);
    }
    for (auto i = 1; i != crossResult.size(); ++i)
    {
        result.Push(crossResult.at(i).mPoint);
    }

    //  clipLine => points
    if (back.mLinkB != 0)
    {
        auto i = _points.at(back.mLinkB) == result.GetPoints().back()
                    ? back.mLinkB + 1 
                    : back.mLinkB;
        for (; i != _points.size(); ++i)
        { result.Push(_points.at(i)); }
    }
    return std::move(result);
}

ClipShape ClipShape::ClipB(const CrossResult & crossResult) const
{
    ClipShape result;
    auto & front = crossResult.front();
    auto & back = crossResult.back();

    for (auto 
        i = front.mLinkB; 
        i != back.mLinkB && 
        i != _points.size(); ++i)
    {
        result.Push(_points.at(i));
    }

    for (auto it = crossResult.rbegin(); it != crossResult.rend(); ++it)
    {
        result.Push(it->mPoint);
    }

    return std::move(result);
}

void ClipShape::FlipCross(CrossResult & result) const
{
    if (!Max(result.front(), result.back()))
    {
        std::reverse(result.begin(), result.end());
    }
}

bool ClipShape::Roll(ClipLine & clipLine) const
{
    if (Polygon::IsContains(clipLine.front(), _points))
    {
        auto fn = [&](const Vec4 & point)
        {
            return !Polygon::IsContains(point, _points);
        };
        auto it = std::find_if(clipLine.begin(), clipLine.end(), fn);

        if (it == clipLine.end()) { return false; }

        std::rotate(clipLine.begin(), it, clipLine.end());
    }
    return true;
}

算法效果.gif

即使在今天，我依然觉得这个机制可以创造很多玩法，当年《百战天虫》可就是靠这一特色大红大紫，而《弹弹堂》正是借鉴了《百战天虫》。