September 2014

Sun Mon Tue Wed Thu Fri Sat
  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30        










« The 2009 product family has been announced | Main | Robotic hatching inside AutoCAD using F# and .NET »

February 14, 2008

Robotic hatching inside AutoCAD using .NET

This may strike you as a fairly bizarre title for a post, but I was inspired to develop the below code by a robotic lawnmower we bought about a year ago. This fantastic tool bounces around our garden, changing direction randomly when it hits the lawn's boundary. I got to thinking how to implement a similar technique to hatch a boundary with a polyline. While this is mostly for fun, I can see a few interesting potential uses: you might use the technique to test randomly generated paths of, for example, a robot or you might simply want to supplement traditional hatching with something more random in nature.

The principle is actually very simple: we're going to take a point on the edge of the boundary, and fire a ray (an infinite line) in a random direction - but planar to the boundary - and find out where it intersects the boundary. The tricky piece is that - depending on how "jagged" your boundary is - the ray may actually intersect multiple (i.e. > 2) times. If we want to stay inside the boundary - a requirement for my little robotic hatcher - we need to exclude the segments that would lead us to exiting the boundary to reach the other end.

Excluding the "bad" segments actually proved to be the tricky part. I ended up taking a DevNote from the ADN site (Testing Whether A Point Lies Inside A Curve, for those of you who are ADN members), and converting the C++ code to C#. I won't comment much on the implementation - it's using a similar technique to the one I have in my own code, firing rays to determine intersections - but to be frank I'm only vaguely aware of how it works (ah, the joys of copy & paste development :-).

Here's the converted code. I have it saved in a file called point-in-curve.cs, but clearly the specific name doesn't matter, as long as it is included in your project.

using Autodesk.AutoCAD.DatabaseServices;

using Autodesk.AutoCAD.Geometry;


namespace PointInCurve

{

  public class Fns

  {

    enum IncidenceType

    {

      ToLeft = 0,

      ToRight = 1,

      ToFront = 2,

      Unknown

    };


    static IncidenceType CurveIncidence(

      Curve cur,

      double param,

      Vector3d dir,

      Vector3d normal

    )

    {

      Vector3d deriv1 =

        cur.GetFirstDerivative(param);

      if (deriv1.IsParallelTo(dir))

      {

        // Need second degree analysis


        Vector3d deriv2 =

          cur.GetSecondDerivative(param);

        if (deriv2.IsZeroLength() ||

            deriv2.IsParallelTo(dir))

          return IncidenceType.ToFront;

        else

          if (deriv2.CrossProduct(dir).

              DotProduct(normal) < 0)

            return IncidenceType.ToRight;

          else

            return IncidenceType.ToLeft;

      }


      if (deriv1.CrossProduct(dir).

          DotProduct(normal) < 0)

        return IncidenceType.ToLeft;

      else

        return IncidenceType.ToRight;

    }


    static public bool IsInsideCurve(

      Curve cur,

      Point3d testPt

    )

    {

      if (!cur.Closed)

        // Cannot be inside

        return false;


      Polyline2d poly2d = cur as Polyline2d;

      if (poly2d != null &&

          poly2d.PolyType != Poly2dType.SimplePoly)

        // Not supported

        return false;


      Point3d ptOnCurve =

        cur.GetClosestPointTo(testPt, false);


      if (Tolerance.Equals(testPt, ptOnCurve))

        return true;


      // Check it's planar


      Plane plane = cur.GetPlane();

      if (!cur.IsPlanar)

        return false;


      // Make the test ray from the plane


      Vector3d normal = plane.Normal;

      Vector3d testVector =

        normal.GetPerpendicularVector();

      Ray ray = new Ray();

      ray.BasePoint = testPt;

      ray.UnitDir = testVector;


      Point3dCollection intersectionPoints =

        new Point3dCollection();


      // Fire the ray at the curve

      cur.IntersectWith(

        ray,

        Intersect.OnBothOperands,

        intersectionPoints,

        0, 0

      );


      ray.Dispose();

      int numberOfInters =

        intersectionPoints.Count;

      if (numberOfInters == 0)

        // Must be outside

        return false;


      int nGlancingHits = 0;

      double epsilon = 2e-6; // (trust me on this)

      for (int i = 0; i < numberOfInters; i++)

      {

        // Get the first point, and get its parameter

        Point3d hitPt = intersectionPoints[i];

        double hitParam =

          cur.GetParameterAtPoint(hitPt);

        double inParam = hitParam - epsilon;

        double outParam = hitParam + epsilon;


        IncidenceType inIncidence =

          CurveIncidence(cur, inParam, testVector, normal);

        IncidenceType outIncidence =

          CurveIncidence(cur, outParam, testVector, normal);


        if ((inIncidence == IncidenceType.ToRight &&

            outIncidence == IncidenceType.ToLeft) ||

            (inIncidence == IncidenceType.ToLeft &&

            outIncidence == IncidenceType.ToRight))

          nGlancingHits++;

      }

      return ((numberOfInters + nGlancingHits) % 2 == 1);

    }

  }

}

