XbSlicer, re-organized the entire project

diff --git a/.clang-format b/.clang-format
new file mode 100644 (file)
index 0000000..94d2231
--- /dev/null
+++ b/.clang-format
@@ -0,0 +1,157 @@
+---
+Language:        Cpp
+# BasedOnStyle:  Google
+AccessModifierOffset: -4
+AlignAfterOpenBracket: Align
+AlignConsecutiveMacros: false
+AlignConsecutiveAssignments: true
+AlignConsecutiveDeclarations: false
+AlignEscapedNewlines: Left
+AlignOperands:   true
+AlignTrailingComments: true
+AllowAllArgumentsOnNextLine: true
+AllowAllConstructorInitializersOnNextLine: true
+AllowAllParametersOfDeclarationOnNextLine: true
+AllowShortBlocksOnASingleLine: false
+AllowShortCaseLabelsOnASingleLine: false
+AllowShortFunctionsOnASingleLine: All
+AllowShortLambdasOnASingleLine: All
+AllowShortIfStatementsOnASingleLine: WithoutElse
+AllowShortLoopsOnASingleLine: true
+AlwaysBreakAfterDefinitionReturnType: None
+AlwaysBreakAfterReturnType: None
+AlwaysBreakBeforeMultilineStrings: true
+AlwaysBreakTemplateDeclarations: Yes
+BinPackArguments: true
+BinPackParameters: true
+BraceWrapping:
+  AfterCaseLabel:  false
+  AfterClass:      false
+  AfterControlStatement: false
+  AfterEnum:       false
+  AfterFunction:   false
+  AfterNamespace:  false
+  AfterObjCDeclaration: false
+  AfterStruct:     false
+  AfterUnion:      false
+  AfterExternBlock: false
+  BeforeCatch:     false
+  BeforeElse:      false
+  IndentBraces:    false
+  SplitEmptyFunction: true
+  SplitEmptyRecord: true
+  SplitEmptyNamespace: true
+BreakBeforeBinaryOperators: None
+BreakBeforeBraces: Allman
+BreakBeforeInheritanceComma: false
+BreakInheritanceList: BeforeColon
+BreakBeforeTernaryOperators: true
+BreakConstructorInitializersBeforeComma: false
+BreakConstructorInitializers: BeforeColon
+BreakAfterJavaFieldAnnotations: false
+BreakStringLiterals: true
+ColumnLimit:     80
+CommentPragmas:  '^ IWYU pragma:'
+CompactNamespaces: false
+ConstructorInitializerAllOnOneLineOrOnePerLine: true
+ConstructorInitializerIndentWidth: 4
+ContinuationIndentWidth: 4
+Cpp11BracedListStyle: true
+DerivePointerAlignment: true
+DisableFormat:   false
+ExperimentalAutoDetectBinPacking: false
+FixNamespaceComments: true
+ForEachMacros:
+  - foreach
+  - Q_FOREACH
+  - BOOST_FOREACH
+IncludeBlocks:   Regroup
+IncludeCategories:
+  - Regex:           '^<ext/.*\.h>'
+    Priority:        2
+  - Regex:           '^<.*\.h>'
+    Priority:        1
+  - Regex:           '^<.*'
+    Priority:        2
+  - Regex:           '.*'
+    Priority:        3
+IncludeIsMainRegex: '([-_](test|unittest))?$'
+IndentCaseLabels: false
+IndentPPDirectives: None
+IndentWidth:     4
+IndentWrappedFunctionNames: false
+JavaScriptQuotes: Leave
+JavaScriptWrapImports: true
+KeepEmptyLinesAtTheStartOfBlocks: false
+MacroBlockBegin: ''
+MacroBlockEnd:   ''
+MaxEmptyLinesToKeep: 1
+NamespaceIndentation: None
+ObjCBinPackProtocolList: Never
+ObjCBlockIndentWidth: 2
+ObjCSpaceAfterProperty: false
+ObjCSpaceBeforeProtocolList: true
+PenaltyBreakAssignment: 2
+PenaltyBreakBeforeFirstCallParameter: 1
+PenaltyBreakComment: 300
+PenaltyBreakFirstLessLess: 120
+PenaltyBreakString: 1000
+PenaltyBreakTemplateDeclaration: 10
+PenaltyExcessCharacter: 1000000
+PenaltyReturnTypeOnItsOwnLine: 200
+PointerAlignment: Left
+RawStringFormats:
+  - Language:        Cpp
+    Delimiters:
+      - cc
+      - CC
+      - cpp
+      - Cpp
+      - CPP
+      - 'c++'
+      - 'C++'
+    CanonicalDelimiter: ''
+    BasedOnStyle:    google
+  - Language:        TextProto
+    Delimiters:
+      - pb
+      - PB
+      - proto
+      - PROTO
+    EnclosingFunctions:
+      - EqualsProto
+      - EquivToProto
+      - PARSE_PARTIAL_TEXT_PROTO
+      - PARSE_TEST_PROTO
+      - PARSE_TEXT_PROTO
+      - ParseTextOrDie
+      - ParseTextProtoOrDie
+    CanonicalDelimiter: ''
+    BasedOnStyle:    google
+ReflowComments:  true
+SortIncludes:    true
+SortUsingDeclarations: true
+SpaceAfterCStyleCast: false
+SpaceAfterLogicalNot: false
+SpaceAfterTemplateKeyword: true
+SpaceBeforeAssignmentOperators: true
+SpaceBeforeCpp11BracedList: false
+SpaceBeforeCtorInitializerColon: true
+SpaceBeforeInheritanceColon: true
+SpaceBeforeParens: ControlStatements
+SpaceBeforeRangeBasedForLoopColon: true
+SpaceInEmptyParentheses: false
+SpacesBeforeTrailingComments: 2
+SpacesInAngles:  false
+SpacesInContainerLiterals: true
+SpacesInCStyleCastParentheses: false
+SpacesInParentheses: false
+SpacesInSquareBrackets: false
+Standard:        Auto
+StatementMacros:
+  - Q_UNUSED
+  - QT_REQUIRE_VERSION
+TabWidth:        8
+UseTab:          Never
+...
+

diff --git a/.gitignore b/.gitignore
new file mode 100644 (file)
index 0000000..e657f11
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,8 @@
+tags
+xbslicer*
+build/
+stl_files/*
+gcode_files/*
+*.~
+
+!/stl_files/cube.stl

diff --git a/LICENSE b/LICENSE
new file mode 100644 (file)
index 0000000..18536e8
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1,22 @@
+MIT License
+
+Copyright (c) 2020 XinqiBao
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
+

diff --git a/Makefile b/Makefile
new file mode 100644 (file)
index 0000000..bd07ab5
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,57 @@
+EXE                    =       xbslicer
+
+DIR                    =       $(shell pwd)
+SRC_DIR                =       $(DIR)/src
+BUILD_DIR      =       $(DIR)/build
+
+vpath %.cc $(SRC_DIR)
+vpath %.hh $(SRC_DIR)
+vpath %.o  $(BUILD_DIR)
+
+CXX    := g++
+OPTIONS        = -std=c++11
+MODE ?= debug
+
+OBJ    := main.o Slicer.o Slicing.o GCode.o STL.o \
+       Configurations.o BufferReadBinary.o BufferWrite.o \
+       Vec2d.o Vec3d.o Triangle.o Cross.o Loop.o Layer.o \
+       DoubleToString.o
+
+ifeq ($(strip $(MODE)), release)
+       OPTIONS += -O2
+       TARGET = $(EXE)
+else
+       OPTIONS += -g
+       TARGET = $(EXE)-staging
+endif
+
+all: $(TARGET)
+
+$(TARGET): $(OBJ)
+       @echo $(strip $(MODE))
+       $(CXX) $(OPTIONS) -pthread $(addprefix $(BUILD_DIR)/, $(OBJ)) -o $@
+
+%.o:%.cc
+       @mkdir -p $(BUILD_DIR)
+       $(CXX) $(OPTIONS) -c $< -o $(BUILD_DIR)/$@
+
+main.o: Slicer.o
+Slicer.o: STL.o Slicing.o BufferWrite.o Slicer.hh
+STL.o: Configurations.o BufferReadBinary.o Triangle.o STL.hh
+Slicing.o: STL.o GCode.o Slicing.hh
+GCode.o: Configurations.o Layer.o GCode.hh
+Configurations.o: Configurations.hh
+BufferReadBinary.o: BufferReadBinary.hh
+BufferWrite.o: DoubleToString.o BufferWrite.hh
+Vec2d.o: Vec3d.o Vec2d.hh
+Vec3d.o: Configurations.o BufferReadBinary.o Vec3d.hh
+Triangle.o: Vec3d.o Triangle.hh
+Cross.o: Vec2d.o Cross.hh
+Loop.o: Loop.hh
+Layer.o: Loop.o Cross.o BufferWrite.o Layer.hh
+DoubleToString.o: DoubleToString.hh
+
+.PHONY: clean
+clean:
+       @rm -rf $(BUILD_DIR) $(EXE)*
+       @echo "Clean finished!"

diff --git a/README.md b/README.md
new file mode 100644 (file)
index 0000000..812293b
--- /dev/null
+++ b/README.md
@@ -0,0 +1,39 @@
+# XbSlicer
+
+A program for slicing 3D models in STL format to GCode file.
+
+Some optimizations have been implemented, check [XbSlicer paper](http://xinqibao2017.com/file/AnOptimizedSlicerFor3DPrinting.pdf) for detail.
+
+Yet this software itself is not the best, but it does something. It's a personal project for practice, helped by professor Dov Kruger, from Department of Electrical & Computer Engineering at Stevens Institute of Technology.
+
+## How to run
+
+run `make` to get the executable file.
+
+`make MODE=release` get the release version.
+
+run `xbslicer` or `xbslicer-staging` with input filename, otherwise it'll take a default file.
+
+```
+./xbslicer cube.stl
+```
+
+Input file has to be stored in `stl_files/`, output gcode file will be in `gcode_files/`.
+
+It can take STL file both in ASCII and Binary format.
+
+ASCII format file with extension `.stl`, Binary format file has to be with extension `.stlb`.
+
+## TODO
+
+Complicated models will require SupportMaterial to print actually stuff, XbSlicer is not support for this.
+
+Still it can print some simple models with the GCode files generated by XbSlicer.
+
+## To improve
+
+For now, the config file is like hard coded, every time make some change in config file, it requires to build the whole project to make it work. It is really frustrating, config file need to be read-in on running time.
+
+Also, the input and output file path is not flexible, as long as file extension, especially for Binary STL file.
+
+For a good command running experience, it need to have support like parser, user can pass in arguments to modify something.

diff --git a/src/BufferReadBinary.cc b/src/BufferReadBinary.cc
new file mode 100644 (file)
index 0000000..1c7cb15
--- /dev/null
+++ b/src/BufferReadBinary.cc
@@ -0,0 +1,45 @@
+/*
+        Buffer for reading binary STL file
+*/
+#include "BufferReadBinary.hh"
+
+BufferReadBinary::BufferReadBinary(std::string& fileTarget)
+    : remain(0), readIn(0), numTrianglesInBlock(0)
+{
+    prebuffer          = new char[PREBUFFER_SIZE + BUFFER_SIZE];
+    buffer             = prebuffer + PREBUFFER_SIZE;
+    fn                 = open(fileTarget.c_str(), O_RDONLY);
+    readIn             = read(fn, buffer, BUFFER_SIZE);
+    phead              = buffer + 80;
+    numTrianglesInFile = *(uint32_t*)phead;
+    phead += sizeof(uint32_t);
+    readIn -= 84;
+    numTrianglesInBlock = readIn / 50;
+    remain              = readIn % 50;
+}
+BufferReadBinary::~BufferReadBinary()
+{
+    delete[] prebuffer;
+    close(fn);
+}
+uint32_t BufferReadBinary::getNumTrianglesInFile()
+{
+    return numTrianglesInFile;
+}
+uint32_t BufferReadBinary::getNumTrianglesInBlock()
+{
+    return numTrianglesInBlock;
+}
+void BufferReadBinary::step2Bytes() { phead += 2; }
+void BufferReadBinary::stepFloat() { phead += sizeof(float); }
+float BufferReadBinary::getFloat() { return *(float*)phead; }
+void BufferReadBinary::readBuffer()
+{
+    char* pd = buffer - remain;
+    char* pf = buffer + BUFFER_SIZE - remain;
+    for (int i = remain; i > 0; i--, pd++, pf++) *pd = *pf;
+    readIn              = read(fn, buffer, BUFFER_SIZE);
+    phead               = buffer - remain;
+    numTrianglesInBlock = (readIn + remain) / 50;
+    remain              = (readIn + remain) % 50;
+}

diff --git a/src/BufferReadBinary.hh b/src/BufferReadBinary.hh
new file mode 100644 (file)
index 0000000..87768b6
--- /dev/null
+++ b/src/BufferReadBinary.hh
@@ -0,0 +1,36 @@
+/*
+        Buffer for reading binary STL file
+*/
+#pragma once
+
+#include <fcntl.h>
+#include <sys/stat.h>
+#include <unistd.h>
+
+#include <string>
+//#include "Components.hh"
+
+class BufferReadBinary
+{
+private:
+    char* prebuffer;  // just before buffer
+    char* buffer;
+    char* phead;
+    int fn;
+    uint32_t BUFFER_SIZE    = 32768;  // 32K
+    uint32_t PREBUFFER_SIZE = 64;
+    uint32_t readIn;
+    uint32_t remain;  // bytes that left in buffer, not enough for one triangle
+    uint32_t numTrianglesInFile;
+    uint32_t numTrianglesInBlock;
+
+public:
+    BufferReadBinary(std::string& fileTarget);
+    ~BufferReadBinary();
+    uint32_t getNumTrianglesInFile();
+    uint32_t getNumTrianglesInBlock();
+    void step2Bytes();
+    void stepFloat();
+    float getFloat();
+    void readBuffer();
+};

