{"action":"created","comment":{"url":"https://api.github.com/repos/mosra/magnum-extras/pulls/comments/44733077","id":44733077,"diff_hunk":"@@ -0,0 +1,344 @@\n+/*\n+    This file is part of Magnum.\n+\n+    Copyright © 2010, 2011, 2012, 2013, 2014, 2015\n+              Vladimír Vondruš <mosra@centrum.cz>\n+    Copyright © 2015 Andrea Capobianco <andrea.c.2205@gmail.com>\n+    Copyright © 2015 Jonathan Hale <squareys@googlemail.com>\n+\n+    Permission is hereby granted, free of charge, to any person obtaining a\n+    copy of this software and associated documentation files (the \"Software\"),\n+    to deal in the Software without restriction, including without limitation\n+    the rights to use, copy, modify, merge, publish, distribute, sublicense,\n+    and/or sell copies of the Software, and to permit persons to whom the\n+    Software is furnished to do so, subject to the following conditions:\n+\n+    The above copyright notice and this permission notice shall be included\n+    in all copies or substantial portions of the Software.\n+\n+    THE SOFTWARE IS PROVIDED \"AS IS\", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\n+    IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\n+    FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL\n+    THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\n+    LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING\n+    FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER\n+    DEALINGS IN THE SOFTWARE.\n+*/\n+\n+#include <Magnum/Math/Functions.h>\n+\n+#include <stdio.h>\n+#include <stdlib.h>\n+#include \"Octree.h\"\n+\n+namespace Magnum { namespace Octree {\n+\n+/* Function is called for the root node only, to create the initial bounding box */\n+template <typename T>\n+Octree<T>& Octree<T>::createInitialBounds(const std::vector<Shapes::AxisAlignedBox3D>& points, Int maxDepth) {\n+\n+    _center = {0, 0, 0};\n+    _radius = 0.f;\n+    _depth = maxDepth;\n+    _isLeafNode = true;\n+\n+    Vector3 min {points.at(0).min()};\n+    Vector3 max {points.at(0).max()};\n+\n+    /* find minimal and maximal x,y,z in the data points */\n+    for(auto point : points) {\n+        min = Math::min(point.min(), min);\n+        max = Math::max(point.max(), max);\n+    }\n+\n+    const Vector3 radius = max - min;\n+\n+    /* bounds should be squared, not rectangular. Take the largest radius. */\n+    _radius = radius.max() * 0.5f;\n+\n+    /* find the center of the bounding box */\n+    _center = min + Vector3 {_radius};\n+\n+    return *this;\n+}\n+\n+/* insert operation. At the moment every leaf has exactly one data point. Depth is unlimited. */\n+template <typename T>\n+Octree<T>& Octree<T>::insert(const Shapes::AxisAlignedBox3D& point, T data) {\n+\n+    /*\n+     * Use a simple code for making traversion simple, by using bitwise or operations\n+     * < means, that the childs coordinate is less than the coordinate of the center of the current node\n+     * > means greater than\n+     * e.g. child[3].x < center.x, child[3].y > center.y, child[3].z > center.z\n+     * child:\t0 1 2 3 4 5 6 7\n+     * x:       < < < < > > > >\n+     * y:       < < > > < < > >\n+     * z:       < > < > < > < >\n+     */\n+\n+    if(isLeafNode()) {\n+        /* maximum depth is reached */\n+        if(_depth == 0 || _entries.size() == 0) {\n+            _entries.push_back(point);\n+            _data.push_back(data);\n+            return *this;\n+        } else {\n+            /* max depth isn't reached yet -> split node */\n+\n+            /*\n+             * if node is a leaf, max depth isn't reached and it contains more than a point,\n+             * it means that the contained points are too large to fit in a child node.\n+             * This means, looking at only the first point, still works.\n+             */\n+\n+            /* if max depth isn't reached, it means, in the leaf node was exactly one point */\n+            const Shapes::AxisAlignedBox3D& oldPoint = _entries.at(0);\n+            const T oldData = _data.at(0);\n+\n+            /*\n+             * {-0.5, -0.5, -0.5},\n+             * {-0.5, -0.5, +0.5},\n+             * {-0.5, +0.5, -0.5},\n+             * {-0.5, +0.5, +0.5},\n+             * {+0.5, -0.5, -0.5},\n+             * {+0.5, -0.5, +0.5},\n+             * {+0.5, +0.5, -0.5},\n+             * {+0.5, +0.5, +0.5}\n+             */\n+            Int octContainingBox = getOctantContainingBox(point);\n+            Int octContainingOldBox = getOctantContainingBox(oldPoint);\n+\n+            if((octContainingOldBox != -1) || (octContainingBox != -1)) {\n+\n+                /* create the 8 new children */\n+                for(int i = 0; i < 8; ++i) {\n+                    _children[i] = new Octree{\n+                        _center + (_radius * Vector3 {\n+                            (i & 4 ? 0.5f : -0.5f),\n+                            (i & 2 ? 0.5f : -0.5f),\n+                            (i & 1 ? 0.5f : -0.5f)}),","path":"src/Magnum/Octree/Octree.hpp","position":120,"original_position":120,"commit_id":"46e739ee4971e802b8cffa9c78205a03235bcde8","original_commit_id":"8c29e48b41c998a56633adb46212519c591713f5","user":{"login":"mosra","id":344828,"avatar_url":"https://avatars.githubusercontent.com/u/344828?v=3","gravatar_id":"","url":"https://api.github.com/users/mosra","html_url":"https://github.com/mosra","followers_url":"https://api.github.com/users/mosra/followers","following_url":"https://api.github.com/users/mosra/following{/other_user}","gists_url":"https://api.github.com/users/mosra/gists{/gist_id}","starred_url":"https://api.github.com/users/mosra/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mosra/subscriptions","organizations_url":"https://api.github.com/users/mosra/orgs","repos_url":"https://api.github.com/users/mosra/repos","events_url":"https://api.github.com/users/mosra/events{/privacy}","received_events_url":"https://api.github.com/users/mosra/received_events","type":"User","site_admin":false},"body":"With mosra/magnum@247d8dba6f9fcbaf313e695d516c082ac70fb410 it might be possible to rewrite this as:\r\n\r\n```cpp\r\nMath::lerp(Vector3{-0.5f}, Vector3{0.5f}, Math::BoolVector<3>{UnsignedByte{i}})\r\n```\r\n\r\n... but it's in reverse order, so then something like `Math::swizzle<'z', 'y', 'x'>()` (or maybe there's some other more clever solution that avoids the reordering, I don't know). Mentioning it just in case you find it useful somewhere.","created_at":"2015-11-12T23:49:18Z","updated_at":"2015-11-12T23:49:18Z","html_url":"https://github.com/mosra/magnum-extras/pull/1#discussion_r44733077","pull_request_url":"https://api.github.com/repos/mosra/magnum-extras/pulls/1","_links":{"self":{"href":"https://api.github.com/repos/mosra/magnum-extras/pulls/comments/44733077"},"html":{"href":"https://github.com/mosra/magnum-extras/pull/1#discussion_r44733077"},"pull_request":{"href":"https://api.github.com/repos/mosra/magnum-extras/pulls/1"}}},"pull_request":{"url":"https://api.github.com/repos/mosra/magnum-extras/pulls/1","id":50444026,"html_url":"https://github.com/mosra/magnum-extras/pull/1","diff_url":"https://github.com/mosra/magnum-extras/pull/1.diff","patch_url":"https://github.com/mosra/magnum-extras/pull/1.patch","issue_url":"https://api.github.com/repos/mosra/magnum-extras/issues/1","number":1,"state":"open","locked":false,"title":"[WIP] View Frustrum Culling using Octrees","user":{"login":"ACapo","id":7528007,"avatar_url":"https://avatars.githubusercontent.com/u/7528007?v=3","gravatar_id":"","url":"https://api.github.com/users/ACapo","html_url":"https://github.com/ACapo","followers_url":"https://api.github.com/users/ACapo/followers","following_url":"https://api.github.com/users/ACapo/following{/other_user}","gists_url":"https://api.github.com/users/ACapo/gists{/gist_id}","starred_url":"https://api.github.com/users/ACapo/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ACapo/subscriptions","organizations_url":"https://api.github.com/users/ACapo/orgs","repos_url":"https://api.github.com/users/ACapo/repos","events_url":"https://api.github.com/users/ACapo/events{/privacy}","received_events_url":"https://api.github.com/users/ACapo/received_events","type":"User","site_admin":false},"body":"Hello @mosra,\r\nthis is what I've been working on together with @Squareys for the last few months. It's in a working state but there's still some cleanup work to do. I'd appreciate if you could take a look at the code and point out major issues you find.\r\n\r\nGreetings,\r\n@ACapo\r\n","created_at":"2015-11-11T22:13:05Z","updated_at":"2015-11-12T23:49:18Z","closed_at":null,"merged_at":null,"merge_commit_sha":"db9179b1444059c5c012714378df4a8da3a0cf0d","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/mosra/magnum-extras/pulls/1/commits","review_comments_url":"https://api.github.com/repos/mosra/magnum-extras/pulls/1/comments","review_comment_url":"https://api.github.com/repos/mosra/magnum-extras/pulls/comments{/number}","comments_url":"https://api.github.com/repos/mosra/magnum-extras/issues/1/comments","statuses_url":"https://api.github.com/repos/mosra/magnum-extras/statuses/46e739ee4971e802b8cffa9c78205a03235bcde8","head":{"label":"Squareys:octree","ref":"octree","sha":"46e739ee4971e802b8cffa9c78205a03235bcde8","user":{"login":"Squareys","id":1889284,"avatar_url":"https://avatars.githubusercontent.com/u/1889284?v=3","gravatar_id":"","url":"https://api.github.com/users/Squareys","html_url":"https://github.com/Squareys","followers_url":"https://api.github.com/users/Squareys/followers","following_url":"https://api.github.com/users/Squareys/following{/other_user}","gists_url":"https://api.github.com/users/Squareys/gists{/gist_id}","starred_url":"https://api.github.com/users/Squareys/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Squareys/subscriptions","organizations_url":"https://api.github.com/users/Squareys/orgs","repos_url":"https://api.github.com/users/Squareys/repos","events_url":"https://api.github.com/users/Squareys/events{/privacy}","received_events_url":"https://api.github.com/users/Squareys/received_events","type":"User","site_admin":false},"repo":{"id":45945462,"name":"magnum-extras","full_name":"Squareys/magnum-extras","owner":{"login":"Squareys","id":1889284,"avatar_url":"https://avatars.githubusercontent.com/u/1889284?v=3","gravatar_id":"","url":"https://api.github.com/users/Squareys","html_url":"https://github.com/Squareys","followers_url":"https://api.github.com/users/Squareys/followers","following_url":"https://api.github.com/users/Squareys/following{/other_user}","gists_url":"https://api.github.com/users/Squareys/gists{/gist_id}","starred_url":"https://api.github.com/users/Squareys/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Squareys/subscriptions","organizations_url":"https://api.github.com/users/Squareys/orgs","repos_url":"https://api.github.com/users/Squareys/repos","events_url":"https://api.github.com/users/Squareys/events{/privacy}","received_events_url":"https://api.github.com/users/Squareys/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/Squareys/magnum-extras","description":"Extras for Magnum graphics engine http://mosra.cz/blog/magnum.php","fork":true,"url":"https://api.github.com/repos/Squareys/magnum-extras","forks_url":"https://api.github.com/repos/Squareys/magnum-extras/forks","keys_url":"https://api.github.com/repos/Squareys/magnum-extras/keys{/key_id}","collaborators_url":"https://api.github.com/repos/Squareys/magnum-extras/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/Squareys/magnum-extras/teams","hooks_url":"https://api.github.com/repos/Squareys/magnum-extras/hooks","issue_events_url":"https://api.github.com/repos/Squareys/magnum-extras/issues/events{/number}","events_url":"https://api.github.com/repos/Squareys/magnum-extras/events","assignees_url":"https://api.github.com/repos/Squareys/magnum-extras/assignees{/user}","branches_url":"https://api.github.com/repos/Squareys/magnum-extras/branches{/branch}","tags_url":"https://api.github.com/repos/Squareys/magnum-extras/tags","blobs_url":"https://api.github.com/repos/Squareys/magnum-extras/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/Squareys/magnum-extras/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/Squareys/magnum-extras/git/refs{/sha}","trees_url":"https://api.github.com/repos/Squareys/magnum-extras/git/trees{/sha}","statuses_url":"https://api.github.com/repos/Squareys/magnum-extras/statuses/{sha}","languages_url":"https://api.github.com/repos/Squareys/magnum-extras/languages","stargazers_url":"https://api.github.com/repos/Squareys/magnum-extras/stargazers","contributors_url":"https://api.github.com/repos/Squareys/magnum-extras/contributors","subscribers_url":"https://api.github.com/repos/Squareys/magnum-extras/subscribers","subscription_url":"https://api.github.com/repos/Squareys/magnum-extras/subscription","commits_url":"https://api.github.com/repos/Squareys/magnum-extras/commits{/sha}","git_commits_url":"https://api.github.com/repos/Squareys/magnum-extras/git/commits{/sha}","comments_url":"https://api.github.com/repos/Squareys/magnum-extras/comments{/number}","issue_comment_url":"https://api.github.com/repos/Squareys/magnum-extras/issues/comments{/number}","contents_url":"https://api.github.com/repos/Squareys/magnum-extras/contents/{+path}","compare_url":"https://api.github.com/repos/Squareys/magnum-extras/compare/{base}...{head}","merges_url":"https://api.github.com/repos/Squareys/magnum-extras/merges","archive_url":"https://api.github.com/repos/Squareys/magnum-extras/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/Squareys/magnum-extras/downloads","issues_url":"https://api.github.com/repos/Squareys/magnum-extras/issues{/number}","pulls_url":"https://api.github.com/repos/Squareys/magnum-extras/pulls{/number}","milestones_url":"https://api.github.com/repos/Squareys/magnum-extras/milestones{/number}","notifications_url":"https://api.github.com/repos/Squareys/magnum-extras/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/Squareys/magnum-extras/labels{/name}","releases_url":"https://api.github.com/repos/Squareys/magnum-extras/releases{/id}","created_at":"2015-11-10T22:48:52Z","updated_at":"2015-11-10T22:48:53Z","pushed_at":"2015-11-12T22:51:09Z","git_url":"git://github.com/Squareys/magnum-extras.git","ssh_url":"git@github.com:Squareys/magnum-extras.git","clone_url":"https://github.com/Squareys/magnum-extras.git","svn_url":"https://github.com/Squareys/magnum-extras","homepage":null,"size":111,"stargazers_count":0,"watchers_count":0,"language":"CMake","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"mosra:master","ref":"master","sha":"9dc641372f3dee138753f84550c0bc365024ae2a","user":{"login":"mosra","id":344828,"avatar_url":"https://avatars.githubusercontent.com/u/344828?v=3","gravatar_id":"","url":"https://api.github.com/users/mosra","html_url":"https://github.com/mosra","followers_url":"https://api.github.com/users/mosra/followers","following_url":"https://api.github.com/users/mosra/following{/other_user}","gists_url":"https://api.github.com/users/mosra/gists{/gist_id}","starred_url":"https://api.github.com/users/mosra/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mosra/subscriptions","organizations_url":"https://api.github.com/users/mosra/orgs","repos_url":"https://api.github.com/users/mosra/repos","events_url":"https://api.github.com/users/mosra/events{/privacy}","received_events_url":"https://api.github.com/users/mosra/received_events","type":"User","site_admin":false},"repo":{"id":40245189,"name":"magnum-extras","full_name":"mosra/magnum-extras","owner":{"login":"mosra","id":344828,"avatar_url":"https://avatars.githubusercontent.com/u/344828?v=3","gravatar_id":"","url":"https://api.github.com/users/mosra","html_url":"https://github.com/mosra","followers_url":"https://api.github.com/users/mosra/followers","following_url":"https://api.github.com/users/mosra/following{/other_user}","gists_url":"https://api.github.com/users/mosra/gists{/gist_id}","starred_url":"https://api.github.com/users/mosra/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mosra/subscriptions","organizations_url":"https://api.github.com/users/mosra/orgs","repos_url":"https://api.github.com/users/mosra/repos","events_url":"https://api.github.com/users/mosra/events{/privacy}","received_events_url":"https://api.github.com/users/mosra/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/mosra/magnum-extras","description":"Extras for Magnum graphics engine http://mosra.cz/blog/magnum.php","fork":false,"url":"https://api.github.com/repos/mosra/magnum-extras","forks_url":"https://api.github.com/repos/mosra/magnum-extras/forks","keys_url":"https://api.github.com/repos/mosra/magnum-extras/keys{/key_id}","collaborators_url":"https://api.github.com/repos/mosra/magnum-extras/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/mosra/magnum-extras/teams","hooks_url":"https://api.github.com/repos/mosra/magnum-extras/hooks","issue_events_url":"https://api.github.com/repos/mosra/magnum-extras/issues/events{/number}","events_url":"https://api.github.com/repos/mosra/magnum-extras/events","assignees_url":"https://api.github.com/repos/mosra/magnum-extras/assignees{/user}","branches_url":"https://api.github.com/repos/mosra/magnum-extras/branches{/branch}","tags_url":"https://api.github.com/repos/mosra/magnum-extras/tags","blobs_url":"https://api.github.com/repos/mosra/magnum-extras/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/mosra/magnum-extras/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/mosra/magnum-extras/git/refs{/sha}","trees_url":"https://api.github.com/repos/mosra/magnum-extras/git/trees{/sha}","statuses_url":"https://api.github.com/repos/mosra/magnum-extras/statuses/{sha}","languages_url":"https://api.github.com/repos/mosra/magnum-extras/languages","stargazers_url":"https://api.github.com/repos/mosra/magnum-extras/stargazers","contributors_url":"https://api.github.com/repos/mosra/magnum-extras/contributors","subscribers_url":"https://api.github.com/repos/mosra/magnum-extras/subscribers","subscription_url":"https://api.github.com/repos/mosra/magnum-extras/subscription","commits_url":"https://api.github.com/repos/mosra/magnum-extras/commits{/sha}","git_commits_url":"https://api.github.com/repos/mosra/magnum-extras/git/commits{/sha}","comments_url":"https://api.github.com/repos/mosra/magnum-extras/comments{/number}","issue_comment_url":"https://api.github.com/repos/mosra/magnum-extras/issues/comments{/number}","contents_url":"https://api.github.com/repos/mosra/magnum-extras/contents/{+path}","compare_url":"https://api.github.com/repos/mosra/magnum-extras/compare/{base}...{head}","merges_url":"https://api.github.com/repos/mosra/magnum-extras/merges","archive_url":"https://api.github.com/repos/mosra/magnum-extras/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/mosra/magnum-extras/downloads","issues_url":"https://api.github.com/repos/mosra/magnum-extras/issues{/number}","pulls_url":"https://api.github.com/repos/mosra/magnum-extras/pulls{/number}","milestones_url":"https://api.github.com/repos/mosra/magnum-extras/milestones{/number}","notifications_url":"https://api.github.com/repos/mosra/magnum-extras/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/mosra/magnum-extras/labels{/name}","releases_url":"https://api.github.com/repos/mosra/magnum-extras/releases{/id}","created_at":"2015-08-05T12:56:56Z","updated_at":"2015-10-10T12:53:29Z","pushed_at":"2015-11-12T22:51:10Z","git_url":"git://github.com/mosra/magnum-extras.git","ssh_url":"git@github.com:mosra/magnum-extras.git","clone_url":"https://github.com/mosra/magnum-extras.git","svn_url":"https://github.com/mosra/magnum-extras","homepage":null,"size":188,"stargazers_count":0,"watchers_count":0,"language":"CMake","has_issues":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":1,"mirror_url":null,"open_issues_count":1,"forks":1,"open_issues":1,"watchers":0,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/mosra/magnum-extras/pulls/1"},"html":{"href":"https://github.com/mosra/magnum-extras/pull/1"},"issue":{"href":"https://api.github.com/repos/mosra/magnum-extras/issues/1"},"comments":{"href":"https://api.github.com/repos/mosra/magnum-extras/issues/1/comments"},"review_comments":{"href":"https://api.github.com/repos/mosra/magnum-extras/pulls/1/comments"},"review_comment":{"href":"https://api.github.com/repos/mosra/magnum-extras/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/mosra/magnum-extras/pulls/1/commits"},"statuses":{"href":"https://api.github.com/repos/mosra/magnum-extras/statuses/46e739ee4971e802b8cffa9c78205a03235bcde8"}}}}