Apollonian Sphere Packing via Web Service and AVF

Spheres are not as common as planar faceted objects in the architectural domain. In spite of that, this week has been the week of the spheres, after looking at how to generate spherical solids, display them using AVF, and use them for geometrical proximity filtering.

We'll round this off now by displaying lots of spheres. A convenient and interesting way to generate a large number of them is to use Kean Walmsley's Apollonian gasket and sphere packing web service to fill a sphere with solid spheres (project overview).

To give you a quick first impression of what it is all about, here are some views of different levels of Apollonian sphere packing using Revit transient solids generated by the GeometryCreationUtilities class and its CreateRevolvedGeometry method and displayed in the Revit graphics area using the Analysis Visualization Framework AVF. Apollonian packing with three levels:

Apollonian packing with three levels

Apollonian packing with five levels:

Apollonian packing with five levels

Apollonian packing with seven levels:

Apollonian packing with seven levels

Retrieval and display of this data in Revit requires the following steps and functionality, listed here in the order of their implementation in the source code:

I'll simply present these sections of code with some comments on each.

String Formatting and Parsing

The string formatting and parsing is required both to obtain input data from the user and to present some timing and statistical results at the end.

The input to the sphere packing algorithm web service consists of an outer sphere radius and the number of steps to execute, which varies from 2 upwards, where 10 is a pretty high number.

I implemented a little .NET form to request this input from the user together with a centre point defining the location in the Revit model to display the packing:

Apollonian sphere packing input data

The following trivial methods are used to parse this input data and format the timing results:

  /// <summary>
  /// Return a string for a real number
  /// formatted to two decimal places.
  /// </summary>
  public static string RealString( double a )
    return a.ToString( "0.##" );
  /// <summary>
  /// Return an integer parsed 
  /// from the given string.
  /// </summary>
  static int StringToInt( string s )
    return int.Parse( s );
  /// <summary>
  /// Return a real number parsed 
  /// from the given string.
  /// </summary>
  static double StringToReal( string s )
    return double.Parse( s );
  /// <summary>
  /// Return an XYZ point or vector 
  /// parsed from the given string.
  /// </summary>
  static XYZ StringToPoint( string s )
    s.TrimStart( new char[] { '(', ' ' } );
    s.TrimEnd( new char[] { ')', ' ' } );
    string[] a = s.Split( new char[] { ',', ' ' } );
    return ( 3 == a.Length ) 
      ? new XYZ( 
          StringToReal( a[0] ), 
          StringToReal( a[1] ), 
          StringToReal( a[2] ) )
      : null;

All trivial stuff, and still it helps to have it nicely sorted.

Web service request and JSON deserialisation

The use of Kean's sphere packing web service is straightforward.

You send it an HTTP request, it returns results in JSON format, you unpack them, and Bob's your uncle.

Kean describes it in detail and presents the source code implementing it in his discussion of consuming data from a restful web service.

It was originally designed for use in AutoCAD.NET. I simply grabbed his code and reuse it completely unchanged:

  static dynamic ApollonianPackingWs( 
    double r, 
    int numSteps, 
    bool circles )
    string json = null;
    // Call our web-service synchronously (this 
    // isn't ideal, as it blocks the UI thread)
    HttpWebRequest request =
        + ( circles ? "circles" : "spheres" )
        + "/" + r.ToString()
        + "/" + numSteps.ToString()
      ) as HttpWebRequest;
    // Get the response
      HttpWebResponse response =
        request.GetResponse() as HttpWebResponse
      // Get the response stream
      StreamReader reader =
        new StreamReader( 
          response.GetResponseStream() );
      // Extract our JSON results
      json = reader.ReadToEnd();
    if( !String.IsNullOrEmpty( json ) )
      // Use our dynamic JSON converter to 
      // populate/return our list of results
      var serializer = new JavaScriptSerializer();
        new[] { new DynamicJsonConverter() }
      // We need to make sure we have enough space 
      // for our JSON, as the default limit may well 
      // get exceeded
      serializer.MaxJsonLength = 50000000;
      return serializer.Deserialize( json, 
        typeof( List<object> ) );
    return null;

AVF Functionality

The code implementing AVF functionality has also already been presented and discussed elsewhere. The last use I made of it was for the initial sphere display using AVF.

All I did here was to replace the PaintSolid method used there to handle multiple solids. I implemented this trivial helper class to associate a solid with a level in order to represent the levels in different colours in the visualisation:

  class SolidAndLevel
    public Solid Solid { get; set; }
    public int Level { get; set; }

