Hi Farshid, I've just done a review of your changes and like you feel that performance when handling large flat groups will be prohibitive. This leaves the next question as to what would be a more efficient solution, and whether this might be sufficiently effecient to handle the large group issues.
My first thought would be to avoid using the dedicate visitor and associated std::multimap. Creating the visitor on the stack and map on the heap will be inefficient. Caching a sort data structure that enables reuse would be a saving, as well as using a CPU cache friendly data structure such as a std::vector<pair<float, uint>> or std::vector<double, Node*> or other combination of types. Another approach might be to sort in batches, for instance just have a next four or next eight children be sorted and traversed, and then the next batch. This wouldn't be as efficient at sorting and handling the optimium dpeth order of the large flat group, but it would limit the data structure to a small cache friendly size. For an efficient well balanced scene graph I would expect groups to be broken down into a quad or oct tree so these small batches might well be sufficient to handle all the spatialized groups within one batch. Thoughts? Robert. On Fri, Mar 18, 2011 at 12:20 AM, Farshid Lashkari <[email protected]> wrote: > Hi Robert, > I just noticed that this patch causes significant slowdown on very > large/flat scene graphs. The slowdown seems to be caused by inserting values > into the multimap. Unless we can come up with a better solution, I would > suggest abandoning this optimization. > Cheers, > Farshid > On Thu, Mar 17, 2011 at 11:28 AM, Farshid Lashkari <[email protected]> wrote: >> >> Hi Robert, >> I've attached the optimization to IntersectionVisitor we previously >> discussed, which traverses group children by bounding sphere depth order >> when using the LIMIT_NEAREST mode. >> I'm not sure what is the best method for overriding the traversal order of >> group nodes, so let me know if there is a more efficient method. Basically, >> I create a dummy node visitor that traverses the groups children and saves >> them in a multimap ordered by their bounding sphere depth. >> The IntersectionVisitor then iterates through the multimap and manually >> calls "accept" on the nodes. >> Cheers, >> Farshid > > _______________________________________________ > osg-submissions mailing list > [email protected] > http://lists.openscenegraph.org/listinfo.cgi/osg-submissions-openscenegraph.org > > _______________________________________________ osg-submissions mailing list [email protected] http://lists.openscenegraph.org/listinfo.cgi/osg-submissions-openscenegraph.org
