A Plane Crashes Into a Mesh..

Just kidding, but kind of related. Imagine some 3D model in space; it could be the starship Enterprise, it could be the guy from DOOM, it could be a Ferrari Enzo (drool) or anything. It’s just a 3D model. Now you’re given an arbitrary plane that intersects this model. You know everything about both objects; you have all the vertices for the model and you know the orientation of the plane.

How would you go about finding the shape formed on the plane by the intersection of the object?

Actually, how would you do it more efficiently than what I’m starting with? Hopefully there is some data about the model so you can trivially throw out triangles that are not even close but you’re going to need to find out which triangles intersect the plane–which is three vector subtractions and three dot products per triangle. Then it’s a matter of finding the point on each segment of each triangle that is actually intersected, which is just a little algebra & geometry finding where lines intersect planes. Then you have your shape.

Without being able to trivially throw scores of them away, though, I don’t like the idea of checking every single triangle, although I guess for completeness it would have to be done. Perhaps I could exploit a spatial locality principle and once I find one triangle that intersects, if I knew how to get to adjacent triangles then they would be much more likely to be intersected and once I reach the original triangle the job is effectively done…

Suggestions?

Bah, but then again the triangles of the model are most likely quite randomly ordered and the plane can be at any orientation so it’s highly unlikely to be easy to find local triangles.

use space partitioning to easilly reject triangles in large blocks. in order for a triangle to intersect the plane (assuming you only desire a planar intersection) it must have a point on either side of the plane. this is only a few dot products. then figure out which edges of the triangle intersect the plane and at which points. this forms an edge. through all of these edges into a list and render the list and you should have your silhouette.

should be a piece of cake.

it depends on what you really want from this… but if you want the shape and not just the silhouette. all you need to do is project all of the vertices to the plane, the model will be flattened, and you will have your shape.

if you want to reduce the number of triangles in the final flattened mesh, just remove the back facing triangles, and merge all of the rest into convex polygons (a little trickier). once no more convex polygons can be produced, break them up into triangles, and you have a reduced polygon flat mesh.

hope that helps. i have to get to sleep.

She/he is certainly not looking for the projection of
the entire object on the plane, just the intersecting
silouette.

I would definately try the “brute force” way, where you
check all triangles for intersections, etc. At
least you will know the right answer so that
you can try experimenting with other methods.

This might sound crazy, but I suspect that there has
got to be some sort of depth test on a particular
projetion using an EQUAL operation (the intersection
of LEQUAL and GEQUAL) that would work. Food for
thought!

Yes! Correct, I do not want to project the whole object onto the plane, I just want to find the shape of the intersection between plane and object.

z.b.: if you have a cylinder along the Z axis, and you take the XY plane and rotate it 45 degrees about the Y axis; I would want to find the ellipse formed on the plane by the intersecting cylinder. If you took the XZ plane, the shape would be a rectangle.

I’ll go ahead and run some tests with the strategy, and see how performance scales; it’s a whole lot of multiplying going on! If things get too ugly I’m sure I could either shove it into a background thread to be processed over time before hand or just precalculate the results and then pretend they came up on the spot… Although it would be much cooler to have the flexibility of not requiring the user to specify what is going to happen ahead of time.

Thanks all, I’ll look into this some more.

In any case, it’s very similar to collision detection, and there are some methods to increase the performance of that.

One of the simplest, I suppose, would be to make a 3D array that contains the triangles that intersect a block.
I should mention that I haven’t done this myself yet, it’s just something I’m considering for my own collision detection when I get around to it.

2D version:

 X-> 1      2      3
 +------+------+------+
Y|      |      |      |
 |  |\  |      |      |
1|  | \ |      |      |
 |  |  \|      |      |
 +--+---*------+------+
 |  |   |\     |      |
 |  |   | \    |      |
2|  +---+--    |      |
 |      |      |      |
 +------+------+------+

 

basically you’d put the ID of the triangle in all the cells that contain it, so in this example in cells (1,1), (1,2), (2,2).

It’s relatively simple to do some raycasts through a regular 3D grid and through that determine the potential hits.
You could keep such a 3D array static, and it will allow you to not check triangles that are not even close to having an intersection.

