将 2D L 系统转换为直线的最快方法是什么

Question

我正在构建 3D 图形引擎，我想绘制 2D L 系统。但是我注意到，一旦你增加迭代次数，这就会变得很慢。我正在寻找一种方法将我的 L 系统快速扩展为 vector<Line>，其中包含 2 个点的 class 行。这是我当前的代码：

// LParser::LSystem2D contains the L-system (replacement rules, angle increase, etc..)
// the turtle is a class I use to track the current angle and position as I generate lines
// Lines2D is a std::list of Lines (with lines a class containing 2 points and a color)
void expand(char c, const LParser::LSystem2D &ls2D, Turtle &T, Lines2D &L2D, const Color &line_color, int max_depth,
            int depth = 0) {
    const std::string str = ls2D.get_replacement(c);
    for (const auto &character: str) {
        if (character == '+' || character == '-') {
            T.angle += (-((character == '-') - 0.5) * 2) * ls2D.get_angle(); // adds or subtracts the angle
            continue;
        } else if (character == '(') {
            T.return_pos.push({T.pos, T.angle}); // if a bracket is opened the current position and angle is stored
            continue;
        } else if (character == ')') {
            T.pos = T.return_pos.top().first; // if a bracket is closed we return to the stored position and angle
            T.angle = T.return_pos.top().second;
            T.return_pos.pop();
            continue;
        } else if (max_depth > depth + 1) {
            expand(character, ls2D, T, L2D, line_color, max_depth, depth + 1); // recursive call
        } else {
            // max depth is reached, we add the line to Lines2D
            L2D.emplace_back(Line2D(
                    {T.pos, {T.pos.x + cos(toRadians(T.angle)), T.pos.y + sin(toRadians(T.angle))}, line_color}));
            T.pos = {T.pos.x + cos(toRadians(T.angle)), T.pos.y + sin(toRadians(T.angle))};
        };
    }
}

Lines2D gen_lines(const LParser::LSystem2D &ls2D, const Color &line_color) {
    std::string init = ls2D.get_initiator();
    Lines2D L2D;
    Turtle T;
    T.angle = ls2D.get_starting_angle();
    for (const auto &c:init) {
        if (c == '+' || c == '-') {
            T.angle += (-((c == '-') - 0.5) * 2) * ls2D.get_angle();
            continue;
        } else if (c == '(') {
            T.return_pos.push({T.pos, T.angle});
            continue;
        } else if (c == ')') {
            T.pos = T.return_pos.top().first;
            T.angle = T.return_pos.top().second;
            T.return_pos.pop();
            continue;
        }
        expand(c, ls2D, T, L2D, line_color, ls2D.get_nr_iterations());
    }
    return L2D;
}

Alphabet = {L, R, F}

Draw = {
       L -> 1,
       R -> 1,
       F -> 1
}

Rules = {
       L -> "+RF-LFL-FR+",
       R -> "-LF+RFR+FL-",
       F -> "F"
}

Initiator     = "L"
Angle         = 90
StartingAngle = 0
Iterations    = 4

L-系统示例

我想不出有什么方法可以（显着）提高性能。我虽然关于多线程，但你现在需要在每个线程的开头定位你的位置，但是你需要扩展前一个字符。

有没有更高效的算法来完成这个任务？或者实现它以便我可以使用多线程的方法？

编辑：我研究了答案，这就是我想出的，这提高了性能，但一个缺点是我的程序将使用更多的 ram（我被限制为 2GB，这是很多但仍然。）一种解决方案是使用队列，但这会降低性能。

Lines2D LSystem2DParser::generateLines() {
    Lines2D lines;
    drawing = l_system2d.get_initiator();
    Timer T;
    expand();
    T.endTimer("end of expand: ");
    Timer T2;
    lines = convert();
    T2.endTimer("end of convert: ");
    return lines;
}

