Octree building / script-based rendering for OpenSCAD

OctreeBuilder.h OpenSCAD

#include "cgal.h"
#include "CGAL_Nef_polyhedron.h"
#include "cgalutils.h"
#include "printutils.h"
#include <CGAL/Octree.h>
#include "linalg.h"
#include "../IndexedMesh.h"
#include <unordered_set>
#include <unordered_map>
#include <flat_set>
#include "node.h"
#include "TransformNode.h"
#include "OffsetNode.h"
// #include "LeafNode.h"


class SharedNodesDetector : public NodeVisitor
{
  const Tree& tree;
  std::unordered_map<std::string, size_t>& key_occurrences;

  SharedNodesDetector(const Tree& tree, std::unordered_map<std::string, size_t>& key_occurrences) : tree(tree), key_occurrences(key_occurrences) {}
  Response visit(State& state, const AbstractNode& node) override {
    if (state.isPrefix()) {
      auto key = this->tree.getIdString(node);
      key_occurrences[key]++;
    }
    return Response::ContinueTraversal;
  }

public:
  static std::unordered_set<std::string> detect(const std::vector<Tree>& trees) {
    std::unordered_map<std::string, size_t> key_occurrences;
    for (const auto &tree : trees) {
      if (tree.root()) {
        SharedNodesDetector detector(tree, key_occurrences);
        detector.traverse(*tree.root());
      }
    }
    std::unordered_set<std::string> set;
    for (auto &pair : key_occurrences) {
      if (pair.second > 1) {
        set.insert(pair.first);//, set.end());
      }
    }
    return std::move(set);
  }
};

struct RenderStep {
  // Same as a cache key (string source for subtree).
  using ArtefactId = std::string;

  // We split repeated subtrees out to separate render steps.
  // Optionally, can also convert 3D imports to formats that are faster to deserialize, and put that conversion as an extra render step.
  std::unordered_map<ArtefactId, std::shared_ptr<RenderStep>> dependencies;

  std::shared_ptr<const AbstractNode> root;

  // Each render step has its own partition
  std::vector<BoundingBox> cells;

  // Mapping from any node to the set of cell (indices) the node's bbox intersects with.
  std::unordered_map<shared_ptr<const AbstractNode>, std::flat_set<size_t>> node_cell_indices;

  // Any node -> artefact id (if node is shared or generally the result of a computation)
  std::unordered_map<shared_ptr<const AbstractNode>, ArtefactId> node_artefact_ids;

  std::string output_file;
};

class RenderStepsBuilder
{
  const std::unordered_set<std::string>& sharedKeys;

  // std::unordered_map<std::string, std::shared_ptr<RenderStep>> stepBySharedKey;
  std::stack<std::shared_ptr<RenderStep>> currentStep;
  std::unordered_map<ArtefactId, std::shared_ptr<RenderStep>> &allDependencies;

  RenderStepsBuilder(const std::unordered_set<std::string>& sharedNodesCacheKeys) : sharedNodesCacheKeys(sharedNodesCacheKeys) {}

  void collect(const std::shared_ptr<const AbstractNode> &node) {

  }
public:
  
  void collect(const Tree &tree) {
    if (!node) return;
    auto key = tree.getIdString(*node);
    if (sharedKeys.find(key) == sharedKeys.end()) {
      // Not a shared node, just recurse!
      for (const auto &child : node.children) {
        collectRenderSteps(tree, child, currentStep, allDependencies, sharedKeys);
      }
    } else {
      // Shared node.
      auto &sharedStep = allDependencies[key];
      if (!sharedStep) {
        // Haven't built that dependency yet!
        sharedStep = make_shared<RenderStep>();
        Tree subTree(node);
        collectRenderSteps(subTree, node, sharedStep, allDependencies, sharedKeys);
      }
      currentStep.dependencies[key] = sharedStep;
    }
  }

};

class PointsCollector
{
  typedef std::unordered_map<Vector3d, size_t> PointMap;
  std::unordered_set<std::string> sharedNodesCacheKeys;
  std::unordered_map<std::string, PointMap> sharedNodesPointMaps;
  const Tree& tree;

  void collectWithoutCaching(const AbstractNode &node, const Transform3d& world_transform, PointMap& out) {
    auto visitChildren = [&](const Transform3d& transform) {
      for (auto &child : node.children) {
        if (child) {
          collect(*child, transform, out);
        }
      }
    };
    if (auto transformNode = dynamic_cast<const TransformNode*>(&node)) {
      visitChildren(world_transform * transformNode->matrix);
    } else if (auto leafNode = dynamic_cast<const LeafNode*>(&node)) {
      shared_ptr<const Geometry> geom(leafNode->createGeometry());
      if (geom) {
        IndexedMesh im;
        im.append_geometry(geom);
        // TODO: detect if im.isEmpty() (e.g. 2D case)
        auto &vec = im.vertices.getArray();
        for (const auto &pt : vec) {
          out[world_transform * pt]++;
        }
      }
    } else if (auto offsetNode = dynamic_cast<const OffsetNode*>(&node)) {
      // TODO
    } else {
      visitChildren(world_transform);
    }
  }