As to the best size for such a 3D array - I haven’t got a clue. It’s a tradeoff between storage (more cells means more storage, e.g. the same triangle might be in 20 cells or just 1), and intersections tests.
My guess is that a 5x5x5 grid might be a good tradeoff, but that’s really just a wild guess.
It may also be a good idea to make the size of the grid dependent on the object.

A 3D grid generally gives only a constant factor improvement in runtime, so it doesn’t scale very well (it’s not obvious, but twice the object size still results in twice the runtime…). For large objects, an octtree (or similar recursive space partitioning) would perform better.

In the most simple case, an octtree node is an axis aligned box. You can simply decide if the plane intersects the box by checking the corners with a few dot products. If the plane intersects the node, you check every child node recursively, and/or every triangle contained directly in the node.

Ideally I would like to get this working in real time. The 3D models that are going to receive this treatment will probably have relatively low polygon counts (The program will have MANY 3D objects on the screen at one time so I’m trying to be frugal with the triangles) so it might not be completely improbable–real time would also be nice because then the user could see the results interactively instead of having to specify it before execution, and have it precalcluated so that he first sees it when the the time to insert the plane comes, only to have it be wrong. (The consistent flow of time and interactivity is important in this program)

So basically the first-try algorithm I’ve come up with is:

[ul][li]Specify the object position and plane orientation[/li] [li]Iteratively ( :frowning: ) find the triangles that intersect the plane[/li] [li]For each triangle found, find the edges that intersect and create a vertex on the plane at the point of intersection[/li] [li]Draw a line loop around the vertices[/li] [/ul]
So, it’s a place to start. I already see another troublesome spot; the triangles may be randomly ordered, but the vertices will definitely have to be specified in order for the outline to be properly drawn. Perhaps I can do some sort of sorting on them once they’re all found.
Oh well, I’ll play with this tonight.

Originally posted by Omaha:
[b]Ideally I would like to get this working in real time. The 3D models that are going to receive this treatment will probably have relatively low polygon counts (The program will have MANY 3D objects on the screen at one time so I’m trying to be frugal with the triangles) so it might not be completely improbable–real time would also be nice because then the user could see the results interactively instead of having to specify it before execution, and have it precalcluated so that he first sees it when the the time to insert the plane comes, only to have it be wrong. (The consistent flow of time and interactivity is important in this program)

So basically the first-try algorithm I’ve come up with is:

  • [li]Specify the object position and plane orientation[/li]> [li]Iteratively ( :frowning: ) find the triangles that intersect the plane[/li]> [li]For each triangle found, find the edges that intersect and create a vertex on the plane at the point of intersection[/li]> [li]Draw a line loop around the vertices[/li]>

So, it’s a place to start. I already see another troublesome spot; the triangles may be randomly ordered, but the vertices will definitely have to be specified in order for the outline to be properly drawn. Perhaps I can do some sort of sorting on them once they’re all found.
Oh well, I’ll play with this tonight.[/b]
this is how i would do it and my original suggestion. i would use octree space partitioning as well as i originally suggested as did someone else.
you should try to be more specific than ‘shape’… that can be a lot of things. what are you trying to do? some kind of visual effect? a planar shadow projection algorithm? some kind of modeling visualization tool?

if you just want the ‘shape’, i would just render the geometry in a flat colour, and do the projections in a vertex shader. then you could move your plane around in real time, and everything would jump right on it.

If you just want to see this shape you can put two clip planes near either side of your cutting plane.

I just had another idea when I thought about the problem of getting a real volume intersection, opposed to a simple collection of lines from triangle/plane intersections…

I have not actually tried this, but I think it is worth mentioning it.

You could store not only vertices and triangles, but also edges (perhaps in a half-edge structure, google should give a lot of hits if you don’t know what that is…). Then every triangle has three edges, and every edge connects two triangles.

With this, you search for an edge intersecting the plane. From this you get your first point. Now you take one of the triangles of this edge. This triangle has two other edges, one of these is again intersecting the plane, from this you get your second point, and so on…

Theoretically, this series of points should be a loop, so you should get back to the first point (at least if the mesh is forming a closed body). But it may be that you have more than one seperate loop, so be sure to check for this…

These loops can easily be fed into the gnu tesselators, and this should give you a new triangle mesh that represents the cut surface of the mesh and the plane…