diff --git a/src/BufferWrite.cc b/src/BufferWrite.cc
new file mode 100644 (file)
index 0000000..2108134
--- /dev/null
+++ b/src/BufferWrite.cc
@@ -0,0 +1,84 @@
+/*
+        Buffer for writing
+*/
+#include "BufferWrite.hh"
+
+#include <fcntl.h>
+#include <stdio.h>
+#include <sys/stat.h>
+#include <unistd.h>
+
+#include <string>
+
+BufferWrite::BufferWrite(std::string& fileTarget)
+{
+    buffer     = new char[BUFFER_SIZE + POSTBUFFER_SIZE];
+    postbuffer = buffer + BUFFER_SIZE;
+    phead      = buffer;
+    remove(fileTarget.c_str());
+    creat(fileTarget.c_str(), S_IREAD | S_IWRITE);
+    fn = open(fileTarget.c_str(), O_WRONLY | O_APPEND);
+}
+BufferWrite::~BufferWrite()
+{
+    flush();
+    delete[] buffer;
+    close(fn);
+}
+
+void BufferWrite::flushOnlyBuffer()
+{
+    size_t size = write(fn, buffer, BUFFER_SIZE);
+    // copy the stuff in postbuffer to buffer
+    for (int i = 0; i < phead - postbuffer; i++) buffer[i] = postbuffer[i];
+    phead -= BUFFER_SIZE;
+}
+
+void BufferWrite::writeG0(double x, double y)
+{
+    *this << "G0 F4800 X" << x << " Y" << y << '\n';
+    if (phead >= postbuffer) flushOnlyBuffer();
+}
+void BufferWrite::writeG1(double x, double y, double e)
+{
+    *this << "G1 F2000 X" << x << " Y" << y << " E" << e << '\n';
+    if (phead >= postbuffer) flushOnlyBuffer();
+}
+void BufferWrite::flush()
+{
+    uint32_t sizeToWrite = phead - buffer;
+    size_t size          = write(fn, buffer, sizeToWrite);
+    phead                = buffer;
+}
+
+BufferWrite& operator<<(BufferWrite& buf, const char* ch)
+{
+    // check buffer is full or not. If full, only flush the buffer
+    for (int i = 0; ch[i] != '\0'; i++, buf.phead++) *buf.phead = ch[i];
+    return buf;
+}
+BufferWrite& operator<<(BufferWrite& buf, char ch)
+{
+    *buf.phead = ch;
+    buf.phead++;
+    return buf;
+}
+BufferWrite& operator<<(BufferWrite& buf, std::string& str)
+{
+    return buf << str.c_str();
+}
+BufferWrite& operator<<(BufferWrite& buf, double val)
+{
+#if 0
+    //TODO: translating double to string REALLY take so much time!!!
+    //TODO: make our own doubleToString()
+    //snprintf(buf.phead, 9, "%lf", val);
+    //buf.phead += 9;
+    std::string str = std::to_string(val);
+    return buf << str;
+#endif
+#if 1  // faster way for DoubleToString
+    buf.phead = formatDouble(val, buf.phead);
+    return buf;
+#endif
+}

diff --git a/src/BufferWrite.hh b/src/BufferWrite.hh
new file mode 100644 (file)
index 0000000..5ae1265
--- /dev/null
+++ b/src/BufferWrite.hh
@@ -0,0 +1,39 @@
+/*
+        Buffer for writing
+*/
+
+#pragma once
+
+#include <fcntl.h>
+#include <stdio.h>
+#include <sys/stat.h>
+#include <unistd.h>
+
+#include <string>
+
+#include "DoubleToString.hh"
+//#include "Components.hh"
+
+class BufferWrite
+{
+private:
+    char* postbuffer;  // just after buffer
+    char* buffer;
+    char* phead;
+    int fn;
+    uint32_t BUFFER_SIZE     = 32768;  // 32K
+    uint32_t POSTBUFFER_SIZE = 256;
+    void flushOnlyBuffer();
+
+public:
+    void writeG0(double x, double y);
+    void writeG1(double x, double y, double e);
+    void flush();
+
+    BufferWrite(std::string& fileTarget);
+    ~BufferWrite();
+    friend BufferWrite& operator<<(BufferWrite& buf, const char* ch);
+    friend BufferWrite& operator<<(BufferWrite& buf, char ch);
+    friend BufferWrite& operator<<(BufferWrite& buf, std::string& str);
+    friend BufferWrite& operator<<(BufferWrite& buf, double val);
+};

diff --git a/src/Configurations.cc b/src/Configurations.cc
new file mode 100644 (file)
index 0000000..9d7efcd
--- /dev/null
+++ b/src/Configurations.cc
@@ -0,0 +1,20 @@
+#include "Configurations.hh"
+using namespace std;
+
+string stl_filePath   = "./stl_files/";    // directory for storing stl files
+string gcode_filePath = "./gcode_files/";  // directory for storing gcode files
+
+double thr = 0.000000001;        // Threshold
+double dzEachLevel = 1;          // high for mm to assign to one level
+double centerX           = 100;  // center X
+double centerY           = 100;  // center Y
+double centerZ           = 0;    // center Z
+bool needMoveToCenter    = true;
+bool needSupportMaterial = true;
+
+double zStart = 0.3;
+double zgap = 0.2;     // gap between each adjacent layers
+double ingap = 0.2;    // gap for infill
+double ef    = 0.015;  // factor for extrude, e += distance * ef
+double emax  = 100;    // When E bigger than 10000, the precision will lose,
+                    // terrible things happen

diff --git a/src/Configurations.hh b/src/Configurations.hh
new file mode 100644 (file)
index 0000000..5e1d4d0
--- /dev/null
+++ b/src/Configurations.hh
@@ -0,0 +1,23 @@
+#pragma once
+
+#include <string>
+
+#define NUM_THREADS 4
+
+extern std::string stl_filePath;    // directory for storing stl files
+extern std::string gcode_filePath;  // directory for storing gcode files
+
+extern double thr;          // Threshold
+extern double dzEachLevel;  // high for mm to assign to one level
+extern double centerX;      // center X
+extern double centerY;      // center Y
+extern double centerZ;      // center Z
+extern bool needMoveToCenter;
+extern bool needSupportMaterial;
+
+extern double zStart;
+extern double zgap;   // gap between each adjacent layers
+extern double ingap;  // gap for infill
+extern double ef;     // factor for extrude, e += distance * ef
+extern double emax;   // When E bigger than 10000, the precision will lose,
+                     // terrible things happen

diff --git a/src/Cross.cc b/src/Cross.cc
new file mode 100644 (file)
index 0000000..aadea5c
--- /dev/null
+++ b/src/Cross.cc
@@ -0,0 +1,26 @@
+#include "Cross.hh"
+
+Cross::Cross(Vec2d* p1, Vec2d* p2) : p1(*p1), p2(*p2) {}
+Cross::Cross(const Vec2d& p1, const Vec2d& p2) : p1(p1), p2(p2) {}
+
+bool Cross::equal(const Cross* cr) const
+{
+    return (p1.equal(cr->p1) && p2.equal(cr->p2)) ||
+           (p1.equal(cr->p2) && p2.equal(cr->p1));
+}
+bool Cross::equal(const Cross& cr) const
+{
+    if ((p1.equal(cr.p1) && p2.equal(cr.p2)) ||
+        (p1.equal(cr.p2) && p2.equal(cr.p1)))
+        return true;
+    return false;
+}
+
+std::ostream& operator<<(std::ostream& s, const Cross* cr)
+{
+    return s << cr->p1 << "  ---  " << cr->p2;
+}
+std::ostream& operator<<(std::ostream& s, const Cross& cr)
+{
+    return s << cr.p1 << "  ---  " << cr.p2;
+}

diff --git a/src/Cross.hh b/src/Cross.hh
new file mode 100644 (file)
index 0000000..dde9040
--- /dev/null
+++ b/src/Cross.hh
@@ -0,0 +1,18 @@
+#pragma once
+#include <iostream>
+
+#include "Vec2d.hh"
+
+class Cross
+{
+public:
+    Vec2d p1, p2;
+    bool equal(const Cross* cr) const;
+    bool equal(const Cross& cr) const;
+
+    Cross(Vec2d* p1, Vec2d* p2);
+    Cross(const Vec2d& p1, const Vec2d& p2);
+
+    friend std::ostream& operator<<(std::ostream& s, const Cross* cr);
+    friend std::ostream& operator<<(std::ostream& s, const Cross& cr);
+};

