From 51e25316e8dbb9383f8d296a649abdaf4bc249ce Mon Sep 17 00:00:00 2001
From: Matt Keeter <matt.j.keeter@gmail.com>
Date: Sat, 22 Mar 2014 12:54:06 -0400
Subject: [PATCH] Adding hash-based mesh loading (better big-O)

---
 src/loader.cpp |  8 ++++++++
 src/mesh.cpp   | 53 ++++++++++++++++++++++++++++++++++++++++++++++++++
 src/mesh.h     |  1 +
 3 files changed, 62 insertions(+)

diff --git a/src/loader.cpp b/src/loader.cpp
index 4131d02..f0f4268 100644
--- a/src/loader.cpp
+++ b/src/loader.cpp
@@ -8,6 +8,14 @@ Loader::Loader(QObject* parent, const QString& filename)
 
 void Loader::run()
 {
+    QTime timer;
+    timer.start();
     emit got_mesh(Mesh::load_stl(filename));
+    qDebug() << "Sorted:" << timer.elapsed();
+
+    timer.start();
+    emit got_mesh(Mesh::load_stl_hash(filename));
+    qDebug() << "Hash:" << timer.elapsed();
+
     emit loaded_file(filename);
 }
diff --git a/src/mesh.cpp b/src/mesh.cpp
index 36ad10e..6520741 100644
--- a/src/mesh.cpp
+++ b/src/mesh.cpp
@@ -56,6 +56,59 @@ typedef std::pair<Vec3, GLuint> Vec3i;
 
 ////////////////////////////////////////////////////////////////////////////////
 
+Mesh* Mesh::load_stl_hash(const QString& filename)
+{
+    QFile file(filename);
+    file.open(QIODevice::ReadOnly);
+
+    QDataStream data(&file);
+    data.setByteOrder(QDataStream::LittleEndian);
+    data.setFloatingPointPrecision(QDataStream::SinglePrecision);
+
+    // Skip .stl file header
+    data.skipRawData(80);
+
+    // Load the triangle count from the .stl file
+    uint32_t tri_count;
+    data >> tri_count;
+
+    // This vector will store triangles as sets of 3 indices
+    std::vector<GLuint> indices(tri_count * 3);
+
+    std::vector<GLfloat> verts;
+    verts.reserve(tri_count * 9);
+
+    QHash<QByteArray, GLuint> map;
+    map.reserve(tri_count * 3);
+
+    float xyz[3];
+    QByteArray v(sizeof(xyz), 0);
+    for (unsigned i=0; i < tri_count; ++i)
+    {
+        // Skip face's normal vector
+        data.skipRawData(3*sizeof(float));
+
+        for (int j=0; j < 3; ++j)
+        {
+            data >> xyz[0] >> xyz[1] >> xyz[2];
+            memcpy(v.data(), xyz, sizeof(xyz));
+            if (!map.contains(v))
+            {
+                map[v] = verts.size() / 3;
+                verts.push_back(xyz[0]);
+                verts.push_back(xyz[1]);
+                verts.push_back(xyz[2]);
+            }
+            indices[i*3 + j] = map[v];
+        }
+
+        // Skip face attribute
+        data.skipRawData(sizeof(uint16_t));
+    }
+
+    return new Mesh(verts, indices);
+}
+
 Mesh* Mesh::load_stl(const QString& filename)
 {
     QFile file(filename);
diff --git a/src/mesh.h b/src/mesh.h
index f83a477..80f2a1e 100644
--- a/src/mesh.h
+++ b/src/mesh.h
@@ -11,6 +11,7 @@ class Mesh
 public:
     Mesh(std::vector<GLfloat> vertices, std::vector<GLuint> indices);
     static Mesh* load_stl(const QString& filename);
+    static Mesh* load_stl_hash(const QString& filename);
 
     float min(size_t start) const;
     float max(size_t start) const;
-- 
2.39.2