Through the Interface

Recursive F# code to generate random point clouds inside AutoCAD

At the beginning of the week, we looked at some iterative F# code to generate random point clouds inside AutoCAD. We then took the time to use Reflector to dig under the hood and understand why the previous recursive implementation was causing stack problems.

For completeness (and - I admit it - being driven slightly by laziness, as this is a quick post to crank out :-) here's the recursive version of the random point cloud generation code in F#:

// Use lightweight F# syntax

#light

// Declare a specific namespace and module name

module MyNamespaceRecursive.MyApplication

// Import managed assemblies

#I @"C:\Program Files\Autodesk\AutoCAD 2008"

#r "acdbmgd.dll"

#r "acmgd.dll"

open Autodesk.AutoCAD.Runtime

open Autodesk.AutoCAD.ApplicationServices

open Autodesk.AutoCAD.DatabaseServices

open Autodesk.AutoCAD.Geometry

// Get a random vector on a plane

let randomVectorOnPlane pl =

  // Create our random number generator

  let ran = new System.Random()

  // First we get the absolute value

  // of our x, y and z coordinates

  let absx = ran.NextDouble()

  let absy = ran.NextDouble()

  // Then we negate them, half of the time

  let x = if (ran.NextDouble() < 0.5) then -absx else absx

  let y = if (ran.NextDouble() < 0.5) then -absy else absy

  let v2 = new Vector2d(x,y)

  new Vector3d(pl,v2)

// Get a random vector in 3D space

// Note: _ is only used to make sure this function gets

// executed when it is called... if we have no argument

// it's a value that doesn't require repeated execution

let randomVector3d _ =

  // Create our random number generator

  let ran = new System.Random()

  // First we get the absolute value

  // of our x, y and z coordinates

  let absx = ran.NextDouble()

  let absy = ran.NextDouble()

  let absz = ran.NextDouble()

  // Then we negate them, half of the time

  let x = if (ran.NextDouble() < 0.5) then -absx else absx

  let y = if (ran.NextDouble() < 0.5) then -absy else absy

  let z = if (ran.NextDouble() < 0.5) then -absz else absz

  new Vector3d(x, y, z)

// Now we declare our command

[<CommandMethod("ptsr")>]

let createPoints () =

  // Let's get the usual helpful AutoCAD objects

  let doc =

    Application.DocumentManager.MdiActiveDocument

  let ed = doc.Editor

  let db = doc.Database

  // "use" has the same effect as "using" in C#

  use tr =

    db.TransactionManager.StartTransaction();

  // Get appropriately-typed BlockTable and BTRs

  let bt =

    tr.GetObject

      (db.BlockTableId,OpenMode.ForRead)

    :?> BlockTable

  let ms =

    tr.GetObject

      (bt.[BlockTableRecord.ModelSpace],

      OpenMode.ForRead)

    :?> BlockTableRecord

  // A function that accepts an ObjectId and returns

  // a list of random points on its surface

  let rec getNPoints n (sol:Solid3d) ptlist =

    if n <= 0 then

      ptlist

    else

      let mp = sol.MassProperties

      let pl = new Plane()

      pl.Set(mp.Centroid,randomVector3d n)

      let reg = sol.GetSection(pl)

      let ray = new Ray()

      ray.BasePoint <- mp.Centroid

      ray.UnitDir <- randomVectorOnPlane pl

      let pts = new Point3dCollection()

      reg.IntersectWith

        (ray,

        Intersect.OnBothOperands,

        pts,

        0, 0)

      pl.Dispose()

      reg.Dispose()

      ray.Dispose()

      getNPoints

        (n - pts.Count) sol

        (ptlist @ Seq.untyped_to_list pts)

  let generatePoints numPoints (x : ObjectId) =

    let obj = tr.GetObject(x,OpenMode.ForRead)

    match obj with

    | :? Solid3d ->

      let sol = (obj :?> Solid3d)

      getNPoints numPoints sol []

    | _ -> []

  // A recursive function to show the contents of a list

  let rec drawPointList (x:Point3d list) =

    match x with

    | [] -> ()

    | h :: t ->

      ed.DrawVector(h,h,1,true)

      drawPointList t

  // Let's generate 100K points per solid

  let points = generatePoints 100000

  // Here's where we plug everything together...

  Seq.untyped_to_list ms |> // ObjectIds from modelspace

    List.map points |>      // Get points for each object

      List.concat |>        // No need for the outer list

        drawPointList       // Draw the resultant points

  // As usual, committing is cheaper than aborting

  tr.Commit()

This code is much more elegant from a functional perspective, and F#'s tail call optimization means the resultant code runs just as efficiently as if we'd used iterative code with mutable state. To make the code optimizable, I had to adjust the arguments to the genNPoints function to accept an accumulator object (being the list of points generated thus far). Appending to this list, rather than the one being returned by the next recursion call, allows F# to optimize the recursion into a loop.

Thanks to Namin for his comments on the last post - they were very helpful to my understanding of the problem.

Next week I'm going to try to spend some time diving into the new APIs coming with AutoCAD 2009.

Using Reflector to diagnose tail call optimization in F#

I've talked about Lutz Roeder's Reflector tool a couple of times and it's proven to be very useful to me, once again.

I mentioned in my last post about some problems I was having with tail recursion, and my choice to replace certain recursive functions with iterative versions. Today we're going to use Reflector to take a look under the hood of some compiled assemblies, to determine which recursive functions have been optimised correctly and which have not.

Let's start by taking a look at the two recursive functions I mentioned last time, starting with the most simple:

// A recursive function to show the contents of a list

let rec drawPointList (x:Point3d list) =

match x with

| [] -> ()

  | h :: t ->

  ed.DrawVector(h,h,1,true)

    drawPointList t

Here's what we see when we open the compiled assembly in Reflector and disassemble the equivalent function into C#:

[Serializable]

internal class drawPointList@140 : FastFunc<List<Point3d>, Unit>

{

  // Fields

  public Editor ed;

  // Methods

  public drawPointList@140(Editor ed)

  {

    this.ed = ed;

  }

  public override Unit Invoke(List<Point3d> x)

  {

    while (true)

    {

      List<Point3d> list = x;

      if (!(list is List<Point3d>._Cons))

      {

          break;

      }

      List<Point3d> list2 = ((List<Point3d>._Cons) list)._Cons2;

      Point3d from = ((List<Point3d>._Cons) list)._Cons1;

      this.ed.DrawVector(from, from, 1, true);

      x = list2;

    }

    return null;

  }

}