diff --git a/src/DoubleToString.cc b/src/DoubleToString.cc
new file mode 100644 (file)
index 0000000..e1780cb
--- /dev/null
+++ b/src/DoubleToString.cc
@@ -0,0 +1,337 @@
+#include "DoubleToString.hh"
+
+#include <cmath>
+using namespace std;
+
+/**
+         @author: Dov Kruger
+         Ultrafast float formatting for fast printing
+         This code is not well tested, and it definitely does not print every
+   floating point value Given that we have a known range and a known precision,
+   this code is a model for how we might print numbers into gcode at high speed.
+         We determine how big the number is and pull off digits in order.
+         Given exactly 6 digits after the decimal we print using two groups of 3
+   digits which are loaded from an array lookup.
+ */
+
+// code below generated by builddigits.cc
+char* formatDouble(double d, char* p)
+{
+    if (d < 0)
+    {
+        *p++ = '-';
+        d    = -d;
+    }
+    static const int exponent[] = {0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3,
+                                   3, 3, 3, 4, 4, 4, 5, 5, 5, 6};
+    static const int div[]      = {1,      1,      1,      10,    10,    10,
+                              10,     100,    100,    100,   1000,  1000,
+                              1000,   1000,   10000,  10000, 10000, 100000,
+                              100000, 100000, 1000000};
+    int e;
+    double m     = frexp(d, &e);
+    int whole    = int(d);
+    int fdivisor = 1000000;  // starting divisor for 6 digits after the decimal
+    int fracDigits =
+        int((d - whole) *
+            fdivisor);  // mult by constant to give desired number of digits
+    if (e >= 0)
+    {
+        int divisor = div[e];
+        for (int numdig = exponent[e]; numdig > 0; numdig--, divisor /= 10)
+        {
+            int dig = whole / divisor;
+            *p++    = dig + '0';
+            whole -= dig * divisor;
+            //         cout << dig;
+        }
+    }
+    *p++ = whole + '0';
+    *p++ = '.';
+
+    int first3 = (*(int*)(digits + (fracDigits / 1000 * 4))) >> 8;
+    *p++       = first3;
+    first3 >>= 8;
+    *p++ = first3;
+    first3 >>= 8;
+    *p++        = first3;
+    int second3 = (*(int*)(digits + fracDigits % 1000 * 4)) >> 8;
+    *p++        = second3;
+    second3 >>= 8;
+    *p++ = second3;
+    second3 >>= 8;
+    *p++ = second3;
+
+    //*p++= '\0';
+    // cerr << "e=" << e << '\n';
+    return p;
+}
+
+const char digits[4000] = {
+    '0', '0', '0', '0', '0', '0', '0', '1', '0', '0', '0', '2', '0', '0', '0',
+    '3', '0', '0', '0', '4', '0', '0', '0', '5', '0', '0', '0', '6', '0', '0',
+    '0', '7', '0', '0', '0', '8', '0', '0', '0', '9', '0', '0', '1', '0', '0',
+    '0', '1', '1', '0', '0', '1', '2', '0', '0', '1', '3', '0', '0', '1', '4',
+    '0', '0', '1', '5', '0', '0', '1', '6', '0', '0', '1', '7', '0', '0', '1',
+    '8', '0', '0', '1', '9', '0', '0', '2', '0', '0', '0', '2', '1', '0', '0',
+    '2', '2', '0', '0', '2', '3', '0', '0', '2', '4', '0', '0', '2', '5', '0',
+    '0', '2', '6', '0', '0', '2', '7', '0', '0', '2', '8', '0', '0', '2', '9',
+    '0', '0', '3', '0', '0', '0', '3', '1', '0', '0', '3', '2', '0', '0', '3',
+    '3', '0', '0', '3', '4', '0', '0', '3', '5', '0', '0', '3', '6', '0', '0',
+    '3', '7', '0', '0', '3', '8', '0', '0', '3', '9', '0', '0', '4', '0', '0',
+    '0', '4', '1', '0', '0', '4', '2', '0', '0', '4', '3', '0', '0', '4', '4',
+    '0', '0', '4', '5', '0', '0', '4', '6', '0', '0', '4', '7', '0', '0', '4',
+    '8', '0', '0', '4', '9', '0', '0', '5', '0', '0', '0', '5', '1', '0', '0',
+    '5', '2', '0', '0', '5', '3', '0', '0', '5', '4', '0', '0', '5', '5', '0',
+    '0', '5', '6', '0', '0', '5', '7', '0', '0', '5', '8', '0', '0', '5', '9',
+    '0', '0', '6', '0', '0', '0', '6', '1', '0', '0', '6', '2', '0', '0', '6',
+    '3', '0', '0', '6', '4', '0', '0', '6', '5', '0', '0', '6', '6', '0', '0',
+    '6', '7', '0', '0', '6', '8', '0', '0', '6', '9', '0', '0', '7', '0', '0',
+    '0', '7', '1', '0', '0', '7', '2', '0', '0', '7', '3', '0', '0', '7', '4',
+    '0', '0', '7', '5', '0', '0', '7', '6', '0', '0', '7', '7', '0', '0', '7',
+    '8', '0', '0', '7', '9', '0', '0', '8', '0', '0', '0', '8', '1', '0', '0',
+    '8', '2', '0', '0', '8', '3', '0', '0', '8', '4', '0', '0', '8', '5', '0',
+    '0', '8', '6', '0', '0', '8', '7', '0', '0', '8', '8', '0', '0', '8', '9',
+    '0', '0', '9', '0', '0', '0', '9', '1', '0', '0', '9', '2', '0', '0', '9',
+    '3', '0', '0', '9', '4', '0', '0', '9', '5', '0', '0', '9', '6', '0', '0',
+    '9', '7', '0', '0', '9', '8', '0', '0', '9', '9', '0', '1', '0', '0', '0',
+    '1', '0', '1', '0', '1', '0', '2', '0', '1', '0', '3', '0', '1', '0', '4',
+    '0', '1', '0', '5', '0', '1', '0', '6', '0', '1', '0', '7', '0', '1', '0',
+    '8', '0', '1', '0', '9', '0', '1', '1', '0', '0', '1', '1', '1', '0', '1',
+    '1', '2', '0', '1', '1', '3', '0', '1', '1', '4', '0', '1', '1', '5', '0',
+    '1', '1', '6', '0', '1', '1', '7', '0', '1', '1', '8', '0', '1', '1', '9',
+    '0', '1', '2', '0', '0', '1', '2', '1', '0', '1', '2', '2', '0', '1', '2',
+    '3', '0', '1', '2', '4', '0', '1', '2', '5', '0', '1', '2', '6', '0', '1',
+    '2', '7', '0', '1', '2', '8', '0', '1', '2', '9', '0', '1', '3', '0', '0',
+    '1', '3', '1', '0', '1', '3', '2', '0', '1', '3', '3', '0', '1', '3', '4',
+    '0', '1', '3', '5', '0', '1', '3', '6', '0', '1', '3', '7', '0', '1', '3',
+    '8', '0', '1', '3', '9', '0', '1', '4', '0', '0', '1', '4', '1', '0', '1',
+    '4', '2', '0', '1', '4', '3', '0', '1', '4', '4', '0', '1', '4', '5', '0',
+    '1', '4', '6', '0', '1', '4', '7', '0', '1', '4', '8', '0', '1', '4', '9',
+    '0', '1', '5', '0', '0', '1', '5', '1', '0', '1', '5', '2', '0', '1', '5',
+    '3', '0', '1', '5', '4', '0', '1', '5', '5', '0', '1', '5', '6', '0', '1',
+    '5', '7', '0', '1', '5', '8', '0', '1', '5', '9', '0', '1', '6', '0', '0',
+    '1', '6', '1', '0', '1', '6', '2', '0', '1', '6', '3', '0', '1', '6', '4',
+    '0', '1', '6', '5', '0', '1', '6', '6', '0', '1', '6', '7', '0', '1', '6',
+    '8', '0', '1', '6', '9', '0', '1', '7', '0', '0', '1', '7', '1', '0', '1',
+    '7', '2', '0', '1', '7', '3', '0', '1', '7', '4', '0', '1', '7', '5', '0',
+    '1', '7', '6', '0', '1', '7', '7', '0', '1', '7', '8', '0', '1', '7', '9',
+    '0', '1', '8', '0', '0', '1', '8', '1', '0', '1', '8', '2', '0', '1', '8',
+    '3', '0', '1', '8', '4', '0', '1', '8', '5', '0', '1', '8', '6', '0', '1',
+    '8', '7', '0', '1', '8', '8', '0', '1', '8', '9', '0', '1', '9', '0', '0',
+    '1', '9', '1', '0', '1', '9', '2', '0', '1', '9', '3', '0', '1', '9', '4',
+    '0', '1', '9', '5', '0', '1', '9', '6', '0', '1', '9', '7', '0', '1', '9',
+    '8', '0', '1', '9', '9', '0', '2', '0', '0', '0', '2', '0', '1', '0', '2',
+    '0', '2', '0', '2', '0', '3', '0', '2', '0', '4', '0', '2', '0', '5', '0',
+    '2', '0', '6', '0', '2', '0', '7', '0', '2', '0', '8', '0', '2', '0', '9',
+    '0', '2', '1', '0', '0', '2', '1', '1', '0', '2', '1', '2', '0', '2', '1',
+    '3', '0', '2', '1', '4', '0', '2', '1', '5', '0', '2', '1', '6', '0', '2',
+    '1', '7', '0', '2', '1', '8', '0', '2', '1', '9', '0', '2', '2', '0', '0',
+    '2', '2', '1', '0', '2', '2', '2', '0', '2', '2', '3', '0', '2', '2', '4',
+    '0', '2', '2', '5', '0', '2', '2', '6', '0', '2', '2', '7', '0', '2', '2',
+    '8', '0', '2', '2', '9', '0', '2', '3', '0', '0', '2', '3', '1', '0', '2',
+    '3', '2', '0', '2', '3', '3', '0', '2', '3', '4', '0', '2', '3', '5', '0',
+    '2', '3', '6', '0', '2', '3', '7', '0', '2', '3', '8', '0', '2', '3', '9',
+    '0', '2', '4', '0', '0', '2', '4', '1', '0', '2', '4', '2', '0', '2', '4',
+    '3', '0', '2', '4', '4', '0', '2', '4', '5', '0', '2', '4', '6', '0', '2',
+    '4', '7', '0', '2', '4', '8', '0', '2', '4', '9', '0', '2', '5', '0', '0',
+    '2', '5', '1', '0', '2', '5', '2', '0', '2', '5', '3', '0', '2', '5', '4',
+    '0', '2', '5', '5', '0', '2', '5', '6', '0', '2', '5', '7', '0', '2', '5',
+    '8', '0', '2', '5', '9', '0', '2', '6', '0', '0', '2', '6', '1', '0', '2',
+    '6', '2', '0', '2', '6', '3', '0', '2', '6', '4', '0', '2', '6', '5', '0',
+    '2', '6', '6', '0', '2', '6', '7', '0', '2', '6', '8', '0', '2', '6', '9',
+    '0', '2', '7', '0', '0', '2', '7', '1', '0', '2', '7', '2', '0', '2', '7',
+    '3', '0', '2', '7', '4', '0', '2', '7', '5', '0', '2', '7', '6', '0', '2',
+    '7', '7', '0', '2', '7', '8', '0', '2', '7', '9', '0', '2', '8', '0', '0',
+    '2', '8', '1', '0', '2', '8', '2', '0', '2', '8', '3', '0', '2', '8', '4',
+    '0', '2', '8', '5', '0', '2', '8', '6', '0', '2', '8', '7', '0', '2', '8',
+    '8', '0', '2', '8', '9', '0', '2', '9', '0', '0', '2', '9', '1', '0', '2',
+    '9', '2', '0', '2', '9', '3', '0', '2', '9', '4', '0', '2', '9', '5', '0',
+    '2', '9', '6', '0', '2', '9', '7', '0', '2', '9', '8', '0', '2', '9', '9',
+    '0', '3', '0', '0', '0', '3', '0', '1', '0', '3', '0', '2', '0', '3', '0',
+    '3', '0', '3', '0', '4', '0', '3', '0', '5', '0', '3', '0', '6', '0', '3',
+    '0', '7', '0', '3', '0', '8', '0', '3', '0', '9', '0', '3', '1', '0', '0',
+    '3', '1', '1', '0', '3', '1', '2', '0', '3', '1', '3', '0', '3', '1', '4',
+    '0', '3', '1', '5', '0', '3', '1', '6', '0', '3', '1', '7', '0', '3', '1',
+    '8', '0', '3', '1', '9', '0', '3', '2', '0', '0', '3', '2', '1', '0', '3',
+    '2', '2', '0', '3', '2', '3', '0', '3', '2', '4', '0', '3', '2', '5', '0',
+    '3', '2', '6', '0', '3', '2', '7', '0', '3', '2', '8', '0', '3', '2', '9',
+    '0', '3', '3', '0', '0', '3', '3', '1', '0', '3', '3', '2', '0', '3', '3',
+    '3', '0', '3', '3', '4', '0', '3', '3', '5', '0', '3', '3', '6', '0', '3',
+    '3', '7', '0', '3', '3', '8', '0', '3', '3', '9', '0', '3', '4', '0', '0',
+    '3', '4', '1', '0', '3', '4', '2', '0', '3', '4', '3', '0', '3', '4', '4',
+    '0', '3', '4', '5', '0', '3', '4', '6', '0', '3', '4', '7', '0', '3', '4',
+    '8', '0', '3', '4', '9', '0', '3', '5', '0', '0', '3', '5', '1', '0', '3',
+    '5', '2', '0', '3', '5', '3', '0', '3', '5', '4', '0', '3', '5', '5', '0',
+    '3', '5', '6', '0', '3', '5', '7', '0', '3', '5', '8', '0', '3', '5', '9',
+    '0', '3', '6', '0', '0', '3', '6', '1', '0', '3', '6', '2', '0', '3', '6',
+    '3', '0', '3', '6', '4', '0', '3', '6', '5', '0', '3', '6', '6', '0', '3',
+    '6', '7', '0', '3', '6', '8', '0', '3', '6', '9', '0', '3', '7', '0', '0',
+    '3', '7', '1', '0', '3', '7', '2', '0', '3', '7', '3', '0', '3', '7', '4',
+    '0', '3', '7', '5', '0', '3', '7', '6', '0', '3', '7', '7', '0', '3', '7',
+    '8', '0', '3', '7', '9', '0', '3', '8', '0', '0', '3', '8', '1', '0', '3',
+    '8', '2', '0', '3', '8', '3', '0', '3', '8', '4', '0', '3', '8', '5', '0',
+    '3', '8', '6', '0', '3', '8', '7', '0', '3', '8', '8', '0', '3', '8', '9',
+    '0', '3', '9', '0', '0', '3', '9', '1', '0', '3', '9', '2', '0', '3', '9',
+    '3', '0', '3', '9', '4', '0', '3', '9', '5', '0', '3', '9', '6', '0', '3',
+    '9', '7', '0', '3', '9', '8', '0', '3', '9', '9', '0', '4', '0', '0', '0',
+    '4', '0', '1', '0', '4', '0', '2', '0', '4', '0', '3', '0', '4', '0', '4',
+    '0', '4', '0', '5', '0', '4', '0', '6', '0', '4', '0', '7', '0', '4', '0',
+    '8', '0', '4', '0', '9', '0', '4', '1', '0', '0', '4', '1', '1', '0', '4',
+    '1', '2', '0', '4', '1', '3', '0', '4', '1', '4', '0', '4', '1', '5', '0',
+    '4', '1', '6', '0', '4', '1', '7', '0', '4', '1', '8', '0', '4', '1', '9',
+    '0', '4', '2', '0', '0', '4', '2', '1', '0', '4', '2', '2', '0', '4', '2',
+    '3', '0', '4', '2', '4', '0', '4', '2', '5', '0', '4', '2', '6', '0', '4',
+    '2', '7', '0', '4', '2', '8', '0', '4', '2', '9', '0', '4', '3', '0', '0',
+    '4', '3', '1', '0', '4', '3', '2', '0', '4', '3', '3', '0', '4', '3', '4',
+    '0', '4', '3', '5', '0', '4', '3', '6', '0', '4', '3', '7', '0', '4', '3',
+    '8', '0', '4', '3', '9', '0', '4', '4', '0', '0', '4', '4', '1', '0', '4',
+    '4', '2', '0', '4', '4', '3', '0', '4', '4', '4', '0', '4', '4', '5', '0',
+    '4', '4', '6', '0', '4', '4', '7', '0', '4', '4', '8', '0', '4', '4', '9',
+    '0', '4', '5', '0', '0', '4', '5', '1', '0', '4', '5', '2', '0', '4', '5',
+    '3', '0', '4', '5', '4', '0', '4', '5', '5', '0', '4', '5', '6', '0', '4',
+    '5', '7', '0', '4', '5', '8', '0', '4', '5', '9', '0', '4', '6', '0', '0',
+    '4', '6', '1', '0', '4', '6', '2', '0', '4', '6', '3', '0', '4', '6', '4',
+    '0', '4', '6', '5', '0', '4', '6', '6', '0', '4', '6', '7', '0', '4', '6',
+    '8', '0', '4', '6', '9', '0', '4', '7', '0', '0', '4', '7', '1', '0', '4',
+    '7', '2', '0', '4', '7', '3', '0', '4', '7', '4', '0', '4', '7', '5', '0',
+    '4', '7', '6', '0', '4', '7', '7', '0', '4', '7', '8', '0', '4', '7', '9',
+    '0', '4', '8', '0', '0', '4', '8', '1', '0', '4', '8', '2', '0', '4', '8',
+    '3', '0', '4', '8', '4', '0', '4', '8', '5', '0', '4', '8', '6', '0', '4',
+    '8', '7', '0', '4', '8', '8', '0', '4', '8', '9', '0', '4', '9', '0', '0',
+    '4', '9', '1', '0', '4', '9', '2', '0', '4', '9', '3', '0', '4', '9', '4',
+    '0', '4', '9', '5', '0', '4', '9', '6', '0', '4', '9', '7', '0', '4', '9',
+    '8', '0', '4', '9', '9', '0', '5', '0', '0', '0', '5', '0', '1', '0', '5',
+    '0', '2', '0', '5', '0', '3', '0', '5', '0', '4', '0', '5', '0', '5', '0',
+    '5', '0', '6', '0', '5', '0', '7', '0', '5', '0', '8', '0', '5', '0', '9',
+    '0', '5', '1', '0', '0', '5', '1', '1', '0', '5', '1', '2', '0', '5', '1',
+    '3', '0', '5', '1', '4', '0', '5', '1', '5', '0', '5', '1', '6', '0', '5',
+    '1', '7', '0', '5', '1', '8', '0', '5', '1', '9', '0', '5', '2', '0', '0',
+    '5', '2', '1', '0', '5', '2', '2', '0', '5', '2', '3', '0', '5', '2', '4',
+    '0', '5', '2', '5', '0', '5', '2', '6', '0', '5', '2', '7', '0', '5', '2',
+    '8', '0', '5', '2', '9', '0', '5', '3', '0', '0', '5', '3', '1', '0', '5',
+    '3', '2', '0', '5', '3', '3', '0', '5', '3', '4', '0', '5', '3', '5', '0',
+    '5', '3', '6', '0', '5', '3', '7', '0', '5', '3', '8', '0', '5', '3', '9',
+    '0', '5', '4', '0', '0', '5', '4', '1', '0', '5', '4', '2', '0', '5', '4',
+    '3', '0', '5', '4', '4', '0', '5', '4', '5', '0', '5', '4', '6', '0', '5',
+    '4', '7', '0', '5', '4', '8', '0', '5', '4', '9', '0', '5', '5', '0', '0',
+    '5', '5', '1', '0', '5', '5', '2', '0', '5', '5', '3', '0', '5', '5', '4',
+    '0', '5', '5', '5', '0', '5', '5', '6', '0', '5', '5', '7', '0', '5', '5',
+    '8', '0', '5', '5', '9', '0', '5', '6', '0', '0', '5', '6', '1', '0', '5',
+    '6', '2', '0', '5', '6', '3', '0', '5', '6', '4', '0', '5', '6', '5', '0',
+    '5', '6', '6', '0', '5', '6', '7', '0', '5', '6', '8', '0', '5', '6', '9',
+    '0', '5', '7', '0', '0', '5', '7', '1', '0', '5', '7', '2', '0', '5', '7',
+    '3', '0', '5', '7', '4', '0', '5', '7', '5', '0', '5', '7', '6', '0', '5',
+    '7', '7', '0', '5', '7', '8', '0', '5', '7', '9', '0', '5', '8', '0', '0',
+    '5', '8', '1', '0', '5', '8', '2', '0', '5', '8', '3', '0', '5', '8', '4',
+    '0', '5', '8', '5', '0', '5', '8', '6', '0', '5', '8', '7', '0', '5', '8',
+    '8', '0', '5', '8', '9', '0', '5', '9', '0', '0', '5', '9', '1', '0', '5',
+    '9', '2', '0', '5', '9', '3', '0', '5', '9', '4', '0', '5', '9', '5', '0',
+    '5', '9', '6', '0', '5', '9', '7', '0', '5', '9', '8', '0', '5', '9', '9',
+    '0', '6', '0', '0', '0', '6', '0', '1', '0', '6', '0', '2', '0', '6', '0',
+    '3', '0', '6', '0', '4', '0', '6', '0', '5', '0', '6', '0', '6', '0', '6',
+    '0', '7', '0', '6', '0', '8', '0', '6', '0', '9', '0', '6', '1', '0', '0',
+    '6', '1', '1', '0', '6', '1', '2', '0', '6', '1', '3', '0', '6', '1', '4',
+    '0', '6', '1', '5', '0', '6', '1', '6', '0', '6', '1', '7', '0', '6', '1',
+    '8', '0', '6', '1', '9', '0', '6', '2', '0', '0', '6', '2', '1', '0', '6',
+    '2', '2', '0', '6', '2', '3', '0', '6', '2', '4', '0', '6', '2', '5', '0',
+    '6', '2', '6', '0', '6', '2', '7', '0', '6', '2', '8', '0', '6', '2', '9',
+    '0', '6', '3', '0', '0', '6', '3', '1', '0', '6', '3', '2', '0', '6', '3',
+    '3', '0', '6', '3', '4', '0', '6', '3', '5', '0', '6', '3', '6', '0', '6',
+    '3', '7', '0', '6', '3', '8', '0', '6', '3', '9', '0', '6', '4', '0', '0',
+    '6', '4', '1', '0', '6', '4', '2', '0', '6', '4', '3', '0', '6', '4', '4',
+    '0', '6', '4', '5', '0', '6', '4', '6', '0', '6', '4', '7', '0', '6', '4',
+    '8', '0', '6', '4', '9', '0', '6', '5', '0', '0', '6', '5', '1', '0', '6',
+    '5', '2', '0', '6', '5', '3', '0', '6', '5', '4', '0', '6', '5', '5', '0',
+    '6', '5', '6', '0', '6', '5', '7', '0', '6', '5', '8', '0', '6', '5', '9',
+    '0', '6', '6', '0', '0', '6', '6', '1', '0', '6', '6', '2', '0', '6', '6',
+    '3', '0', '6', '6', '4', '0', '6', '6', '5', '0', '6', '6', '6', '0', '6',
+    '6', '7', '0', '6', '6', '8', '0', '6', '6', '9', '0', '6', '7', '0', '0',
+    '6', '7', '1', '0', '6', '7', '2', '0', '6', '7', '3', '0', '6', '7', '4',
+    '0', '6', '7', '5', '0', '6', '7', '6', '0', '6', '7', '7', '0', '6', '7',
+    '8', '0', '6', '7', '9', '0', '6', '8', '0', '0', '6', '8', '1', '0', '6',
+    '8', '2', '0', '6', '8', '3', '0', '6', '8', '4', '0', '6', '8', '5', '0',
+    '6', '8', '6', '0', '6', '8', '7', '0', '6', '8', '8', '0', '6', '8', '9',
+    '0', '6', '9', '0', '0', '6', '9', '1', '0', '6', '9', '2', '0', '6', '9',
+    '3', '0', '6', '9', '4', '0', '6', '9', '5', '0', '6', '9', '6', '0', '6',
+    '9', '7', '0', '6', '9', '8', '0', '6', '9', '9', '0', '7', '0', '0', '0',
+    '7', '0', '1', '0', '7', '0', '2', '0', '7', '0', '3', '0', '7', '0', '4',
+    '0', '7', '0', '5', '0', '7', '0', '6', '0', '7', '0', '7', '0', '7', '0',
+    '8', '0', '7', '0', '9', '0', '7', '1', '0', '0', '7', '1', '1', '0', '7',
+    '1', '2', '0', '7', '1', '3', '0', '7', '1', '4', '0', '7', '1', '5', '0',
+    '7', '1', '6', '0', '7', '1', '7', '0', '7', '1', '8', '0', '7', '1', '9',
+    '0', '7', '2', '0', '0', '7', '2', '1', '0', '7', '2', '2', '0', '7', '2',
+    '3', '0', '7', '2', '4', '0', '7', '2', '5', '0', '7', '2', '6', '0', '7',
+    '2', '7', '0', '7', '2', '8', '0', '7', '2', '9', '0', '7', '3', '0', '0',
+    '7', '3', '1', '0', '7', '3', '2', '0', '7', '3', '3', '0', '7', '3', '4',
+    '0', '7', '3', '5', '0', '7', '3', '6', '0', '7', '3', '7', '0', '7', '3',
+    '8', '0', '7', '3', '9', '0', '7', '4', '0', '0', '7', '4', '1', '0', '7',
+    '4', '2', '0', '7', '4', '3', '0', '7', '4', '4', '0', '7', '4', '5', '0',
+    '7', '4', '6', '0', '7', '4', '7', '0', '7', '4', '8', '0', '7', '4', '9',
+    '0', '7', '5', '0', '0', '7', '5', '1', '0', '7', '5', '2', '0', '7', '5',
+    '3', '0', '7', '5', '4', '0', '7', '5', '5', '0', '7', '5', '6', '0', '7',
+    '5', '7', '0', '7', '5', '8', '0', '7', '5', '9', '0', '7', '6', '0', '0',
+    '7', '6', '1', '0', '7', '6', '2', '0', '7', '6', '3', '0', '7', '6', '4',
+    '0', '7', '6', '5', '0', '7', '6', '6', '0', '7', '6', '7', '0', '7', '6',
+    '8', '0', '7', '6', '9', '0', '7', '7', '0', '0', '7', '7', '1', '0', '7',
+    '7', '2', '0', '7', '7', '3', '0', '7', '7', '4', '0', '7', '7', '5', '0',
+    '7', '7', '6', '0', '7', '7', '7', '0', '7', '7', '8', '0', '7', '7', '9',
+    '0', '7', '8', '0', '0', '7', '8', '1', '0', '7', '8', '2', '0', '7', '8',
+    '3', '0', '7', '8', '4', '0', '7', '8', '5', '0', '7', '8', '6', '0', '7',
+    '8', '7', '0', '7', '8', '8', '0', '7', '8', '9', '0', '7', '9', '0', '0',
+    '7', '9', '1', '0', '7', '9', '2', '0', '7', '9', '3', '0', '7', '9', '4',
+    '0', '7', '9', '5', '0', '7', '9', '6', '0', '7', '9', '7', '0', '7', '9',
+    '8', '0', '7', '9', '9', '0', '8', '0', '0', '0', '8', '0', '1', '0', '8',
+    '0', '2', '0', '8', '0', '3', '0', '8', '0', '4', '0', '8', '0', '5', '0',
+    '8', '0', '6', '0', '8', '0', '7', '0', '8', '0', '8', '0', '8', '0', '9',
+    '0', '8', '1', '0', '0', '8', '1', '1', '0', '8', '1', '2', '0', '8', '1',
+    '3', '0', '8', '1', '4', '0', '8', '1', '5', '0', '8', '1', '6', '0', '8',
+    '1', '7', '0', '8', '1', '8', '0', '8', '1', '9', '0', '8', '2', '0', '0',
+    '8', '2', '1', '0', '8', '2', '2', '0', '8', '2', '3', '0', '8', '2', '4',
+    '0', '8', '2', '5', '0', '8', '2', '6', '0', '8', '2', '7', '0', '8', '2',
+    '8', '0', '8', '2', '9', '0', '8', '3', '0', '0', '8', '3', '1', '0', '8',
+    '3', '2', '0', '8', '3', '3', '0', '8', '3', '4', '0', '8', '3', '5', '0',
+    '8', '3', '6', '0', '8', '3', '7', '0', '8', '3', '8', '0', '8', '3', '9',
+    '0', '8', '4', '0', '0', '8', '4', '1', '0', '8', '4', '2', '0', '8', '4',
+    '3', '0', '8', '4', '4', '0', '8', '4', '5', '0', '8', '4', '6', '0', '8',
+    '4', '7', '0', '8', '4', '8', '0', '8', '4', '9', '0', '8', '5', '0', '0',
+    '8', '5', '1', '0', '8', '5', '2', '0', '8', '5', '3', '0', '8', '5', '4',
+    '0', '8', '5', '5', '0', '8', '5', '6', '0', '8', '5', '7', '0', '8', '5',
+    '8', '0', '8', '5', '9', '0', '8', '6', '0', '0', '8', '6', '1', '0', '8',
+    '6', '2', '0', '8', '6', '3', '0', '8', '6', '4', '0', '8', '6', '5', '0',
+    '8', '6', '6', '0', '8', '6', '7', '0', '8', '6', '8', '0', '8', '6', '9',
+    '0', '8', '7', '0', '0', '8', '7', '1', '0', '8', '7', '2', '0', '8', '7',
+    '3', '0', '8', '7', '4', '0', '8', '7', '5', '0', '8', '7', '6', '0', '8',
+    '7', '7', '0', '8', '7', '8', '0', '8', '7', '9', '0', '8', '8', '0', '0',
+    '8', '8', '1', '0', '8', '8', '2', '0', '8', '8', '3', '0', '8', '8', '4',
+    '0', '8', '8', '5', '0', '8', '8', '6', '0', '8', '8', '7', '0', '8', '8',
+    '8', '0', '8', '8', '9', '0', '8', '9', '0', '0', '8', '9', '1', '0', '8',
+    '9', '2', '0', '8', '9', '3', '0', '8', '9', '4', '0', '8', '9', '5', '0',
+    '8', '9', '6', '0', '8', '9', '7', '0', '8', '9', '8', '0', '8', '9', '9',
+    '0', '9', '0', '0', '0', '9', '0', '1', '0', '9', '0', '2', '0', '9', '0',
+    '3', '0', '9', '0', '4', '0', '9', '0', '5', '0', '9', '0', '6', '0', '9',
+    '0', '7', '0', '9', '0', '8', '0', '9', '0', '9', '0', '9', '1', '0', '0',
+    '9', '1', '1', '0', '9', '1', '2', '0', '9', '1', '3', '0', '9', '1', '4',
+    '0', '9', '1', '5', '0', '9', '1', '6', '0', '9', '1', '7', '0', '9', '1',
+    '8', '0', '9', '1', '9', '0', '9', '2', '0', '0', '9', '2', '1', '0', '9',
+    '2', '2', '0', '9', '2', '3', '0', '9', '2', '4', '0', '9', '2', '5', '0',
+    '9', '2', '6', '0', '9', '2', '7', '0', '9', '2', '8', '0', '9', '2', '9',
+    '0', '9', '3', '0', '0', '9', '3', '1', '0', '9', '3', '2', '0', '9', '3',
+    '3', '0', '9', '3', '4', '0', '9', '3', '5', '0', '9', '3', '6', '0', '9',
+    '3', '7', '0', '9', '3', '8', '0', '9', '3', '9', '0', '9', '4', '0', '0',
+    '9', '4', '1', '0', '9', '4', '2', '0', '9', '4', '3', '0', '9', '4', '4',
+    '0', '9', '4', '5', '0', '9', '4', '6', '0', '9', '4', '7', '0', '9', '4',
+    '8', '0', '9', '4', '9', '0', '9', '5', '0', '0', '9', '5', '1', '0', '9',
+    '5', '2', '0', '9', '5', '3', '0', '9', '5', '4', '0', '9', '5', '5', '0',
+    '9', '5', '6', '0', '9', '5', '7', '0', '9', '5', '8', '0', '9', '5', '9',
+    '0', '9', '6', '0', '0', '9', '6', '1', '0', '9', '6', '2', '0', '9', '6',
+    '3', '0', '9', '6', '4', '0', '9', '6', '5', '0', '9', '6', '6', '0', '9',
+    '6', '7', '0', '9', '6', '8', '0', '9', '6', '9', '0', '9', '7', '0', '0',
+    '9', '7', '1', '0', '9', '7', '2', '0', '9', '7', '3', '0', '9', '7', '4',
+    '0', '9', '7', '5', '0', '9', '7', '6', '0', '9', '7', '7', '0', '9', '7',
+    '8', '0', '9', '7', '9', '0', '9', '8', '0', '0', '9', '8', '1', '0', '9',
+    '8', '2', '0', '9', '8', '3', '0', '9', '8', '4', '0', '9', '8', '5', '0',
+    '9', '8', '6', '0', '9', '8', '7', '0', '9', '8', '8', '0', '9', '8', '9',
+    '0', '9', '9', '0', '0', '9', '9', '1', '0', '9', '9', '2', '0', '9', '9',
+    '3', '0', '9', '9', '4', '0', '9', '9', '5', '0', '9', '9', '6', '0', '9',
+    '9', '7', '0', '9', '9', '8', '0', '9', '9', '9'};

