How can I find the points of intersection between two cubes in 3D space?

[parch]

hi,

I need to find the points of intersection between two cubes, and the algorithm should give the intersection points even though my cubes are rotated in any direction. i need to know, Is there any general algorithm for this and what is the current research(any method) in finding the intersection of two cubes. the application where i am using is unstructured 3d mesh generation. Kindly help me to get a clear idea in this topic.
thanks in advance for your reply..

 

[clustro]

I don't understand question.

Two cubes could intersect along a point, line, plane, or solid.

So you want a computer program that does this? What language? For what purpose?

 

[parch]

hey thanks for your quick reply. I mean two cubes are placed one over another, an we need to find the points of intersection. the algorithm i need is, it should be able to get the intersection points though my cubes are rotated in any direction. I will use it for unstructured 3d cartesian mesh generation. you can have you program in Fortran or C++. Thanks in advance.

 

[clustro]

What are on Earth are you talking about man?

You'll need to use far more precise language than "placed one over another."

A picture is worth a 1,000 words.

 

[parch]

Imagine there are 2 cubes of same finite dimension. Example from 0 to 1 in all three axis. place the first cube with the origin (0,0,0), and place the second cube with the origin (0.5,0.5,0.5). So now both the cubes will get intersected with each other. I need to get the points where the edges of the cubes crosses the outer surface, we get six locations. (just think in 2d to get more clear). Still find problem in my question have ur post.

 

[Dick]

A 'cube' type thing is just described by a1<=x<=a2, b1<=y<=b2, c1<=z<=c2. To intersect two of them just figure out how to intersect two segments in each of the coordinate axes.

 

[parch]

more clear please. any one.

 

[Dick]

Cube of edge length 1 at origin (0,0,0), described by -1/2<=x<=1/2 etc. Same at origin (1/2,1/2,1/2) described by 0<=x<=1, etc. Intersection, 0<=x<=1/2, etc.

 

[parch]

hi dick & clustro

1) I think from the attached figure you will be able to get my question.

2) the red lines in one cube will cut the outer surface of other cube. I need to find the location where the edge(red line) cuts the outer face.(six points will occur! am i rite). Is there any algorithm used for this. and what are the ways it can be done.

3)the algorithm should be more general way where any degree rotation should give me the intersection points. I tried a way where my algorithm fails to locate the points if other cube is rotated more than 90 degree..

thanks in advance...

 

[AUMathTutor]

Just break it up into a finite 3-d grid, and for each cube, decide which grid cubes are filled by the larger cube. Then see which grid-cubes are filled by each of the larger cubes simultaneously, and keep these. This is the intersection.

This method does not offer infinite precision, but it is general and will offer a (relativelty) arbitrary precision.