I then implemented my own code to make use of this library (in this case saved in bounce-hatch.cs):

using Autodesk.AutoCAD.Runtime;

using Autodesk.AutoCAD.ApplicationServices;

using Autodesk.AutoCAD.DatabaseServices;

using Autodesk.AutoCAD.Geometry;

using Autodesk.AutoCAD.EditorInput;

using PointInCurve;


namespace BounceHatch

{

  public class Commands

  {

    // Get a vector in a random direction


    public Vector3d randomUnitVector(

      PlanarEntity pl

    )

    {

      // Create our random number generator


      System.Random ran =

        new System.Random();


      // First we get the absolute value

      // of our x and y coordinates


      double x = ran.NextDouble();

      double y = ran.NextDouble();


      // Then we negate them, half of the time


      if (ran.NextDouble() < 0.5)

        x = -x;

      if (ran.NextDouble() < 0.5)

        y = -y;


      // Create a 2D vector and return it as

      //  3D on our plane


      Vector2d v2 = new Vector2d(x, y);

      return new Vector3d(pl, v2);

    }


    // Allow tracing in 3 colours, depending on

    // whether the vector was accepted, rejected,

    // or superseded by a better one


    enum TraceType

    {

      Accepted = 0,

      Rejected = 1,

      Superseded = 2

    };


    void TraceSegment(

      Point3d start,

      Point3d end,

      TraceType type

    )

    {

      Editor ed =

        Application.DocumentManager.MdiActiveDocument.Editor;

      int vecCol = 0;

      switch (type)

      {

        case TraceType.Accepted:

          vecCol = 3;

          break;

        case TraceType.Rejected:

          vecCol = 1;

          break;

        case TraceType.Superseded:

          vecCol = 2;

          break;

      }

      Matrix3d trans =

        ed.CurrentUserCoordinateSystem.Inverse();

      ed.DrawVector(

        start.TransformBy(trans),

        end.TransformBy(trans),

        vecCol,

        false

      );

    }


    // Test whether a segment goes outside our boundary


    bool TestSegment(

      Curve cur,

      Point3d start,

      Vector3d vec

    )

    {

      // Test 10 points along the segment...


      // (This is inefficient, but it's not a problem for

      //  this application. Some of the redundant overhead

      //  of firing rays for each iteration could be factored

      //  out, among other enhancements, I expect.)


      bool result = true;

      for (int i = 1; i < 10; i++)

      {

        Point3d test = start + (vec * 0.1 * i);


        // Call into our IsInsideCurve library function,

        // "and"-ing the results


        result &=

          PointInCurve.Fns.IsInsideCurve(cur, test);

        if (!result)

          break;

      }

      return result;

    }


    // For a particular boundary, get the next vertex on the

    // curve, found by firing a ray in a random direction


    Point3d nextBoundaryPoint(

      Curve cur,

      Point3d start,

      bool trace

    )