void LSystem2DParser::expand() {
    if (depth >= max_depth) {
        return;
    }
    std::string expansion;
    for (char c : drawing) {
        switch (c) {
            case '+':
            case '-':
            case '(':
            case ')':
                expansion += c;
                break;
            default:
                expansion += replacement_rules[c];
                break;
        }
    }
    drawing = expansion;

    depth++;
    expand();
}

Lines2D LSystem2DParser::convert() {
    Lines2D lines;
    double current_angle = toRadians(l_system2d.get_starting_angle());
    double x = 0, y = 0, xinc = 0, yinc = 0;
    std::stack<std::array<double, 3>> last_pos;
    for (char c: drawing){
        switch (c) {
            case('+'):
                current_angle += angle;
                xinc = cos(current_angle);
                yinc = sin(current_angle);
                break;
            case ('-'):
                xinc = cos(current_angle);
                yinc = sin(current_angle);
                break;
            case ('('):
                last_pos.push({x, y, current_angle});
                break;
            case (')'):
                x = last_pos.top()[0];
                y = last_pos.top()[1];
                current_angle = last_pos.top()[2];
                last_pos.pop();
                break;
            default:
                lines.emplace_back(Line2D(Point2D(x,y), Point2D(x+xinc, y+yinc), line_color));
                x += xinc;
                y += yinc;
                break;
        }
    }
    return Lines2D();
}

编辑 2： It's still slow, in comparison to the code posted below

编辑 3：https://github.com/Robin-Dillen/3DEngine 所有代码

编辑 4：有一个奇怪的错误，循环没有结束

    for (std::_List_const_iterator<Point2D> point = ps.begin(); point != ps.end(); point++) {
        std::_List_const_iterator<Point2D> point2 = point++;
        img.draw_line(roundToInt(point->x * d + dx), roundToInt(point->y * d + dy), roundToInt(point2->x * d + dx),
                      roundToInt(point2->y * d + dy), line_color.convert());
    }

Answer 1

一般来说，优化应用程序性能的第一步是分析代码，以查看究竟在哪里花费了最多的时间。如果没有这一步，优化实际上对性能几乎没有影响的代码会浪费很多精力。

但是，在这种特殊情况下，我希望简化您的代码，以便更轻松地查看正在发生的事情，从而更轻松地解释性能分析的结果。

您的递归函数 expand 可以通过

进行简化

将所有这些参数移出签名。同一个东西没必要放那么多份在栈上！
递归函数应该做的第一件事是检查递归是否完成。在这种情况下，请检查深度。
第二件事，如果需要进一步递归，则执行下一次调用的准备工作。在这种情况下，从当前字符串生成下一个字符串。
终于可以调用递归函数了

下面我将 post 代码实现 Lindenmayer 的原始 L 系统，用于模拟藻类的生长。这比您正在做的要简单得多，但希望展示将递归代码重新组织为执行递归的“标准”样式的方法和好处。

Is there a more efficient algorithm to do this task?

我怀疑。我怀疑您可以改进您的实现，但如果不分析您的代码就很难知道。

a way to implement this so I could use multithreading?

递归算法不适合多线程。

这是实现类似递归算法的简单代码

#include <iostream>
#include <map>

using namespace std;

class cL
{
public:
    cL()
        : myAlphabet("AB")
    {
    }

    void germinate(
        std::map< char, std::string>& rules,
        const std::string& axiom,
        int generations )
    {
        myRules = rules;
        myMaxDepth = generations;
        myDepth = 0;
        myPlant = axiom;
        grow();
    }

private:
    std::string myAlphabet;
    std::map< char, std::string> myRules;
    int myDepth;
    int myMaxDepth;
    std::string myPlant;

    std::string production( const char c )
    {

        if( (int)myAlphabet.find( c ) < 0 )
            throw std::runtime_error(
                "production character not in alphabet");
        auto it = myRules.find( c );
        if( it == myRules.end() )
            throw std::runtime_error(
                "production missing rule");
        return it->second;
    }

    /// recursive growth

