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).

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.

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.

Comments

[Greg Heeley]

Hi Kean
Good looking piece of code.
On similar (ish) lines, do you know of any implementation of a bpoly type command. I am using a method at the moment to run a command line version but due to graphical restrictions its causing me a few problems

[Kean]

Hi Greg,

Someone else has just asked the same question. There isn't an easy answer, unfortunately: there's no boundary detection code exposed, other than via the BOUNDARY/BPOLY/BHATCH commands. So you'd have to do quite a lot of work yourself, to replicate this.

Firing a ray - as in this sample - is a good place to start, though. You would then collect intersection points with other entities in the drawing and perform some analysis on which contribute to the boundary closest to the selected point.

The simplest approach is probably to work through your issues with running the BPLOY command programmatically (the ADN team will be able to help you with this).

Regards,

Kean