You can see that the implementation of Invoke contains a while loop, which loops forever (until the list is empty), rather than calling recursively into itself.

Now let's take a look at the other, more complex function, which generates a list of points via recursion:

// A function that accepts an ObjectId and returns

// a list of random points on its surface

let rec getNPoints n (sol:Solid3d) =

  if n <= 0 then

    []

  else

    let mp = sol.MassProperties

    let pl = new Plane()

    pl.Set(mp.Centroid,randomVector3d sol.ObjectId.OldId)

    let reg = sol.GetSection(pl)

    let ray = new Ray()

    ray.BasePoint <- mp.Centroid

    ray.UnitDir <- randomVectorOnPlane pl

    let pts = new Point3dCollection()

    reg.IntersectWith

      (ray,

       Intersect.OnBothOperands,

       pts,

       0, 0)

    pl.Dispose()

    reg.Dispose()

    ray.Dispose()

    let ptlist = Seq.untyped_to_list pts

    ptlist @ getNPoints (n - pts.Count) sol

This function, when compiled by the F# compiler integrated into Visual Studio and disassembled by Reflector, equates to this C# code:

[Serializable]

internal class getNPoints@101T<T> : OptimizedClosures.FastFunc2<int, Solid3d, List<T>>

{

  // Fields

  public TypeFunc _self0;

  // Methods

  public getNPoints@101T(TypeFunc _self0)

  {

    this._self0 = _self0;

  }

  public override List<T> Invoke(int n, Solid3d sol)

  {

    TypeFunc func = this._self0;

    int num = n;

    int t = 0;

    if ((num > t) ^ true)

    {

      return List<T>.Nil_uniq;

    }

    Solid3dMassProperties h = sol.MassProperties;

    Plane plane = new Plane();

    plane.Set(h.Centroid, MyApplication.randomVector3d<int>(sol.ObjectId.OldId));

    Region section = sol.GetSection(plane);

    Ray entityPointer = new Ray();

    entityPointer.BasePoint = h.Centroid;

    entityPointer.UnitDir = MyApplication.randomVectorOnPlane<Plane>(plane);

    Point3dCollection points = new Point3dCollection();

    section.IntersectWith(entityPointer, Intersect.OnBothOperands, points, 0, 0);

    plane.Dispose();

    section.Dispose();

    entityPointer.Dispose();

    List<T> list = Seq.untyped_to_list<Point3dCollection, T>(points);

    Solid3d u = sol;

    int num2 = n - points.Count;

    return Pervasives.op_Append<T>(FastFunc<int, Solid3d>.InvokeFast2<List<T>>((FastFunc<int, FastFunc<Solid3d, List<T>>>) func.Specialize<T>(), num2, u), list);

  }

}

While a little harder to follow (please don't worry about the details), we can see that the recursive tail call has not been optimised out, as we don't have an iterative construct (e.g. a while loop). Instead we see a call to InvokeFast2 (which will result in Invoke being called recursively), prior to the value being returned.

Why exactly this case hasn't been handled isn't clear to me - in fact I'm pretty sure it's a bug in F#, which I will go ahead and report - but it is clear that (at least for now) we need to change the implementation if we're to avoid a stack overflow. And that's fine: the last post contains an iterative version we can use.

Finallly we're going to take a look at parts of the assembly created by building the code in the recent Robotic Hatching posts. As I mentioned previously, I ended up hitting problems when creating 400 or so segments in the polyline hatch when using my F# implementation. Rather than automatically changing each of the recursive functions (those prefixed by "let rec") to iterative versions, I checked the disassembly listings one by one until I found the problematic one:

// A recursive function to get the points

// for our path

let

  if times <= 0 then

    []

  else

    try

      let pt =

        nextBoundaryPoint cur start doTrace

      (pt :: definePath pt (times-1))

    with exn ->

      if exn.Message = "Could not get point" then

        definePath start times

      else

        failwith exn.Message

rec definePath start times =

Here's how the compiled (and then disassembled/reassembled) function looks in C#:

[Serializable]

internal class definePath@281 : OptimizedClosures.FastFunc2<Point3d, int, List<Point3d>>

{

  // Fields

  public Curve cur;

  public bool doTrace;

  // Methods

  public definePath@281(bool doTrace, Curve cur)

  {

    this.doTrace = doTrace;

    this.cur = cur;

  }

  public override List<Point3d> Invoke(Point3d start, int times)

  {

    int num = times;

    int num2 = 0;

    if ((num > num2) ^ true)

    {

      return List<Point3d>.Nil_uniq;

    }

    try

    {

      Point3d pt = Commands.nextBoundaryPoint(this.cur, start, this.doTrace);

      return new List<Point3d>._Cons(pt, FastFunc<Point3d, int>.InvokeFast2<List<Point3d>>(this, pt, times - 1));

    }

    catch (object obj1)

    {

      Exception exn = (Exception) obj1;

      string message = exn.Message;

      string b = "Could not get point";

      if (string.Equals(message, b))

      {

        return FastFunc<Point3d, int>.InvokeFast2<List<Point3d>>(this, start, times);

      }

      return Operators.failwith<List<Point3d>>(exn.Message);

    }

  }

}

This one is actually only recurses when we catch an exception we expect to occur (and actually have thrown ourselves elsewhere in the code) occasionally during run-time. A better implementation - one that F#'s compiler is able to tail call optimise and meets my aesthetic requirements - is here:

// An iterative function to get the points

// for our path

let definePath start times =

  let pts = new Point3dCollection()

  pts.Add(start) |> ignore

  let mutable i = 0

  while i < times do

    try

      let pt =

        nextBoundaryPoint

          cur pts.[pts.Count-1] doTrace runAsync

      pts.Add(pt) |> ignore

      i <- i + 1

    with exn ->

      if exn.Message <> "Could not get point" then

        failwith exn.Message

  Seq.untyped_to_list pts

I won't bother showing this function's C# equivalent, as determined by Reflector, you should just trust me that it's better. :-)

I did change the implementation slightly, so we no longer add our first vertex when we create the polyline - we simply add it to the array of vertices, which is cleaner - and we also have to pass a start index of 0 into the definePath function, rather than 1. Very minor changes, but they actually do make the code slightly simpler.

Anyway, this kind of analysis and control is made possible by the fact that F# compiles to IL, just like the other .NET languages. This allows us to take advantage of existing tools for code analysis & obfuscation, and ultimately give us better, more consistent control than we would get from a functional programming implementation outside of .NET.

Pointing at clouds: more random musings on AutoCAD and F#

On my way back from the US last week, I started thinking more about uses for random numbers inside AutoCAD: especially ones that allow me to try out some possible application areas for F#.

There's something deliciously perverse about using random numbers in Engineering systems, where it's really important for outcomes to be deterministic (i.e. predictable) & precise. And that perversity appeals to me quite strongly, for some reason. Feel free to drop me a mail if you have an idea why that might be, any amateur psychologists out there... ;-)

