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

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

// 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-系统示例

我想不出任何方法可以(显著地)提高性能。我想是关于multihtreading的，但你现在需要在每个线程的开头定位，但之后你需要扩展前一个字符。

有没有更有效的算法来完成这项任务？或者一种实现这一点的方法，这样我就可以使用多线程了？

编辑：我已经研究了答案，这就是我的想法，这提高了性能，但一个缺点是我的程序将使用更多的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:与下面发布的代码相比，它仍然很慢

编辑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());
}