diff --git a/src/DoubleToString.hh b/src/DoubleToString.hh
new file mode 100644 (file)
index 0000000..b0da446
--- /dev/null
+++ b/src/DoubleToString.hh
@@ -0,0 +1,4 @@
+#pragma once
+
+char* formatDouble(double d, char* p);
+extern const char digits[4000];

diff --git a/src/GCode.cc b/src/GCode.cc
new file mode 100644 (file)
index 0000000..064107e
--- /dev/null
+++ b/src/GCode.cc
@@ -0,0 +1,408 @@
+#include "GCode.hh"
+
+#include <algorithm>
+#include <cmath>
+
+#include "Configurations.hh"
+using namespace std;
+
+Gcode::Gcode(Layer& layer)
+    : loops(layer.getLoops()),
+      commands(layer.getCommands()),
+      parts(layer.getParts()),
+      minX(layer.getMinX()),
+      maxX(layer.getMaxX())
+{
+    if (loops.empty()) return;
+    int reserveSize = 0;
+    for (const auto& lp : loops)
+        reserveSize += lp.size() + int((lp.getmaxX() - lp.getminX()) / dp) * 2;
+    commands.reserve(reserveSize);
+    G0_high(layer.getZ());
+    // outline();
+    // fill();
+    doLoops();
+    layer.generateDe();
+}
+
+void Gcode::G0(double x, double y, double z)
+{
+    commands.push_back(Command(0, x, y));
+    // f << "G0 F6600 X" << x << " Y" << y << " Z" << z << '\n';
+    // f.flush();
+}
+void Gcode::G0(double x, double y)
+{
+    commands.push_back(Command(0, x, y));
+    // f << "G0 F6600 X" << x << " Y" << y << '\n';
+    // f.flush();
+}
+void Gcode::G0_high(double z)
+{
+    // f << "G0 F6600  Z" << z << '\n';
+    // f.flush();
+}
+void Gcode::G1(double x, double y)
+{
+    commands.push_back(Command(1, x, y));
+    // f << "G1 F783 X" << x << " Y" << y << " E" << e << '\n';
+    // f.flush();
+}
+void Gcode::resetE()
+{  // Reset E to 0
+    // f << "G92 E0 ; reset the expected extruder position\n";
+    // f.flush();
+}
+
+static double x = 0, y = 0;
+
+void Gcode::doLoops()
+{
+#if 0  // by erasing the finished loop
+       while(!loops.empty()){
+               double minDistance = pow(loops.front().midX - x, 2) + pow(loops.front().midY - y, 2);
+               int k = 0;
+               double distance;
+               for(int i = 1; i < loops.size(); i++){
+                       distance = pow(loops[i].midX - x, 2) + pow(loops[i].midY - y, 2);
+                       if(distance < minDistance){
+                               minDistance = distance;
+                               k = i;
+                       }
+               }
+               fillLoop(loops[k]);
+               x = commands.back().x;
+               y = commands.back().y;
+               loops.erase(loops.begin() + k);
+       }
+#endif
+#if 1  // by checking the visited value
+    int numLoop = loops.size();
+    while (numLoop)
+    {
+        int i = 0, k = 0;
+        double minDistance, distance;
+        while (loops[i].visited) i++;
+        minDistance = pow(loops[i].midX - x, 2) + pow(loops[i].midY - y, 2);
+        k           = i;
+        for (i++; i < loops.size(); i++)
+        {
+            if (loops[i].visited) continue;
+            distance = pow(loops[i].midX - x, 2) + pow(loops[i].midY - y, 2);
+            if (distance < minDistance)
+            {
+                minDistance = distance;
+                k           = i;
+            }
+        }
+        fillLoop(loops[k]);
+        loops[k].visited = true;  // mark as filled loop
+        x                = commands.back().x;
+        y                = commands.back().y;
+        numLoop--;
+    }
+#endif
+}
+
+void Gcode::fillLoop(Loop& loop)
+{
+    vector<Loop> ploops;
+    ploops.push_back(loop);
+    int numIntersectionsTotal = loop.size();
+    for (auto& plp : loop.subLoops)
+    {
+        ploops.push_back(plp);
+        numIntersectionsTotal += plp.size();
+    }
+
+    // outline
+    double x1, y1, x2, y2;
+
+    int numLoop = ploops.size();
+    while (numLoop)
+    {
+        int i = 0, k = 0;
+        double minDistance, distance;
+        while (ploops[i].visited) i++;
+        minDistance = pow(ploops[i].midX - x, 2) + pow(ploops[i].midY - y, 2);
+        k           = i;
+        for (i++; i < ploops.size(); i++)
+        {
+            if (ploops[i].visited) continue;
+            distance = pow(ploops[i].midX - x, 2) + pow(ploops[i].midY - y, 2);
+            if (distance < minDistance)
+            {
+                minDistance = distance;
+                k           = i;
+            }
+        }
+        // start to print this loop's outline
+        x1 = ploops[k].back().x;
+        y1 = ploops[k].back().y;
+        G0(x1, y1);
+        for (int i = 0; i < ploops[k].size(); i++)
+        {
+            x2 = ploops[k].at(i).x;
+            y2 = ploops[k].at(i).y;
+            G1(x2, y2);
+            x1 = x2, y1 = y2;
+        }
+        ploops[k].visited = true;
+        x                 = commands.back().x;
+        y                 = commands.back().y;
+        numLoop--;
+    }
+    /*
+    for (auto& lp : ploops) {
+            x1 = lp.back().x;
+            y1 = lp.back().y;
+            G0(x1, y1);
+            for (int i = 0; i < lp.size(); i++) {
+                    x2 = lp.at(i).x;
+                    y2 = lp.at(i).y;
+                    G1(x2, y2);
+                    x1 = x2, y1 = y2;
+            }
+    }
+    */
+
+    // fill
+    vector<vector<Cross>> pparts;
+    double invDp = 1.0 / dp;
+    numParts     = (loop.getmaxX() - loop.getminX()) * dp + 1;
+    pparts.reserve(numParts);
+    int meanIntersectionsPerPart = numIntersectionsTotal / numParts * 1.5;
+    for (int i = 0; i < numParts; i++)
+    {
+        pparts.push_back(vector<Cross>());
+        pparts.back().reserve(meanIntersectionsPerPart);
+    }
+    for (const auto& lp : ploops)
+    {  // assign all intersections to partial
+        Vec2d v1, v2(lp.back());
+        int index1, index2 = (v2.x - loop.getminX()) * invDp;
+        int imin, imax;
+
+        for (auto& l : lp.head)
+        {
+            v1     = v2;
+            index1 = index2;
+            v2     = l;
+            index2 = (v2.x - loop.getminX()) * invDp;
+            if (index1 < index2)
+            {
+                imin = index1;
+                imax = index2;
+            }
+            else
+            {
+                imin = index2;
+                imax = index1;
+            }
+            for (int i = imin; i <= imax; i++)
+                pparts[i].push_back(Cross(v1, v2));
+        }
+    }
+
+    vector<double> ys;
+    bool isUp = true;
+    for (double x = loop.getminX() + ingap; x < loop.getmaxX(); x += ingap)
+    {
+        ys.clear();
+        double y1, y2;
+        for (auto& cr : pparts.at((x - loop.getminX()) * invDp))
+        {
+            double x1 = cr.p1.x, y1 = cr.p1.y;
+            double x2 = cr.p2.x, y2 = cr.p2.y;
+            if ((x1 <= x && x < x2) || (x2 <= x && x < x1))
+                ys.push_back((x - x1) * (y2 - y1) / (x2 - x1) + y1);
+        }
+        std::sort(ys.begin(), ys.end());
+        if (ys.size() == 0) continue;
+
+        if (isUp)
+        {
+            y1 = ys.at(0);
+            G0(x, y1);
+            bool isE = true;
+            for (int i = 1; i < ys.size(); i++)
+            {
+                y2 = ys.at(i);
+                if (isE)
+                {
+                    G1(x, y2);
+                    isE = false;
+                }
+                else
+                {
+                    G0(x, y2);
+                    y1  = y2;
+                    isE = true;
+                }
+            }
+            isUp = false;
+        }
+        else
+        {
+            y1 = ys.at(ys.size() - 1);
+            G0(x, y1);
+            bool isE = true;
+            for (int i = ys.size() - 2; i >= 0; i--)
+            {
+                y2 = ys.at(i);
+                if (isE)
+                {
+                    G1(x, y2);
+                    isE = false;
+                }
+                else
+                {
+                    G0(x, y2);
+                    y1  = y2;
+                    isE = true;
+                }
+            }
+            isUp = true;
+        }
+    }
+}
+
+void Gcode::outline()
+{
+    double x1, y1, x2, y2;
+    for (auto& lp : loops)
+    {
+        x1 = lp.back().x;
+        y1 = lp.back().y;
+        G0(x1, y1);
+        for (int i = 0; i < lp.size(); i++)
+        {
+            x2 = lp.at(i).x;
+            y2 = lp.at(i).y;
+            G1(x2, y2);
+            x1 = x2, y1 = y2;
+        }
+    }
+}
+
+void Gcode::fill()
+{
+    double invDp              = 1.0 / dp;
+    minX                      = loops.front().getminX();
+    maxX                      = loops.front().getmaxX();
+    int numIntersectionsTotal = loops.front().size();
+    for (int i = 1; i < loops.size(); i++)
+    {
+        numIntersectionsTotal += loops.at(i).size();
+        if (minX > loops.at(i).getminX()) minX = loops.at(i).getminX();
+        if (maxX < loops.at(i).getmaxX()) maxX = loops.at(i).getmaxX();
+    }
+    numParts = (maxX - minX) * dp + 1;
+    parts.reserve(numParts);
+    int meanIntersectionsPerPart = numIntersectionsTotal / numParts * 1.5;
+    for (int i = 0; i < numParts; i++)
+    {
+        parts.push_back(std::vector<Cross>());
+        parts.back().reserve(meanIntersectionsPerPart);
+    }
+    for (const auto& lp : loops)
+    {  // assign all intersections to partial
+        Vec2d v1(lp.back());
+        Vec2d v2(lp.front());
+        int index1 = (v1.x - minX) * invDp;
+        int index2 = (v2.x - minX) * invDp;
+        int imin, imax;
+        if (index1 < index2)
+        {
+            imin = index1;
+            imax = index2;
+        }
+        else
+        {
+            imin = index2;
+            imax = index1;
+        }
+        for (int i = imin; i <= imax; i++) parts[i].push_back(Cross(v1, v2));
+
+        for (int i = 1; i < lp.size(); i++)
+        {  // from the front to the item before the back
+            v1     = v2;
+            index1 = index2;
+            v2     = lp.at(i);
+            index2 = (v2.x - minX) * invDp;
+            if (index1 < index2)
+            {
+                imin = index1;
+                imax = index2;
+            }
+            else
+            {
+                imin = index2;
+                imax = index1;
+            }
+            for (int i = imin; i <= imax; i++)
+                parts[i].push_back(Cross(v1, v2));
+        }
+    }
+    std::vector<double> ys;
+    bool isUp = true;
+    for (double x = minX + ingap; x < maxX; x += ingap)
+    {
+        ys.clear();
+        double y1, y2;
+        for (auto& cr : parts.at((x - minX) * invDp))
+        {
+            double x1 = cr.p1.x, y1 = cr.p1.y;
+            double x2 = cr.p2.x, y2 = cr.p2.y;
+            if ((x1 <= x && x < x2) || (x2 <= x && x < x1))
+                ys.push_back((x - x1) * (y2 - y1) / (x2 - x1) + y1);
+        }
+        std::sort(ys.begin(), ys.end());
+        if (ys.size() == 0) continue;
+
+        if (isUp)
+        {
+            y1 = ys.at(0);
+            G0(x, y1);
+            bool isE = true;
+            for (int i = 1; i < ys.size(); i++)
+            {
+                y2 = ys.at(i);
+                if (isE)
+                {
+                    G1(x, y2);
+                    isE = false;
+                }
+                else
+                {
+                    G0(x, y2);
+                    y1  = y2;
+                    isE = true;
+                }
+            }
+            isUp = false;
+        }
+        else
+        {
+            y1 = ys.at(ys.size() - 1);
+            G0(x, y1);
+            bool isE = true;
+            for (int i = ys.size() - 2; i >= 0; i--)
+            {
+                y2 = ys.at(i);
+                if (isE)
+                {
+                    G1(x, y2);
+                    isE = false;
+                }
+                else
+                {
+                    G0(x, y2);
+                    y1  = y2;
+                    isE = true;
+                }
+            }
+            isUp = true;
+        }
+    }
+}

