Преобразование dxf в svg

Речь в статье пойдёт о программе на С/С++, написанной под Ubuntu, редактор — CodeBlocks. dxf — открытый формат, спецификация которого написана компанией Autodesk. Предполагаемое назначение — отображение dxf чертежей в веб проектах. Да, можно экспортировать из кое-каких редакторов, например, Librecad под Ubuntu или Acme CAD Converter под Windows, но это не во всех случаях может подходить, например, если нужна кастомизация.

Сначала подробнее про сам формат dxf. Он составлен из пар кодов и ассоциированных значений.
Пример: images.autodesk.com/adsk/files/autocad_2012_pdf_dxf-reference_enu.pdf
Существую готовые библиотеки для парсинга dxf. Я рассматривал github.com/bert/libdxf, но свободная и небольшая библиотека от QCAD оказалась удобнее. Она есть в репозиториях Ubuntu, пакет под названием dxflib. Так как размер библиотеки маленький и она достаточно старая, без сторонних зависимостей, было решено скопировать её прямо в папку проекта. Также совместная компиляция при сборке с -О3, возможно, ускорит работу.
В более новых версиях формата сохраняется совместимость со старыми, то есть просто добавились пары кодов и ассоциированных значений. В dxfsvg я реализовал какую-то базовую часть спецификации — это основные примитивы. К дополнительным примитивам можно отнести, например, размерные стрелочки. Тут может быть вопрос — как я определил, какие примитивы основные? Взял чуть более 26000 файлов, в основном это экспорт из SolidWorks, добавил многопоточное чтение и накопление статистики. Это файлы catalog_array.c и str_array.c папки dir_explore.
str_array.c реализует массив строк названий dxf файлов. Перед строками я также подсунул битовый массив флагов с примитивами для определения их встречаемости. Да, можно было написать через vector, но это я взял из другого своего проекта.

catalog_array.c реализует обход каталогов и подкаталогов

void catalog_contents::processing_files(void* (*start_routine)(void*))
{
    if(filename==nullptr)
    {
        int i=0;
        int THREAD_COUNT=sysconf(_SC_NPROCESSORS_ONLN);
        pthread_t id[THREAD_COUNT];
        printf("thread_count=%d\n", THREAD_COUNT);
        pthread_mutex_t mutex;
        pthread_mutex_init(&mutex, NULL);
        //создаём рабочие потоки
        for(i = 0; i < THREAD_COUNT; i++)
        {
            thread_param param;
            param.contents=this;
            param.thread_count=THREAD_COUNT;
            param.thread_num=i;
            param.mutex=mutex;
            pthread_create(&id[i], NULL, start_routine, &param);
        }
        pthread_mutex_destroy(&mutex);
        //ждем завершения рабочих потоков
        for(i = 0; i < THREAD_COUNT; i++)
        {
            pthread_join(id[i], NULL);
            pthread_detach(id[i]);
        }
    }
    else
    {
        svg_gen svg;
        if (!svg.dxf.in(filename, svg.dxf_filter))
        {
            printf("File %s could not be opened\n", filename);
        }
        else
        {
            this->evaluate_dxf_stats(svg.func_bit_flags);
            svg.svg_generate();
        }
    }
}

Если указано название файла, то будет обрабатываться 1 dxf файл, иначе будет обрабатываться весь каталог. Поскольку применяется dirent.h, то это даёт ухудшение портируемости, так как под Windows понадобится C POSIX library. Многопоточность нужна при обработке большого количества файлов, так как упор идёт в процессор (Xeon 2660v2). Включение HT практически не влияет, даёт прибавку всего в несколько процентов.
Далее про структуру наследования. Она достаточно простая в проекте. Основной класс — svg_gen.

class svg_gen : public dxf_filter, public stats
class dxf_filter : public DL_CreationAdapter, public data_vectors

Если в С++ не было бы множественного наследования, то пришлось бы рассовывать родительские классы в конструкторы. DL_CreationAdapter идёт от dxflib. data_vectors содержит непосредственно примитивы. Формат dxf имеет такое понятие как блоки — набор примитивов, который может вставляться много раз в чертёж. На текущий момент программа не поддерживает вставки (Inserts) из-за невысокой встречаемости и отсутствия необходимости как-то обрабатывать эту геометрию, там где вставки есть. Всё что за пределами блоков — это основная часть, которую нужно парсить.
Как можете видеть, перевод в svg написан достаточно прямолинейно, трудности вызвала обработка сплайнов. Пробелы в математике я устранял при помощи Maple. В итоге образуется многочлен с индексами

Многочлен может быть получен командами Maple
with(CurveFitting):
xydata2 := [[x[0], 1], [x[1], 1], [x[2], 1], [x[3], 1], [x[4], 1], [x[5], 1], [x[6], 1], [x[7], 1], [x[8], 1], [x[9], 1]]
BSplineCurve(xydata2, t, order = 4, knots = [k1, k2, k3, k4, k5, k6, k7, k8, k9, k10, k11, k12, k13, k14])
order=3 — это квадратичные сплайны, order=4 — это кубические.
Сплайны задаются в терминах точек и узлов. Как вывести эти формулы путём математических доказательств и рассуждений я не знаю, так как сильно не заморачивался, но литературы с примерами по такому представлению сплайнов мало, а большинство того что загуглилось — англоязычное.
Все примитивы, кроме линий, окружностей и дуг представлены в виде аппроксимирующих линий. Для оптимизации веса svg файла можно применить кривые Безье второго порядка.
Допустим есть 3 точки: P0, P(t), P2 вида (из Википедии)

Надо найти опорную точку P1 из уравнения

