Loading ...
Sorry, an error occurred while loading the content.

Re: [antiprism] Re: lines_intersection

Expand Messages
  • Adrian Rossiter
    Hi Roger ... Well done for finding the solution. I have checked and I introduced this error into the development code when I was renaming function arguments to
    Message 1 of 22 , Feb 1, 2010
    View Source
    • 0 Attachment
      Hi Roger

      On Mon, 1 Feb 2010, Roger Kaufman wrote:
      > I went over the code they have on their page. The noteworthy change is
      > the P = P0 + sc*u change from P = P1 + ... same for Q.

      Well done for finding the solution. I have checked and I introduced
      this error into the development code when I was renaming function
      arguments to try to make them consistent between the various
      functions.

      I use the function in kcycle and the examples I have tried
      have worked with both forms of the function!

      You are right about the need for these functions to
      take an epsilon argument.


      > if(lines_nearest_points(P, P_dir, Q, Q_dir, N1, N2, epsilon)) {
      ...
      > The call to lines_nearest_points uses P_dir instead of P+P_dir. Same for Q.

      I don't think that should work, generally. lines_nearest_points
      is expecting two points that lie on a line and P_dir won't
      generally lie on the line through P and P+P_dir (only
      in the case where the line passes through the origin.)

      Regarding the parameters, it is probably better for
      lines_intersection to have the same line parameters
      as lines_nearest_points. I will change it to take all
      point parameters. (No plans to add it in, but it would
      be nice to be able to distinguish position vectors and
      free vectors).


      > This maybe should be the only way it can work. If N1 and N2 are two far
      > apart it probably shouldn't give an answer? (it is suppose to be
      > intersection)

      I originally added it as a convenience function to find the
      intersection of lines lying in the same plane. It therefore
      always returns a "best" intersection point (the lines may
      just miss), and returns an unset vector if the lines are
      parallel. Maybe it would be better to call the function
      coplanar_lines_intersection. I will also improve the
      documentation.



      > vec3d lines_intersection_in_segment(vec3d P, vec3d P_dir, vec3d Q, vec3d Q_dir, double epsilon)
      > bool in_segment(vec3d intersection_point, vec3d P, vec3d P_dir, vec3d Q, vec3d Q_dir)
      ...
      > So far in what I have tested this works.

      I'll wait until you send me something, and then add them into vec_utils
      with the others.


      > I am finding the triangle overlap code is going to be fairly complex!

      Did you look into using the GLU Tesselator? It appeared that
      it would make it quite straightforward to pick out the overlapped
      and non-overlapped parts.

      Adrian.
      --
      Adrian Rossiter
      adrian@...
      http://antiprism.com/adrian
    • Roger Kaufman
      Hi Adrian, ... But it will not work (for me) when I have P+P_dir. I suppose I am using it as though it were P0,P1,Q0,Q1. When I use P+P_dir the found
      Message 2 of 22 , Feb 1, 2010
      View Source
      • 0 Attachment
        Hi Adrian,

        > > if(lines_nearest_points(P, P_dir, Q, Q_dir, N1, N2, epsilon)) {
        > ...
        > > The call to lines_nearest_points uses P_dir instead of P+P_dir. Same for Q.
        >
        > I don't think that should work, generally. lines_nearest_points
        > is expecting two points that lie on a line and P_dir won't
        > generally lie on the line through P and P+P_dir (only
        > in the case where the line passes through the origin.)

        But it will not work (for me) when I have P+P_dir. I suppose I am using it as though it were P0,P1,Q0,Q1. When I use P+P_dir the found intersections are never on the lines but always a little bit to the side of them.

        > Regarding the parameters, it is probably better for
        > lines_intersection to have the same line parameters
        > as lines_nearest_points. I will change it to take all

        I think you are right. P_dir suggests it will find the nearpoints in only that direction. But actually it finds the intersection as though the line were theoretically infinite. Unless I am wrong, there is no directionality implied in the outcome.

        > I originally added it as a convenience function to find the
        > intersection of lines lying in the same plane. It therefore
        > always returns a "best" intersection point (the lines may
        > just miss), and returns an unset vector if the lines are
        > parallel. Maybe it would be better to call the function
        > coplanar_lines_intersection. I will also improve the
        > documentation.

        Actually it works quite fine in 3D! So I don't think the name needs to be restricted to coplanar. The problem is, if two lines are not parallel but don't come near one another, the nearest points on those two lines are identified. Then the function returns a point midway on that segment. I included an OFF file below in which I tested this.

        OFF
        4 2 0
        1 1 10
        1 1 -10
        10 -1 1
        -10 -1 1
        2 0 1
        2 2 3

        The function finds the nearpoints quite nicely but the lines don't interesect. I changed (my copy of) the function because I think it should always test for this. The average of N1 and N2 is sort of moot after that.

        If the midpoint of the shortest segment were wanted, perhaps another function (without the mag() test), would be called lines_average_nearpoints()?

        vec3d lines_intersection(vec3d P, vec3d P_dir, vec3d Q, vec3d Q_dir, double epsilon)
        {
        vec3d N1, N2;
        if(lines_nearest_points(P, P_dir, Q, Q_dir, N1, N2, epsilon) && ((N1-N2).mag() < epsilon))
        return (N1+N2)/2.0;
        else
        return vec3d();
        }

        > Did you look into using the GLU Tesselator? It appeared that
        > it would make it quite straightforward to pick out the overlapped
        > and non-overlapped parts.

        In my searches nothing like this ever came up. Could you point me to something? (I have searched using GLU Tessalator and finding hints of it). Is this something available or does it need to be linked in? I would rather avoid having to add anything library-wise. Actually I find this an interesting problem.

        Roger
      • Adrian Rossiter
        Hi Roger ... I have included a test program at the end of the email that checks the nearpoints on a couple of diagonals through a unit cube (that don t pass
        Message 3 of 22 , Feb 1, 2010
        View Source
        • 0 Attachment
          Hi Roger

          On Mon, 1 Feb 2010, Roger Kaufman wrote:
          >>> if(lines_nearest_points(P, P_dir, Q, Q_dir, N1, N2, epsilon)) {
          >> ...
          >>> The call to lines_nearest_points uses P_dir instead of P+P_dir. Same for Q.
          >>
          >> I don't think that should work, generally. lines_nearest_points
          >> is expecting two points that lie on a line and P_dir won't
          >> generally lie on the line through P and P+P_dir (only
          >> in the case where the line passes through the origin.)
          >
          > But it will not work (for me) when I have P+P_dir. I suppose I am using
          > it as though it were P0,P1,Q0,Q1. When I use P+P_dir the found
          > intersections are never on the lines but always a little bit to the side
          > of them.

          I have included a test program at the end of the email that
          checks the nearpoints on a couple of diagonals through a unit
          cube (that don't pass through the origin!). lines_nearest_points()
          gives the wrong answer using P_dir and the right answer
          using P+P_dir.

          If you have the right answer using P_dir it may be that your
          P_dir vector is really a position vector of a point on the
          line rather than a free vector in the direction of the line.


          >> Regarding the parameters, it is probably better for
          >> lines_intersection to have the same line parameters
          >> as lines_nearest_points. I will change it to take all
          >
          > I think you are right. P_dir suggests it will find the nearpoints in
          > only that direction. But actually it finds the intersection as though
          > the line were theoretically infinite. Unless I am wrong, there is no
          > directionality implied in the outcome.

          I meant to comment on this from your other email. There
          are two ways that you might set up a parametric equation
          of a line using vectors.

          R is a point on the line passing through P and Q
          R = tQ + (1-t)P for some number t (-inf<t<inf)

          R is a point on the line through P with direction v
          R = P + sv for some number s (-inf<s<inf)

          To see the connection. v = k(Q-P) for some number k
          R = P + sv
          R = P + sk(Q-P)
          R = P + skQ - skP
          R = skQ + (1-sk)P

          So, a line can be represented by (P, Q) or by (P, v).
          The parameters are related by t = sk so any point
          given by one equation form can also given by the other.

          I thought that for consistency just one of the forms
          could be used, and that it might as well be the form
          using all points (just because that is what the original
          function used).


          > Actually it works quite fine in 3D! So I don't think the name needs to
          > be restricted to coplanar. The problem is, if two lines are not parallel
          > but don't come near one another, the nearest points on those two lines
          ...
          > If the midpoint of the shortest segment were wanted, perhaps another
          > function (without the mag() test), would be called
          > lines_average_nearpoints()?

          The easiest way to sort this out might be to get
          rid of the function! It is only a convenience function
          and it isn't a clear choice what will be generally
          convenient so programs could just set up their own.


          >> Did you look into using the GLU Tesselator? It appeared that
          >> it would make it quite straightforward to pick out the overlapped
          >> and non-overlapped parts.
          >
          > In my searches nothing like this ever came up. Could you point me to
          > something? (I have searched using GLU Tessalator and finding hints of
          > it). Is this something available or does it need to be linked in? I
          > would rather avoid having to add anything library-wise. Actually I find
          > this an interesting problem.

          It is described in "CSG Uses for Winding Rules" in the
          OpenGL Red Book

          http://glprogramming.com/red/chapter11.html


          The GLU Tesselator is already linked in, if it is available,
          as it is used for the triangulation. The fallback triangulation
          routine fails in many cases, but is handy for building Antiprism
          without OpenGL (although the development build is currently broken
          for building without OpenGL.) I may add the GLU Tesselator code
          into Antiprism to be built if a GLU library is not available.
          That way everything, apart from antiview, could be built and work
          properly without needing OpenGL to be installed.

          Adrian.
          --
          Adrian Rossiter
          adrian@...
          http://antiprism.com/adrian
        • Adrian Rossiter
          Hi Roger ... I forgot to include it. It is below. Adrian. -- Adrian Rossiter adrian@antiprism.com http://antiprism.com/adrian #include
          Message 4 of 22 , Feb 1, 2010
          View Source
          • 0 Attachment
            Hi Roger

            On Mon, 1 Feb 2010, Adrian Rossiter wrote:
            > I have included a test program at the end of the email that

            I forgot to include it. It is below.

            Adrian.
            --
            Adrian Rossiter
            adrian@...
            http://antiprism.com/adrian



            #include "../anti/base/antiprism.h"

            int main()
            {
            vec3d C100 = vec3d(1,0,0);
            vec3d C011 = vec3d(0,1,1);
            vec3d C010 = vec3d(0,1,0);
            vec3d C101 = vec3d(1,0,1);

            vec3d P0 = C100;
            vec3d P1 = C011;
            vec3d P_dir = P1-P0;
            vec3d Q0 = C010;
            vec3d Q1 = C101;
            vec3d Q_dir = Q1-Q0;

            vec3d N1, N2;

            lines_nearest_points(P0, P_dir, Q0, Q_dir, N1, N2);
            fprintf(stderr, "\nintersect: point, dir\n");
            N1.dump("N1");
            N2.dump("N2");

            lines_nearest_points(P0, P0+P_dir, Q0, Q0+Q_dir, N1, N2);
            fprintf(stderr, "\nintersect: point, point+dir\n");
            N1.dump("N1");
            N2.dump("N2");

            return 0;
            }
          • Roger Kaufman
            Hi Adrian, ... Then my P_dir is really a position vector as you say. You have vec3d P0 = C100; vec3d P1 = C011; vec3d P_dir = P1-P0; but the P0+P_dir would be
            Message 5 of 22 , Feb 1, 2010
            View Source
            • 0 Attachment
              Hi Adrian,

              > I have included a test program at the end of the email that
              > checks the nearpoints on a couple of diagonals through a unit
              > cube (that don't pass through the origin!). lines_nearest_points()
              > gives the wrong answer using P_dir and the right answer
              > using P+P_dir.
              >
              > If you have the right answer using P_dir it may be that your
              > P_dir vector is really a position vector of a point on the
              > line rather than a free vector in the direction of the line.

              Then my P_dir is really a position vector as you say. You have

              vec3d P0 = C100;
              vec3d P1 = C011;
              vec3d P_dir = P1-P0;

              but the P0+P_dir would be P1-P0+P0.

              I am going to change my parameter names not to use the term P_dir because it is (for me) really the other end point of the line segment.

              Alternatively I could call it as, however this seems a bit absurd since they will be added back in right away.

              vec3d intersection = lines_intersection(P0, P1-P0, Q0, Q1-Q0, epsilon);

              > The easiest way to sort this out might be to get
              > rid of the function! It is only a convenience function
              > and it isn't a clear choice what will be generally
              > convenient so programs could just set up their own.

              I agree with this! Then my convienience function will just specify the segment end points and I can keep it local to this program.

              I still want to point out, though, that it is possible that the outcome of the current function might look like an intersection when in fact the lines can't intersect.

              > > would rather avoid having to add anything library-wise. Actually I find
              > > this an interesting problem.
              >
              > It is described in "CSG Uses for Winding Rules" in the
              > OpenGL Red Book
              >
              > http://glprogramming.com/red/chapter11.html

              I was looking at this a long while back. It is a bit involved reading for me so I didn't pursue it.

              I like the problem and I think I can solve all intersection types simply by knowing the following info

              1) what vertices are internal and external to the opposite triangle
              2) what line intersections happened.

              The Star of David pattern seems hard, but it is actually the case that line intersections occured and no vertices are internal to either triangle.

              There are rules to find the circuits of the seperate polygons which I won't elaborate on here. (also I haven't gone over them all yet)

              > The GLU Tesselator is already linked in, if it is available,
              > as it is used for the triangulation. The fallback triangulation
              > routine fails in many cases, but is handy for building Antiprism
              > without OpenGL (although the development build is currently broken
              > for building without OpenGL.) I may add the GLU Tesselator code
              > into Antiprism to be built if a GLU library is not available.
              > That way everything, apart from antiview, could be built and work
              > properly without needing OpenGL to be installed.

              I wonder if it would be allowed to compile in just the tesselator code like you did with qhull? But perhaps it would require too much supporting GL code to be included.

              Roger
            • Roger Kaufman
              Hi Adrian, ... I found this on opengl blending. I had seen it before and even have some example programs about it. This site says
              Message 6 of 22 , Feb 1, 2010
              View Source
              • 0 Attachment
                Hi Adrian,

                > > It is described in "CSG Uses for Winding Rules" in the
                > > OpenGL Red Book
                > >
                > > http://glprogramming.com/red/chapter11.html
                >
                > I was looking at this a long while back. It is a bit involved reading for me so I didn't pursue it.

                I found this on opengl blending. I had seen it before and even have some example programs about it.

                This site says

                http://stackoverflow.com/questions/393785/how-to-setup-blending-for-additive-color-overlays

                it is as simple as

                glEnable(GL_BLEND);
                glBlendFunc(GL_SRC_ALPHA, GL_ONE);


                However, even if this were implimented it would only be in antiview.

                I am working to make a physical model of the blending which can be shown in any viewer.

                Just one problem will be how to blend a triangle which is totally within another triangle. Because the outer triangle would cover the inner triangle, the coplanar clash of colors would still occur in the viewer. The outer triangle needs to be re-built as a polygon with a hole in it. Then the inner triangle's color needs to be the average of the two.

                Triangle within triangles could occur in compounds for instance.

                Then there could be triangles within triangles and so on. These would have to be a blending of all the parent triangles.

                Sounds hard, but not impossible. It will be fun.

                Roger
              • Adrian Rossiter
                Hi Roger ... I ll remove it then. ... The approach is quite difficult to follow! I didn t really get it until I had written some code. ... SGI changed the
                Message 7 of 22 , Feb 2, 2010
                View Source
                • 0 Attachment
                  Hi Roger

                  On Mon, 1 Feb 2010, Roger Kaufman wrote:
                  >> The easiest way to sort this out might be to get
                  >> rid of the function! It is only a convenience function
                  ...
                  > I agree with this! Then my convienience function will just specify the
                  > segment end points and I can keep it local to this program.

                  I'll remove it then.


                  >> It is described in "CSG Uses for Winding Rules" in the
                  >> OpenGL Red Book
                  >>
                  >> http://glprogramming.com/red/chapter11.html
                  >
                  > I was looking at this a long while back. It is a bit involved reading
                  > for me so I didn't pursue it.

                  The approach is quite difficult to follow! I didn't really get
                  it until I had written some code.


                  >> for building without OpenGL.) I may add the GLU Tesselator code
                  >> into Antiprism to be built if a GLU library is not available.
                  ...
                  > I wonder if it would be allowed to compile in just the tesselator code
                  > like you did with qhull? But perhaps it would require too much
                  > supporting GL code to be included.

                  SGI changed the license on their sample OpenGL implementation
                  about a year ago and it should be fine now to include the code
                  directly in Antiprism.

                  It looks like it may be possible to extract the tesselator
                  library. Running some searches through the code the only GL
                  and GLU dependencies I could see were types and constants.
                  However, if there is a GL or GLU function in there that I
                  missed then it could easily introduce a dependency on lots
                  of other code.

                  Adrian.
                  --
                  Adrian Rossiter
                  adrian@...
                  http://antiprism.com/adrian
                • Adrian Rossiter
                  Hi Roger ... It is interesting, but it looks like the problem of blending coplanar polygons might require a bit more than this. Each plane would probably need
                  Message 8 of 22 , Feb 2, 2010
                  View Source
                  • 0 Attachment
                    Hi Roger

                    On Tue, 2 Feb 2010, Roger Kaufman wrote:
                    > I found this on opengl blending. I had seen it before and even have some
                    > example programs about it.
                    >
                    > This site says
                    >
                    > http://stackoverflow.com/questions/393785/how-to-setup-blending-for-additive-color-overlays
                    >
                    > it is as simple as
                    >
                    > glEnable(GL_BLEND);
                    > glBlendFunc(GL_SRC_ALPHA, GL_ONE);

                    It is interesting, but it looks like the problem of blending
                    coplanar polygons might require a bit more than this.

                    Each plane would probably need to be rendered seperately and
                    then combined together afterwards. Also, I can't work out
                    offhand how the face colours could be given equal weight in
                    an overlap without it depending on how many are involved in
                    the overlap. For consistency it would probably be necessary
                    to order the faces of a plane by colour.

                    Adrian.
                    --
                    Adrian Rossiter
                    adrian@...
                    http://antiprism.com/adrian
                  • Roger Kaufman
                    Hi Adrian, ... For dealing with two triangles only, I think what I can write will be fairly efficient and not too complex. If it were to deal with large
                    Message 9 of 22 , Feb 2, 2010
                    View Source
                    • 0 Attachment
                      Hi Adrian,

                      > >> It is described in "CSG Uses for Winding Rules" in the
                      > >> OpenGL Red Book
                      > >>
                      > >> http://glprogramming.com/red/chapter11.html
                      > >
                      > > I was looking at this a long while back. It is a bit involved reading
                      > > for me so I didn't pursue it.
                      >
                      > The approach is quite difficult to follow! I didn't really get
                      > it until I had written some code.

                      For dealing with two triangles only, I think what I can write will be fairly efficient and not too complex. If it were to deal with large polygons then that would be another matter.

                      One thing I have to experiment with is seeing if a vertex is on the opposite face. I think I should be able to utilize the existing

                      is_point_on_surface_hull()

                      but I have never tried this on a 2D surface. Even if it works, it looks like this might be faster even if it is more specialize. (the fastest code is at the bottom with a demostration applet)

                      http://www.blackpawn.com/texts/pointinpoly/default.html

                      It looks like it isn't true for edges. But the intersection test should find those. I also have to test for congruent corners.


                      I have also been interested in the outcome of the winding rules idea. I don't want to keep track of windings, but it looks like, before it were sent to sort_merge, that any even number stack of congruent triangles could be deleted (or perhaps better to be made invisible) and at least simulate this sort of effect. I think this is modulo-2. It is something to try at least.

                      Roger
                    • Roger Kaufman
                      Hi Adrian, ... By the letter of the definition congruent triangles are just have the same angles and edge lengths. What I meant to say is simulataneous
                      Message 10 of 22 , Feb 2, 2010
                      View Source
                      • 0 Attachment
                        Hi Adrian,

                        >before it were sent to sort_merge, that any even number stack of >congruent triangles could be deleted (or perhaps better to be made >invisible) and at least simulate this sort of effect. I think this is >modulo-2. It is something to try at least.

                        By the letter of the definition "congruent triangles" are just have the same angles and edge lengths. What I meant to say is simulataneous triangles such as the faces that are considered duplicate by sort_merge.

                        In looking for code examples of finding the results of overlapping triangles, what I have found instead is code just to determine if triangles collide and returning a truth value. Coders seem to have competed on this and have theoretically most efficient codings, many in publications. But just a truth value doesn't do me much good!

                        I also wanted to mention that when using the triangulation (as with off_util -t), overlapping triangles are not triangulated into their "sub-parts". Even if all the triangles edges are replaced with two edges and the intersection points, the triangulation of the result is not the desired one. Edges will be put in place that go across the boundries of the sub-parts. Triangulation doesn't seem to care about overlapping polygons.

                        There is no way around it. I have to find the intersection parts myself and rebuild the faces. I have researched this quite a lot and haven't found much to help it. I should have spent the time coding! Looks like I am the pioneer in this respect.

                        Roger
                      • Alan M
                        ... Somehow, this reminds me of the discussion of the orientation of the figure-8
                        Message 11 of 22 , Feb 2, 2010
                        View Source
                        • 0 Attachment

                          --- In antiprism@yahoogroups.com, Adrian Rossiter <Adrian@...> wrote:

                          > It is described in "CSG Uses for Winding Rules" in the

                          > Open GL Red Book

                          > http://glprogramming.com/red/chapter11.html

                          Somehow, this reminds me of the discussion of the orientation of the figure-8 in synergeo. See the Even-odd rule - Wikipedia, the free encyclopedia.

                        • Roger Kaufman
                          Hi Adrian, ... I have given this some more thought and the algorithm gets simpler. Redefine the problem as this. Given two triangles which intersect, the aim
                          Message 12 of 22 , Feb 3, 2010
                          View Source
                          • 0 Attachment
                            Hi Adrian,

                            > There is no way around it. I have to find the intersection parts myself and rebuild the faces. I have researched this quite a lot and haven't found much to help it. I should have spent the time coding! Looks like I am the pioneer in this respect.

                            I have given this some more thought and the algorithm gets simpler.

                            Redefine the problem as this. Given two triangles which intersect, the aim is to inscribe the intersecting part of the one triangle in the other and vise-versa. This is done by introducing new edges, and sub-dividing existing edges.

                            Once this is done, a skeleton graph of the sub-divided triangles exist. Use graph traveral to traverse the circuits of the holes that have formed. This forms the new faces. No circuit can encompass more than one hole.

                            There is just the one special case where one triangle complete encompasses another triangle. That just requires a special traversal.

                            I may be done with this sooner than I thought!

                            Roger
                          • Adrian Rossiter
                            Hi Roger ... It depends on the winding. If you join a couple of triangles that wind in opposite directions by a bridging (double) edge then you get a zero
                            Message 13 of 22 , Feb 4, 2010
                            View Source
                            • 0 Attachment
                              Hi Roger

                              On Tue, 2 Feb 2010, Roger Kaufman wrote:
                              > I also wanted to mention that when using the triangulation (as with
                              > off_util -t), overlapping triangles are not triangulated into their
                              > "sub-parts". Even if all the triangles edges are replaced with two edges
                              > and the intersection points, the triangulation of the result is not the
                              > desired one. Edges will be put in place that go across the boundries of
                              > the sub-parts. Triangulation doesn't seem to care about overlapping
                              > polygons.

                              It depends on the winding. If you join a couple of
                              triangles that wind in opposite directions by a bridging
                              (double) edge then you get a zero density where they
                              overlap, which is removed by triangulation. You can see
                              this viewing the following file in Antiview


                              OFF
                              6 1 0
                              0 0 0
                              1 0 0
                              0 1 0
                              -0.2 0.5 0
                              0.5 -0.2 0
                              1 1 0
                              8 0 1 2 0 3 5 4 3 0.0 0.0 0.0


                              Of the six triangle tips that are displayed three from
                              one triangle have positive density, and three from the
                              other have negative density. In the triangulation
                              code the GLU tesselator selects non-zero density
                              regions, but can also select based on positive
                              and negative density, which would then assign the
                              non-overlapping parts to the triangle that they
                              came from.

                              Adrian.
                              --
                              Adrian Rossiter
                              adrian@...
                              http://antiprism.com/adrian
                            • Adrian Rossiter
                              Hi Roger ... I thought about the how you might solve this, and you seem to be describing what I was thinking of, except the the triangle in triangle wouldn t
                              Message 14 of 22 , Feb 4, 2010
                              View Source
                              • 0 Attachment
                                Hi Roger

                                On Wed, 3 Feb 2010, Roger Kaufman wrote:
                                > Redefine the problem as this. Given two triangles which intersect, the
                                > aim is to inscribe the intersecting part of the one triangle in the
                                > other and vise-versa. This is done by introducing new edges, and
                                > sub-dividing existing edges.
                                >
                                > Once this is done, a skeleton graph of the sub-divided triangles exist.
                                > Use graph traveral to traverse the circuits of the holes that have
                                > formed. This forms the new faces. No circuit can encompass more than one
                                > hole.
                                >
                                > There is just the one special case where one triangle complete
                                > encompasses another triangle. That just requires a special traversal.

                                I thought about the how you might solve this, and you
                                seem to be describing what I was thinking of, except the
                                the triangle in triangle wouldn't be a special case.

                                This is the method I was think of. You have two triangles.
                                Replace their edges by lines. Merge the lines that are close
                                enough. Find the insersections of these lines with each
                                other. Keep the intersection points that lie on either
                                triangle. Merge points that are close enough. Order the points
                                on each line, taking note of the geometric direction of the
                                ordering. Order the rays coming out of each intersection by
                                angle around the plane normal (each line giving two rays
                                one in its point-order direction and one in the opposite
                                direction.)

                                You can now find the (convex) areas that tile the two
                                triangles by selecting a point and a ray, and moving
                                along the ray to the next point, then coming out the
                                following ray to the next point etc. If there is no
                                further point on a ray then discard the area. Once you
                                get back to the original point then an area has been
                                found. Carry on until all the point/ray rairs are
                                exhausted.

                                With the final set of areas each area is wholly in
                                one triangle, or in the other triangle, or in both
                                triangles. The centroid of the area can be checked
                                to see which region it lies in, and hence the whole
                                area.

                                This same technique can be used in code for stellation.
                                The plane is divided up by lines and the required face
                                is built up from the convex areas which are found in the
                                same way as above

                                http://www.uwgb.edu/dutchs/SYMMETRY/stelicos.htm

                                Adrian.

                                P.S. I have to go out now and I haven't had chance to check
                                through what I have written carefully.
                                --
                                Adrian Rossiter
                                adrian@...
                                http://antiprism.com/adrian
                              • Roger Kaufman
                                Hi Adrian, ... I was looking at this a bit. First I didn t know that antiview did this! I ve been looking at winding number and there seems to be algorithms
                                Message 15 of 22 , Feb 4, 2010
                                View Source
                                • 0 Attachment
                                  Hi Adrian,

                                  > Of the six triangle tips that are displayed three from
                                  > one triangle have positive density, and three from the
                                  > other have negative density. In the triangulation
                                  > code the GLU tesselator selects non-zero density
                                  > regions, but can also select based on positive
                                  > and negative density, which would then assign the
                                  > non-overlapping parts to the triangle that they
                                  > came from.

                                  I was looking at this a bit. First I didn't know that antiview did this!

                                  I've been looking at "winding number" and there seems to be algorithms having to do with calculating them. I would be interesting to be able to do this and color by winding number. I should look into it.

                                  Then with winding number, one could also make invisible even number windings which is what I think modula-2 rendering is. There are a few regular polyhedra with star polygons that look nice this way.

                                  But regular polyhedra I am at a loss to find anything with 0 density. In fact I can't make anything that does this in antiview. Something that will have 0 density seems to have to be contrived.

                                  I am not sure that my idea of even stacked triangles (from my output) will always work. I will try it when I get far enough.


                                  One thing I wanted to mention is that while make two-triangle test models I was able to make them such that one face would have an inward normal and the other have an outward normal. At first I thought the program was not finding the co-planar faces! This could would not work in this case

                                  vec3d norm = face_norm(verts, faces[i]).unit();
                                  double D = vdot(verts[faces[i][0]]-C, norm);
                                  if(D < 0) // Make sure the normal points outwards
                                  norm = -norm;

                                  Is it because the centroid is also on the plane with the two coplanar triangles? I think that was the reason.

                                  The interesting thing is that the model was considered oriented. I thought when it was oriented, all the normals were the same way. e.g. J85 as generated had all the normals pointed in. But if I do

                                  off_util -O J85

                                  then all the normals point out. However, I see this is not always true as in U75.

                                  I also found is that when U75 is triangulated it is no longer orientable! This means that the coplanar coloring isn't going to work on U75! There are several others which for which this is the case. An interesting situation is U72 which off_report says it is oriented by it is not orientable!

                                  off_util -t U72 | off_report

                                  However

                                  off_util -t U72 -O | off_report

                                  says that is is oriented. But then

                                  off_util -t U72 | off_util -O | off_report

                                  says that is is not orientable and is not oriented! I am hoping there is a bug going on somewhere. Or perhaps some limitation happened.


                                  Thanks for the link on stellations. It is something I was thinking might be fun to do in the future. Have you ever thought about it?

                                  As for my color blending method, I should have something in a week or two, given I have enough time. Then you can look at the program and we can discuss the method and what else could have been done if anything.

                                  But this thing about triangulation producing non-orientable models has me bumbed out. This means that some of models I want to make with blended colors might not be possible with my method.

                                  Roger


                                  Roger
                                • Adrian Rossiter
                                  Hi Roger ... If you mean regular polygon, in this case all the edges wind the same way around the centre. If you choose a point in some closed region and shoot
                                  Message 16 of 22 , Feb 5, 2010
                                  View Source
                                  • 0 Attachment
                                    Hi Roger

                                    On Fri, 5 Feb 2010, Roger Kaufman wrote:
                                    > But regular polyhedra I am at a loss to find anything with 0 density. In
                                    > fact I can't make anything that does this in antiview. Something that
                                    > will have 0 density seems to have to be contrived.

                                    If you mean regular polygon, in this case all the edges wind
                                    the same way around the centre. If you choose a point in some
                                    closed region and shoot out a ray from this point away from the
                                    centre at least one edge crosses the ray and all the edges cross
                                    the ray in the same direction. The region therefore has a non-zero
                                    density.


                                    > One thing I wanted to mention is that while make two-triangle test
                                    > models I was able to make them such that one face would have an inward
                                    > normal and the other have an outward normal. At first I thought the
                                    > program was not finding the co-planar faces! This could would not work
                                    > in this case
                                    >
                                    > vec3d norm = face_norm(verts, faces[i]).unit();
                                    > double D = vdot(verts[faces[i][0]]-C, norm);
                                    > if(D < 0) // Make sure the normal points outwards
                                    > norm = -norm;
                                    >
                                    > Is it because the centroid is also on the plane with the two coplanar
                                    > triangles? I think that was the reason.

                                    If you have a triangle on a plane then the vertices, in
                                    order, wind in some direction around the triangle centroid
                                    relative to one side of the plane. The direction of the
                                    normal depends on this winding direction. If you have two
                                    triangles on the same plane that wind in different
                                    direcions then they will have normals that point in
                                    opposite directions.


                                    > The interesting thing is that the model was considered oriented. I
                                    > thought when it was oriented, all the normals were the same way. e.g.
                                    > J85 as generated had all the normals pointed in. But if I do
                                    >
                                    > off_util -O J85
                                    >
                                    > then all the normals point out. However, I see this is not always true
                                    > as in U75.

                                    I haven't had chance to comment on your utility to display
                                    normals yet. I was thinking that the face attached normals
                                    would be of visual interest and could be an option in off2*
                                    and antiview. If there is a geometric use then an option
                                    could be added to off_util for now.

                                    As regards normal direction. The orientable resource
                                    models should be oriented to have a positive volume. I
                                    haven't checked this recently. I notice that U75 has
                                    zero volume but the reported figure is on the negative
                                    side of zero on my machine. I guess it might come
                                    out positive on someone elses.

                                    U75 is like the octahemioctahedron in having faces
                                    with inward and outward pointing normals. If you
                                    look at the vertex figure

                                    http://en.wikipedia.org/wiki/File:Great_dirhombicosidodecahedron_vertfig.png

                                    The lower pentagam and upper triangle are attached to
                                    the square running bottom left to upper right on
                                    opposite sides of its plane (i.e. their centres lie
                                    on opposite sides). They therefore wind in different
                                    directions with respect to the centre of the polyhedron,
                                    and one will have its normal pointing out and the
                                    other one has its normal pointing in.


                                    > I also found is that when U75 is triangulated it is no longer
                                    > orientable! This means that the coplanar coloring isn't going to work on
                                    > U75! There are several others which for which this is the case. An
                                    > interesting situation is U72 which off_report says it is oriented by it
                                    > is not orientable!
                                    >
                                    > off_util -t U72 | off_report
                                    >
                                    > However
                                    >
                                    > off_util -t U72 -O | off_report
                                    >
                                    > says that is is oriented. But then
                                    >
                                    > off_util -t U72 | off_util -O | off_report
                                    >
                                    > says that is is not orientable and is not oriented! I am hoping there is
                                    > a bug going on somewhere. Or perhaps some limitation happened.

                                    This is a good one to find. I haven't checked but I
                                    think I know what is going on. It looks like a bug
                                    caused by having incomplete information about how
                                    faces are connected when more than two meet at an edge.

                                    The first minor issue is that after finding a polyhedron
                                    is oriented it isn't necessary to try and orient it to
                                    check whether it is orientable!

                                    The main problem though is that the orientation process
                                    probably changes the connections, and its choice of
                                    connection may not be that by which the polyhedron
                                    is oriented, and may make the polyhedron unorientable.

                                    If this is is the case, I will report that orientability
                                    is not determinable where a polyhedron has edges shared
                                    by more than two faces (but never an odd number of faces).
                                    I will also have to review what happens for the number of
                                    parts.


                                    > Thanks for the link on stellations. It is something I was thinking might
                                    > be fun to do in the future. Have you ever thought about it?

                                    Only as something to keep in mind. It probably needs a GUI to
                                    select the faces.


                                    > But this thing about triangulation producing non-orientable models has
                                    > me bumbed out. This means that some of models I want to make with
                                    > blended colors might not be possible with my method.

                                    If you are choosing your normals relative to a point then it
                                    shouldn't matter whether the polyhedron is oriented. For
                                    faces passing through the point then you could "normalise"
                                    the direction using the coordinate axes.

                                    If you are using the original orientation then you could
                                    assign a triangle the normal of the face it came from.

                                    Adrian.
                                    --
                                    Adrian Rossiter
                                    adrian@...
                                    http://antiprism.com/adrian
                                  • Adrian Rossiter
                                    Hi Roger ... Here is an example. Three prisms are joined, each sharing an edge with the other two http://www.antiprism.com/misc/orient_choice.jpg The
                                    Message 17 of 22 , Feb 5, 2010
                                    View Source
                                    • 0 Attachment
                                      Hi Roger

                                      On Fri, 5 Feb 2010, Adrian Rossiter wrote:
                                      > The main problem though is that the orientation process
                                      > probably changes the connections, and its choice of
                                      > connection may not be that by which the polyhedron
                                      > is oriented, and may make the polyhedron unorientable.

                                      Here is an example. Three prisms are joined, each sharing
                                      an edge with the other two

                                      http://www.antiprism.com/misc/orient_choice.jpg

                                      The orientation of the top face of each pyramid determines
                                      the orientation of its other faces. Orientation starts at
                                      the vertical square face at "start" and progresses to the
                                      vertical square face at "current".

                                      There are two possibilities for orienting the next face,
                                      which is on the starting pyramid. One choice is consistent
                                      with the orientation of the "start" face and will find the
                                      shape is orientable. The other choice leads to a clash of
                                      orientations and will find that the sphape is non-orientable.

                                      If the connections were given as part of the description
                                      of the shape then there would be no ambiguity.

                                      Adrian.
                                      --
                                      Adrian Rossiter
                                      adrian@...
                                      http://antiprism.com/adrian
                                    • Adrian Rossiter
                                      ... That should have said prism instead of pyramid (there were no pyramids!) Adrian. -- Adrian Rossiter adrian@antiprism.com http://antiprism.com/adrian
                                      Message 18 of 22 , Feb 5, 2010
                                      View Source
                                      • 0 Attachment
                                        On Fri, 5 Feb 2010, Adrian Rossiter wrote:
                                        > Here is an example. Three prisms are joined, each sharing
                                        ...
                                        > The orientation of the top face of each pyramid determines
                                        ...
                                        > which is on the starting pyramid. One choice is consistent

                                        That should have said prism instead of pyramid (there were
                                        no pyramids!)

                                        Adrian.
                                        --
                                        Adrian Rossiter
                                        adrian@...
                                        http://antiprism.com/adrian
                                      • Alan M
                                        Each perpendicular line segment is really the cross product of the area of the face. For example, if each face were a parallelogram, then the resulting
                                        Message 19 of 22 , Feb 5, 2010
                                        View Source
                                        • 0 Attachment
                                          Each perpendicular line segment is really the cross product of the area of the face. For example, if each face were a parallelogram, then the resulting AREA-vector would be the product of two adjacent edges of that parallelogram times the sine of the angle between them. If the angle were a right angle, then the resulting rectangle would have more area than an oblique parallelogram, of course, since the sine of a right angle reaches the maximum of 1. If you are using a triangle, then you are dealing with half of a parallelogram, so your "cross product" would be half as much of course. See http://mathworld.wolfram.com/CrossProduct.html

                                          Note that the only consistency we need to worry about is whether all the vectors point in or point out of the closed polyhedron. Please, let's all not get hung-up whether this is a left-hand or a right-hand coordinate system. I think that either http://mathworld.wolfram.com/Left-HandedCoordinateSystem.html
                                          and/or http://mathworld.wolfram.com/Right-HandedCoordinateSystem.html
                                          are both arbitrary.

                                          Yes, I know about the breakdown of parity and the "right-hand rule" of physics as told in http://scienceworld.wolfram.com/biography/Ampere.html

                                          After all, the vectors have to total to a closed loop, so it really doesn't matter which direction around the loop to go!

                                          http://groups.yahoo.com/group/synergeo/message/22818

                                          --- In antiprism@yahoogroups.com, Adrian Rossiter <Adrian@...> wrote:
                                          >
                                          > If you have a triangle on a plane then the vertices, in
                                          > order, wind in some direction around the triangle centroid
                                          > relative to one side of the plane. The direction of the
                                          > normal depends on this winding direction. If you have two
                                          > triangles on the same plane that wind in different
                                          > directions then they will have normals that point in
                                          > opposite directions.
                                        • Roger Kaufman
                                          Hi Adrian, ... This was a bit of a panic on my part. The code works on everything unitile2d produces. But is possible to create a tiling by hand such that the
                                          Message 20 of 22 , Feb 7, 2010
                                          View Source
                                          • 0 Attachment
                                            Hi Adrian,

                                            > > program was not finding the co-planar faces! This could would not work
                                            > > in this case
                                            > >
                                            > > vec3d norm = face_norm(verts, faces[i]).unit();
                                            > > double D = vdot(verts[faces[i][0]]-C, norm);
                                            > > if(D < 0) // Make sure the normal points outwards
                                            > > norm = -norm;
                                            > >
                                            > > Is it because the centroid is also on the plane with the two coplanar
                                            > > triangles? I think that was the reason.
                                            >
                                            > If you have a triangle on a plane then the vertices, in
                                            > order, wind in some direction around the triangle centroid
                                            > relative to one side of the plane. The direction of the
                                            > normal depends on this winding direction. If you have two
                                            > triangles on the same plane that wind in different
                                            > direcions then they will have normals that point in
                                            > opposite directions.

                                            This was a bit of a panic on my part. The code works on everything unitile2d produces. But is possible to create a tiling by hand such that the normals point in opposite directions and it isn't possible using the code above to determine direction. The program doesn't need to be able to work with models that are already just one plane.

                                            > I haven't had chance to comment on your utility to display
                                            > normals yet. I was thinking that the face attached normals
                                            > would be of visual interest and could be an option in off2*
                                            > and antiview. If there is a geometric use then an option
                                            > could be added to off_util for now.

                                            The program is becoming a mix of code. Where it should all end up can be dealt with later. It is possible some of it might go in src_extra if desired.

                                            But it is nice to plot the normals and see how they stay put no matter what position the model is translated to. I am wondering if a polyhedra can be scaled and positioned such that all the normal to face distances are minimial.

                                            > > says that is is not orientable and is not oriented! I am hoping there is
                                            > > a bug going on somewhere. Or perhaps some limitation happened.
                                            >
                                            > This is a good one to find. I haven't checked but I
                                            > think I know what is going on. It looks like a bug
                                            > caused by having incomplete information about how
                                            > faces are connected when more than two meet at an edge.
                                            >
                                            > The first minor issue is that after finding a polyhedron
                                            > is oriented it isn't necessary to try and orient it to
                                            > check whether it is orientable!

                                            Again more panic on my part. The planes only need to be found before triangulation. On 3D models it is no problem to force normals to all point one way. So in that respect it doesn't even matter of the model is oriented on the way into the program!

                                            It also doesn't matter if the output is orientable. The models are being produced for the sake of viewing. I am not even sure yet, that the output will always come out as closed polyhedra, although I am hoping this is the case!

                                            Roger
                                          Your message has been successfully submitted and would be delivered to recipients shortly.