Here is the code to create an AVF display style, get or create a SpatialFieldManager, set up an analysis result schema, and display the spherical solids using PaintSolids, taking a list of SolidAndLevel instances as input:

  void CreateAvfDisplayStyle(
    Document doc,
    View view )
    using( Transaction t = new Transaction( doc ) )
      t.Start( "Create AVF Style" );
        coloredSurfaceSettings = new
      coloredSurfaceSettings.ShowGridLines = false;
      AnalysisDisplayColorSettings colorSettings
        = new AnalysisDisplayColorSettings();
      AnalysisDisplayLegendSettings legendSettings
        = new AnalysisDisplayLegendSettings();
      legendSettings.ShowLegend = false;
      AnalysisDisplayStyle analysisDisplayStyle
        = AnalysisDisplayStyle
          .CreateAnalysisDisplayStyle( doc,
            "Paint Solid", coloredSurfaceSettings,
            colorSettings, legendSettings );
        = analysisDisplayStyle.Id;
  static int _schemaId = -1;
  void PaintSolids(
    Document doc,
    IList<SolidAndLevel> solids )
    Application app = doc.Application;
    View view = doc.ActiveView;
    if( view.AnalysisDisplayStyleId
      == ElementId.InvalidElementId )
      CreateAvfDisplayStyle( doc, view );
    SpatialFieldManager sfm
      = SpatialFieldManager.GetSpatialFieldManager(
        view );
    if( null == sfm )
      sfm = SpatialFieldManager
        .CreateSpatialFieldManager( view, 1 );
    if( _schemaId != -1 )
      IList<int> results
        = sfm.GetRegisteredResults();
      if( !results.Contains( _schemaId ) )
        _schemaId = -1;
    if( _schemaId == -1 )
      AnalysisResultSchema resultSchema
        = new AnalysisResultSchema(
          "PaintedSolids", "Description" );
      _schemaId = sfm.RegisterResult( resultSchema );
    foreach( SolidAndLevel sl in solids )
      FaceArray faces = sl.Solid.Faces;
      Transform trf = Transform.Identity;
      foreach( Face face in faces )
        int idx = sfm.AddSpatialFieldPrimitive(
          face, trf );
        IList<UV> uvPts = new List<UV>( 1 );
        uvPts.Add( face.GetBoundingBox().Min );
        FieldDomainPointsByUV pnts
          = new FieldDomainPointsByUV( uvPts );
        List<double> doubleList 
          = new List<double>( 1 );
        doubleList.Add( sl.Level );
        IList<ValueAtPoint> valList
          = new List<ValueAtPoint>( 1 );
        valList.Add( new ValueAtPoint( doubleList ) );
        FieldValues vals = new FieldValues( valList );
          idx, pnts, vals, _schemaId );

Spherical Solid Creation and Mainline

The spherical solid creation is absolutely unchanged from the discussion on Monday, so I can get right down to the mainline Execute method putting it all together. It

Each of the steps is timed, the spheres are counted, and the final results are presented, looking like this for three levels:

Results of Apollonian packing with three levels

For five levels:

Results of Apollonian packing with five levels

For seven levels:

Results of Apollonian packing with seven levels

Revit actually required some additional time on my system to complete and return from the command after these messages were displayed, and mostly that took longer than the entire command execution itself.

Here is the Execute mainline implementing these steps:

  public Result Execute(
    ExternalCommandData commandData,
    ref string message,
    ElementSet elements )
    UIApplication uiapp = commandData.Application;
    UIDocument uidoc = uiapp.ActiveUIDocument;
    Application app = uiapp.Application;
    CreationApp creapp = app.Create;
    Document doc = uidoc.Document;
    if( !(doc.ActiveView is View3D) )
        = "Please run this commahnd in a 3D view.";
      return Result.Failed;
    XYZ centre = XYZ.Zero;
    double radius = 100.0;
    int steps = 3;
    using( Form1 f = new Form1() )
      if( DialogResult.OK != f.ShowDialog() )
        return Result.Cancelled;
      centre = StringToPoint( f.GetCentre() );
      radius = StringToReal( f.GetRadius() );
      steps = StringToInt( f.GetLevel() );
    // Time the web service operation
    Stopwatch sw = Stopwatch.StartNew();
    dynamic res = ApollonianPackingWs( 
      radius, steps, false );
    double timeWs = sw.Elapsed.TotalSeconds;
    // Create solids, going through our "dynamic"
    // list, accessing each property dynamically
    sw = Stopwatch.StartNew();
    List<SolidAndLevel> solids 
      = new List<SolidAndLevel>();
    Dictionary<int, int> counters 
      = new Dictionary<int, int>();
    foreach( dynamic tup in res )
      double rad = System.Math.Abs( (double) tup.R );
      Debug.Assert( 0 < rad, 
        "expected positive sphere radius" );
      XYZ cen = new XYZ( (double) tup.X, 
        (double) tup.Y, (double) tup.Z );
      int lev = tup.L;
      Solid s = CreateSphereAt( creapp, cen, rad );
      solids.Add( new SolidAndLevel { 
        Solid = s, Level = lev } );
      if( !counters.ContainsKey( lev ) )
        counters[lev] = 0;
    double timeSpheres = sw.Elapsed.TotalSeconds;
    // Set up AVF and paint solids
    sw = Stopwatch.StartNew();
    PaintSolids( doc, solids );
    double timeAvf = sw.Elapsed.TotalSeconds;
    int total = 0;
    string counts = string.Empty;
    List<int> keys = new List<int>( counters.Keys );
    foreach( int key in keys )
      if( 0 < counts.Length )
        counts += ",";
      int n = counters[key];
      counts += n.ToString();
      total += n;
    string report = string.Format( 
      "{0} levels retrieved with following sphere "
      + "counts: {1} = total {2}; times in seconds "
      + "for web service {3}, sphere creation {4} "
      + "and AVF {5}.",
      counters.Count, counts, total, 
      RealString( timeWs ), 
      RealString( timeSpheres ), 
      RealString( timeAvf ) );
    TaskDialog.Show( "Apollonian Packing", report );
    return Result.Succeeded;

Since Kean did all the web service implementation and JSON extraction work for me, it all boiled down to just putting together a few ready-made components. Thank you, Kean!

Please refer to Kean's project overview for all the nitty-gritty background details.

Here is Apollonian.zip containing the complete source code, Visual Studio solution and add-in manifest for this external command.

Anyway, this should provide enough spheres for this week and keep us all happy and occupied over the weekend.