  bool shouldBeShared(const std::string &key) const {
    return sharedNodesCacheKeys.find(key) != sharedNodesCacheKeys.end();
  }

protected:
  PointsCollector(const Tree& tree)
    : tree(tree), sharedNodesCacheKeys(std::move(SharedNodesDetector::detect(tree)))
  {}

  void collect(const AbstractNode &node, const Transform3d& world_transform, PointMap& out) {
    auto key = this->tree.getIdString(node);
    if (shouldBeShared(key)) {
      PointMap *pointMap = nullptr;
      auto sharedIt = sharedNodesPointMaps.find(key);
      if (sharedIt != sharedNodesPointMaps.end()) {
        // Points of shared node have already been collected.
        pointMap = &sharedIt->second;
      } else {
        // Collect points of shared node and cache them.
        pointMap = &sharedNodesPointMaps[key];
        collectWithoutCaching(node, Transform3d::Identity(), *pointMap);
      }
      assert(pointMap);
      for (const auto &p : *pointMap) {
        out[world_transform * p.first]++;
      }
    } else {
      collectWithoutCaching(node, world_transform, out);
    }
  }

public:
  static PointMap collect(const Tree& tree) {
    PointsCollector::PointMap points;
    if (tree.root()) {
      PointsCollector pointsCollector(tree);
      pointsCollector.collect(*tree.root(), Transform3d::Identity(), points);
    }
    return std::move(points);
  }
};

struct RenderingOptions {

};

std::vector<std::shared_ptr<RenderStep>> createRenderSteps(const std::vector<std::pair<std::shared_ptr<const AbstractNode>, std::string>>& rootsAndOutputNames, const RenderingOptions &options) {
  std::vector<std::shared_ptr<RenderStep>> result;

  return std::move(results);
}

struct PartitionResult {

  // std::unordered_map<shared_ptr<const AbstractNode>, std::string> shared_subtrees_ids;
  // // 
  // std::unordered_map<std::string, std::unordered_set<std::string>> shared_subtrees_dependencies;
  // std::unordered_map<shared_ptr<const AbstractNode>, std::string> shared_subtrees_ids;
};


PartitionResult partitionTree(const Tree &tree, size_t maxPointsInCellsWithOperations) {
  std::unordered_map<std::string, shared_ptr<const AbstractNode>> example_instance_for_each_shared_key;
  // std::unordered_set<std::string> shared_keys;
  std::unordered_map<shared_ptr<const AbstractNode>, std::flat_set<size_t>> cell_indices_by_node;

  PartitionResult result;

  return std::move(result);
}
//  {

    // this->bbox.setNull();
    // for (const auto& poly : polygons) {
    //   for (const auto& p : poly) {
    //     this->bbox.extend(p);
// }
// typedef CGAL::Simple_cartesian<double> Kernel;
// typedef Kernel::Point_3 Point;
// typedef CGAL::Octree<Kernel, Point_vector> Octree;
// CGAL::Octree createOctree(const Tree& tree) {
  
// }


// // TODO(ochafik): Have GeometryEvaluator inherit this
// class AbstractGeometryEvaluator  : public NodeVisitor
// {
//   const Tree& tree;

// public:
//   [[nodiscard]] const Tree& getTree() const { return this->tree; }

// protected:

//   AbstractGeometryEvaluator(const Tree& tree) : tree(tree) {}

//   const std::string& getCacheKey(const AbstractNode& node) {
//     return this->tree.getIdString(node);
//   }

//   void smartCacheInsert(const AbstractNode& node,
//                                           const shared_ptr<const Geometry>& geom)
//   {
//     const std::string& key = this->getCacheKey(node);

//     if (CGALCache::acceptsGeometry(geom)) {
//       if (!CGALCache::instance()->contains(key)) CGALCache::instance()->insert(key, geom);
//     } else {
//       if (!GeometryCache::instance()->contains(key)) {
//         if (!GeometryCache::instance()->insert(key, geom)) {
//           LOG(message_group::Warning, Location::NONE, "", "GeometryEvaluator: Node didn't fit into cache.");
//         }
//       }
//     }
//   }

//   bool isSmartCached(const AbstractNode& node)
//   {
//     const std::string& key = this->getCacheKey(node);
//     return (GeometryCache::instance()->contains(key) ||
//             CGALCache::instance()->contains(key));
//   }

//   shared_ptr<const Geometry> smartCacheGet(const AbstractNode& node, bool preferNef)
//   {
//     const std::string& key = this->getCacheKey(node);
//     shared_ptr<const Geometry> geom;
//     bool hasgeom = GeometryCache::instance()->contains(key);
//     bool hascgal = CGALCache::instance()->contains(key);
//     if (hascgal && (preferNef || !hasgeom)) geom = CGALCache::instance()->get(key);
//     else if (hasgeom) geom = GeometryCache::instance()->get(key);
//     return geom;
//   }
// };

