Check if cuboids are overlapping as fast as possible (no iteration) in c++

[alexas]

I have a cuboid class where cuboid coordinates are provided as set of arrays:

  Cuboid3D cube_a ({1.0f, 2.0f, 3.0f, 4.0f, 5.0f, 6.0f, 7.0f, 8.0f}, // x coord
                  {2.0f, 4.0f, 3.0f, 7.0f, 2.0f, 9.0f, 5.0f, 2.0f}, // y coord
                  1.0f, 3.0f, 6.0f, 9.0f, 4.0f, 3.0f, 1.0f, 7.0f}); // z coord

  Cuboid3D cube_b ({3.0f, 4.0f, 5.0f, 2.0f, 1.0f, 2.0f, 3.0f, 2.0f}, // x coord
                  {1.0f, 3.0f, 5.0f, 2.0f, 1.0f, 2.0f, 3.0f, 4.0f}, // y coord       
                  {1.0f, 3.0f, 6.0f, 9.0f, 4.0f, 3.0f, 1.0f, 7.0f}); // z coord 

I need to find the fastest way to get true/false result if cubes are intersected in any point. So the typical way to solve this

 if ((cubeA.maxX > cubeB.minX)&& // Determining overlap in the x plane
    (cubeA.minX < cubeB.maxX)&&
    (cubeA.maxY > cubeB.minY)&& // Determining overlap in the y plane
    (cubeA.minY < cubeB.minY)&&
    (cubeA.maxZ > cubeB.minZ)&& // Determining overlap in the z plane 
    (cubeA.minZ < cubeB.maxZ))
        cout<<"not intersecting";

My problem is how to implement this without iteration, i.e. how to compare the points - how to get max min from arrays without iteration. I need this to work as fast as possible as it will be used many times.

[lastchance]

That way of testing for overlap would only work if your cuboids are "axis-aligned". Neither of your example cuboids are axis-aligned. (I'm not actually sure that they are even cuboids - hexahedra, maybe, but not cuboids).

[alexas]

Thank you , it is a good comment. So it seems I am in deeper trouble than I thought.

[dhayden]

It looks to me like your if statement is true when the cuboids do intersection, contrary to the cout statement.

However, that code is about as fast it can be (for axis aligned shapes as lastchance wrote). Any modern computer or phone will execute that if faster than it takes the light to travel from the screen to your eyes.

I need this to work as fast as possible as it will be used many times.

In this case, the question isn't how fast you can compare two shapes, but how can you avoid comparing some shapes altogether. Please describe the problem in a little more detail. Someone is likely to know a fast way to solve it.

[jonnin]

check the radius as if they were spheres first, if the sphere around the cubes are not hitting, the cubes are not either, and that is just a partial distance formula (don't need the sqrts, the squares compare just as well). If the spheres are hitting, you need to go a little deeper, but the rapid elimination of non-candidates should earn you tons of time back.

[lastchance]

I think you should have member variables minX, maxX, minY, maxY, minZ, maxZ of each cuboid. (These should be set on creation and updated only if the shape is transformed.)

Then you will need a finer-grained detailedCheck( cubeA, cubeB ) (which has a high chance of success) for the cases where the limits are OK.

if ( cubeA.maxX > cubeB.minX && 
     cubeA.minX < cubeB.maxX &&
     cubeA.maxY > cubeB.minY && 
     cubeA.minY < cubeB.maxY &&
     cubeA.maxZ > cubeB.minZ && 
     cubeA.minZ < cubeB.maxZ &&
     detailedCheck( cubeA, cubeB ) ) cout << "Intersecting";

I think your detailedCheck() function would need to return true if any one vertex of B is inside A or any one vertex of A is inside B. There are various ways of checking that.

[alexas]

The code will be used in Monte Carlo simulation. The new "cuboids" will be constantly created - sampled - and should be destroyed if they are intersecting with the previously created shapes. It will be repeated billions of time on the supercomputer cluster. I am inexperienced member of team who tries his best to learn c++ in the most complex environment while meantime I am taking some intermediate courses.

What I know - that only "if" should be used, and it should give out information about intersection as soon as it detects it for the new shape.

As an example, I can provide the method used to compare and find identical shapes - I have a feeling that it should be smth very similar

bool
Rectangle3D::operator==(const Rectangle3D& other) const
{
    if (!std::equal(_x_coords.begin(), _x_coords.end(), other._x_coords.begin(), other._x_coords.end(),
                    [&] (const auto &rhs, const auto &lhs) {return std::fabs(rhs - lhs) < 1.0e-13;})) return false;

    if (!std::equal(_y_coords.begin(), _y_coords.end(), other._y_coords.begin(), other._y_coords.end(),
                    [&] (const auto &rhs, const auto &lhs) {return std::fabs(rhs - lhs) < 1.0e-13;})) return false;

    if (!std::equal(_z_coords.begin(), _z_coords.end(), other._z_coords.begin(), other._z_coords.end(),
                    [&] (const auto &rhs, const auto &lhs) {return std::fabs(rhs - lhs) < 1.0e-13;})) return false;

    return true;
}

[jonnin]

_z_coords.begin(), _z_coords.end(),
^^ iteration

your requirement is confusing, you said no iteration but hiding it does not make it go away.
also if statements may or may not be the most efficient way to do things depends on hardware.

here, you can just say bool answer = first condition, answer &= second, answer &= third, return answer and you won't have any ifs -- whether that is faster or not, though, only way to know is to test it. Unnecessary jumps are bad, but many CPU and compilers etc can make them go away. Also here, your ifs let you exit early as soon as you hit false, which saves work. If you take the conditions out, you lose that. I am getting ahead of you though -- before looking at this kind of tweaking, you need to get it working and profile where the slowness is.

equality and touching are completely different concepts. equality is easy. Touching is a little more complicated.

[dhayden]

The new "cuboids" will be constantly created - sampled - and should be destroyed if they are intersecting with the previously created shapes. It will be repeated billions of time on the supercomputer cluster.

If there are lots of shapes to compare against then you need to reduce the number that you'll look out using one of the techniques already discussed. If you really are just looking for the fastest way to compare two shapes then use jonnin's (my preference too) or lastchance's method to do a quick comparison that will rule out distant objects

[alexas]

Sorry for my not very well defined language. When I mentioned no iteration I mean no cycle should be involved like for, etc.

[againtry]

The task you have set yourself is a massive one and I doubt whether knowing a lot or a little about C++ should be at the top of any priority list in climbing a very steep learning curve, especially with billions of objects/collisions, which even an alleged god would have to rationalise.

If a quick fix and a couple of nebulous if's is a solution then I hope you are the one in line for the Nobel (and/or equivalent) that will bring, I hope you do/can :)

Here's a place where I would start
https://en.wikipedia.org/wiki/Collision_detection

I would then follow through with supplementary pointers that article makes and even consult Minkowski's efforts on the subject.

While it might seem strange at first, I would also find out from Blender fracture and physics simulations programmers what the latest is in their open-source field. It's open source albeit often in Python but they have a mountain of runs on the board

I am guessing but this may also be of use as a small indicator of blender activity
https://www.cbcity.de/simple-3d-collision-detection-with-python-scripting-in-blender

:)

[alexas]

Thank you againtry and all other contributors,

Yes you are damn right. It won't be easy solution and it is not possible for a beginner to do. I went deeper into the topic. What I need it is actually described in the separate paper:

Franklin, W. Randolph, and Salles VG Magalhães. "Parallel intersection detection in massive sets of cubes." Proceedings of the 6th ACM SIGSPATIAL Workshop on Analytics for Big Geospatial Data. 2017.

https://wrf.ecse.rpi.edu/p/224-parcube-bigspatial-2017.pdf

[dhayden]

Divide the space into subspaces. Record each cube that is in each subspace, either wholly or partly.

Given a new cube, determine which subspace(s) it's in. Compare it to the existing cubes in those subspaces only.

[jonnin]

not possible for a beginner to do...
I am going to disagree. You found some PH.D level paper on it, which by its nature is going attack the problem in a complicated way. Now, the guy in the paper may have some slick way to do it that beats anything we can do off the cuff and so on, but, you are a beginner and your team knows it.

1) I fully believe you can do it. It won't be easy (its going to take a few weeks instead of a few hours). But its a cube or at least geometric simple shape of some sort, not a random nurbs where you check a jillion normals to figure it out.

