Re: [brlcad-devel] Tree depth and curve quality in SSI

[Clifford Y. <cli...@gm...>]

On Tue, Jul 24, 2012 at 9:55 AM, phoenix <284...@qq...> 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