    {

      // Create and define our ray


      Ray ray = new Ray();

      ray.BasePoint = start;

      ray.UnitDir =

        randomUnitVector(cur.GetPlane());


      // Get the intersection points until we

      // have at least 2 returned

      // (will usually happen straightaway)


      Point3dCollection pts =

        new Point3dCollection();

      do

      {

        cur.IntersectWith(

          ray,

          Intersect.OnBothOperands,

          pts,

          0, 0

        );

        if (pts.Count < 2)

        {

          ray.UnitDir =

            randomUnitVector(cur.GetPlane());

        }

      }

      while (pts.Count < 2);


      ray.Dispose();

      // For each of the intersection points - which

      // are points elsewhere on the boundary - let's

      // check to make sure we don't have to leave the

      // area to reach them


      bool first = true;

      double nextLen = 0.0;

      Point3d nextPt = start;


      foreach (Point3d pt in pts)

      {

        // Get the distance between this intersection

        // and the last accepted point - both points

        // are on our ray


        Vector3d vec = pt - start;

        double len = vec.Length;


        // If the vector length is positive and either

        // the first to be a candidate or closer than

        // the previous one (we generally select the

        // closest non-zero option) then check it out

        // further


        if (len > Tolerance.Global.EqualVector &&

            (first || len < nextLen))

        {

          // Run our tests to make sure the segment is

          // inside our boundary


          if (TestSegment(cur, start, vec))

          {

            // Draw the previous segment before overwriting


            if (trace)

              TraceSegment(

                start,

                nextPt,

                TraceType.Superseded

              );


            nextLen = len;

            nextPt = pt;

            first = false;

          }

          else

            // This segment has been rejected,

            // as it goes outside

            if (trace)

              TraceSegment(

                start,

                pt,

                TraceType.Rejected

              );

        }

      }


      // Draw our accepted segment and return it


      if (nextLen > Tolerance.Global.EqualVector)

      {

        if (trace)

          TraceSegment(

            start,

            nextPt,

            TraceType.Accepted

          );

        return nextPt;

      }

      else

        // If we didn't find a good segment, throw an

        // exception to be handled by the calling function

        throw new Exception(

          ErrorStatus.PointNotOnEntity,

          "Could not find another intersection point."

        );

    }


    [CommandMethod("BOUNCE")]

    public void BounceHatch()