diff --git a/src/GCode.hh b/src/GCode.hh
new file mode 100644 (file)
index 0000000..ac145f7
--- /dev/null
+++ b/src/GCode.hh
@@ -0,0 +1,37 @@
+#pragma once
+
+/*
+        @author: Xinqi Bao
+        After having loops for one layer, can use this class to generate the
+   gcode
+*/
+
+#include <vector>
+
+#include "Cross.hh"
+#include "Layer.hh"
+#include "Loop.hh"
+
+static double dp = 1;
+
+class Gcode
+{
+private:
+    int numParts;
+    double &minX, &maxX;
+    std::vector<Loop>& loops;
+    std::vector<Command>&
+        commands;  // contain each line of gcode, stored to layer
+    std::vector<std::vector<Cross>>& parts;
+    void G0(double x, double y, double z);
+    void G0(double x, double y);
+    void G0_high(double z);
+    void G1(double x, double y);
+    void resetE();
+    void outline();           // method before implement subLoops
+    void fill();              // method before implement subLoops
+    void doLoops();           //***method using implement subLoops***
+    void fillLoop(Loop& lp);  //***method using implement subLoops***
+public:
+    Gcode(Layer& layer);
+};

diff --git a/src/Layer.cc b/src/Layer.cc
new file mode 100644 (file)
index 0000000..7e715eb
--- /dev/null
+++ b/src/Layer.cc
@@ -0,0 +1,102 @@
+
+#include "Layer.hh"
+
+#include <cmath>
+
+#include "Configurations.hh"
+using namespace std;
+
+double Command::e = 0;
+void Command::G0_high(std::ostream& s, double z)
+{
+    s << "G0 F6600  Z" << z << '\n';
+}
+
+void Command::resetE(std::ostream& s)
+{
+    e = 0;
+    s << "G92 E0 ; reset the expected extruder position\n";
+}
+
+std::ostream& operator<<(std::ostream& s, const Command& c)
+{
+    switch (c.cmd)
+    {  // TODO: figure out the more efficient way, without switch!!
+    case 0:
+        return s << "G0 F6600 X" << c.x << " Y" << c.y << '\n';
+    case 1:
+        Command::e += c.de;
+        return s << "G1 F783 X" << c.x << " Y" << c.y << " E" << Command::e
+                 << '\n';
+    }
+}
+
+void Command::G0_high(BufferWrite& buf, double z)
+{
+    buf << "G0 F6600  Z" << z << '\n';
+}
+
+void Command::resetE(BufferWrite& buf)
+{
+    e = 0;
+    buf << "G92 E0 ; reset the expected extruder position\n";
+}
+
+BufferWrite& operator<<(BufferWrite& buf, const Command& c)
+{
+    switch (c.cmd)
+    {  // TODO: figure out the more efficient way, without switch!!
+    case 0:
+        buf.writeG0(c.x, c.y);
+        return buf;
+    case 1:
+        Command::e += c.de;
+        buf.writeG1(c.x, c.y, Command::e);
+        return buf;
+    }
+}
+
+Command::Command(uint16_t cmd, double x, double y) : cmd(cmd), x(x), y(y) {}
+
+Layer::Layer(double z) : z(z) {}
+
+double Layer::getZ() const { return z; }
+
+double& Layer::getMinX() { return minX; }
+
+double& Layer::getMaxX() { return maxX; }
+
+vector<Loop>& Layer::getLoops() { return loops; }
+
+vector<Command>& Layer::getCommands() { return commands; }
+
+vector<vector<Cross>>& Layer::getParts() { return parts; }
+
+void Layer::commandsOut(ostream& s) const
+{
+    Command::G0_high(s, z);
+    Command::resetE(s);
+    for (const auto& c : commands) s << c;
+    s.flush();
+}
+
+void Layer::commandsOut(BufferWrite& buf) const
+{
+    Command::G0_high(buf, z);
+    Command::resetE(buf);
+    for (const auto& c : commands) buf << c;
+    // buf.flush();
+}
+
+void Layer::generateDe()
+{
+    tx = commands.front().x;
+    ty = commands.front().y;
+    for (auto& tc : commands)
+    {
+        if (tc.cmd == 1)
+            tc.de = sqrt(pow(tc.x - tx, 2) + pow(tc.y - ty, 2)) * ef;
+        tx = tc.x;
+        ty = tc.y;
+    }
+}

