Spatial Querying: Implementation of BVH tree for IFC files using NCollection_UBTree by aothms · Pull Request #130 · IfcOpenShell/IfcOpenShell

aothms · 2016-09-05T12:27:25Z

Rationale

By 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.

Bounding box intersection: 0.000 seconds

Solid volume containment: 0.597 seconds

API

Python

fn = "Duplex_A_20110907_optimized.ifc"
f = ifcopenshell.open(fn)
wall = f["2O2Fr$t4X7Zf8NOew3FLPP"]

tree_settings = ifcopenshell.geom.settings()
tree_settings.set(tree_settings.DISABLE_OPENING_SUBTRACTIONS, True)
t = ifcopenshell.geom.tree(f, tree_settings)

# For multiple files use:
# t = ifcopenshell.geom.tree()
# t.add_file(f, tree_settings)
# t.add_file(...)

print("Intersecting with wall 2O2Fr$t4X7Zf8NOew3FLPP")
print(t.select(wall))

print("Contained within wall 2O2Fr$t4X7Zf8NOew3FLPP")
print(t.select(wall, completely_within=True))

print("Intersecting with bounding box wall 2O2Fr$t4X7Zf8NOew3FLPP")
print(t.select_box(wall))

print("Surrounding bounding box wall 2O2Fr$t4X7Zf8NOew3FLPP")
print(t.select_box(wall, extend=1.))

print("Contained within bounding box wall 2O2Fr$t4X7Zf8NOew3FLPP")
print(t.select_box(wall, extend=0.001, completely_within=True))

print("Containing point (0,0,0)")
print(t.select((0.,0.,0.)))

print("Intersecting with (-1,-1,-1) -> (1,1,1)")
print(t.select_box(((-1.,-1.,-1.),(1.,1.,1.))))

print("Contained within (-2,-2,-2) -> (10,10,10)")
print(t.select_box(((-2.,-2.,-2.),(10.,10.,10.)), completely_within=True))

C++

IfcParse::IfcFile f;
f.Init("Duplex_A_20110907_optimized.ifc");

IfcGeom::IteratorSettings settings;
settings.set(IfcGeom::IteratorSettings::DISABLE_OPENING_SUBTRACTIONS, true);

IfcGeom::tree tree(f, settings);

IfcSchema::IfcWallStandardCase* wall = f.entityByGuid("2O2Fr$t4X7Zf8NOew3FLPP")->as<IfcSchema::IfcWallStandardCase>();

std::cout << "Intersecting with wall 2O2Fr$t4X7Zf8NOew3FLPP" << std::endl;
std::vector<IfcSchema::IfcProduct*> contained = tree.select(wall);

Implementation

Open Cascade NCollection_UBTree

Performance

Nothing conclusive, querying times for bounding boxes below timer resolution for small-medium sized models. Tree construction + geometry generation linearithmic (?).

jf--- · 2016-09-26T07:51:15Z

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? Or are these OCCT >= 7.0 specific?

aothms · 2016-09-26T09:26:10Z

Or are these OCCT >= 7.0 specific?

I guess they are. I used NCollection_UBTree [1]. But I can't find this in the 7.0.1 documentation. Guess they renamed things a bit. Good that you brought this to my attention. Better make it compatible with OCCT 7+ before merging this in :)

Must say it works rather well. Would be quite awesome if this is wrapped in pyOCC. I guess the reason it is not is because it is a templated class to allow some genericity (which SWIG does not automatically wrap). Maybe I will send in a pyOCC PR someday. Really quite a valuable OCCT component.

[1] https://www.opencascade.com/doc/occt-6.9.1/refman/html/class_n_collection___u_b_tree_1_1_tree_node.html

jf--- · 2016-09-26T09:46:15Z

Yeah, so I was ( pleasantly ) surprised by the BVH package myself in OCCT...
made me wonder whether to ditch FCL ( which is insanely fast and works with pointclouds too... )
a PR would be awesome... wrt the templating, would it be possible to just template using a double and call it a day or is it not the numerical type, as in CGAL that requires templating?

aothms · 2016-09-26T09:57:42Z

would it be possible to just template using a double and call it a day or is it not the numerical type, as in CGAL that requires templating

Well there are two template parameters (in 6.9) the type for the bounding box, which I guess is always Bnd_Box and a type that is associated to the bounding volume, maybe either a TopoDS_Shape or PyObject* in the case of pyOCC. In OCCT7 things look rather different.

These BVH trees work well for things that can be divided into distinct elements (e.g. the objects within an IFC file). For point clouds it might work if you are able to create meaningful segmentations or euclidean clusters (e.g using PCL), but otherwise other tree structures (kd-trees etc., not sure what FCL provides) are much more suitable.

jf--- · 2016-09-26T10:49:50Z

yeah, so FCL might be of interest for you, since this can handle pointclouds... that lib has awesome performance and deals well with degenerated geom ( eg non-convex )

jf--- · 2017-01-18T15:54:26Z

@aothms what about the BVH related classes in OCC. Are these of interest?

aothms · 2017-01-22T18:30:26Z

@jf--- Well, I don't know yet what's the relations between [1] and [2]. That's actually the thing I wanted to find out before merging this PR, but didn't get to it yet.

