Faster Points in Breps?

Hi all,

I wonder if there’s other ways can make Points in Breps faster?

As the attached shown there’s about 23k points and took the component 4.2s to process. In real go the amount of points would be much higher.

I’ve also tried Mesh Inclusion, however, as guessed in this thread, the points locate on mesh’s edges didn’t get culled so the result was wrong:

This method gets the diagonal vector of the bounding box of the mesh and shoots a ray from the point in that direction. If the number of times the ray intersects with the mesh is odd, the point is inside. (425.7 KB)

Points in Breps

Points in Meshes

With the “Mesh Inclusion” component you are making a datatree matching error.
You are using “Point in Breps” component for breps (notice the plural “s”), but “Mesh inclusion” for the meshes.
“Mesh inclusion” works with a single mesh at time.
In each of your point tree branches the component is testing the first point with the first mesh, second with second, etc etc, and then using the last mesh for all the points until the end (280).

Your points are in an already complex datatree, and making the proper matching to test inclusion to all the meshes is needlessly even more complex.

You can approach this in two ways, and use both at the same time:

  • flatten your point tree (and later unflatten it)
  • join the meshes into a single mesh

Problem: as your breps have some congruent edges, the resulting mesh will have some non-manifold edges, making it fail completely any point inclusion test.
So, first do a solid union of your breps, and only then convert it into a mesh.

About the optimization of the testing, maybe this is related/useful: Subdivided Voxelization:

If possible, explain how your point tree is structured.
Optimization might require starting with larger cells and then sub-sampling.

1 Like

Hi @maje90

Thanks for the reply, thought I did exactly the same as you did but I got 10844 points. Tolerance maybe?
Besides some points locate on mesh faces still not recognized as Inside. What I hope to get is something more similar to collision check I guess.

If possible I’d like to keep the datatree of points for the later use.

I usually have 0.00001 as absolute tolerance and 0.01 for angular… I don’t know why you are having different result though… If I change the tolerances the result doesn’t change.

Can you clarify what you mean with “collision check”.
Also, more generally, it is probably simpler and better if you explain what your final goal is.

Keeping your current point datatree prevent the optimization process. I think re-building the datatree iteratively while subsampling is better. That’s why I ask you to explain how it is structured and what is going on.

For example, if we start with macro-voxels that are 16x16x16 larger than your final “module”, when a macro-voxel center is found inside your mesh, we keep it and later subdivide it, but when it is outside, we check for mesh proximity, and if the distance is larger than a macro-voxel half-diagonal, we discard it and so we also discard 4096 modules, saving a lot of computation time.
Maybe. We are not the first doing this thing. Proper software have surely excellent algorithms to do this. We can just put up some code and hope to optimize it “a bit”.

X,Y,Z grid basically.

In fact as I mentioned Points in Breps already achieved what I need and want (cull out all the points that not only inside Breps but also coincident the surface of Breps), but just slow. Therefore I out-source to Mesh thought it could be faster in terms of process. Maybe I was wrong.

Using a single mesh as I mentioned (first do brep solid union, then converto to a single mesh) is faster.
If you have problem with accuracy, maybe give your mesh a little offset outward…

(If you don’t have weaverbird you can make a one-liner in c# like A=M.Offset(D); )

39 ms seems few to me, but you mentioned a “much higher” amount… that’s why I talked about optimization by sub-sampling…

Thanks, I just did something similar and seem get better.

I’m a bit concern about this “1” solid union, because what if there’re shapes not intersect each other and can not be all union into a single geometry?

Yes! Its much faster than Points in Breps for sure!
The 3d grid of points in the uploaded file is 27(pts)*21(pts)*15(pts), the voxel size is about “10”.
If i go smaller later on, like say “1”, than it becomes 270(pts)*210(pts)*150(pts).
And that’s why I need to find something else other than native Points in Breps.

Not a problem. As said, the solid union is needed only to avoid non-manifold edges in the final mesh.
If you have many disjoint breps, simply convert to them and then also use “Mesh Join” or kangaroo “Combine&Clean” and you’ll have a single mesh. (a single mesh object can be composed of many disjoint pieces)

2022-09-20 22_10_30-Grasshopper - unnamed

… we can try via c#, but the result is a normal 3d grid, until you properly describe how your datatree is structured.
I personally think it would be simpler if you change the rest of your code (before or after this step) to use a more … “intuitive” grid.
Your current one… I am not able to follow it.