From: phoenix <284281400@qq...>  20120724 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 
From: phoenix <284281400@qq...>  20120724 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 subsurfaces' 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 Email. I will try it out tomorrow. Cheers! Wu 
From: Clifford Yapp <cliffyapp@gm...>  20120724 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 subsurfaces. 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 subsurfaces (using the quadsplit 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 35 for S2. 7. Check that all boxes in S1_set1 intersect at least one box in S2_set1, and vice versa. Remove any nonintersecting 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 35 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 nonintersecting and of no further interest.) 13. Repeat steps 812 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 