{"action":"created","issue":{"url":"https://api.github.com/repos/IfcOpenShell/IfcOpenShell/issues/130","repository_url":"https://api.github.com/repos/IfcOpenShell/IfcOpenShell","labels_url":"https://api.github.com/repos/IfcOpenShell/IfcOpenShell/issues/130/labels{/name}","comments_url":"https://api.github.com/repos/IfcOpenShell/IfcOpenShell/issues/130/comments","events_url":"https://api.github.com/repos/IfcOpenShell/IfcOpenShell/issues/130/events","html_url":"https://github.com/IfcOpenShell/IfcOpenShell/pull/130","id":175061053,"number":130,"title":"Spatial Querying: Implementation of BVH tree for IFC files using NCollection_UBTree","user":{"login":"aothms","id":1096535,"avatar_url":"https://avatars.githubusercontent.com/u/1096535?v=3","gravatar_id":"","url":"https://api.github.com/users/aothms","html_url":"https://github.com/aothms","followers_url":"https://api.github.com/users/aothms/followers","following_url":"https://api.github.com/users/aothms/following{/other_user}","gists_url":"https://api.github.com/users/aothms/gists{/gist_id}","starred_url":"https://api.github.com/users/aothms/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/aothms/subscriptions","organizations_url":"https://api.github.com/users/aothms/orgs","repos_url":"https://api.github.com/users/aothms/repos","events_url":"https://api.github.com/users/aothms/events{/privacy}","received_events_url":"https://api.github.com/users/aothms/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":1,"created_at":"2016-09-05T12:27:25Z","updated_at":"2016-09-26T07:51:15Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/IfcOpenShell/IfcOpenShell/pulls/130","html_url":"https://github.com/IfcOpenShell/IfcOpenShell/pull/130","diff_url":"https://github.com/IfcOpenShell/IfcOpenShell/pull/130.diff","patch_url":"https://github.com/IfcOpenShell/IfcOpenShell/pull/130.patch"},"body":"# Rationale\r\nBy arranging the bounding volumes into a bounding volume hierarchy, the time complexity (the number of tests performed) can be reduced to logarithmic in the number of objects. With such a hierarchy in place, during collision testing, children volumes do not have to be examined if their parent volumes are not intersected. From [wikipedia](https://en.wikipedia.org/wiki/Bounding_volume_hierarchy).\r\n\r\n#### Bounding box intersection: 0.000 seconds\r\n![Bounding box intersection](https://cloud.githubusercontent.com/assets/1096535/18247480/1fc1c2a6-7373-11e6-8723-b42014385312.png)\r\n#### Solid volume containment: 0.597 seconds\r\n![Solid volume containment](https://cloud.githubusercontent.com/assets/1096535/18247481/1fc34040-7373-11e6-9c64-67d90264c7fd.png)\r\n\r\n# API\r\n\r\n### Python\r\n\r\n~~~\r\nfn = \"Duplex_A_20110907_optimized.ifc\"\r\nf = ifcopenshell.open(fn)\r\nwall = f[\"2O2Fr$t4X7Zf8NOew3FLPP\"]\r\n\r\ntree_settings = ifcopenshell.geom.settings()\r\ntree_settings.set(tree_settings.DISABLE_OPENING_SUBTRACTIONS, True)\r\nt = ifcopenshell.geom.tree(f, tree_settings)\r\n\r\n# For multiple files use:\r\n# t = ifcopenshell.geom.tree()\r\n# t.add_file(f, tree_settings)\r\n# t.add_file(...)\r\n\r\nprint(\"Intersecting with wall 2O2Fr$t4X7Zf8NOew3FLPP\")\r\nprint(t.select(wall))\r\n\r\nprint(\"Contained within wall 2O2Fr$t4X7Zf8NOew3FLPP\")\r\nprint(t.select(wall, completely_within=True))\r\n\r\nprint(\"Intersecting with bounding box wall 2O2Fr$t4X7Zf8NOew3FLPP\")\r\nprint(t.select_box(wall))\r\n\r\nprint(\"Surrounding bounding box wall 2O2Fr$t4X7Zf8NOew3FLPP\")\r\nprint(t.select_box(wall, extend=1.))\r\n\r\nprint(\"Contained within bounding box wall 2O2Fr$t4X7Zf8NOew3FLPP\")\r\nprint(t.select_box(wall, extend=0.001, completely_within=True))\r\n\r\nprint(\"Containing point (0,0,0)\")\r\nprint(t.select((0.,0.,0.)))\r\n\r\nprint(\"Intersecting with (-1,-1,-1) -> (1,1,1)\")\r\nprint(t.select_box(((-1.,-1.,-1.),(1.,1.,1.))))\r\n\r\nprint(\"Contained within (-2,-2,-2) -> (10,10,10)\")\r\nprint(t.select_box(((-2.,-2.,-2.),(10.,10.,10.)), completely_within=True))\r\n~~~\r\n\r\n### C++\r\n\r\n~~~\r\nIfcParse::IfcFile f;\r\nf.Init(\"Duplex_A_20110907_optimized.ifc\");\r\n\r\nIfcGeom::IteratorSettings settings;\r\nsettings.set(IfcGeom::IteratorSettings::DISABLE_OPENING_SUBTRACTIONS, true);\r\n\r\nIfcGeom::tree tree(f, settings);\r\n\r\nIfcSchema::IfcWallStandardCase* wall = f.entityByGuid(\"2O2Fr$t4X7Zf8NOew3FLPP\")->as<IfcSchema::IfcWallStandardCase>();\r\n\r\nstd::cout << \"Intersecting with wall 2O2Fr$t4X7Zf8NOew3FLPP\" << std::endl;\r\nstd::vector<IfcSchema::IfcProduct*> contained = tree.select(wall);\r\n~~~\r\n\r\n# Implementation\r\nOpen Cascade [NCollection_UBTree](https://www.opencascade.com/doc/occt-6.9.1/refman/html/class_n_collection___u_b_tree_1_1_tree_node.html)\r\n\r\n# Performance\r\nNothing conclusive, querying times for bounding boxes below timer resolution for small-medium sized models. Tree construction + geometry generation linearithmic (?).\r\n\r\n![treestats](https://cloud.githubusercontent.com/assets/1096535/18247561/8f64dcf6-7373-11e6-9299-631748b53ce6.png)\r\n\r\n"},"comment":{"url":"https://api.github.com/repos/IfcOpenShell/IfcOpenShell/issues/comments/249502222","html_url":"https://github.com/IfcOpenShell/IfcOpenShell/pull/130#issuecomment-249502222","issue_url":"https://api.github.com/repos/IfcOpenShell/IfcOpenShell/issues/130","id":249502222,"user":{"login":"jf---","id":620988,"avatar_url":"https://avatars.githubusercontent.com/u/620988?v=3","gravatar_id":"","url":"https://api.github.com/users/jf---","html_url":"https://github.com/jf---","followers_url":"https://api.github.com/users/jf---/followers","following_url":"https://api.github.com/users/jf---/following{/other_user}","gists_url":"https://api.github.com/users/jf---/gists{/gist_id}","starred_url":"https://api.github.com/users/jf---/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jf---/subscriptions","organizations_url":"https://api.github.com/users/jf---/orgs","repos_url":"https://api.github.com/users/jf---/repos","events_url":"https://api.github.com/users/jf---/events{/privacy}","received_events_url":"https://api.github.com/users/jf---/received_events","type":"User","site_admin":false},"created_at":"2016-09-26T07:51:15Z","updated_at":"2016-09-26T07:51:15Z","body":"interesting work... I've been integrating collision detection with the cython FCL wrappers, hence my curiosity. OCC has a BVH package, [have you looked into it](https://dev.opencascade.org/doc/refman/html/package_bvh.html)? "}}
{"actor":{"display_login":"jf---"}}