Re: [brlcad-devel] Tree depth and curve quality in SSI From: phoenix <284281400@qq...> - 2012-07-24 13:55:47 Attachments: Message as HTML ```Hi, > Noticed in your log you ran into a tradeoff between tree build depth > and curve quality. This is actually a useful thing to consider in > more detail - once you have the initial bounding box set, I think > there may be a refinement approach you can take that involves a lot > less overhead than deeper tree builds. I also think about this approach when I write my code - but it's not implemented yet because it needs further looking into the surface tree building process. Now I just use the constructor of SurfaceTree to build a surface tree with a max depth for a face (because it is easy to implement with the existing functions), but when calculating the intersection, I only consider the useful parts (not the entire tree of course). You are right, to build a surface tree with deeper hierarchy takes a long time and consumes lots of memory resources, but only a small subset of it is used in the latter calculation. Maybe the first step is to look deeper into how we build a surface tree and find a way to integrate it into the intersection calculation process - that is, only useful parts of the tree will be generated. When this is finished, maybe a tolerance value will be adapted so that we do not use a constant INTERSECT_MAX_DEPTH, which is not quite elegant. Cheers! Wu```
 Re: [brlcad-devel] Tree depth and curve quality in SSI From: phoenix <284281400@qq...> - 2012-07-24 15:27:46 Attachments: Message as HTML ```> Actually, you might even be able to go with the "build successive sets > of intersecting bounding boxes" approach without ever needing the tree > overhead in the first place. Thanks for your detailed description of the algorithm. Really make sense. Yeh, all we need is to split the surface into four parts using the ON_NurbsSurface::Split method, and this is what the SurfaceTree() routine actually does. Splitting a surface and calculate the sub-surfaces' bounding boxes is just like generating a BBNode's four children. That's also what I intend to do as I said in the last E-mail. I will try it out tomorrow. Cheers! Wu```
 Re: [brlcad-devel] Tree depth and curve quality in SSI From: Clifford Yapp - 2012-07-24 15:03:40 ```On Tue, Jul 24, 2012 at 9:55 AM, phoenix <284281400@...> wrote: > Maybe the first step is to look deeper into how we build > a surface tree and find a way to integrate it into the intersection > calculation process - that is, only useful parts of the tree will be > generated. When this is finished, maybe a tolerance value will be adapted so > that we do not use a constant INTERSECT_MAX_DEPTH, which is not quite > elegant. Actually, you might even be able to go with the "build successive sets of intersecting bounding boxes" approach without ever needing the tree overhead in the first place. The surface tree as currently implemented is primarily used for ray intersections - each ray is starting "from the beginning" when approaching the surface, and hence needs the full tree to be present ahead of time. The SSI calculation, on the other hand, is concerned only with the parts of the surfaces that intersect - the "tree" is just a temporary structure used to find those parts. For SSI, you don't even need a tree at all in the sense of defining parent and child bounding boxes - you just need the intersecting box sets from the two surfaces. My guess is the following - the "piece" you will need from the surface tree building routine is the logic that takes an input surface and generates four sub-surfaces. The routines for calculating bboxes I believe come from openNURBS and aren't specific to the surface tree. The quad surface split may be a good candidate to refactor into a separate function call, if it's not already set up that way. The the algorithm then becomes something along these lines: 1. take two input surfaces, S1 and S2, and calculate their bounding boxes. Check if they overlap. 2 If they do, establish four sets of a structure holding a bounding box and a surface - S1_set1, S2_set1, S1_set2 and S2_set2. The structure would be something like: struct Surface_And_Box { ON_BoundingBox bbox; ON_NurbsSurface surf; } 3. Break S1 into 4 sub-surfaces (using the quad-split functionality broken out from the tree routines) 4. Calculate the bboxes for the 4 subsurfaces of S1 5. Make structure instances holding the bboxes and the corresponding subsurfaces and insert them into S1_set1. 6. Repeat 3-5 for S2. 7. Check that all boxes in S1_set1 intersect at least one box in S2_set1, and vice versa. Remove any non-intersecting boxes from the sets. 8. Now that we have S1_set1 and S2_set1, the iterative refinement can begin. Iterate over the boxes in S1_set1, checking to see if they are dimensionally small enough to serve the SSI algorithm's purposes. For each instance that is small enough, simply move it to S1_set2. If it is not small enough, perform steps 3-5 with the subsurface associated with the given bounding box, except results are inserted into S1_set2 rather than S1_set1 9. Perform the steps from #8 for S2_set1, putting the results in S2_set2. 10. Clear S1_set1 and S2_set1. 11. Test all the bboxes in S1_set1 and S2_set1 for intersection with bboxes in the other set. Move the structures associated with any boxes that do intersect to S1_set1 and S2_set1 respectively. 12. Clear S1_set2 and S2_set2 (anything left in them is non-intersecting and of no further interest.) 13. Repeat steps 8-12 until all boxes in S1_set1 and S2_set1 have suitable size for SSI fitting, then proceed with the remainder of the SSI algorithm. Cheers, Cliff ```