So, I got to thinking... an interesting domain area for our development partners is that of laser scanning. These systems often generate huge (and I mean huge) data-sets: millions upon millions of points are generated by laser scanners (often known as point clouds), and these need to be managed in some way by software - often by solutions that are integrated with Autodesk products.

So I thought, wouldn't it be fun to go through an AutoCAD model and generated huge arrays of points representing the shell of solid objects in the model - essentially generating random point clouds - to see how F# deals with such humungous data-sets.

The general approach I decided to use was to go through all of the entities in the model-space, open them up and - for those that are of type Solid3d - generate 100,000 points (say) that are found on the shell of the object. To find points on the shell, I adopted the following technique:

1. Create a random 3D vector
2. Generate a random plane intersecting the solid (by using the centroid of the solid as the origin and the generated vector as the normal)
3. Create a region representing the section of the solid and the plane
4. Create another random vector, this time on the plane
5. Use this vector to fire a ray
6. Get the intersection of the ray and the region
7. Repeat until we have enough points

To display each point we just draw a zero-length vector, which I decided to make red.

In my initial implementation, I used a classic functional programming technique, that of tail recursion. As a bit of a purist, I try to use functional (as opposed to imperative) techniques whenever I can when writing F# code. The problem is that tail recursion can significantly drain your stack space, as it results in a new function call - and a new level in the call stack - for every item in your list (and after all we're talking about huge numbers of points). Some compilers/evaluation systems can optimise out the recursive function call, reducing it to a simple branch, but F# doesn't currently appear to do so with my code (it is supposed to, so there may be something about the way my recursive functions are structured that prevents them from being identified as tail-recursive).

Here are a couple of examples of tail-recursive functions - one to generate a list of points, the other to draw them:

  // A function that accepts an ObjectId and returns

  // a list of random points on its surface

  let rec getNPoints n (sol:Solid3d) =

    if n <= 0 then

      []

    else

      let mp = sol.MassProperties

      let pl = new Plane()

      pl.Set(mp.Centroid,randomVector3d sol.ObjectId.OldId)

      let reg = sol.GetSection(pl)

      let ray = new Ray()

      ray.BasePoint <- mp.Centroid

      ray.UnitDir <- randomVectorOnPlane pl

      let pts = new Point3dCollection()

      reg.IntersectWith

        (ray,

        Intersect.OnBothOperands,

        pts,

        0, 0)

      pl.Dispose()

      reg.Dispose()

      ray.Dispose()

      let ptlist = Seq.untyped_to_list pts

      ptlist @ getNPoints (n - pts.Count) sol

  // A recursive function to show the contents of a list

  let rec drawPointList (x:Point3d list) =

    match x with

    | h :: t ->

      ed.DrawVector(h,h,1,true)

      drawPointList t

    | [] -> ()

While more elegant from a functional perspective, this elegance results in sub-optimal execution. The way to "fix" this is to introduce iterative code - whether a for, foreach or while loop - to avoid the recursion.

Here's the complete F# code that makes use of iterative techniques rather than recursion:

// Use lightweight F# syntax

#light

// Declare a specific namespace and module name

module MyNamespace.MyApplication

// Import managed assemblies

#I @"C:\Program Files\Autodesk\AutoCAD 2008"

#r "acdbmgd.dll"

#r "acmgd.dll"

open System

open Autodesk.AutoCAD.Runtime

open Autodesk.AutoCAD.ApplicationServices

open Autodesk.AutoCAD.DatabaseServices

open Autodesk.AutoCAD.Geometry

// Get a random vector on a plane

let randomVectorOnPlane pl =

  // Create our random number generator

  let ran = new System.Random()

  // First we get the absolute value

  // of our x, y and z coordinates

  let absx = ran.NextDouble()

  let absy = ran.NextDouble()

  // Then we negate them, half of the time

  let x = if (ran.NextDouble() < 0.5) then -absx else absx

  let y = if (ran.NextDouble() < 0.5) then -absy else absy

  let v2 = new Vector2d(x,y)

  new Vector3d(pl,v2)

// Get a random vector in 3D space

// Note: _ is only used to make sure this function gets

// executed when it is called... if we have no argument

// it's a value that doesn't require repeated execution

let randomVector3d _ =

  // Create our random number generator

  let ran = new System.Random()

  // First we get the absolute value

  // of our x, y and z coordinates

  let absx = ran.NextDouble()

  let absy = ran.NextDouble()

  let absz = ran.NextDouble()

  // Then we negate them, half of the time

  let x = if (ran.NextDouble() < 0.5) then -absx else absx

  let y = if (ran.NextDouble() < 0.5) then -absy else absy

  let z = if (ran.NextDouble() < 0.5) then -absz else absz

  new Vector3d(x, y, z)

// Now we declare our command

[<CommandMethod("pts")>]

let createPoints () =

  // Let's get the usual helpful AutoCAD objects

  let doc =

    Application.DocumentManager.MdiActiveDocument

  let ed = doc.Editor

  let db = doc.Database

  // "use" has the same effect as "using" in C#

  use tr =

    db.TransactionManager.StartTransaction();

  // Get appropriately-typed BlockTable and BTRs

  let bt =

    tr.GetObject

      (db.BlockTableId,OpenMode.ForRead)

    :?> BlockTable

  let ms =

    tr.GetObject

      (bt.[BlockTableRecord.ModelSpace],

      OpenMode.ForRead)

    :?> BlockTableRecord

  // A function that accepts an ObjectId and returns

  // a list of random points on its surface

  let getNPoints n (sol:Solid3d) =

    let ptcol = new Point3dCollection()

    while ptcol.Count < n do

      let mp = sol.MassProperties

      let pl = new Plane()

      pl.Set

        (mp.Centroid, randomVector3d n)

      let reg = sol.GetSection(pl)

      let ray = new Ray()

      ray.BasePoint <- mp.Centroid

      ray.UnitDir <- randomVectorOnPlane pl

      let pts = new Point3dCollection()

      reg.IntersectWith

        (ray,

        Intersect.OnBothOperands,

        pts,

        0, 0)

      pl.Dispose()

      reg.Dispose()

      ray.Dispose()

      for pt in pts do

        ptcol.Add pt |> ignore

    Seq.untyped_to_list ptcol

  let generatePoints numPoints (x : ObjectId) =

    let obj = tr.GetObject(x,OpenMode.ForRead)

    match obj with

    | :? Solid3d ->

      let sol = (obj :?> Solid3d)

      getNPoints numPoints sol

    | _ -> []

  // An iterative function to draw a point list

  let drawPointList (x:Point3d list) =

    for pt in x do

      ed.DrawVector(pt,pt,1,true)

  // Let's generate 10K points per solid

  let points = generatePoints 100000

  // Here's where we plug everything together...

  Seq.untyped_to_list ms |> // ObjectIds from modelspace

    List.map points |>      // Get points for each object

      List.concat |>        // No need for the outer list

        drawPointList       // Draw the resultant points

  // As usual, committing is cheaper than aborting

  tr.Commit()

