Topic: Can I get an assist from Math Geniuses

[gile]

Hi,

Looking a little further at the results, I notice we were making a big mistake.
Compare the results of any previous command with one which runs sequentally...
None of the previously posted commands returns the expectyed result as foreach point in the collection, we're calling tree.NearestNeighbours(pt, 5) where pt can be any other point in the collection.

One way would be to get the nearest neighbours sequentially and compute the normals using parallel.

Code - C#: [Select]

1.         [CommandMethod("GetNormals")]
2.         public void GetNormals()
3.         {
4.             Document doc = Application.DocumentManager.MdiActiveDocument;
5.             Editor ed = doc.Editor;
6.             Database db = doc.Database;
7.             RXClass rxc = RXClass.GetClass(typeof(DBPoint));
8.  
9.             using (BlockTableRecord btr = (BlockTableRecord)db.CurrentSpaceId.Open(OpenMode.ForWrite))
10.             {
11.                 ObjectId[] ids = btr.Cast<ObjectId>().Where(id => id.ObjectClass == rxc).ToArray();
12.                 int len = ids.Length;
13.                 HashSet<Point3d> pts = new HashSet<Point3d>();
14.                 for (int i = 0; i < len; i++)
15.                 {
16.                     using (DBPoint pt = (DBPoint)ids[i].Open(OpenMode.ForRead))
17.                     {
18.                         pts.Add(pt.Position);
19.                     }
20.                 }
21.                 Point3dTree tree = new Point3dTree(pts, false);
22.                 Vector3d camera = ed.GetCurrentView().ViewDirection;
23.  
24.                 ParallelQuery<Tuple<Point3d, Vector3d>> normals = pts
25.                     .Select(pt => new Tuple<Point3d, Point3dCollection>(pt, tree.NearestNeighbours(pt, 5)))
26.                     .AsParallel()
27.                     .Select(tuple => GetNormal(tuple, camera));
28.  
29.                 foreach (var item in normals)
30.                 {
31.                     using (Line line = new Line(item.Item1, item.Item1 + 200 * item.Item2))
32.                     {
33.                         btr.AppendEntity(line);
34.                     }
35.                 }
36.             }
37.         }
38.  
39.         private Tuple<Point3d, Vector3d> GetNormal(Tuple<Point3d, Point3dCollection> tuple, Vector3d camera)
40.         {
41.             Point3d pt = tuple.Item1;
42.             Point3dCollection neighbors = tuple.Item2;
43.             Point3d npt = Nearest(pt, neighbors), lpt;
44.             Vector3d normal = new Vector3d(), tmp;
45.             while (neighbors.Count > 1)
46.             {
47.                 lpt = npt;
48.                 neighbors.Remove(npt);
49.                 npt = Nearest(npt, neighbors);
50.                 tmp = (lpt - pt).CrossProduct(npt - pt);
51.                 if (normal.DotProduct(tmp) < 0)
52.                     normal -= tmp;
53.                 else
54.                     normal += tmp;
55.             }
56.             if (normal.DotProduct(camera) < 0)
57.             {
58.                 normal = normal.Negate();
59.             }
60.             return new Tuple<Point3d, Vector3d>(pt, normal / normal.Length);
61.         }
62.  
63.         private Point3d Nearest(Point3d pt, Point3dCollection pts)
64.         {
65.             double best = double.MaxValue;
66.             Point3d ret = new Point3d();
67.             foreach (Point3d pnt in pts)
68.             {
69.                 double cur = pt.DistanceTo(pnt);
70.                 if (cur < best)
71.                 {
72.                     best = cur;
73.                     ret = pnt;
74.                 }
75.             }
76.             return ret;
77.         }

[nobody]

Can the code be updated to export the normal values (which I don't even know what that is)?  The software I am using is able to use the normal value like below:

740421.8800000000 3740249.9199999999 308.3200000000 -0.0078839810 -0.2789954587 0.9602600569

first three are coordinates and elevation, last three are supposed to represent a normal value (though I don't know what a normal value is)

Thanks!

[WILL HATCH]

Hi,

Looking a little further at the results, I notice we were making a big mistake.
Compare the results of any previous command with one which runs sequentally...
None of the previously posted commands returns the expectyed result as foreach point in the collection, we're calling tree.NearestNeighbours(pt, 5) where pt can be any other point in the collection.

One way would be to get the nearest neighbours sequentially and compute the normals using parallel.

I'm not quite sure what you mean here, but this version has serious performance losses compared to your last version, I'll try to make sense of why over the weekend.

[WILL HATCH]

Can the code be updated to export the normal values (which I don't even know what that is)?  The software I am using is able to use the normal value like below:

740421.8800000000 3740249.9199999999 308.3200000000 -0.0078839810 -0.2789954587 0.9602600569

first three are coordinates and elevation, last three are supposed to represent a normal value (though I don't know what a normal value is)

Thanks!

the normal is perpendicular to the surface

replace the portion where we draw the lines with the following:

Code - C#: [Select]

1.                 using (StreamWriter sw = new StreamWriter(new FileStream(db.Filename.Substring(0, db.Filename.Length - 4) + ".txt" ,FileMode.Create)))
2.                 {
3.  
4.                     foreach (var item in normals)
5.                     {
6.                         double[] output = item.Item1.ToArray().Concat(item.Item2.ToArray()).ToArray();
7.                         sw.WriteLine(string.Format("{0} {1} {2} {3} {4} {5}", output[0], output[1], output[2], output[3], output[4], output[5]));
8.                     }
9.                 }

[gile]

I'm not quite sure what you mean here, but this version has serious performance losses compared to your last version, I'll try to make sense of why over the weekend.

Sorry my english isn't so good to give a clear explanation.
If you try to run my last "all parallel version" or one of yours two (or more) times on the same points coud, you'll see the results are different each time.
This is due to the calling of tree.NearestNeighbours(pt, 5) in a parallel execution. There may be as different pt as the number of cores processed at the same time and the pt returned as Item1 of the tuple may be different from the one used to compute the vector in the tuple Item2.

Before improving speed performances we have to make sure the method returns the expected results. IOW, start with a strong sequential method and then try to parallelize what can be without returning wrong results.

[gile]

OK, I got it.
This issue was due to the using of (global) fields in the Point3dTree class.
I updated the code here.
The parallel execution seems to work fine now.

[nobody]

I can't thank you enough gentleman! Your code produced exactly what I needed, which enabled me to produce the model I was looking for: