If there are bunches of vertexes in some arbitrary space, probably more than 8,
I want to test in groups of 8,
if they form a cube.
If they do, I group them into the same id,
then test the next group?
Any ideas?
Thanks
Jack

There's probably some good algorithm to do this which I don't know about, so I'm cooking up my own wild-ass idea:

If you have a huge number of vertices, your problem will be that doing deeply nested loops to brute force search for cubes would take FOREVER.



Broad phase:

Cubes have 12 edges of the same length which are arranged orthogonally (without that constraint you could have a parallelepiped).

Create a list of tuples for all pairs of verts: (vert a, vert b, squared distance between them). (If you have a minimum or maximum acceptable size for your cube, apply that here before wasting time adding to the list.)

Sort the list by squared distance (or any alternative method you can think of that lets you traverse the list once ordered by distance).

Scan linearly and look for 12+ consecutive entries with the same squared length (within whatever tolerance you want).
If you want to eliminate parallelepipeds at this point, look for 12+ vertices with twice the squared length - these will be the face diagonals.
If you find a set, pass those to narrow phase:

Narrow phase (naive brute force; there are probably better ways to do this):

- (loops 1 and 2) Pick arbitrary vertices A, B.
-- (loop 3) Add vertex C if AC is orthogonal to AB.
--- (loop 4) Add vertex D if AD is orthogonal to AB and AC.
---- Calculate where vertices E, F, G and H should be (the other four corners) and check to see if they exist within your batch.
----- If all vertices are found, you have a cube!

To prevent finding duplicate cubes with different vertex order, make sure that each nested loop does not consider vertices that any outer loop has checked already.

i.e. a standard combination loop like this:

for (int a = 0; a < N-(number of loops nested inside this one); ++a)
{
  for (int b = a+1; b < N-(number of loops nested inside this one); ++b)
  {
    // etc.
  }
}

Whether or not the broad phase plus the narrow phase has any advantage over just the narrow phase alone depends on whether you have enough non-cube vertices to warrant the pair distance calculation and sorting operation or not.

If you know anything else about the vertices (like, you know they're all evenly spaced on a grid, or you know they are all part of cubes) then there could be scenario-specific algorithms you could use to find cubes much more quickly.

Besides the huge costs in triple nested loops, you'll likely run into rounding error problems with the orthogonality check, at least in the general case.

Basically, the "is part of cube" information was destroyed when switching to vertices.

If possible, a simpler approach could be to attach a unique number to each cube, and keep that number in the vertex data.

Honestly, the best way I can think of it is to make a graph out of the vertices.

Every vert must connect to every vert. That is to say that for N number of Verts. Each Vert has a degree of N.

First phase would probably be to check the angle between a vertex. Obviously you would need a list of some sort. Well, you could probably check a whole mess of stuff at once for every edge look up. If you get a failed edge, you can actually use the angle between those points to create a cone and immediately omit anything between them in a revolute.