Как генерировать трехмерные деревья в любой заданной точке и направлении в пространстве с помощью C++ и L-Systems?

Question

Я программирую на C++ 3d-сцену, в которой деревья можно "выращивать" в любой точке и в любом направлении. Я нахожу, что деревья / планеты L-систем выглядят очень хорошо, но я не могу найти в Google какую-либо функцию или библиотеку, которые могут позволить мне передать координату точки, вектор направления и некоторые другие параметры и вернуть массив этого "выращенного" набора точек дерева.

Я не могу даже Google достаточно информации, чтобы начать. Так что любая идея или ссылка, на которую я могу сослаться, или повторно использовать и внести некоторые коррективы, чтобы выполнить эту задачу. Я нашел несколько парсеров L-sys, но это выглядело как просто рисование на месте без контроля растущих направлений, а также не смог дать мне целые координаты точки.

Answer 1

Вероятно, это проблема, которую быстрее реализовать самостоятельно, а не искать и пытаться интегрировать некоторые сторонние библиотеки.

Реализовать L-системы довольно просто. Вам нужно реализовать 2 части.

Первая часть - система перезаписи строк. Это просто. Вам просто нужно иметь словарь правил перезаписи (ключ ключа, строковое значение), а затем применять эти правила для начальной строки i-times (где i - количество итераций).

Псевдо-код:

map<char, string> rewriteRules = {{'L', "L+R+"}, {'R',"-L+R"}};

string rewrite(string str) {
    string result = "";
    for each (char c in str) {
        if (rewriteRules contains key c) {
            result += rewriteRules[c];
        }
        else {
            result += c; // identity
        }
    }
}

Вторая, более сложная часть - это интерпретация результирующей строки символов. Самый простой способ интерпретировать графику, похожую на черепаху, в 3D - это использовать кватернионы - их легко объединить.

Правила переписывания, описанные выше, описывают кривую Дракона, а семантическое значение символов:

• L, R: провести линию вперед
• +: повернуть налево на 90 градусов
• -: повернуть направо на 90 градусов

Следующие фрагменты кода демонстрируют реализацию перемещения и вращения в 3D с использованием кватернионов. Это от моего интерпретатора L-системы, написанного на C# (надеюсь, вы меня простите:).

Quaternion rotationQuat = Quaternion.Indentity;
Vector3D position;

Vector3D forwardVector = new Vector3D(1, 0, 0);
Vector3D upVector = new Vector3D(0, 1, 0);
Vector3D rightVector = forwardVector.Cross(upVector);

public void Forward(double distance, bool draw) {
    Vector3D moveVector = rotationQuat.Transform(forwardVector * distance);
    Vector3D oldPosition = position;
    position += moveVector;

    if (draw) {
        // draw cylinder/box from oldPosition to (new) position
    }
}

public void Yaw(double angle) {
    rotationQuat *= new Quaternion(upVector, angle);
}

public void Pitch(double angle) {
    rotationQuat *= new Quaternion(rightVector, angle);
}

public void Roll(double angle) {
    rotationQuat *= new Quaternion(forwardVector, angle);
}

Таким образом, чтобы интерпретировать строку, вам просто нужно пройти строку и интерпретировать каждый символ. Самый простой способ - просто переключиться:

for each (char c in string) {
    switch(c) {
    case 'L':
    case 'R':
        Forward(10, true);
        break;
    case '+':
        Yaw(90);
        break;
    case '-':
        Yaw(-90);
        break;
    default:
        break; // do nothing
    }
}

Если вы хотите поэкспериментировать с L-системами (даже в 3D), есть хороший веб-сайт http://malsys.cz/ где вы можете сделать это (эти фрагменты C# взяты из него:)

Удачи с L-системами!

Answer 2

Я не знаю ни одной библиотеки с открытым исходным кодом, которая бы обеспечивала алгоритмы 3d L-системы, я подозреваю, что вам придется написать свою собственную.

Начните с реализации 2d, это довольно просто, страница википедии - хорошее место, чтобы увидеть простые примеры, как только реализация 2d будет завершена, отсюда следует расширение до трети.