Sign in to follow this  

How to test vertices if they form a cube?

Recommended Posts

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?

Edited by lucky6969b

Share this post

Link to post
Share on other sites
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. Edited by Nypyren

Share this post

Link to post
Share on other sites

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.

Share this post

Link to post
Share on other sites

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.

Edited by Tangletail

Share this post

Link to post
Share on other sites

pick a vertex. 


determine the next two closest vertices in 3d space.


if the edges between those vertices are not at a right angle, the vertices can't form a cube.  or check the angle formed by the edges between the first vertex and all other possible pairs of vertices.


continue adding vertices and edges and checking the angle between edges until you get a cube.


but a truly arbitrary set of points would almost never decompose entirely into cubes.

Edited by Norman Barrows

Share this post

Link to post
Share on other sites

This sounds like combinatoric hell. If you have 9 vertices altogether then there are still 9 combinations of 8 to check. When you have 10 there are 45 combinations of 8 to check. How many vertices do you have? with 50 you are looking at half a billion if my maths is correct. It gets very big very fast. I would think that will be the biggest problem you have rather than actually working out if the vertices form a cube or not. Do you have anyway to cut that down? For example, is there a limit to how big a cube will be?


I would focus more on ways to show it isn't a cube quickly rather than on ways to show vertices do form a cube because you are likely going to end up with astronomical numbers of combinations (100 vertices are not pretty).

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this