Из этого уравнения выражаем P1, принимаем t=0.5, так как точки расположены равномерно.

В итоге получился достаточно простой код

string svg_gen::solve_quadratic_beizer(vector<point> pt)
{
    if(pt.size()>=4)
    {
        string res;
        char pair[32]={0};
        snprintf(pair,31,"%.3f,%.3f ", pt[0].x, pt[0].y);
        res.append(pair);
        int i=0;
        start:
        double Px=2*pt[i+1].x-0.5*(pt[i].x+pt[i+2].x);
        double Py=2*pt[i+1].y-0.5*(pt[i].y+pt[i+2].y);
        res=res+'Q';
        memset(pair, 0, 32);
        snprintf(pair,31,"%.3f,%.3f ", Px, Py);
        res.append(pair);
        memset(pair, 0, 32);
        snprintf(pair,31,"%.3f,%.3f ", pt[i+2].x, pt[i+2].y);
        res.append(pair);
        if(pt.size()>i+4) {i=i+2; goto start;}
        else
        {   i=i+3;
                while(i<pt.size())
                {
                    memset(pair, 0, 32);
                    snprintf(pair,31,"L%.3f,%.3f ", pt[i].x, pt[i].y);
                    res.append(pair);
                    ++i;
                }
        }
        return res;
    }
    else
    {
        string res="";
        return res;
    }
}

Функцию Безье можно использовать в эллиптических дугах и сплайнах. Я добавил только в сплайны второго порядка. Рассмотрим пример. Вычисления опираются на формулы, полученные из Maple. Как видно, наличие препроцессора в С++ хорошо помогает сократить длину формул.

class spline_koeff
{
public:
    double b1;
    double b2;
    double b3;
    int n=0;
    void coeffs(double t, vector<point> pt, vector<double> k);
};

void spline_koeff::coeffs(double t,vector<point> pt, vector<double> k)
{
    #define k2 k[n+1]
    #define k3 k[n+2]
    #define k4 k[n+3]
    #define k5 k[n+4]
    if(k2-k4!=0&&k3-k4!=0&&k3-k5!=0&&n<(int)pt.size())
    {
        b1=pow(k4-t,2)/(-k4+k2)/(-k4+k3);
        b2=-(t*t*k2+k2*k3*k5+k2*k3*k4-k4*k2*k5-2*t*k3*k2-k4*t*t+2*t*k4*k5-t*t*k5+t*t*k3-k3*k4*k5)/(-k4+k2)/(-k4+k3)/(-k5+k3);
        b3=pow(-t+k3,2)/(-k4+k3)/(-k5+k3);
    }
    else
    {b1=0;b2=0;b3=0;}
}

void svg_gen::spline_points_and_knots_degree2(vector<point> pt, vector<double> k, double x_min, double y_max)
{
        point pt1, pt2;
        string res="<path d=\"M";
        double t=0;
        vector<point> pair;
    spline_koeff b123;
    for(int j=3; j<(int)k.size()-2; ++j)
    {
        double ink=(k[j]-k[j-1])/10;
        b123.n=j-3;
        t=k[j-1];
        int i=0;
        while(i<10)
        {
            b123.coeffs(t, pt, k);
            #define b1 b123.b1
            #define b2 b123.b2
            #define b3 b123.b3
            #define n b123.n
            pt1.x=b1*pt[n].x+b2*pt[n+1].x+b3*pt[n+2].x;
            pt1.y=b1*pt[n].y+b2*pt[n+1].y+b3*pt[n+2].y;
            t=t+ink;
            printf("t1=%f\n",t);
            b123.coeffs(t, pt, k);
            pt2.x=b1*pt[n].x+b2*pt[n+1].x+b3*pt[n+2].x;
            pt2.y=b1*pt[n].y+b2*pt[n+1].y+b3*pt[n+2].y;
            t=t-ink;
            printf("t2=%f\n",t);
            char buf[72]= {0};
            snprintf(buf,71,"%.3f,%.3f %.3f,%.3f ", pt1.x-x_min, y_max-pt1.y, pt2.x-x_min, y_max-pt2.y);
            point pt={pt1.x-x_min, y_max-pt1.y};
            pair.emplace_back(pt);
            if(i==9)
            {
                point pt={pt2.x-x_min, y_max-pt2.y};
                pair.emplace_back(pt);
            }
           // res.append(buf);
            t=t+ink;
            ++i;
        }
    }
    res=res+solve_quadratic_beizer(pair);
    res.append("\"/>\n");
    this->resulting_svg=this->resulting_svg+res;
}

Если поменять комметирование, то получим аппроксимацию линиями

/*point pt={pt1.x-x_min, y_max-pt1.y};
            pair.emplace_back(pt);
            if(i==9)
            {
                point pt={pt2.x-x_min, y_max-pt2.y};
                pair.emplace_back(pt);
            }*/
           res.append(buf);

Я уменьшил в 2 раза количество точек для аппроксимации Безье. В итоге результат на каких-то сплайнах
При линейной интерполяции

Кривыми

Размер 12,2кб против 7,1кб в пользу интерполяции квадратичными кривыми Безье.
Исследования выбоки показали, что SolidWorks применяет сплайны третьего порядка, но эти кривые достаточно короткие и их можно просто аппрокисимровать линиями.
В LibreCad есть тоже открытая реализация экспорта в SVG /LibreCAD-master/librecad/src/lib/generators/ Там экспорт идёт из внутренних структур редактора. Это существенно усложняет процесс извлечения нужной части кода.
Ссылка на репозиторий github.com/SanyaZ7/dxf_to_svg
Спасибо за внимание.