diff --git a/src/Layer.hh b/src/Layer.hh
new file mode 100644 (file)
index 0000000..bc83171
--- /dev/null
+++ b/src/Layer.hh
@@ -0,0 +1,58 @@
+#pragma once
+#include <iostream>
+#include <vector>
+
+#include "BufferWrite.hh"
+#include "Cross.hh"
+#include "Loop.hh"
+
+class Command
+{
+public:
+    uint16_t cmd;
+    double x, y, de = 0;
+    Command(uint16_t cmd, double x, double y);
+    /*************************************************************************/
+    /*
+            part for to file directly
+    */
+    static double e;
+    static void G0_high(std::ostream& s, double z);
+    static void resetE(std::ostream& s);
+    friend std::ostream& operator<<(std::ostream& s, const Command& c);
+    /*************************************************************************/
+    /*************************************************************************/
+    /*
+            part for to writing buffer
+    */
+    static void G0_high(BufferWrite& buf, double z);
+    static void resetE(BufferWrite& buf);
+    friend BufferWrite& operator<<(BufferWrite& buf, const Command& c);
+    /*************************************************************************/
+};
+
+/*
+        Each sliced layer
+*/
+class Layer
+{
+private:
+    double z;
+    double tx, ty;
+    double minX, maxX;
+    std::vector<Loop> loops;
+    std::vector<Command> commands;
+    std::vector<std::vector<Cross>> parts;
+
+public:
+    double getZ() const;
+    double& getMinX();
+    double& getMaxX();
+    std::vector<Loop>& getLoops();
+    std::vector<Command>& getCommands();
+    std::vector<std::vector<Cross>>& getParts();
+    void commandsOut(std::ostream& s) const;   // output to gcode file
+    void commandsOut(BufferWrite& buf) const;  // output to writing buffer
+    void generateDe();                         // Calculate how much to extrude
+    Layer(double z);
+};

diff --git a/src/Loop.cc b/src/Loop.cc
new file mode 100644 (file)
index 0000000..3485db7
--- /dev/null
+++ b/src/Loop.cc
@@ -0,0 +1,115 @@
+#include "Loop.hh"
+
+#include <cmath>
+#include <iostream>
+
+#include "Configurations.hh"
+using namespace std;
+
+Loop::Loop(Vec2d& p, uint32_t size = 10) : completed(false)
+{
+    head.reserve(size);
+    head.push_back(p);
+    minX = p.x, maxX = p.x;
+    minY = p.y, maxY = p.y;
+}
+
+bool Loop::isCompleted() const { return completed; }
+void Loop::add(double x, double y) { add(new Vec2d(x, y)); }
+void Loop::add(Vec2d* p) { add(*p); }
+void Loop::add(Vec2d& p)
+{
+    if (head.front().equal(p))
+    {  // Loop complete
+        completed = true;
+        midX      = (minX + maxX) / 2;
+        midY      = (minY + maxY) / 2;
+        return;
+    }
+    if (minX > p.x) minX = p.x;
+    if (maxX < p.x) maxX = p.x;
+    if (minY > p.y) minY = p.y;
+    if (maxY < p.y) maxY = p.y;
+    head.push_back(p);
+}
+int Loop::size() const { return head.size(); }
+const Vec2d& Loop::at(int i) const { return head.at(i % head.size()); }
+const Vec2d& Loop::front() const { return head.front(); }
+const Vec2d& Loop::back() const { return head.back(); }
+Vec2d& Loop::at(int i) { return head.at(i % head.size()); }
+Vec2d& Loop::front() { return head.front(); }
+Vec2d& Loop::back() { return head.back(); }
+double Loop::getminX() const { return minX; }
+double Loop::getmaxX() const { return maxX; }
+double Loop::getminY() const { return minY; }
+double Loop::getmaxY() const { return maxY; }
+double Loop::getXsum() const { return xsum; }
+double Loop::getYsum() const { return ysum; }
+void Loop::loopSum()
+{
+    for (const auto& v : head)
+    {
+        xsum += v.x;
+        ysum += v.y;
+    }
+}
+void Loop::optimize()
+{
+    if (head.size() < 4) return;
+    Vec2d p1(head.back());  // position at -1, 0, 1
+    Vec2d p2(head.front());
+    Vec2d p3(head.at(1));
+    if (fabs((p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y)) <
+        thr)
+        head.erase(head.begin());
+
+    for (int i = 0; i < head.size() - 2; i++)
+    {  // position form 0, 1, 2   to   end-2, end-1, end
+        p1 = head.at(i);
+        p2 = head.at(i + 1);
+        p3 = head.at(i + 2);
+        if (fabs((p2.x - p1.x) * (p3.y - p1.y) -
+                 (p3.x - p1.x) * (p2.y - p1.y)) < thr)
+        {  // in same line
+            head.erase(head.begin() + (i + 1));
+            i--;
+        }
+    }
+
+    p1 = head.at(head.size() - 2);  // position at -2, -1, 0
+    p2 = head.back();
+    p3 = head.front();
+    if (fabs((p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y)) <
+        thr)
+        head.pop_back();
+
+    for (auto& lp : subLoops) lp.optimize();
+}
+bool Loop::checkSubLoop(Loop& lp)
+{
+    if (lp.getminX() > minX && lp.getmaxX() < maxX && lp.getminY() > minY &&
+        lp.getmaxY() < maxY)
+    {
+        subLoops.push_back(lp);
+        for (auto& l : lp.subLoops)
+        {
+            subLoops.push_back(l);
+        }
+        lp.subLoops.clear();
+        return true;
+    }
+    return false;
+}
+void Loop::print() const
+{
+    if (head.size() == 0)
+    {
+        cout << "null\n";
+        return;
+    }
+    cout << head.at(0);
+    for (int i = 1; i < head.size(); i++)
+    {
+        cout << " --> " << head.at(i);
+    }
+}

diff --git a/src/Loop.hh b/src/Loop.hh
new file mode 100644 (file)
index 0000000..ec1222f
--- /dev/null
+++ b/src/Loop.hh
@@ -0,0 +1,46 @@
+#pragma once
+
+/*
+        @author: Xinqi Bao
+*/
+
+#include <vector>
+
+#include "Vec2d.hh"
+
+class Loop
+{
+private:
+    bool completed;
+    double minX, maxX, minY, maxY;
+    double xsum = 0, ysum = 0;
+
+public:
+    std::vector<Vec2d> head;
+    std::vector<Loop> subLoops;
+    double midX = 0, midY = 0;
+    bool visited = false;
+
+    Loop(Vec2d& p, uint32_t size);
+    bool isCompleted() const;
+    void add(double x, double y);
+    void add(Vec2d* p);
+    void add(Vec2d& p);
+    int size() const;
+    const Vec2d& at(int i) const;
+    const Vec2d& front() const;
+    const Vec2d& back() const;
+    Vec2d& at(int i);
+    Vec2d& front();
+    Vec2d& back();
+    double getminX() const;
+    double getmaxX() const;
+    double getminY() const;
+    double getmaxY() const;
+    double getXsum() const;
+    double getYsum() const;
+    void loopSum();
+    void optimize();
+    bool checkSubLoop(Loop& lp);
+    void print() const;
+};

diff --git a/src/STL.cc b/src/STL.cc
new file mode 100644 (file)
index 0000000..5515c84
--- /dev/null
+++ b/src/STL.cc
@@ -0,0 +1,205 @@
+#include "STL.hh"
+
+#include <fstream>
+
+#include "BufferReadBinary.hh"
+#include "Configurations.hh"
+using namespace std;
+
+Stl::Stl() {}  // Have to call the function read() later
+Stl::Stl(std::string& stl_target, bool isBinary)
+{
+    // TODO: if the stl file does not exist
+    read(stl_target, isBinary);
+}
+
+double Stl::getZmax() const { return zmax; }
+double Stl::getZmin() const { return zmin; }
+
+int Stl::read(string& stl_target, bool isBinary)
+{
+    // TODO: read for ASCII and binary
+    int numTriangles;
+    if (isBinary)
+        numTriangles = readBinary(stl_target);
+    else
+        numTriangles = readASCII(stl_target);
+    setMinAndMax();
+    if (needMoveToCenter) moveToCenter();
+    assignTriangles();
+    return numTriangles;
+}
+
+// see stl format for ASCII file
+int Stl::readASCII(string& fileTarget)
+{
+    ifstream f(fileTarget);
+    streampos pos = f.tellg();
+    f.seekg(0, ios_base::end);
+    int len = f.tellg();
+    f.seekg(pos);
+    triangles.reserve(len / 150);
+    /*char s[256];
+    while (f >> s) {
+            if (!strcmp(s,"facet")) {
+                    triangles.push_back(Triangle(f));
+            }
+    }*/                //old version for read stl
+    f.ignore(256, '\n');
+    while (f.peek() != 'e') triangles.push_back(Triangle(f));
+    f.close();
+    return triangles.size();
+}
+
+// see stl format for binary file
+// will much faster than read in by ASCII file
+// and using BufferReadBinary.o to reduce the I/O time
+int Stl::readBinary(string& fileTarget)
+{
+    BufferReadBinary buffer(fileTarget);
+    // a number in the stl file which means total number for triangles
+    uint32_t numTrianglesInFile = buffer.getNumTrianglesInFile();
+    triangles.reserve(numTrianglesInFile);
+    while (numTrianglesInFile)
+    {
+        int numTrianglesInBlock = buffer.getNumTrianglesInBlock();
+        numTrianglesInFile -= numTrianglesInBlock;
+        while (numTrianglesInBlock)
+        {
+            triangles.push_back(Triangle(buffer));
+            numTrianglesInBlock--;
+        }
+        buffer.readBuffer();
+    }
+    return triangles.size();
+}
+
+// By using more memory to speed up the program
+// After assign the triangles, no need to check triangles which is out of the
+// high range
+void Stl::assignTriangles()
+{
+    double invDz = 1.0 / dzEachLevel;
+    numLevels    = (zmax - zmin) * invDz + 1;
+    levels.reserve(numLevels);
+    int meanTrianglesPerLevel = triangles.size() / numLevels * 1.5;
+    for (int i = 0; i < numLevels; i++)
+    {
+        levels.push_back(vector<Triangle>());
+        levels.back().reserve(meanTrianglesPerLevel);
+    }
+    for (const auto& t : triangles)
+    {
+        double zmint, zmaxt;
+        if (t.v1.z < t.v2.z)
+        {
+            zmint = t.v1.z;
+            zmaxt = t.v2.z;
+        }
+        else
+        {
+            zmaxt = t.v1.z;
+            zmint = t.v2.z;
+        }
+        zmint = zmint < t.v3.z ? zmint : t.v3.z;
+        zmaxt = zmaxt > t.v3.z ? zmaxt : t.v3.z;
+        for (int slice = int((zmint - zmin) * invDz);
+             slice <= int((zmaxt - zmin) * invDz); slice++)
+            levels[slice].push_back(t);
+    }
+    triangles.clear();
+    // triangles.~vector();
+}
+
+// set the minimum and maximum of x, y and z, can be used by latter optimization
+void Stl::setMinAndMax()
+{
+    if (triangles.empty()) return;
+    xmin = xmax = triangles.front().v1.x;
+    ymin = ymax = triangles.front().v1.y;
+    zmin = zmax = triangles.front().v1.z;
+
+    for (const auto& t : triangles)
+    {
+        double xmint = t.v1.x, xmaxt = t.v1.x;
+        double ymint = t.v1.y, ymaxt = t.v1.y;
+        double zmint = t.v1.z, zmaxt = t.v1.z;
+
+        if (t.v2.x < xmint)
+            xmint = t.v2.x;
+        else
+            xmaxt = t.v2.x;
+        if (t.v3.x < xmint)
+            xmint = t.v3.x;
+        else if (t.v3.x > xmaxt)
+            xmaxt = t.v3.x;
+
+        if (t.v2.y < ymint)
+            ymint = t.v2.y;
+        else
+            ymaxt = t.v2.y;
+        if (t.v3.y < ymint)
+            ymint = t.v3.y;
+        else if (t.v3.y > ymaxt)
+            ymaxt = t.v3.y;
+
+        if (t.v2.z < zmint)
+            zmint = t.v2.z;
+        else
+            zmaxt = t.v2.z;
+        if (t.v3.z < zmint)
+            zmint = t.v3.z;
+        else if (t.v3.z > zmaxt)
+            zmaxt = t.v3.z;
+
+        if (xmint < xmin) xmin = xmint;
+        if (xmaxt > xmax) xmax = xmaxt;
+        if (ymint < ymin) ymin = ymint;
+        if (ymaxt > ymax) ymax = ymaxt;
+        if (zmint < zmin) zmin = zmint;
+        if (zmaxt > zmax) zmax = zmaxt;
+    }
+}
+
+// Sometime the model does not locate at a great position
+// By the setted center point of printer table, move the model to a nice place
+void Stl::moveToCenter()
+{
+    double mvX = centerX - (xmax + xmin) / 2;
+    double mvY = centerY - (ymax + ymin) / 2;
+    double mvZ = centerZ - zmin;
+
+    for (auto& t : triangles)
+    {
+        t.v1.x += mvX;
+        t.v1.y += mvY;
+        t.v1.z += mvZ;
+
+        t.v2.x += mvX;
+        t.v2.y += mvY;
+        t.v2.z += mvZ;
+
+        t.v3.x += mvX;
+        t.v3.y += mvY;
+        t.v3.z += mvZ;
+    }
+
+    xmin += mvX;
+    xmax += mvX;
+    ymin += mvY;
+    ymax += mvY;
+    zmin += mvZ;
+    zmax += mvZ;
+}
+
+vector<Triangle>& Stl::getLevel(double z)
+{
+    return levels.at(int(z - zmin) / dzEachLevel);
+}
+
+void Stl::printSTL()
+{  // need to comment "triangles.clear();" in assignTriangles function
+    cout << "number of triangles: " << triangles.size() << '\n';
+    for (int i = 0; i < triangles.size(); i++)
+        cout << "# " << i << " :\n" << triangles.at(i) << '\n';
+}

diff --git a/src/STL.hh b/src/STL.hh
new file mode 100644 (file)
index 0000000..1669438
--- /dev/null
+++ b/src/STL.hh
@@ -0,0 +1,42 @@
+#pragma once
+
+/*
+        @author: Xinqi Bao
+        For reading in stl file, both ASCII and binary.
+        In stl file, the model represented as many triangles.
+        Store every triangles and assign to several groups with a constant high,
+        then send to Slicing.o to slice to defferent layers.
+*/
+
+#include <unistd.h>
+
+#include <string>
+#include <vector>
+
+#include "Triangle.hh"
+
+class Stl
+{
+private:
+    int numLevels;
+    double xmin, xmax, ymin, ymax, zmin, zmax;
+    int readASCII(std::string& fileTarget);
+    int readBinary(std::string& fileTarget);
+    void assignTriangles();
+    void setMinAndMax();
+    void moveToCenter();
+
+public:
+    std::vector<Triangle> triangles;  // contain all the triangles
+    std::vector<std::vector<Triangle>>
+        levels;  // each element is a group of assigned triangles by a range of
+                 // high
+    double getZmax() const;
+    double getZmin() const;
+    std::vector<Triangle>& getLevel(double z);
+    int read(std::string& stl_target, bool isBinary);
+    Stl();
+    Stl(std::string& stl_target, bool isBinary);
+
+    void printSTL();
+};