// class PointsCollector : public AbstractGeometryEvaluator
// {
//   // typedef CGAL::Simple_cartesian<double> Kernel;
//   // typedef Kernel::Point_3 Point;
//   // typedef CGAL::Octree<Kernel, Point_vector> Octree;
//   // Octree octree_;

//   void pushTransform(const Transform3d& transform) {
//     assert(!world_transforms.empty());
//     world_transforms.emplace(world_transforms.top() * transform);
//   }

//   void popTransform() {
//     assert(!world_transforms.empty());
//     world_transforms.pop();
//     assert(!world_transforms.empty());
//   }

//   template <class iter>
//   void addPoints(const iter& start, const iter& end) {
//     const auto &transform = world_transform.top();
//     for (auto it = start; it != end; ++it) {
//       const auto &pt = *it;
//       points[pt]++;
//     }
//   }

//   void processGeometry(const AbstractNode &node) {
//     shared_ptr<const Geometry> geom;
//     if (isSmartCached(node)) {
//       geom = smartCacheGet(node, /* preferNef= */ false);
//     } else {
//       geom = node.createGeometry();
//       smartCacheInsert(node, geom);
//     }
//     // auto ps = CGALUtils::getGeometryAsPolySet(geom);
//     if (geom) {
//       IndexedMesh im;
//       im.append_geometry(geom);
//       auto &vec = im.vertices.getArray();
//       addPoints(vec.begin(), veg.end());
//     }
//   }

//   typedef std::unordered_map<Vector3d, size_t> PointMap;
//   std::stack<PointMap> point_maps;
//   std::stack<Transform3d> world_transforms;
//   std::unordered_set<std::string> sharedNodesCacheKeys;

// public:
  
//   PointsCollector(const Tree& tree, const std::unordered_set<std::string> &sharedNodesCacheKeys)
//     : AbstractGeometryEvaluator(tree),
//       sharedNodesCacheKeys(sharedNodesCacheKeys)
//   {
//     world_transforms.emplace(Transform3d::Identity());
//     point_maps.emplace(PointMap());
//   }

//   // shared_ptr<const Geometry> evaluateGeometry(const AbstractNode& node, bool allownef);

//   // Response visit(State& state, const AbstractNode& node) override;
//   // Response visit(State& state, const AbstractIntersectionNode& node) override;
//   // Response visit(State& state, const AbstractPolyNode& node) override;
//   // Response visit(State& state, const LinearExtrudeNode& node) override {
//   //   // TODO
//   // }
//   // Response visit(State& state, const RotateExtrudeNode& node) override {
//   //   if (state.isPrefix()) {
//   //     point_maps.emplace(PointMap());
//   //   } else if (state.isPostfix()) {
//   //     auto nested_map(std::move(point_maps.pop());
//   //     // TODO
//   //   }
//   // }
//   // Response visit(State& state, const RoofNode& node) override;
//   // Response visit(State& state, const ListNode& node) override;
//   // Response visit(State& state, const GroupNode& node) override;
//   // Response visit(State& state, const RootNode& node) override;
//   Response visit(State& state, const LeafNode& node) override {
//     if (state.isPrefix()) {
//       processGeometry(node);
//     }
//     return Response::ContinueTraversal;
//   }
//   Response visit(State& state, const TransformNode& node) override {
//     if (state.isPrefix()) {
//       pushTransform(node.matrix);
//     } else if (state.isPostfix()) {
//       popTransform();
//     }
//     return Response::ContinueTraversal;
//   }
//   Response visit(State& state, const CsgOpNode& node) override {
//     if (state.isPrefix()) {
//       if (node.type == OpenSCADOperator::MINKOWSKI) {
//         // TODO
//       }
//     }
//     return Response::ContinueTraversal;
//   }
//   // Response visit(State& state, const CgalAdvNode& node) override;
//   // Response visit(State& state, const ProjectionNode& node) override;
//   // Response visit(State& state, const RenderNode& node) override;
//   Response visit(State& state, const TextNode& node) override {
//     if (state.isPrefix()) {
//       processGeometry(node);
//     }
//     return Response::ContinueTraversal;
//   }
//   Response visit(State& state, const OffsetNode& node) override {
//     if (state.isPrefix()) {
//       // TODO
//     }
//     return Response::ContinueTraversal;
//   }
  
//   // void addToParent(const State& state, const AbstractNode& node, const shared_ptr<const Geometry>& geom);
//   // Response lazyEvaluateRootNode(State& state, const AbstractNode& node);

//   // std::map<int, Geometry::Geometries> visitedchildren;
//   // const Tree& tree;
//   // shared_ptr<const Geometry> root;

// public:
// };