PDA

View Full Version : 3D object/plane intersection contour

Budric
07-29-2010, 01:32 PM
Hi,
I'd like to compute the intersection between a plane and a 3D object composed of triangles. Then I'd like to draw this intersection contour.

Seemed easy enough at the start. I started by computing plane/edge line segment intersection. This gives me the contour points, but there's no guarantee on the ordering for resulting polygon.

For example one of the corner cases is a square composed of 2 triangles that's right on the plane:
{(0,0), (1,0), (0, 1)}, {(0,1), (1,0), (1,1)}
Straight line segment intersection gives me the right points, but the order of those points is all wrong - I can't draw them using GL_LINE_STRIP for example and get a contour of a square.

I could try sorting the result points in CCW order. However the result polygon can also be concave.

Another corner case is branching. For example taking an intersection through a shape that looks like this ---V V----
would produce 2 separate contour polygons.

Any suggestions on an algorithm(s) I can use?

ZbuffeR
07-29-2010, 01:41 PM
Just draw using GL_LINES ?

Budric
07-29-2010, 01:54 PM
Well the line (1,0), (0,1) is drawn which I don't want. Any way to get rid of that?

Dark Photon
07-31-2010, 05:35 PM
Well the line (1,0), (0,1) is drawn which I don't want. Any way to get rid of that?
Post a short GLUT test program (see this (http://www.opengl.org/discussion_boards/ubbthreads.php?ubb=showflat&amp;Number=278315#Post2783 15) for a template to start with). Hard code the points to draw (don't include all your intersection logic).

You've got several choices:

* GL_LINES and you specify the points for every 2-point line segment separately
* GL_LINE_STRIP and you specify every contiguous set of line segment points separately, OR
* GL_LINE_STRIP and you specify all the line segments together, but use primitive restart to "break the line strip" between contiguous line segments

http://glprogramming.com/red/images/Image34.gif

Rosario Leonardi
08-01-2010, 09:19 AM
Let me understand your problem. You have a generic shape (example a table) and you want to intersect the shape with a plane.
In the case of the table the leg should generate four circles.
Your algorithm now is intersect every triangle of the mesh and store somewhere the start and the end point of the intersection.

ZbuffeR suggest to use GL_LINES, I do the same. :)

ps: I made the table example cause there is no right order, you must draw each line separatelly (or complicate the logic a lot). :P

Budric
08-03-2010, 08:42 AM
Rosario Leonardi, yes that's the problem I'm trying to solve. The problem with using GL_LINES is that it still doesn't produce the output I want in certain corner cases. For example if the table top is specified as 2 triangles (see my example earlier) and a plane runs right through the table top, so plane intersects 2 triangles. The output of the intersection algorithm has the middle line going from one corner of the table to another.

So I either need to modify intersection algorithm somehow to not output that line (don't know how). Or I need to post process the result and eliminate any "non edge" lines and then draw the shape - mark them off using glEdgeFlag() for example. Again I don't know how I'd do a test for "non-edgeness" - and also work for concave polygons as well.

Budric
08-03-2010, 09:05 AM
This post discusses how to determine whether a diagonal is inside a polygon: http://stackoverflow.com/questions/69383...concave-polygon (http://stackoverflow.com/questions/693837/how-to-determine-a-diagonal-is-in-or-out-of-a-concave-polygon)

I could use that to post process my results. It's going to be slow. I wish I could somehow not output them from the intersection algorithm in the first place. But it's a start.

Any other suggestions welcome.

Rosario Leonardi
08-03-2010, 04:39 PM
mmmm. I think there is no easy solution.
If I understood you have a square (two triangles) and the intersection plane and the square are coincident. In this case the interpenetration test will catch all the side of all triangles, and you don't want the segment shared by coplanar triangles. Right?

One solution can be to threat triangles coplanar to the intersection plane as special case and discart shared segment.

intersection(plane &amp;p, std::vector<triangle> &amp;triangleList)
{
std::vector<points> specialCase;
for(size_t i = 0; i < triangleList.size(); i++)
{
if(plane.isCoplanar(triangleList[i]) &amp;&amp; plane.isPointOnPlane(triangleList[i].a)
{
specialCase.push_back(pair<point, point>(triangleList[i].a, triangleList[i].b));
specialCase.push_back(pair<point, point>(triangleList[i].b, triangleList[i].c));
specialCase.push_back(pair<point, point>(triangleList[i].c, triangleList[i].a));
}else{
pair<point, point> res;
if(plane.intersect(triangleList[i], &amp;res))
outVector.push_back(res);
}
}
// search duplicated segment
for(auto it = specialCase.begin(); it+1 != specialCase.end(); it++)
{
auto found = std::find_if(it, it+1, specialCase.end(), pointDuplicated);
if(found != specialCase.end()){
specialCase.erase(it);
specialCase.erase(found);
}
}
// join the vectors
outVector.insert(outVector.end(), specialCase.begin(), specialCase.end());
}

Where pointDuplicated is a predicate that check if the segment have the same ending point (in both ways).

This give a O(n^2) search, but you shouldn't have a lot of coplanar triangles. :-/
If the number of special case is big you can optimize using a quick sort and then check only the duplicated (O(log(n)) + O(n))