diff --git a/src/Slicer.cc b/src/Slicer.cc
new file mode 100644 (file)
index 0000000..fde2cad
--- /dev/null
+++ b/src/Slicer.cc
@@ -0,0 +1,101 @@
+#include "Slicer.hh"
+
+#include <fstream>
+
+#include "BufferWrite.hh"
+#include "Slicing.hh"
+using namespace std;
+
+void Slicer::slicing()
+{
+    double zmax = stl.getZmax();
+    double zmin = stl.getZmin();
+    numLayer    = (zmax - zmin - zStart) / zgap + 1;
+    layers.reserve(numLayer);
+    checkLayers = new bool[numLayer];
+    for (int i = 0; i < numLayer; i++) checkLayers[i] = false;
+    for (double z = zmin + zStart; z < zmax; z += zgap)
+    {
+        layers.push_back(Layer(z));
+    }
+    cout << finishedCount << "/" << numLayer;
+    for (int i = 0; i < NUM_THREADS; i++)
+    {
+        threads[i] = thread(&Slicer::threadLayer, this);
+    }
+    for (int i = 0; i < NUM_THREADS; i++)
+    {
+        threads[i].join();
+    }
+    cout << "\nWriting...";
+#if 0  // Write to gcode file directly
+       ofstream f(gcode_target, ios_base::out | ios_base::app);
+       for (const auto& layer : layers)
+               layer.commandsOut(f);
+#endif
+#if 1  // Write to writing buffer
+    BufferWrite buffer(gcode_target);
+    for (const auto& layer : layers) layer.commandsOut(buffer);
+    buffer.flush();
+#endif
+    cout << "\nDone!\n";
+}
+
+// mult-threads management function
+void Slicer::threadLayer()
+{
+    for (int index = 0; index < numLayer; index++)
+    {
+        checkMutex.lock();
+        if (checkLayers[index])
+        {
+            checkMutex.unlock();
+            continue;
+        }
+        checkLayers[index] = true;
+        checkMutex.unlock();
+
+        Slicing cl(stl, layers[index]);
+
+        countMutex.lock();
+        finishedCount++;
+        cout << "\r" << finishedCount << "/" << numLayer;
+        countMutex.unlock();
+    }
+}
+
+Slicer::Slicer(std::string& filename) : Slicer(filename.c_str()) {}
+
+Slicer::Slicer(const char* filename)
+{
+#if 0  // Make directory for Windows
+               _mkdir(gcode_filePath.c_str()); //make directory for storing gcode
+#endif
+#if 1
+    std::string mkdir = "mkdir -p ";
+    int res           = system(mkdir.append(gcode_filePath.c_str()).c_str());
+#endif
+
+    // TODO:   STL file extensions: .stl, .stlb, .bif.
+    // This can work for .stl and .stlb, but not good.
+    int extensionLen = 3;
+    bool isBinary;
+    if (filename[strlen(filename) - 1] == 'b')
+    {
+        isBinary = true;
+        extensionLen++;
+    }
+    else
+        isBinary = false;
+
+    // change the file extension from ".stl" to ".gcode"
+    stl_target = stl_filePath;
+    stl_target.append(filename);
+    gcode_target = gcode_filePath;
+    gcode_target.append(filename, strlen(filename) - extensionLen);
+    gcode_target.append("gcode");
+    remove(gcode_target.c_str());  // remove old gcode file
+    std::cout << "\tFile: " << filename << "\nReading...";
+    std::cout << "\nNumber of triangles: " << stl.read(stl_target, isBinary);
+    std::cout << "\nRead finish\n";
+}

diff --git a/src/Slicer.hh b/src/Slicer.hh
new file mode 100644 (file)
index 0000000..c11ae2c
--- /dev/null
+++ b/src/Slicer.hh
@@ -0,0 +1,40 @@
+#pragma once
+
+/*
+        @author: Xinqi Bao
+        Main class to manage the whole program.
+        Include reading file, slicing each layer and writting to file,
+        using mult-threads.
+*/
+
+#include <cstring>
+#include <iostream>
+#include <mutex>
+#include <string>
+#include <thread>
+#include <vector>
+
+#include "Configurations.hh"
+#include "Layer.hh"
+#include "STL.hh"
+
+class Slicer
+{
+private:
+    Stl stl;
+    int numLayer;
+    int finishedCount = 0;  // count for each finished layers
+    bool* checkLayers;
+    std::string stl_target;     // original stl file name
+    std::string gcode_target;   // the name for outputting gcode file
+    std::vector<Layer> layers;  // contain each layers with loops and gcode
+    std::thread threads[NUM_THREADS];
+    std::mutex checkMutex;
+    std::mutex countMutex;
+    void threadLayer();
+
+public:
+    void slicing();
+    Slicer(std::string& filename);
+    Slicer(const char* filename);
+};

diff --git a/src/Slicing.cc b/src/Slicing.cc
new file mode 100644 (file)
index 0000000..3a79b81
--- /dev/null
+++ b/src/Slicing.cc
@@ -0,0 +1,332 @@
+#include "Slicing.hh"
+
+#include <cmath>
+#include <iostream>
+
+#include "Configurations.hh"
+using namespace std;
+
+Slicing::Slicing(Stl* stl, Layer* layer) : Slicing(*stl, *layer) {}
+
+Slicing::Slicing(Stl& stl, Layer& layer)
+    : z(layer.getZ()), loops(layer.getLoops()), triangles(stl.getLevel(z))
+{
+    intersection();
+    mkLoop();
+    Gcode g(layer);
+}
+
+// return true if this pair of vectors cross this level
+inline bool Slicing::isCross(const Vec3d& v1, const Vec3d& v2) const
+{  // not include at the vertex
+    return (v1.z + thr < z && z < v2.z - thr) ||
+           (v2.z + thr < z && z < v1.z - thr);
+}
+
+// check if the cut through both triangles' sides
+bool Slicing::isSectionExist(Cross& cr) const
+{
+    for (const auto& temp : intersections)
+        if (temp.equal(cr)) return true;
+    return false;
+}
+
+// push every sections into the vetor
+// Total as 10 different cross cases, side-side for 3, vertex-side for 3,
+// vertex-vertex for 3, through whole facet for 1.
+// More rare cases been checked more, saving whole execution time.
+void Slicing::intersection()
+{
+    intersections.reserve(triangles.size() >> 1);
+    for (const auto& t : triangles)
+    {
+        if (isCross(t.v1, t.v2))
+        {
+            if (isCross(t.v1, t.v3))
+            {  // Cross v1--v2 and v1--v3
+                intersections.push_back(
+                    Cross(Vec2d(t.v1, t.v2, z), Vec2d(t.v1, t.v3, z)));
+                continue;
+            }
+            else if (fabs(z - t.v3.z) < thr)
+            {  // Cross v1--v2 and v3
+                intersections.push_back(
+                    Cross(Vec2d(t.v1, t.v2, z), Vec2d(t.v3.x, t.v3.y)));
+                continue;
+            }
+            else
+            {  // definitely cross v1--v2 and v2--v3
+                intersections.push_back(
+                    Cross(Vec2d(t.v1, t.v2, z), Vec2d(t.v2, t.v3, z)));
+                continue;
+            }
+        }
+        else if (isCross(t.v1, t.v3))
+        {
+            if (fabs(z - t.v2.z) < thr)
+            {  // Cross v1--v3 and v2
+                intersections.push_back(
+                    Cross(Vec2d(t.v1, t.v3, z), Vec2d(t.v2.x, t.v2.y)));
+                continue;
+            }
+            else
+            {  // Cross v1--v3 and v2--v3
+                intersections.push_back(
+                    Cross(Vec2d(t.v1, t.v3, z), Vec2d(t.v2, t.v3, z)));
+                continue;
+            }
+        }
+        else if (fabs(z - t.v1.z) < thr)
+        {
+            if (isCross(t.v2, t.v3))
+            {  // Cross v1 and v2--v3
+                intersections.push_back(
+                    Cross(Vec2d(t.v1.x, t.v1.y), Vec2d(t.v2, t.v3, z)));
+                continue;
+            }
+            else if (fabs(z - t.v2.z) < thr)
+            {
+                if (fabs(z - t.v3.z) < thr)  // Through the whole facet
+                    continue;
+                else
+                {  // v1 and v2
+                    Cross cr(Vec2d(t.v1.x, t.v1.y), Vec2d(t.v2.x, t.v2.y));
+                    if (!isSectionExist(cr)) intersections.push_back(cr);
+                    continue;
+                }
+            }
+            else if (fabs(z - t.v3.z) < thr)
+            {  // v1 and v3, still need "if()", because may only cross one
+               // vertex(v1)
+                Cross cr(Vec2d(t.v1.x, t.v1.y), Vec2d(t.v3.x, t.v3.y));
+                if (!isSectionExist(cr)) intersections.push_back(cr);
+                continue;
+            }
+        }
+        else if (fabs(z - t.v2.z) < thr)
+        {
+            if (fabs(z - t.v3.z) < thr)
+            {  // v2 and v3
+                Cross cr(Vec2d(t.v2.x, t.v2.y), Vec2d(t.v3.x, t.v3.y));
+                if (!isSectionExist(cr)) intersections.push_back(cr);
+                continue;
+            }
+        }
+    }
+}
+
+// Combine intersections to loops
+// TODO: vector.erase() take to much time, need to be optimied
+void Slicing::mkLoop()
+{
+    if (intersections.empty()) return;
+#if 1  // implement with subLoops
+    Vec2d p1(intersections.back().p1);
+    Vec2d p2(intersections.back().p2);
+    Loop lp(p1, intersections.size() >> 1);
+    lp.add(p2);
+    intersections.erase(intersections.end() - 1);
+    while (!intersections.empty())
+    {
+        if (!lp.isCompleted())
+        {
+            /**/
+            for (int i = intersections.size() - 1; i >= 0; i--)
+            {
+                if (p2.equal(intersections[i].p1))
+                {
+                    p1 = p2;
+                    p2 = intersections[i].p2;
+                    intersections.erase(intersections.begin() + i);
+                    lp.add(p2);
+                    break;
+                }
+                else if (p2.equal(intersections[i].p2))
+                {
+                    p1 = p2;
+                    p2 = intersections[i].p1;
+                    intersections.erase(intersections.begin() + i);
+                    lp.add(p2);
+                    break;
+                }
+            }
+            /*
+            int i = 0;
+            for (const auto& temp : intersections) {
+                    if (p2.equal(temp.p1)) {
+                            p1 = p2;
+                            p2 = temp.p2;
+                            intersections.erase(intersections.begin() + i);
+                            lp.add(p2);
+                            break;
+                    }
+                    else if (p2.equal(temp.p2)) {
+                            p1 = p2;
+                            p2 = temp.p1;
+                            intersections.erase(intersections.begin() + i);
+                            lp.add(p2);
+                            break;
+                    }
+                    i++;
+            }*/
+        }
+        else
+        {  // creat a new Loop
+            bool isSubLoop = false;
+            for (int i = loops.size() - 1; i >= 0; i--)
+            {
+                isSubLoop = loops[i].checkSubLoop(lp);
+                if (isSubLoop) break;
+                if (lp.checkSubLoop(loops[i]))
+                {
+                    // lp.subLoops.push_back(loops[i]);
+                    loops.erase(loops.begin() + i);
+                }
+            }
+            if (!isSubLoop) loops.push_back(lp);
+            p1 = intersections.back().p1;
+            p2 = intersections.back().p2;
+            lp = Loop(p1, intersections.size() >> 1);
+            lp.add(p2);
+            intersections.erase(intersections.end());
+        }
+    }
+    bool isSubLoop = false;
+    for (int i = loops.size() - 1; i >= 0; i--)
+    {
+        isSubLoop = loops[i].checkSubLoop(lp);
+        if (isSubLoop) break;
+        if (lp.checkSubLoop(loops[i]))
+        {
+            // lp.subLoops.push_back(loops[i]);
+            loops.erase(loops.begin() + i);
+        }
+    }
+    if (!isSubLoop) loops.push_back(lp);
+#endif
+#if 0
+       //Vec2d p1(intersections.front().p1);
+       //Vec2d p2(intersections.front().p2);
+       Vec2d p1(intersections.back().p1);
+       Vec2d p2(intersections.back().p2);
+       loops.push_back(Loop(p1, intersections.size() >> 1));
+       loops.back().add(p2);
+       //intersections.erase(intersections.begin());
+       intersections.pop_back();
+       while (!intersections.empty()) {
+               if (!loops.back().isCompleted()) {
+                       /**/
+                       for (int i = intersections.size()-1; i >= 0; i--) {
+                               if (p2.equal(intersections[i].p1)) {
+                                       p1 = p2;
+                                       p2 = intersections[i].p2;
+                                       intersections.erase(intersections.begin() + i);
+                                       loops.back().add(p2);
+                                       break;
+                               }
+                               else if (p2.equal(intersections[i].p2)) {
+                                       p1 = p2;
+                                       p2 = intersections[i].p1;
+                                       intersections.erase(intersections.begin() + i);
+                                       loops.back().add(p2);
+                                       break;
+                               }
+                       }
+                       /*
+                       int i = 0;
+                       for (const auto& temp : intersections) {
+                               if (p2.equal(temp.p1)) {
+                                       p1 = p2;
+                                       p2 = temp.p2;
+                                       intersections.erase(intersections.begin() + i);
+                                       loops.back().add(p2);
+                                       break;
+                               }
+                               else if (p2.equal(temp.p2)) {
+                                       p1 = p2;
+                                       p2 = temp.p1;
+                                       intersections.erase(intersections.begin() + i);
+                                       loops.back().add(p2);
+                                       break;
+                               }
+                               i++;
+                       }*/
+               }
+               else {  //creat a new Loop
+                       //p1 = intersections.front().p1;
+                       //p2 = intersections.front().p2;
+                       p1 = intersections.back().p1;
+                       p2 = intersections.back().p2;
+                       loops.push_back(Loop(p1, intersections.size() >> 1));
+                       loops.back().add(p2);
+                       //intersections.erase(intersections.begin());
+                       intersections.pop_back();
+               }
+       }
+#endif
+#if 0  // Why take more time??
+       int size = intersections.size();
+       bool* bools = new bool[size];
+       for (int i = 0; i < size; i++)
+               bools[i] = true;
+       Vec2d p1(intersections.front().p1);
+       Vec2d p2(intersections.front().p2);
+       loops.push_back(Loop(p1, intersections.size() >> 1));
+       loops.back().add(p2);
+       bools[0] = false;
+       for (int i = 1; i < size; i++) {
+               if (!loops.back().isCompleted()) {
+                       for (int k = 0; k < size; k++) {
+                               if (!bools[k])
+                                       continue;
+                               if (p2.equal(intersections[k].p1)) {
+                                       p1 = p2;
+                                       p2 = intersections[k].p2;
+                                       loops.back().add(p2);
+                                       bools[k] = false;
+                                       break;
+                               }
+                               else if (p2.equal(intersections[k].p2)) {
+                                       p1 = p2;
+                                       p2 = intersections[k].p1;
+                                       loops.back().add(p2);
+                                       bools[k] = false;
+                                       break;
+                               }
+                       }
+               }
+               else {
+                       for (int k = 0; k < size; k++) {
+                               if (!bools[k])
+                                       continue;
+                               Vec2d p1(intersections[k].p1);
+                               Vec2d p2(intersections[k].p2);
+                               loops.push_back(Loop(p1, intersections.size() >> 1));
+                               loops.back().add(p2);
+                               bools[k] = false;
+                       }
+               }
+       }
+       delete bools;
+#endif
+    for (auto& lp : loops) lp.optimize();
+}
+
+void Slicing::printVector() const
+{
+    cout << "\nZ as " << z << ":\tcontain " << intersections.size() << "\n";
+    for (const auto& i : intersections)
+    {
+        cout << i << '\n';
+    }
+}
+
+void Slicing::printLoop() const
+{
+    for (int i = 0; i < loops.size(); i++)
+    {
+        cout << "\nLoop " << i << ", Z as " << z << '\n';
+        loops.at(i).print();
+        cout << "\n\n";
+    }
+}