2) Your solution may not be the fastest thing ever written. But its only billions and you said its a super computer. If you use one or more of the techniques here that organize the data such that when a new cube appears, you can look at a small set of possible intersecting cubes and ignore the rest, you have a great start. If you can then do the checks on your list of candidates in parallel over the processors you have, it will knock it out very fast.

[lastchance]

@Alexas,
Maybe you should tell us more about YOUR particular "cuboids". Your numerical examples don't correspond to your explanation (or to that paper).

(1) Are they axis-aligned?
If they are, then you would only need SIX pieces of information, not 24; either
(xmin,xmax,ymin,ymax,zmin,zmax) - limits of coordinates
or
( xc, yc, zc, L,W, H ) - centre and three edge lengths.


(2) Are they actually cuboids (orthogonal faces)? Your numerical examples may be hexahedra (six faces), but, while I haven't checked, they don't appear to be cuboids. If it was an arbitrarily-aligned cuboid then it would still only need NINE pieces of information, not 24; e.g.
( xc, yc, zc, L, W, H, nx, ny, nz ) - centre, length of sides, orientation of one edge or axis.


(3) Do these "cuboids" move or get transformed in any way? (You have another thread where you are rotating a figure).


I like @dhayden's suggestion for cutting down the search range. It would work very well in parallel.


The paper that you cite is a conference paper, not a journal paper. If you can look up the authors then you may find that they publish a later (and probably better written) journal paper. Note that a key element of that paper is parallelisation (standard multithreading, OpenMP and use of GPUs/Cuda).


Anyway, could you clear up the precise nature of your "cuboids" first.

[alexas]

thank you very much for your insights. Yes, you are totally right, these are not Cuboids, they are hexahedra as in general the x,y,z arrays can obtain any value. They are enclosures for molecules and will be randomly generated, so it is important not to generate new ones intersecting previously created. I read quite a lot of articles about that yet I feel it is too early for me to fully comprehend what they are trying to state. I was told by my supervisor that we are gonna implement this in a way it is described in the paper I posted before. Problem is that I can't even understand the algorithm idea they wrote - need some "translation" to normal human language
P.S. as you can guess, previously my biggest achievement in programming was the calculator in c++ :) anyway I have no choice only to learn in such steep curve as I was provided for me

[againtry]

@alexas
The article is interesting but my guess is there is much more appropriate info around if you look in the right place. It runs the rsik of being part of (yet another) xy problem starting up.

That aside, you say you have billions of hexahedra all dancing to a Monte Carlo tune.

Given that, I would incorporate some learning curve stuff on numerical methods, scaling, approximations, precision and errors. Why refine the 3d model so much when the inherent errors in the simulation probably outstrip the strictly/mathematically 'correct' coordinate transforms?

Monte Carlo is 'as rough as guts'. The classic approximation to pi by applying MC methods - the Buffon Needle Problem - gets to something like pi eventually but it's pretty slow and fairly rough.

If they are hexahedra why not simplify and assume spheres, or points even? Why use cuboids, or cubes? The whole universe is successfully modelled by cosmologists as points. The whole genome et al is modelled and animated with molecules made up of elements as spheres. For that see: https://www.wehi.edu.au/wehi-tv/animation perhaps talk to them about modelling colliding particles.

Still, none of is meant to be any sort of a stumbling block to your Nobel :)

[alexas]

Update: just to close the topic , I want to say that we chose the simpler way, actually recommended here previously - first we do coarse check when we treat polygons as spheres, and later we do the detail check by converting them to vectors and then checking the intersections.

[againtry]

Close the topic by green ticking it.

[jonnin]

It may be useful to keep a list of all sorted by the distance of each from center of the universe (0,0 hopefully) as well, to make this idea a little slicker? It only works if the radii are generally smallish, that is if you have giant things in the 'corners' that can take up 1/2 the universe, its kinda pointless, but if they are molecules and all about the same size, it will help.