[1] https://dev.opencascade.org/doc/refman/html/class_n_collection___u_b_tree.html
[2] https://dev.opencascade.org/doc/refman/html/class_b_v_h___tree_3_01_t_00_01_n_00_01_b_v_h___binary_tree_01_4.html

AnastasiiaPanteleeva · 2021-01-17T16:31:40Z

Good afternoon,
Could you help me please with my problem? “completely_within” function does not work for me properly.
Despite “completely_within = True”, the result also includes walls that are intersected by the selected box but not completely inside.

my example:

`# -- coding: utf-8 --

import ifcopenshell
import ifcopenshell.geom
import OCC
from OCC.Core.BRepBndLib import brepbndlib_Add

model = ifcopenshell.open("D:\M2\Checker_Test\Duplex_A.ifc")

tree_settings = ifcopenshell.geom.settings()
tree_settings.set(tree_settings.DISABLE_OPENING_SUBTRACTIONS, True)
t = ifcopenshell.geom.tree(model, tree_settings)

elements = t.select_box(((-0.24150015000001304, -22.182734150000012, 6.609000000000000),
(9.041500150000003, 4.38273415000005, 9.000000150000012)),
completely_within = True)

#checking coordinates Z

settings = ifcopenshell.geom.settings()
settings.set(settings.USE_PYTHON_OPENCASCADE, True)
bbox = OCC.Core.Bnd.Bnd_Box()

for element in elements:
if element.is_a("IfcWallStandardCase"):
shape = ifcopenshell.geom.create_shape(settings, element).geometry
brepbndlib_Add (shape, bbox)

MaxZ = bbox.CornerMax().Z()
MinZ = bbox.CornerMin().Z()

print ("the Z - coordinates of the box 6.609000000000000 - 9.000000150000012,
the Z - coordinates of the walls {} - {}".format(MinZ,MaxZ))
`

the Z - coordinates of the box 6.609000000000000 - 9.000000150000012, the Z - coordinates of the walls 5.9999999 - 6.6090001

samiba6 · 2022-06-20T14:30:17Z

Hey @aothms does this tree still reliable to work with ?
thanks for answering 😊

aothms · 2022-06-21T11:08:50Z

@samiba6 sure, has been extended since with things like distances and ray intersection

aothms added 2 commits September 5, 2016 14:13

Implementation of BVH tree for IFC files using NCollection_UBTree

5bc211e

Fixes for gcc and OCCT < v6.8

64a70fb

aothms added 3 commits January 14, 2017 20:15

Enable BVH selection by TopoDS_Shape

63cfe2f

Merge branch 'master' into bvh_tree

aaa58a8

Small fixes to tree

4356258

aothms added 3 commits September 13, 2017 11:40

Merge unconflicted files

04d52f8

Merge conflicted files and other changes

2b9c71e

Eliminate one warning (some remain) + add tree test

a4ad90e

aothms merged commit 96ec925 into IfcOpenShell:master Sep 13, 2017

aothms mentioned this pull request Oct 20, 2020

Plans to include Python convenience API for shape analysis? #1040

Closed

aothms mentioned this pull request Aug 1, 2021

Missing fcl dependency for Blender 2.93 alpha (python 3.9) #1357

Closed

bimintelligence mentioned this pull request Jan 1, 2023

Brep solid from IfcFace #2669

Closed

franseoane mentioned this pull request Nov 15, 2025

Bonsai Fatal Error; Update Bonsai_Windows 10 #7344

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Spatial Querying: Implementation of BVH tree for IFC files using NCollection_UBTree#130

Spatial Querying: Implementation of BVH tree for IFC files using NCollection_UBTree#130
aothms merged 8 commits into
IfcOpenShell:masterfrom
aothms:bvh_tree

aothms commented Sep 5, 2016 •

edited

Loading

Uh oh!

jf--- commented Sep 26, 2016 •

edited

Loading

Uh oh!

aothms commented Sep 26, 2016

Uh oh!

jf--- commented Sep 26, 2016

Uh oh!

aothms commented Sep 26, 2016

Uh oh!

jf--- commented Sep 26, 2016 •

edited

Loading

Uh oh!

jf--- commented Jan 18, 2017

Uh oh!

aothms commented Jan 22, 2017 •

edited

Loading

Uh oh!

AnastasiiaPanteleeva commented Jan 17, 2021

Uh oh!

samiba6 commented Jun 20, 2022

Uh oh!

aothms commented Jun 21, 2022

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

Uh oh!

Conversation

aothms commented Sep 5, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Rationale

Bounding box intersection: 0.000 seconds

Solid volume containment: 0.597 seconds

API

Python

C++

Implementation

Performance

Uh oh!

jf--- commented Sep 26, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

aothms commented Sep 26, 2016

Uh oh!

jf--- commented Sep 26, 2016

Uh oh!

aothms commented Sep 26, 2016

Uh oh!

jf--- commented Sep 26, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

jf--- commented Jan 18, 2017

Uh oh!

aothms commented Jan 22, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

AnastasiiaPanteleeva commented Jan 17, 2021

Uh oh!

samiba6 commented Jun 20, 2022

Uh oh!

aothms commented Jun 21, 2022

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

aothms commented Sep 5, 2016 •

edited

Loading

jf--- commented Sep 26, 2016 •

edited

Loading

jf--- commented Sep 26, 2016 •

edited

Loading

aothms commented Jan 22, 2017 •

edited

Loading