Isovist optimization

Hello guys,

So I’m making this project where I needed to recreate isovist code. I managed to recreate a code where every rectangle determines if it’s seeing the outer rectangle or not (for architectural purposes hehe).

My issues is the that the code takes about 30ms and I am using it in an optimization. it would help a lot if anyone can tell me a faster way to get the same results.

here is my code:

private void RunScript(List<Polyline> spaces, Polyline boundary, int nOfRays, double rad, List<string> spaceStrings, string desiredView, string streetView, ref object IsoVist)
  {
    var crvTree = new DataTree<Polyline>();
    //add boundary to test
    var obstacleCrvs = new List<Polyline>();
    obstacleCrvs.AddRange(spaces);
    obstacleCrvs.Add(boundary);

    //isovist params
    var centers = spaces.Select(x => x.CenterPoint());
    var angle = (Math.PI * 2) / nOfRays;
    var isoVist = new DataTree<Point3d>();


    //socring params
    var resultantView = false;
    var scores = new List<int>();
    int totalScore = 0;


    //duplicating tree while removing test point
    for (int i = 0; i < obstacleCrvs.Count - 1 ; i++)
    {
      var newCrvs = new List<Polyline>();
      newCrvs.AddRange(obstacleCrvs);

      newCrvs.RemoveAt(i);
      crvTree.AddRange(newCrvs, new GH_Path(i));
    }
    //-----------------
    //creating isovist
    //-----------------
    var xVector = new Vector3d(1, 0, 0);
    //    var origin = new Point3d(0, 0, 0);

    var rotatedVectors = new List<Vector3d>();
    var lines = new List<Line>();

    int m = 0;
    foreach(Point3d center in centers)
    {
      for(int i = 0;i < nOfRays;i++)
      {
        xVector.Rotate((Math.PI * 2) / nOfRays, new Vector3d(0, 0, 1));
        rotatedVectors.Add(xVector);
        lines.Add(new Line(center, xVector, rad));
      }
      //    }
      //intersect rays with curves
      Rhino.Geometry.Intersect.CurveIntersections curveLinIntersects = null;
      for(int i = 0; i < lines.Count ;i++)
      {
        var orderPoints = new List<Point3d>();

        for(int j = 0; j < crvTree.Branch(m).Count ;j++)
        {
          curveLinIntersects =
            Rhino.Geometry.Intersect.Intersection.CurveCurve(crvTree.Branch(m)[j].ToNurbsCurve(),
            lines[i].ToNurbsCurve(),
            RhinoDocument.ModelAbsoluteTolerance, RhinoDocument.ModelAbsoluteTolerance);

          for(int k = 0; k < curveLinIntersects.Count ;k++)
          {
            var curveLinIntersect = curveLinIntersects[k].PointB;
            orderPoints.Add(curveLinIntersect);
          }
        }
        var ptToAdd = orderPoints.OrderBy(x => x.DistanceTo(center)).FirstOrDefault();
        isoVist.Add(ptToAdd, new GH_Path(m));
      }
      m++;
    }

    IsoVist = isoVist;
  }

and here is my script file
isovist.gh (13.4 KB)
thank you.

For performance reasons it’s good to avoid deeply nested loops. I notice you have a five-level deep nested loops, and also manipulating lists inside the loops (can cause memory allocations). That is typically slow in many languages, not sure how well C# handles this though.

Try make simpler loops and save temp results in lists (or arrays) and process the lists/arrays in the following loops (not nested).

If you can, save data in arrays and reference the data by indexes. In that way you don’t have to manipulate the data size (avoiding memory allocation). This depends on the number of data items though.

Arrays are easy to run in parallel (typically doesn’t cause data-races) which is another reason for using arrays.

You can mimic removal of items in static arrays by setting values to “-1” or double.MinValue etc. at those indexes, and later you can cleanup the lists from those marked-for-deletion-items before outputting the data. And so on.

Using DataTree’s for internal algorithms is no-no at least for me. I use arrays, one or more dimensions, and only at the end of the code I copy the array data into DataTrees, if need be for the output format. DataTrees are slow.

// Rolf

For your code, there’re some key points.

  • Use LineLine intersection instead of CurveCurve, when possible.
  • Do not use .ToNurbsCurve() in the loop. Cache the result if you need to.
  • Use custom Min instead of OrderBy().FirstOrDefault()