diff --git a/src/Slicing.hh b/src/Slicing.hh
new file mode 100644 (file)
index 0000000..475cd8b
--- /dev/null
+++ b/src/Slicing.hh
@@ -0,0 +1,36 @@
+#pragma once
+
+/*
+        @author: Xinqi Bao
+        With a particular z, get lines from triangles at this position.
+        Then make loops from the pool of intersections, store the result into
+   layer object.
+*/
+
+#include <vector>
+
+#include "Cross.hh"
+#include "GCode.hh"
+#include "Loop.hh"
+#include "STL.hh"
+#include "Triangle.hh"
+
+class Slicing
+{
+private:
+    double z;
+    std::vector<Loop>& loops;
+    std::vector<Triangle>& triangles;
+    std::vector<Cross> intersections;
+    bool isCross(const Vec3d& v_1, const Vec3d& v_2) const;
+    bool isSectionExist(Cross& cr) const;
+    void intersection();
+    void mkLoop();
+
+public:
+    Slicing(Stl* stl, Layer* layer);
+    Slicing(Stl& stl, Layer& layer);
+
+    void printVector() const;
+    void printLoop() const;
+};

diff --git a/src/Triangle.cc b/src/Triangle.cc
new file mode 100644 (file)
index 0000000..cbf4b04
--- /dev/null
+++ b/src/Triangle.cc
@@ -0,0 +1,53 @@
+#include "Triangle.hh"
+
+#include <iostream>
+
+#include "BufferReadBinary.hh"
+#include "Vec3d.hh"
+
+std::istream& operator>>(std::istream& s, Skip& skip)
+{
+    while (isspace(s.get()) && !s.eof())
+        ;
+    while (!isspace(s.get()) && !s.eof())
+        ;
+    return s;
+}
+static Skip skip;
+
+Triangle::Triangle() {}
+
+Triangle::Triangle(std::istream& s)
+{
+    s >> skip >> skip >> normal;
+    s.ignore(1);
+    s.ignore(256, '\n');
+    s >> skip >> v1;
+    s >> skip >> v2;
+    s >> skip >> v3;
+    s.ignore(1);
+    s.ignore(256, '\n');
+    s.ignore(256, '\n');
+}
+
+Triangle::Triangle(BufferReadBinary& buffer)
+{
+    normal.readBuffer(buffer);
+    v1.readBuffer(buffer);
+    v2.readBuffer(buffer);
+    v3.readBuffer(buffer);
+    buffer.step2Bytes();
+}
+
+Triangle::Triangle(Vec3d& normal, Vec3d& v1, Vec3d& v2, Vec3d& v3)
+    : normal(normal), v1(v1), v2(v2), v3(v3)
+{
+}
+
+std::ostream& operator<<(std::ostream& s, Triangle& tri)
+{
+    return s << "normal: " << tri.normal << '\n'
+             << "vertex: " << tri.v1 << '\n'
+             << "vertex: " << tri.v2 << '\n'
+             << "vertex: " << tri.v3 << '\n';
+}

diff --git a/src/Triangle.hh b/src/Triangle.hh
new file mode 100644 (file)
index 0000000..136806e
--- /dev/null
+++ b/src/Triangle.hh
@@ -0,0 +1,30 @@
+#pragma once
+
+/*
+        @author: Xinqi Bao
+        Triangle with 3 3-D vectors.
+*/
+
+#include <iostream>
+
+#include "BufferReadBinary.hh"
+#include "Vec3d.hh"
+
+class Skip
+{
+public:
+    friend std::istream& operator>>(std::istream& s, Skip& skip);
+};
+
+class Triangle
+{
+public:
+    Vec3d normal, v1, v2, v3;
+
+    Triangle();
+    Triangle(std::istream& s);
+    Triangle(BufferReadBinary& buffer);
+    Triangle(Vec3d& normal, Vec3d& v1, Vec3d& v2, Vec3d& v3);
+
+    friend std::ostream& operator<<(std::ostream& s, Triangle& tri);
+};

diff --git a/src/Vec2d.cc b/src/Vec2d.cc
new file mode 100644 (file)
index 0000000..8dd463e
--- /dev/null
+++ b/src/Vec2d.cc
@@ -0,0 +1,35 @@
+#include "Vec2d.hh"
+
+#include <cmath>
+
+#include "Configurations.hh"
+
+Vec2d::Vec2d() {}
+Vec2d::Vec2d(double x, double y) : x(x), y(y) {}
+Vec2d::Vec2d(const Vec3d& v1, const Vec3d& v2, double z)
+{
+    x = (v1.x - v2.x) * (z - v1.z) / (v1.z - v2.z) + v1.x;
+    y = (v1.y - v2.y) * (z - v1.z) / (v1.z - v2.z) + v1.y;
+}
+
+bool Vec2d::equal(const Vec2d& v) const
+{
+    if (fabs(x - v.x) < thr && fabs(y - v.y) < thr) return true;
+    return false;
+}
+bool Vec2d::equal(const Vec2d* v) const { return equal(*v); }
+double Vec2d::sum() const { return x + y; }
+
+std::istream& operator>>(std::istream& s, Vec2d& v) { return s >> v.x >> v.y; }
+std::istream& operator>>(std::istream& s, Vec2d* v)
+{
+    return s >> v->x >> v->y;
+}
+std::ostream& operator<<(std::ostream& s, const Vec2d& v)
+{
+    return s << v.x << "," << v.y;
+}
+std::ostream& operator<<(std::ostream& s, const Vec2d* v)
+{
+    return s << v->x << "," << v->y;
+}

diff --git a/src/Vec2d.hh b/src/Vec2d.hh
new file mode 100644 (file)
index 0000000..b6fd6dc
--- /dev/null
+++ b/src/Vec2d.hh
@@ -0,0 +1,28 @@
+#pragma once
+
+/*
+        @author: Xinqi Bao
+        2-D vector, with 2 double vaule points.
+*/
+
+#include <iostream>
+
+#include "Vec3d.hh"
+
+class Vec2d
+{
+public:
+    double x, y;
+    bool equal(const Vec2d& v) const;
+    bool equal(const Vec2d* v) const;
+    double sum() const;
+
+    Vec2d();
+    Vec2d(double x, double y);
+    Vec2d(const Vec3d& v1, const Vec3d& v2, double z);
+
+    friend std::istream& operator>>(std::istream& s, Vec2d& v);
+    friend std::istream& operator>>(std::istream& s, Vec2d* v);
+    friend std::ostream& operator<<(std::ostream& s, const Vec2d& v);
+    friend std::ostream& operator<<(std::ostream& s, const Vec2d* v);
+};

diff --git a/src/Vec3d.cc b/src/Vec3d.cc
new file mode 100644 (file)
index 0000000..51e58cc
--- /dev/null
+++ b/src/Vec3d.cc
@@ -0,0 +1,43 @@
+#include "Vec3d.hh"
+
+#include <cmath>
+
+#include "Configurations.hh"
+
+Vec3d::Vec3d() {}
+Vec3d::Vec3d(double x, double y, double z) : x(x), y(y), z(z) {}
+void Vec3d::readBuffer(BufferReadBinary& buffer)
+{
+    x = buffer.getFloat();
+    buffer.stepFloat();
+    y = buffer.getFloat();
+    buffer.stepFloat();
+    z = buffer.getFloat();
+    buffer.stepFloat();
+}
+
+bool Vec3d::equal(const Vec3d& v) const
+{
+    if (fabs(x - v.x) < thr && fabs(y - v.y) < thr && fabs(z - v.z) < thr)
+        return true;
+    return false;
+}
+bool Vec3d::equal(const Vec3d* v) const { return equal(*v); }
+double Vec3d::sum() const { return x + y + z; }
+
+std::istream& operator>>(std::istream& s, Vec3d& v)
+{
+    return s >> v.x >> v.y >> v.z;
+}
+std::istream& operator>>(std::istream& s, Vec3d* v)
+{
+    return s >> v->x >> v->y >> v->z;
+}
+std::ostream& operator<<(std::ostream& s, const Vec3d& v)
+{
+    return s << v.x << "," << v.y << "," << v.z;
+}
+std::ostream& operator<<(std::ostream& s, const Vec3d* v)
+{
+    return s << v->x << "," << v->y << "," << v->z;
+}

diff --git a/src/Vec3d.hh b/src/Vec3d.hh
new file mode 100644 (file)
index 0000000..57674e0
--- /dev/null
+++ b/src/Vec3d.hh
@@ -0,0 +1,28 @@
+#pragma once
+
+/*
+        @author: Xinqi Bao
+        3-D vector, with 3 double vaule points.
+*/
+
+#include <iostream>
+
+#include "BufferReadBinary.hh"
+
+class Vec3d
+{
+public:
+    double x, y, z;
+    void readBuffer(BufferReadBinary& buffer);
+    bool equal(const Vec3d& v) const;
+    bool equal(const Vec3d* v) const;
+    double sum() const;
+
+    Vec3d();
+    Vec3d(double x, double y, double z);
+
+    friend std::istream& operator>>(std::istream& s, Vec3d& v);
+    friend std::istream& operator>>(std::istream& s, Vec3d* v);
+    friend std::ostream& operator<<(std::ostream& s, const Vec3d& v);
+    friend std::ostream& operator<<(std::ostream& s, const Vec3d* v);
+};

diff --git a/src/main.cc b/src/main.cc
new file mode 100644 (file)
index 0000000..3502f98
--- /dev/null
+++ b/src/main.cc
@@ -0,0 +1,15 @@
+#include <fstream>
+#include <iostream>
+#include <string>
+
+#include "Slicer.hh"
+using namespace std;
+
+int main(int argc, char* argv[])
+{
+    const char* filename = argc < 2 ? "cube.stl" : argv[1];
+    Slicer slicer(filename);  // eliipticalvase.stl
+    slicer.slicing();
+
+    return 0;
+}

diff --git a/stl_files/cube.stl b/stl_files/cube.stl
new file mode 100644 (file)
index 0000000..0038e65
--- /dev/null
+++ b/stl_files/cube.stl
@@ -0,0 +1,86 @@
+solid CADmodel
+facet normal 0.0 -0.0 900.0
+outer loop
+vertex 15.0 -15.0 15.0
+vertex 15.0 15.0 15.0
+vertex -15.0 15.0 15.0
+endloop
+endfacet
+facet normal 0.0 0.0 900.0
+outer loop
+vertex 15.0 -15.0 15.0
+vertex -15.0 15.0 15.0
+vertex -15.0 -15.0 15.0
+endloop
+endfacet
+facet normal -900.0 0.0 0.0
+outer loop
+vertex -15.0 -15.0 15.0
+vertex -15.0 15.0 15.0
+vertex -15.0 15.0 -15.0
+endloop
+endfacet
+facet normal -900.0 0.0 0.0
+outer loop
+vertex -15.0 -15.0 15.0
+vertex -15.0 15.0 -15.0
+vertex -15.0 -15.0 -15.0
+endloop
+endfacet
+facet normal 0.0 900.0 0.0
+outer loop
+vertex 15.0 15.0 15.0
+vertex 15.0 15.0 -15.0
+vertex -15.0 15.0 -15.0
+endloop
+endfacet
+facet normal 0.0 900.0 0.0
+outer loop
+vertex 15.0 15.0 15.0
+vertex -15.0 15.0 -15.0
+vertex -15.0 15.0 15.0
+endloop
+endfacet
+facet normal 900.0 0.0 0.0
+outer loop
+vertex 15.0 -15.0 15.0
+vertex 15.0 -15.0 -15.0
+vertex 15.0 15.0 -15.0
+endloop
+endfacet
+facet normal 900.0 -0.0 0.0
+outer loop
+vertex 15.0 -15.0 15.0
+vertex 15.0 15.0 -15.0
+vertex 15.0 15.0 15.0
+endloop
+endfacet
+facet normal 0.0 0.0 -900.0
+outer loop
+vertex 15.0 -15.0 -15.0
+vertex -15.0 -15.0 -15.0
+vertex -15.0 15.0 -15.0
+endloop
+endfacet
+facet normal 0.0 0.0 -900.0
+outer loop
+vertex 15.0 -15.0 -15.0
+vertex -15.0 15.0 -15.0
+vertex 15.0 15.0 -15.0
+endloop
+endfacet
+facet normal 0.0 -900.0 0.0
+outer loop
+vertex 15.0 -15.0 -15.0
+vertex 15.0 -15.0 15.0
+vertex -15.0 -15.0 15.0
+endloop
+endfacet
+facet normal 0.0 -900.0 0.0
+outer loop
+vertex 15.0 -15.0 -15.0
+vertex -15.0 -15.0 15.0
+vertex -15.0 -15.0 -15.0
+endloop
+endfacet
+endsolid CADmodel