    {

      Document doc =

        Application.DocumentManager.MdiActiveDocument;

      Database db = doc.Database;

      Editor ed = doc.Editor;

      bool doTrace = false;


      // Get various bits of user input


      PromptEntityOptions peo =

        new PromptEntityOptions(

          "\nSelect point on closed loop: "

        );

      PromptEntityResult per =

        ed.GetEntity(peo);


      if (per.Status != PromptStatus.OK)

        return;


      PromptIntegerOptions pio =

        new PromptIntegerOptions(

          "\nEnter number of segments: "

          );

      pio.DefaultValue = 500;


      PromptIntegerResult pir =

        ed.GetInteger(pio);


      if (pir.Status != PromptStatus.OK)

        return;


      PromptKeywordOptions pko =

        new PromptKeywordOptions(

          "\nDisplay segment trace: "

        );


      pko.Keywords.Add("Yes");

      pko.Keywords.Add("No");

      pko.Keywords.Default = "Yes";


      PromptResult pkr =

        ed.GetKeywords(pko);


      if (pkr.Status != PromptStatus.OK)

        return;


      Transaction tr =

        db.TransactionManager.StartTransaction();

      using (tr)

      {

        // Check the selected object - make sure it's

        // a closed loop (could do some more checks here)


        DBObject obj =

          tr.GetObject(per.ObjectId, OpenMode.ForRead);

        Curve cur = obj as Curve;

        if (cur == null)

          ed.WriteMessage("\nThis is not a curve.");

        else

        {

          if (!cur.Closed)

            ed.WriteMessage("\nLoop is not closed.");

          else

          {

            // Extract parameters from our user-input...


            // A flag for our vector tracing

            doTrace = (pkr.StringResult == "Yes");

            // The number of segments

            int numBounces = pir.Value;

            // The first vertex of our path

            Point3d latest =

              per.PickedPoint.

                TransformBy(ed.CurrentUserCoordinateSystem).

                  OrthoProject(cur.GetPlane());


            // Create our polyline path, adding the

            // initial vertex


            Polyline path = new Polyline();

            path.Normal = cur.GetPlane().Normal;


            path.AddVertexAt(

              0,

              latest.Convert2d(cur.GetPlane()),

              0.0, 0.0, 0.0

            );


            // For each segment, get the next vertex

            // and add it to the path


            int i = 1;

            while (i <= numBounces)

            {

              try

              {

                Point3d next =

                  nextBoundaryPoint(cur, latest, doTrace);

                path.AddVertexAt(

                  i++,

                  next.Convert2d(cur.GetPlane()),

                  0.0, 0.0, 0.0

                );

                latest = next;

              }

              catch (Exception ex)

              {

                // If there's an exception we know about

                // then ignore it and allow the loop to

                // continue (we probably did not increment

                // i in this case, as it will fail on

                // nextBoundaryPoint)


                if (ex.ErrorStatus !=

                    ErrorStatus.PointNotOnEntity)

                  throw ex;

              }

            }


            // Open the modelspace


            BlockTable bt =

              (BlockTable)

                tr.GetObject(

                  db.BlockTableId,

                  OpenMode.ForRead

                );

            BlockTableRecord btr =

              (BlockTableRecord)

                tr.GetObject(

                  bt[BlockTableRecord.ModelSpace],

                  OpenMode.ForWrite

                );


            // We need to transform the path polyline so

            // that it's over our boundary


            path.TransformBy(

              Matrix3d.Displacement(

                cur.StartPoint - Point3d.Origin

              )

            );


            // Add our path to the modelspace


            btr.AppendEntity(path);

            tr.AddNewlyCreatedDBObject(path, true);

          }

        }


        // Commit, whether we added a path or not.


        tr.Commit();


        // If we're tracing, pause for user input

        // before regenerating the graphics


        if (doTrace)

        {

          pko =

            new PromptKeywordOptions(

              "\nPress return to clear trace vectors: "

            );

          pko.AllowNone = true;

          pko.AllowArbitraryInput = true;

          pkr = ed.GetKeywords(pko);

          ed.Regen();

        }

      }

    }

  }

}

As I've mentioned in the above code, this is not the most efficient possible implementation: we do several (currently 10) checks per potential vertex, to see whether it needs to be excluded. This number might well be reduced, or the library could be updated to provide a more efficient implementation. But for our purposes it works fine, so I'm not going to worry too much. Optimization is left as an exercise for the reader. :-)

Here's what happens when we run the BOUNCE command on a couple of boundaries. The first one I just created for testing - it's a lightweight polyline with three downward prongs that makes it likely that rays fired from the boundary will intersect it multiple (>2) times. For each of these examples I've composed three views: the boundary (pre-hatching), the trace vectors displayed to show the successful vectors (in green) and the excluded vectors (in red), and then the final hatch.

This first loop has been hatched with 100 segments, to clearly show the way the pattern works (or can work, as it's randomly generated).

Basic_loop

The second loop I started drawing with straight segments and then switched to arcs. Somehow I ended up creating something that looks like it's out of Alien, although I wasn't (consciously, at least) in any way inspired by Giger (even though he's Swiss and has a museum in nearby Gruyères). Anyway, this one I hatched with 1000 segments, selecting the initial point on the boundary of the left-most leg: you can see that even with that many segments, not every piece of the boundary was reached using a random algorithm.

Strange_loop

Update:

While working with this a little more, I realised I was not disposing the ray objects we were using for intersection calculations. I've now fixed the above code by inserting calls to ray.Dispose() in the appropriate places.

TrackBack

TrackBack URL for this entry:
http://www.typepad.com/services/trackback/6a00d83452464869e200e5502fecae8833

Listed below are links to weblogs that reference Robotic hatching inside AutoCAD using .NET:

blog comments powered by Disqus

Feed/Share

10 Random Posts