Here are the results of the PTS command called on a set of 6 Solid3d objects, essentially generating and drawing 600,000 points. The code doesn't currently result in any persistent graphics at all - if you change views the points all disappear. At some point I'd like to extend this to store the generated points persistently, but for now the point of the exercise (no pun intended :-) is more to see how F# performs with large data-sets, rather than how we deal with the issue of persistence.

A final note: I now realise the use of tail recursion was almost certainly the wall I hit with the F# implementation in this previous post.

Parallelizing robotic AutoCAD hatching with F# and .NET

In the last post we saw some code combining F# with C# to create a random "hatch" - a polyline path that bounces around within a boundary.

This post extends the code to make use of Asynchronous Workflows in F# to parallelize the testing of points along a segment. In the initial design of the application I decided to test 10 points along each segment, to see whether it remained entirely within our boundary: the idea being that this granularity makes it very likely the segment will fail the test, should it happen to leave the boundary at any point. Not 100% guaranteed, but a high probability event. What this code does is take the 10 tests and queue them up for concurrent processing (where the system is capable of it).

Asynchronous Workflows - as suggested by the name - were intended to fire off and manage asynchronous tasks (ones that access network resources, for instance). The segment testing activity is actually very local and processor-bound, so it's not really what the mechanism was intended for, but I thought it would be interesting to try. One interesting point: while testing this code I noticed that it actually ran slower on a single processor machine, which is actually quite logical: only one core is available for processing, so the amount of sequential processing is not reduced but the overhead of synchronizing the various tasks is added. So it was fairly inevitable it would take longer. In the post I first talked about Asynchronous Workflows I showed a sample that queried multiple RSS sites for data: even on a single processor machine this was significantly quicker, as parallelizing the network latency led to a clear gain.

Anyway, as it was slower on this machine I decided only to enable the parallel version of the code in cases where the computer's NUMBER_OF_PROCESSORS environment variable is greater than 1. I checked quickly on a colleague's dual-core machine, and sure enough this variable is set to 2 on his system. I haven't, however, tested the code on a dual- or multi-core system, but I'll be getting a new system in a matter of weeks, which will give me the chance to test it out.