    void grow()
    {
        // check for completion
        if( myDepth == myMaxDepth )
        {
            std::cout << myPlant << "\n";
            return;
        }

        // produce the next growth spurt
        std::string next;
        for( auto c : myPlant )
        {
            next += production( c );
        }
        myPlant = next;

        // recurse
        myDepth++;
        grow();
    }
};

int main()
{
    cL L;
    std::map< char, std::string> Rules;
    Rules.insert(std::make_pair('A',std::string("AB")));
    Rules.insert(std::make_pair('B',std::string("A")));
    for( int d = 2; d < 10; d++ )
    {
        L.germinate( Rules, "A", d );
    }
    return 0;
}

Answer 2

   L2D.emplace_back(Line2D(
            {T.pos, {T.pos.x + cos(toRadians(T.angle)), T.pos.y + sin(toRadians(T.angle))}, line_color}));
    T.pos = {T.pos.x + cos(toRadians(T.angle)), T.pos.y + sin(toRadians(T.angle))};

不分析就很难知道这有多重要。然而：

为什么不以弧度形式存储角度，而是一遍又一遍地将其转换为弧度？
如果在其他地方使用弧度会有问题，至少进行一次转换并存储在本地
添加一个 Line2D 构造函数是个好主意，该构造函数将 Turtle 引用作为参数并进行自己的计算。
是否需要重新计算T.pos？现在回避不是完成了吗？

Answer 3

我已经实现了一个 Lsystem 来生成和绘制一个 Sierpinski ( https://en.wikipedia.org/wiki/L-system#Example_5:_Sierpinski_triangle ) 这与你正在做的非常相似。我以一种直接的方式实现，没有任何技巧。这是对迭代深度为 11 的代码进行时间分析的结果。

raven::set::cRunWatch code timing profile
Calls           Mean (secs)     Total           Scope
       1        0.249976        0.249976        draw
      11        0.0220157       0.242172        grow

grow是递归函数。调用11次，平均执行时间22毫秒

draw 是获取最终生成的字符串并将其绘制在屏幕上的函数。这被调用一次，需要 250 毫秒。

由此得出的结论是，递归函数不需要优化，因为 50% 的应用程序时间都用于绘图。

在您的问题中，您没有提供时间分析数据，甚至没有提供您所说的“相当慢”的意思。我想说的是，如果您的代码生成（而不是绘制）最终字符串所花费的时间超过 100 毫秒，那么您遇到的问题是由标准算法的实施不当引起的。但是，如果您抱怨的速度慢是由于画线造成的，那么您的问题可能是图形库选择不当 - 一些图形库甚至可以做一些简单的事情，比如画线比其他图形库快数百倍。

我邀请你看看我的代码 https://github.com/JamesBremner/Lindenmayer/blob/main/main.cpp

如果您只想解析字符串并将线条保存为矢量，那么事情会更快，因为不涉及图形库。

raven::set::cRunWatch code timing profile
Calls           Mean (secs)     Total           Scope
      11        0.00229241      0.0252165       grow
       1        0.0066558       0.0066558       VectorLines

这是代码

std::vector<std::pair<int,int> > 
VectorLines( const std::string& plant )
{
        raven::set::cRunWatch aWatcher("VectorLines");

        std::vector<std::pair<int,int> > vL;

        int x = 10;
        int y = 10;
        int xinc = 10;
        int yinc = 0;
        float angle = 0;

        for( auto c : plant )
        {
            switch( c )
            {
            case 'A':
            case 'B':
                break;;
            case '+':
                angle += 1;
                xinc = 5 * cos( angle );
                yinc = 5 * sin( angle );
                break;
            case '-':
                angle -= 1;
                xinc = 5 * cos( angle );
                yinc = 5 * sin( angle );
                break;
            }

            x += xinc;
            y += yinc;
            vL.push_back( std::pair<int,int>( x, y ) );
        }
    return vL;
}

将 2D L 系统转换为直线的最快方法是什么

What's the fastest way to convert a 2D L-system to lines

c++

graphics

multithreading

turtle-graphics