Calculate polygon from plane-3d cube intersection?

[paul_nicholls]

Hi all,
I am wondering if any of you know how to find the polygon generated from the intersection of a 3d infinite plane and a 3d cube (or box)?

I have code that finds the intersection of lines and planes, and I know how to split polygons with a plane but not sure how to do the cube/box plane intersection...

The lines making up the polygon wouldn't have to be sorted, I just need them.

any ideas?
cheers,
Paul

[chronozphere]

Some pseudo-code....

 For each line
   Define an infinit line between cube-vertex A and B
   Calculate line/plane intersection for infinit line AB
   Check if the resulting point lies between A and B (is part of the segment/edge AB)
     Keep result and continue with next line
   else
     Delete result and continue with next line

Now you should have 4 points that would make up the polygon that intersects the cube.

Hope this helps.

[michalis]

Now you should have 4 points that would make up the polygon that intersects the cube.

There are up to six points possible. Your code should be prepared to deal with resulting polygons having <= 6 points (for 1 or 2 points you may decide to ignore them, since this means that only a corner/edge of the box touches the plane, but you still have to be prepared for any polygon having between 3 and 6 points).

Uhm, if it's not obvious how to make a case with 6 intersections: imagine a horizontal plane cutting through a box in half. Now rotate this plane, such that it touches two opposite corners of the box. Now rotate just an epsilon more... and you get 6 intersections.

Ok, whole algorithm as I imagine goes like this:

1. First I would just do 12 intersection tests (like chronozphere writes, just test each line (cube edge stretched into infinity) with plane and then cut to the cube). For each intersection, remember the calculated 3D intersection point. Also, for each intersection point remember indexes of 2 neighborhood faces of the intersected edge (these will be needed to connect intersection points into segments).

2. Then merge duplicates on the intersection points list. Remember that if plane crosses exactly the corner of the box, then you will have duplicates (or "almost-by-epsilon-duplicates") on the list of intersection points. During this merging, some intersection points may be determined to have 3 neighboring faces (these are box corners that are intersected by the polygon).

3. Then gather the "neighboring faces" indexes to actually calculate the intersection segments. For each face:
- if it has 0 intersection points, obviously ignore
- if it has 1 intersection point, also ignore (such faces are possible when box cornes are on the list of intersection points)
- if face has 2 intersection points --- cool, add the segment between these two points to the generated polygon

- If any face has more than 2 intersection points, then your plane lies exactly on one of the cube's sides. This is a special case, you should then either abort intersection or return the whole cube face as intersection polygon.

Hope this helps

[NecroDOME]

I think you are looking for CSG (constructive solid geometry)?

http://en.wikipedia.org/wiki/Constru...solid_geometry

[paul_nicholls]

Thanks michalis,
I will see if I can get something working :-)

@ NecroDOME, I am not looking for CSG...I want to try slicing a 3d box (filled with voxels) with the viewing plane and draw the voxels that are on each slice of the box to see if I can draw voxel objects nicer.
cheers,
Paul