Here's the F# code, with the line numbers highlighting the changes in red:

    1 // Use lightweight F# syntax

    2

    3 #light

    4

    5 // Declare a specific namespace and module name

    6

    7 module BounceHatchAsync.Commands

    8

    9 // Import managed assemblies

   10

   11 #I @"C:\Program Files\Autodesk\AutoCAD 2008"

   12 #I @".\PointInCurve\bin\Debug"

   13

   14 #r "acdbmgd.dll"

   15 #r "acmgd.dll"

   16

   17 #R "PointInCurve.dll" // R = CopyFile is true

   18

   19 open System

   20 open Autodesk.AutoCAD.Runtime

   21 open Autodesk.AutoCAD.ApplicationServices

   22 open Autodesk.AutoCAD.DatabaseServices

   23 open Autodesk.AutoCAD.EditorInput

   24 open Autodesk.AutoCAD.Geometry

   25 open PointInCurve

   26

   27 // Get a random vector on a plane

   28

   29 let randomUnitVector pl =

   30

   31   // Create our random number generator

   32   let ran = new System.Random()

   33

   34   // First we get the absolute value

   35   // of our x and y coordinates

   36

   37   let absx = ran.NextDouble()

   38   let absy = ran.NextDouble()

   39

   40   // Then we negate them, half of the time

   41

   42   let x = if (ran.NextDouble() < 0.5) then -absx else absx

   43   let y = if (ran.NextDouble() < 0.5) then -absy else absy

   44

   45   // Create a 2D vector and return it as

   46   //  3D on our plane

   47

   48   let v2 = new Vector2d(x, y)

   49   new Vector3d(pl, v2)

   50

   51 type traceType =

   52   | Accepted

   53   | Rejected

   54   | Superseded

   55

   56 // Draw one of three types of trace vector

   57

   58 let traceSegment (start:Point3d) (endpt:Point3d) trace =

   59

   60   let ed =

   61     Application.DocumentManager.MdiActiveDocument.Editor

   62

   63   let vecCol =

   64     match trace with

   65     | Accepted -> 3

   66     | Rejected -> 1

   67     | Superseded -> 2

   68   let trans =

   69     ed.CurrentUserCoordinateSystem.Inverse()

   70   ed.DrawVector

   71     (start.TransformBy(trans),

   72     endpt.TransformBy(trans),

   73     vecCol,

   74     false)

   75

   76 // Test a segment to make sure it is within our boundary

   77

   78 let testSegment cur (start:Point3d) (vec:Vector3d) =

   79

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

   81   //  this application. Some of the redundant overhead

   82   //  of firing rays for each iteration could be factored

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

   84

   85   let pts =

   86     [for i in 1..10 -> start + (vec * 0.1 * Int32.to_float i)]

   87

   88   // Call into our IsInsideCurve library function,

   89   // "and"-ing the results

   90

   91   let inside pt =

   92     PointInCurve.Fns.IsInsideCurve(cur, pt)

   93

   94   List.for_all inside pts

   95

   96 // Test a segment to make sure it is within our boundary

   97

   98 let testSegmentAsync cur (start:Point3d) (vec:Vector3d) =

   99

  100   let pts =

  101     [for i in 1..10 -> start + (vec * 0.1 * Int32.to_float i)]

  102

  103   // Call into our IsInsideCurve library function,

  104   // "and"-ing the results

  105

  106   let inside pt =

  107     async { return PointInCurve.Fns.IsInsideCurve(cur, pt) }

  108

  109   let tests =

  110     Async.Run

  111       (Async.Parallel

  112         [for pt in pts -> inside pt])

  113

  114   Array.for_all (fun x -> x) tests

  115

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

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

  118

  119 let nextBoundaryPoint (cur:Curve)

  120     (start:Point3d) trace runAsync =

  121

  122   // Get the intersection points until we

  123   // have at least 2 returned

  124   // (will usually happen straightaway)

  125

  126   let rec getIntersect (cur:Curve)

  127     (start:Point3d) vec =

  128

  129     let plane = cur.GetPlane()

  130

  131     // Create and define our ray

  132

  133     let ray = new Ray()

  134     ray.BasePoint <- start

  135     ray.UnitDir <- vec

  136

  137     let pts = new Point3dCollection()

  138     cur.IntersectWith

  139       (ray,

  140       Intersect.OnBothOperands,

  141       pts,

  142       0, 0)

  143

  144     ray.Dispose()

  145

  146     if (pts.Count < 2) then

  147       let vec2 = randomUnitVector plane

  148       getIntersect cur start vec2

  149     else

  150       pts

  151

  152   // For each of the intersection points - which

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

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

  155   // area to reach them

  156

  157   let plane =

  158     cur.GetPlane()

  159   let pts =

  160     randomUnitVector plane |> getIntersect cur start

  161

  162   // Get the distance between two points

  163

  164   let getDist fst snd =

  165     let (vec:Vector3d) = fst - snd

  166     vec.Length

  167

  168   // Compare two (dist, pt) tuples to allow sorting

  169   // based on the distance parameter

  170

  171   let compDist fst snd =

  172     let (dist1, pt1) = fst

  173     let (dist2, pt2) = snd

  174     if dist1 = dist2 then

  175       0

  176     else if dist1 < dist2 then

  177       -1

  178     else // dist1 > dist2

  179       1

  180

  181   // From the list of points we create a list

  182   // of (dist, pt) pairs, which we then sort

  183

  184   let sorted =

  185     [ for pt in pts -> (getDist start pt, pt) ] |>

  186       List.sort compDist

  187

  188   // A test function to check whether a segment

  189   // is within our boundary. It draws the appropriate

  190   // trace vectors, depending on success

  191

  192   let testItem dist =

  193     let (distval, pt) = dist

  194     let vec = pt - start

  195     if (distval > Tolerance.Global.EqualVector) then

  196       let res =

  197         if runAsync then

  198           testSegmentAsync cur start vec

  199         else

  200           testSegment cur start vec

  201       if res then

  202         if trace then

  203           traceSegment start pt traceType.Accepted

  204         Some(dist)

  205       else

  206         if trace then

  207           traceSegment start pt traceType.Rejected

  208         None

  209     else

  210       None

  211

  212   // Get the first item - which means the shortest

  213   // non-zero segment, as the list is sorted on distance

  214   // - that satisifies our condition of being inside

  215   // the boundary

  216

  217   let ret = List.first testItem sorted

  218   match ret with

  219   | Some(d,p) -> p

  220   | None -> failwith "Could not get point"

  221

  222 // We're using a different command name, so we can compare

  223

  224 [<CommandMethod("fba")>]

  225 let bounceHatch() =

  226   let doc =

  227     Application.DocumentManager.MdiActiveDocument

  228   let db = doc.Database

  229   let ed = doc.Editor

  230

  231   // Get various bits of user input

  232

  233   let getInput =

  234     let peo =

  235       new PromptEntityOptions

  236         ("\nSelect point on closed loop: ")

  237     let per = ed.GetEntity(peo)

  238     if per.Status <> PromptStatus.OK then

  239       None

  240     else

  241       let pio =

  242         new PromptIntegerOptions

  243           ("\nEnter number of segments: ")

  244       pio.DefaultValue <- 500

  245       let pir = ed.GetInteger(pio)

  246       if pir.Status <> PromptStatus.OK then

  247         None

  248       else

  249         let pko =

  250           new PromptKeywordOptions

  251             ("\nDisplay segment trace: ")

  252         pko.Keywords.Add("Yes")

  253         pko.Keywords.Add("No")

  254         pko.Keywords.Default <- "Yes"

  255         let pkr = ed.GetKeywords(pko)

  256         if pkr.Status <> PromptStatus.OK then

  257           None

  258         else

  259           Some

  260             (per.ObjectId,

  261             per.PickedPoint,

  262             pir.Value,

  263             pkr.StringResult.Contains("Yes"))

  264

  265   match getInput with

  266   | None -> ignore()

  267   | Some(oid, picked, numBounces, doTrace) ->

  268

  269     // Capture the start time for performance

  270     // measurement

  271

  272     let starttime = System.DateTime.Now

  273

  274     // We'll run asynchronously only when we have

  275     // multiple processing cores

  276

  277     let runAsync =

  278       (Int32.of_string

  279         (Environment.GetEnvironmentVariable

  280           ("NUMBER_OF_PROCESSORS")))

  281             > 1

  282

  283     use tr =

  284       db.TransactionManager.StartTransaction()

  285

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

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

  288

  289     let obj =

  290       tr.GetObject(oid, OpenMode.ForRead)

  291

  292     match obj with

  293     | :? Curve ->

  294       let cur = obj :?> Curve

  295       if cur.Closed then

  296         let latest =

  297           picked.

  298             TransformBy(ed.CurrentUserCoordinateSystem).

  299               OrthoProject(cur.GetPlane())

  300

  301         // Create our polyline path, adding the

  302         // initial vertex

  303

  304         let path = new Polyline()

  305         path.Normal <- cur.GetPlane().Normal

  306

  307         path.AddVertexAt

  308           (0,

  309           latest.Convert2d(cur.GetPlane()),

  310           0.0, 0.0, 0.0)

  311

  312         // A recursive function to get the points

  313         // for our path

  314

  315         let rec definePath start times =

  316           if times <= 0 then

  317             []

  318           else

  319             try

  320               let pt =

  321                 nextBoundaryPoint cur start doTrace runAsync

  322               (pt :: definePath pt (times-1))

  323             with exn ->

  324               if exn.Message = "Could not get point" then

  325                 definePath start times

  326               else

  327                 failwith exn.Message

  328

  329         // Another recursive function to add the vertices

  330         // to the path

  331

  332         let rec addVertices (path:Polyline)

  333           index (pts:Point3d list) =

  334

  335           match pts with

  336           | [] -> []

  337           | a::[] ->

  338             path.AddVertexAt

  339               (index,

  340               a.Convert2d(cur.GetPlane()),

  341               0.0, 0.0, 0.0)

  342             []

  343           | a::b ->

  344             path.AddVertexAt

  345               (index,

  346               a.Convert2d(cur.GetPlane()),

  347               0.0, 0.0, 0.0)

  348             addVertices path (index+1) b

  349

  350         // Plug our two functions together, ignoring

  351         // the results

  352

  353         definePath picked numBounces |>

  354           addVertices path 1 |>

  355             ignore

  356

  357         // Now we'll add our polyline to the drawing

  358

  359         let bt =

  360             tr.GetObject

  361               (db.BlockTableId,

  362               OpenMode.ForRead) :?> BlockTable

  363         let btr =

  364             tr.GetObject

  365               (bt.[BlockTableRecord.ModelSpace],

  366               OpenMode.ForWrite) :?> BlockTableRecord

  367

  368         // We need to transform the path polyline so

  369         // that it's over our boundary

  370

  371         path.TransformBy

  372           (Matrix3d.Displacement

  373             (cur.StartPoint - Point3d.Origin))

  374

  375         // Add our path to the modelspace

  376

  377         btr.AppendEntity(path) |> ignore

  378         tr.AddNewlyCreatedDBObject(path, true)

  379

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

  381

  382         tr.Commit()

  383

  384         // Print how much time has elapsed

  385

  386         let elapsed =

  387           System.DateTime.op_Subtraction

  388             (System.DateTime.Now, starttime)

  389

  390         ed.WriteMessage

  391           ("\nElapsed time: " + elapsed.ToString())

  392

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

  394         // before regenerating the graphics

  395

  396         if doTrace then

  397           let pko =

  398             new PromptKeywordOptions

  399               ("\nPress return to clear trace vectors: ")

  400           pko.AllowNone <- true

  401           pko.AllowArbitraryInput <- true

  402           let pkr = ed.GetKeywords(pko)

  403           ed.Regen()

  404

  405     | _ ->

  406       ed.WriteMessage("\nObject is not a curve.")

Here's the the complete project which defines both FB and FBA commands for simple side-by-side comparison.

Robotic hatching inside AutoCAD using F# and .NET

I had too much fun with the last post just to let it drop: I decided to port the main command to F#, to show how it's possible to combine C# and F# inside a single project.

The premise I started with was that the point-in-curve.cs library is something that we know works - and don't want to re-write - but would like to use from a new application we're developing in F#. This also gives us the chance to compare the performance between C# and F# when solving the same problem (although as we'll be calling through to some C# code from F# this isn't a pure comparison, in truth).

Anyway, on the train heading for Zurich, before flying back out to San Francisco again (yes, I'm back in San Rafael for another couple of days), I finished up the F# equivalent code for the last post's bounce-hatch.cs file.

Here's the F# code:

// Use lightweight F# syntax

#light

// Declare a specific namespace and module name

module BounceHatch.Commands

// Import managed assemblies

#I @"C:\Program Files\Autodesk\AutoCAD 2008"

#I @".\PointInCurve\bin\Debug"

#r "acdbmgd.dll"

#r "acmgd.dll"

#R "PointInCurve.dll" // R = CopyFile is true

open Autodesk.AutoCAD.Runtime

open Autodesk.AutoCAD.ApplicationServices

open Autodesk.AutoCAD.DatabaseServices

open Autodesk.AutoCAD.EditorInput

open Autodesk.AutoCAD.Geometry

open PointInCurve

// Get a random vector on a plane

let randomUnitVector pl =

  // Create our random number generator

  let ran = new System.Random()

  // First we get the absolute value

  // of our x and y coordinates

  let absx = ran.NextDouble()

  let absy = ran.NextDouble()

  // Then we negate them, half of the time

  let x = if (ran.NextDouble() < 0.5) then -absx else absx

  let y = if (ran.NextDouble() < 0.5) then -absy else absy

  // Create a 2D vector and return it as

  //  3D on our plane

  let v2 = new Vector2d(x, y)

  new Vector3d(pl, v2)

type traceType =

  | Accepted

  | Rejected

  | Superseded

// Draw one of three types of trace vector

let traceSegment (start:Point3d) (endpt:Point3d) trace =

  let ed =

    Application.DocumentManager.MdiActiveDocument.Editor

  let vecCol =

    match trace with

    | Accepted -> 3

    | Rejected -> 1

    | Superseded -> 2

  let trans =

    ed.CurrentUserCoordinateSystem.Inverse()

  ed.DrawVector

    (start.TransformBy(trans),

    endpt.TransformBy(trans),

    vecCol,

    false)

// Test a segment to make sure it is within our boundary

let testSegment cur (start:Point3d) (vec:Vector3d) =

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

  let pts =

    [for i in 1..10 -> start + (vec * 0.1 * Int32.to_float i)]

  // Call into our IsInsideCurve library function,

  // "and"-ing the results

  let inside pt =

    PointInCurve.Fns.IsInsideCurve(cur, pt)

  List.for_all inside pts

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

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

let nextBoundaryPoint (cur:Curve)

    (start:Point3d) trace =

  // Get the intersection points until we

  // have at least 2 returned

  // (will usually happen straightaway)

  let rec getIntersect (cur:Curve)

    (start:Point3d) vec =

    let plane = cur.GetPlane()

    // Create and define our ray

    let ray = new Ray()

    ray.BasePoint <- start

    ray.UnitDir <- vec

    let pts = new Point3dCollection()

    cur.IntersectWith

      (ray,

      Intersect.OnBothOperands,

      pts,

      0, 0)

    ray.Dispose()

    if (pts.Count < 2) then

      let vec2 = randomUnitVector plane

      getIntersect cur start vec2

    else

      pts

  // 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

  let plane =

    cur.GetPlane()

  let pts =

    randomUnitVector plane |> getIntersect cur start

  // Get the distance between two points

  let getDist fst snd =

    let (vec:Vector3d) = fst - snd

    vec.Length

  // Compare two (dist, pt) tuples to allow sorting

  // based on the distance parameter

  let compDist fst snd =

    let (dist1, pt1) = fst

    let (dist2, pt2) = snd

    if dist1 = dist2 then

      0

    else if dist1 < dist2 then

      -1

    else // dist1 > dist2

      1

  // From the list of points we create a list

  // of (dist, pt) pairs, which we then sort

  let sorted =

    [ for pt in pts -> (getDist start pt, pt) ] |>

      List.sort compDist

  // A test function to check whether a segment

  // is within our boundary. It draws the appropriate

  // trace vectors, depending on success

  let testItem dist =

    let (distval, pt) = dist

    let vec = pt - start

    if (distval > Tolerance.Global.EqualVector) then

      if testSegment cur start vec then

        if trace then

          traceSegment start pt traceType.Accepted

        Some(dist)

      else

        if trace then

          traceSegment start pt traceType.Rejected

        None

    else

      None

  // Get the first item - which means the shortest

  // non-zero segment, as the list is sorted on distance

  // - that satisifies our condition of being inside

  // the boundary

  let ret = List.first testItem sorted

  match ret with

  | Some(d,p) -> p

  | None -> failwith "Could not get point"

// We're using a different command name, so we can compare

[<CommandMethod("fb")>]

let bounceHatch() =

  let doc =

    Application.DocumentManager.MdiActiveDocument

  let db = doc.Database

  let ed = doc.Editor

  // Get various bits of user input

  let getInput =

    let peo =

      new PromptEntityOptions

        ("\nSelect point on closed loop: ")

    let per = ed.GetEntity(peo)

    if per.Status <> PromptStatus.OK then

      None

    else

      let pio =

        new PromptIntegerOptions

          ("\nEnter number of segments: ")

      pio.DefaultValue <- 500

      let pir = ed.GetInteger(pio)

      if pir.Status <> PromptStatus.OK then

        None

      else

        let pko =

          new PromptKeywordOptions

            ("\nDisplay segment trace: ")

        pko.Keywords.Add("Yes")

        pko.Keywords.Add("No")

        pko.Keywords.Default <- "Yes"

        let pkr = ed.GetKeywords(pko)

        if pkr.Status <> PromptStatus.OK then

          None

        else

          Some

            (per.ObjectId,

            per.PickedPoint,

            pir.Value,

            pkr.StringResult.Contains("Yes"))

  match getInput with

  | None -> ignore()

  | Some(oid, picked, numBounces, doTrace) ->

    // Capture the start time for performance

    // measurement

    let starttime = System.DateTime.Now

    use tr =

      db.TransactionManager.StartTransaction()

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

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

    let obj =

      tr.GetObject(oid, OpenMode.ForRead)

    match obj with

    | :? Curve ->

      let cur = obj :?> Curve

      if cur.Closed then

        let latest =

          picked.

            TransformBy(ed.CurrentUserCoordinateSystem).

              OrthoProject(cur.GetPlane())

        // Create our polyline path, adding the

        // initial vertex

        let path = new Polyline()

        path.Normal <- cur.GetPlane().Normal

        path.AddVertexAt

          (0,

          latest.Convert2d(cur.GetPlane()),

          0.0, 0.0, 0.0)

        // A recursive function to get the points

        // for our path

        let rec definePath start times =

          if times <= 0 then

            []

          else

            try

              let pt =

                nextBoundaryPoint cur start doTrace

              (pt :: definePath pt (times-1))

            with exn ->

              if exn.Message = "Could not get point" then

                definePath start times

              else

                failwith exn.Message

        // Another recursive function to add the vertices

        // to the path

        let rec addVertices (path:Polyline)

          index (pts:Point3d list) =

          match pts with

          | [] -> []

          | a::[] ->

            path.AddVertexAt

              (index,

              a.Convert2d(cur.GetPlane()),

              0.0, 0.0, 0.0)

            []

          | a::b ->

            path.AddVertexAt

              (index,

              a.Convert2d(cur.GetPlane()),

              0.0, 0.0, 0.0)

            addVertices path (index+1) b

        // Plug our two functions together, ignoring

        // the results

        definePath picked numBounces |>

          addVertices path 1 |>

            ignore

        // Now we'll add our polyline to the drawing

        let bt =

            tr.GetObject

              (db.BlockTableId,

              OpenMode.ForRead) :?> BlockTable

        let btr =

            tr.GetObject

              (bt.[BlockTableRecord.ModelSpace],

              OpenMode.ForWrite) :?> BlockTableRecord

        // 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) |> ignore

        tr.AddNewlyCreatedDBObject(path, true)

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

        tr.Commit()

        // Print how much time has elapsed

        let elapsed =

          System.DateTime.op_Subtraction

            (System.DateTime.Now, starttime)

        ed.WriteMessage

          ("\nElapsed time: " + elapsed.ToString())

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

        // before regenerating the graphics

        if doTrace then

          let pko =

            new PromptKeywordOptions

              ("\nPress return to clear trace vectors: ")

          pko.AllowNone <- true

          pko.AllowArbitraryInput <- true

          let pkr = ed.GetKeywords(pko)

          ed.Regen()

    | _ ->

      ed.WriteMessage("\nObject is not a curve.")

I should make a few points about this

• The code is pretty rough - while I tried to solve the problem in a "functional" style, I was re-writing an "imperative" application, so my thinking was a little entrenched. That said, I was able to use some functional techniques to solve certain bits of the problem more elegantly, I believe.
• The performance is on a par (and at times slightly quicker) than the equivalent C# code
• That said, when trying to bounce 400 or more times (on my system, at least) I get a fatal error. I suspect some stack limit is being reached: when running from the debugger this is not hit, although the performance is much slower.

I need to do some more work on this at some point, but I though I'd post it now along with the complete project. I'm going to have a fairly hectic few days here, but will try to post something more at the end of the week.

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.

The 2009 product family has been announced

For information regarding the upcoming release of AutoCAD 2009 and it's siblings (and perhaps its cousins? :-), check out this post on Shaan Hurley's Between the Lines.

My team has been working on API samples for this release, some of which I'll introduce over the coming weeks. Watch this space!

Modifying the color, linetype and lineweight of an AutoCAD entity using standard dialogs from .NET

In the last post we saw code to display and use AutoCAD's built-in colour, linetype and lineweight dialogs. In this post we extend that by using each of them in sequence to display various properties of an entity, allowing the user to modify them.

While this is slightly more "real world" than the last post, it doesn't really make sense to implement a command such as the one below (the property palette is much better, for instance :-). The main purpose is to show how to set the initial values in the various dialogs and afterwards to make use of the values the user selects.

Here's the C# code:

using Autodesk.AutoCAD.Runtime;

using Autodesk.AutoCAD.ApplicationServices;

using Autodesk.AutoCAD.DatabaseServices;

using Autodesk.AutoCAD.EditorInput;

using Autodesk.AutoCAD.Windows;

namespace EntityProperties

{

  public class Commands

  {

    [CommandMethod("SPE")]

    public void SetPropertiesOnEntity()

    {

      Document doc =

        Application.DocumentManager.MdiActiveDocument;

      Database db = doc.Database;

      Editor ed = doc.Editor;

      PromptEntityResult per =

        ed.GetEntity(

          "\nSelect entity to modify: "

        );

      if (per.Status != PromptStatus.OK)

        return;

      Transaction tr =

        db.TransactionManager.StartTransaction();

      using (tr)

      {

        Entity ent =

          (Entity)

            tr.GetObject(

              per.ObjectId,

              OpenMode.ForRead

            );

        ColorDialog cd = new ColorDialog();

        cd.Color = ent.Color;

        System.Windows.Forms.DialogResult dr;

        dr = cd.ShowDialog();

        if (dr != System.Windows.Forms.DialogResult.OK)

          return;

        LinetypeDialog ltd = new LinetypeDialog();

        ltd.Linetype = ent.LinetypeId;

        dr = ltd.ShowDialog();

        if (dr != System.Windows.Forms.DialogResult.OK)

          return;

        LineWeightDialog lwd = new LineWeightDialog();

        lwd.LineWeight = ent.LineWeight;

        dr = lwd.ShowDialog();

        if (dr != System.Windows.Forms.DialogResult.OK)

          return;

        ent.UpgradeOpen();

        if (ent.Color != cd.Color)

          ent.Color = cd.Color;

        if (ent.LinetypeId != ltd.Linetype)

          ent.LinetypeId = ltd.Linetype;

        if (ent.LineWeight != lwd.LineWeight)

          ent.LineWeight = lwd.LineWeight;

        tr.Commit();

      }

    }

  }

}

Notice that we "return" from the code in a number of places, should the user cancel one of the dialogs. This is perfectly safe, as we're "using" the transaction object, and once it leaves scope it will automatically be disposed (and therefore aborted).

Running the SPE command will display in sequence the dialogs shown in the previous post, and use the user's input to change the state of the selected entity.

Using standard AutoCAD dialogs to select colors, linetypes and lineweights with .NET

AutoCAD has a number of handy dialogs available in the "Autodesk.AutoCAD.Windows" namespace. The following code shows how to use three, in particular: ColorDialog, LinetypeDialog and LineWeightDialog. These three classes allow you to very easily implement user-interfaces selecting their corresponding properties.

Here's the C# code:

using Autodesk.AutoCAD.Runtime;

using Autodesk.AutoCAD.ApplicationServices;

using Autodesk.AutoCAD.DatabaseServices;

using Autodesk.AutoCAD.EditorInput;

using Autodesk.AutoCAD.Windows;

namespace AutoCADDialogs

{

  public class Commands

  {

    [CommandMethod("CDL")]

    public void ShowColorDialog()

    {

      Document doc =

        Application.DocumentManager.MdiActiveDocument;

      Database db = doc.Database;

      Editor ed = doc.Editor;

      ColorDialog cd = new ColorDialog();

      System.Windows.Forms.DialogResult dr =

        cd.ShowDialog();

      if (dr == System.Windows.Forms.DialogResult.OK)

      {

        ed.WriteMessage(

          "\nColor selected: " +

          cd.Color.ToString()

        );

      }

    }

    [CommandMethod("LTDL")]

    public void ShowLinetypeDialog()

    {

      Document doc =

        Application.DocumentManager.MdiActiveDocument;

      Database db = doc.Database;

      Editor ed = doc.Editor;

      LinetypeDialog ltd = new LinetypeDialog();

      System.Windows.Forms.DialogResult dr =

        ltd.ShowDialog();

      if (dr == System.Windows.Forms.DialogResult.OK)

      {

        ed.WriteMessage(

          "\nLinetype selected: " +

          ltd.Linetype.ToString()

        );

      }

    }

    [CommandMethod("LWDL")]

    public void ShowLineWeightDialog()

    {

      Document doc =

        Application.DocumentManager.MdiActiveDocument;

      Database db = doc.Database;

      Editor ed = doc.Editor;

      LineWeightDialog lwd = new LineWeightDialog();

      System.Windows.Forms.DialogResult dr =

        lwd.ShowDialog();

      if (dr == System.Windows.Forms.DialogResult.OK)

      {

        ed.WriteMessage(

          "\nLineweight selected: " +

          lwd.LineWeight.ToString()

        );

      }

    }

  }

}

When we run the CDL command, we have three tabs available:

Here's the dialog shown by the LTDL command:

And the LWDL command:

And here is the command-line output for selecting each of the above items:

Command: CDL

Color selected: 91

Command: CDL

Color selected: 56,166,199

Command: CDL

Color selected: DIC 266

Command: LTDL

Linetype selected: (2130316464)

Command: LWDL

Lineweight selected: LineWeight009

In the next post we'll look at at how to use these dialogs in a more realistic way.

Mardi Gras, Super Tuesday and F#

I'm in San Rafael today, at Autodesk's headquarters, to present F# at an internal meeting. I've just come in for a few days, so rather than adjusting to the Pacific timezone I'm settling for living on Eastern time: I get up at 4am (whether I like it or not ;-) and go to bed as early as I can in the evening. Which gives me some time to catch up on email and think about blog posts.

It's a fun time to be in the US, on balance: I flew in (via New York, as it happens) just as one of the most exciting Superbowl finals in recent history was taking place. The crew provided regular updates over the PA system for all the Giants (or Patriots) fans onboard.

And as well as being Shrove Tuesday/Pancake Day/Mardi Gras, today is also Super Tuesday - possibly the most critical day in the run-up to next year's presidential election in the US. Being in California for this is fun, even if I don't get to vote. :-)

Anyway - on to some technical content. On the plane over I decided to update the F# sample I first posted here to create a PolyFaceMesh rather than a series of Faces. Thanks to Jeremy Tammik for pushing me to do this in time for today's presentation... although it was quite fiddly to generate the list of vertices and add them to the PolyFaceMesh object before adding the various FaceRecords connecting them together, it was worth the effort: the finer-grained control you have over the display of edges - and the convenience of having a single, albeit complex, object - make the sample much more elegant and useful, in my opinion.

Here's the updated F# project, for those of you who are interested. Incidentally, for the purpose of today's demo I chose to turn the edge display off for the entire PolyFaceMesh, as it looks better that way: if you're in a 2D wireframe view (the default in AutoCAD), you won't find the "wow" or "wow2" commands create any geometry when you click your center mouse button on the window that's shown: I recommend loading the template.dwg file into AutoCAD before running the commands - it simply has the realistic visual style set and is zoomed into the location the mesh will be created.