The following are also important if you ramp up the input scale.

  • Pre-allocate list. Do not create them dynamically unless necessary
  • Refrain from using DataTree inside your calculation. Per-branch lookup is slow.
  • Make use of Parallel.For and PLINQ
  • foreach on List is slower than for

I created a 2D algorithm of ~1000 lines that doesn’t rely on rays - it calculates the boundary directly. (you still can get the hit points, obviously). It’s more accurate and much faster for occasions with a lot of obstacles.

As for benchmark, my algorithm can process about 2000 rectangluar obstacles in ~30ms.

1 Like

@gankeyu and @RIL

Thank you so much for your help. :pray:
with your help my code went from 34ms to just 3ms.

here is the code:

private void RunScript(List spaces, Polyline boundary, int nOfRays, double rad, List spaceStrings, string desiredView, string streetView, ref object IsoVist, ref object CrvTree)
{
// var crvTree = new DataTree();
//add boundary to test
var obstacleCrvs = new List();
obstacleCrvs.AddRange(spaces);
obstacleCrvs.Add(boundary);

//duplicating tree while removing test point
Line[][][] crvarr = new Line[obstacleCrvs.Count - 1][][];

for (int i = 0; i < obstacleCrvs.Count - 1 ; i++)
{
  var newCrvs = new List<Polyline>(obstacleCrvs.Count);
  newCrvs.AddRange(obstacleCrvs);

  newCrvs.RemoveAt(i);
  var polylineArr = new Line[newCrvs.Count][];

  for(int j = 0; j < newCrvs.Count ; j++)
    polylineArr[j] = newCrvs[j].GetSegments();

  crvarr[i] = polylineArr;
}
//-----------------
//creating isovist
//-----------------
var centers = spaces.Select(x => x.CenterPoint()).ToList();
var angle = (Math.PI * 2) / nOfRays;
Point3d[][] isoVistArr = new Point3d[centers.Count][];
var xVector = new Vector3d(1, 0, 0);
var rotatedVectors = new List<Vector3d>();
//creating lines for each center
var lineTree = new DataTree<Line>();
var lineArr = new Line[centers.Count][];
for(int u = 0; u < centers.Count;u++)
{
  var lines = new Line[nOfRays];
  for(int i = 0;i < nOfRays;i++)
  {
    xVector.Rotate((Math.PI * 2) / nOfRays, new Vector3d(0, 0, 1));
    rotatedVectors.Add(xVector);
    var line = new Line(centers[u], xVector, rad);
    lineTree.Add(line, new GH_Path(u));
    lines[i] = line;
  }
  lineArr[u] = lines;
}
//intersect rays with curves
for(int u = 0; u < centers.Count;u++)
{
  Point3d[] isoVistArrBranch = new Point3d[nOfRays];
  for(int i = 0;i < nOfRays;i++)
  {
    var orderPoints = new List<Point3d>();
    for(int j = 0; j < crvarr[u].Length ;j++)
    {
      for(int k = 0; k < crvarr[u][j].Length ;k++)
      {
        double a;
        double b;
        bool curveLinIntersects =
          Rhino.Geometry.Intersect.Intersection.LineLine(crvarr[u][j][k], lineArr[u][i],
          out a, out b, RhinoDocument.ModelAbsoluteTolerance, true);
        if(curveLinIntersects)
          orderPoints.Add(crvarr[u][j][k].PointAt(a));
      }
    }
    Print(orderPoints.Count.ToString());
    //        var ptToAdd = orderPoints.OrderBy(x => x.DistanceTo(centers[u])).FirstOrDefault();
    var ptToAdd = Rhino.Collections.Point3dList.ClosestPointInList(orderPoints, centers[u]);
    isoVistArrBranch[i] = ptToAdd;
  }
  isoVistArr[u] = isoVistArrBranch;
}
//display isovist
var isoVist = new DataTree<Point3d>();
for (int i = 0; i < isoVistArr.Length; i++)
  isoVist.AddRange(isoVistArr[i], new GH_Path(i));
//    //display crvTree
var crvTree = new DataTree<Line>();
for (int i = 0; i < crvarr.Length; i++)
{
  for (int j = 0; j < crvarr.Length; j++)
  {
    crvTree.AddRange(crvarr[i][j], new GH_Path(i, j));
  }
}
//
CrvTree = crvTree;
IsoVist = isoVist;

}

I hope it helps you. If you have any improvments please don’t hesitate to add them.
Thanks again.

1 Like