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.