Co planar test

tt_su

Playing around with preallocation did not make any noticeable difference at all. I did not play around adding with mesh.add_point - this would have required a rewrite.

Every time to feed the PolygonMesh a Point3d object it will traverse all the existing points and check if is considered to have equal position. It does that to determine if it should merge points and reuse an existing index or add a new item. This process is currently not optimized so it's an O(N^2) operation. Now think of that when you create a triangle with three Point3d points.

Now, if you use add_point to populate the points you are going to user first - then use the indices collected when you generate your polygons you have performed the minimum amount of O(N^2) operations needed - and add_polygon will simply just add the indices to its internal list in O(1) time for each index.

jolran

@unknownuser said:

Not necessarily. A Ruby Hash lookup will be faster than the linear traversing the C code is doing. When I need performance in Ruby I often find that creating a Hash cache object yields the most performance gain.

As always with these things - never assume - test it.

Thanks! That IS what I was wondering.

WIll do some test indeed

Garry K

Thomas,

That explains why a very large mesh starts taking a long time. For a small mesh there may be very little noticeable benefit using add_point. But for a large mesh it would.

With my handrail example - I go up the rail 1 section at a time adding polygons to the mesh. There are 53 points describing this handrails profile and there are 40 cross sections of 53 points describing the 39 sections. I am reading that the index increments in create order ( providing that there aren't duplicates ). So I will know up front how many unique points to add. I could do 2 passes - the first one adding in ALL the points and the second one adding in the polygons using the indexes. I might even be able to predict the number of polygons in the first pass before I actually start adding in the points.

The other strategy I could try is add 53 points (first time) then add 53 points for second profile then add in the polygons.

I believe that law of diminishing returns has set in - 1/3 of a second is very acceptable. But I am intrigued by this strategy.

So when can we expect some form of 3D tree, KD, AABB, BSP, Oct tree ... ???

tt_su

Yea, if it's fast enough for what you do then now need to optimize. But just wanted to give a general idea of what's going on. In case you need to scale up. We should do a blog post on this topic.

I did in fact try recently with a Oct tree implementation we had for vertices - dirty hack. And it gave great performance improvements. But the memory usage was sky high - I suspect it was due to the overhead of using vertices (much more complex objects.).

So I cannot promise anything - other than tell you that we have been looking into it.

Garry K

Thomas,

I've done C and C++ implementations of a number of different 3D index schemes, quad tree, rtree, bsp and oct trees. I'm thinking that you would have to implement this right in Sketchup. The issue isn't with the tree - it is with your == to determine if a point is a duplicate or not - that is already in sketchup. The key bits are whether to fully balance the tree or not - time vs memory. I wouldn't see the need to put the entire vertex into the tree. The x y z and index should be sufficient. Just use the tree to avoid O(N^2)

Anyway - I did switch over to add_point and then after sufficient points are in the mesh then I added in the polygons. Essentially it was add 53 points, add 53 points add 90 polygons add 53 points add 90 polygons.

Time reduced from 0.375 down to 0.175. So - I believe that I've now pretty much hit the wall. No further optimizations make any sense.

The BLOG idea makes sense - I really didn't feel that I had enough information to do all this until yesterday. Mind you I've only been programming in Ruby a short time. Although 20 years with C / C++ didn't hurt.

Garry K

Thomas,

Another thought - you could provide an option with add_point that bypasses checking for duplicates. Only use if you are certain that you have points that are not duplicates.

That could easily speed things up for situations like brick work, latices etc.

Having said that - perhaps we could load the polygon mesh without checking PolygonMesh.points = pts

tt_su

With an Point3D version of the Oct tree I don't think the point comparison will be an issue any more. From the tests with vertices it scaled very well.
Though I have some more ideas for the PolygonMesh class.