Part of the Khronos Group
OpenGL.org

The Industry's Foundation for High Performance Graphics

from games to virtual reality, mobile phones to supercomputers

Results 1 to 8 of 8

Thread: 3D object/plane intersection contour

  1. #1
    Intern Contributor
    Join Date
    Jul 2004
    Location
    Toronto
    Posts
    97

    3D object/plane intersection contour

    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?

  2. #2
    Super Moderator OpenGL Lord
    Join Date
    Dec 2003
    Location
    Grenoble - France
    Posts
    5,575

    Re: 3D object/plane intersection contour

    Just draw using GL_LINES ?

  3. #3
    Intern Contributor
    Join Date
    Jul 2004
    Location
    Toronto
    Posts
    97

    Re: 3D object/plane intersection contour

    Well the line (1,0), (0,1) is drawn which I don't want. Any way to get rid of that?

  4. #4
    Senior Member OpenGL Guru Dark Photon's Avatar
    Join Date
    Oct 2004
    Location
    Druidia
    Posts
    4,569

    Re: 3D object/plane intersection contour

    Quote Originally Posted by Budric
    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 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


  5. #5
    Member Regular Contributor Rosario Leonardi's Avatar
    Join Date
    Aug 2008
    Location
    Italy
    Posts
    356

    Re: 3D object/plane intersection contour

    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
    ~ ~ I tell you, realtime 3D is made of blood, sweat and screams! ~ ~

  6. #6
    Intern Contributor
    Join Date
    Jul 2004
    Location
    Toronto
    Posts
    97

    Re: 3D object/plane intersection contour

    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.

  7. #7
    Intern Contributor
    Join Date
    Jul 2004
    Location
    Toronto
    Posts
    97

    Re: 3D object/plane intersection contour

    This post discusses how to determine whether a diagonal is inside a polygon: http://stackoverflow.com/questions/69383...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.

  8. #8
    Member Regular Contributor Rosario Leonardi's Avatar
    Join Date
    Aug 2008
    Location
    Italy
    Posts
    356

    Re: 3D object/plane intersection contour

    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.

    Code :
    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))
    ~ ~ I tell you, realtime 3D is made of blood, sweat and screams! ~ ~

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •