[osg-users] KdTree support now checked in

James Killian James_Killian at hotmail.com
Thu Jul 17 05:31:32 PDT 2008


Ooops sorry, there is a game http://www.fringe-online.com/ which makes full use of collision detection (anyone can download the install).  The test I am running has 10 ships (5 red, 5 blue) that are all shooting at each other.  I guess what make these numbers special to me is that for every aspect of the game, this code is the most frequent called, and by a significant amount.  Therefore, I'm going to look for any optimization opportunities (such as the KDTree) to help.

The actual data comes from using the Amd Code Analyzer, while running the game.

James Killian
  ----- Original Message ----- 
  From: Adrian Egli OpenSceneGraph (3D) 
  To: OpenSceneGraph Users 
  Sent: Thursday, July 17, 2008 2:27 AM
  Subject: Re: [osg-users] KdTree support now checked in


  Sorry, 
  i don't really understand where the bench come from. what did you messured, linesegement intersection visitor? 


  2008/7/17 James Killian <James_Killian at hotmail.com>:

    I've got some numbers that are interesting:

    In a build before KDTree.. Matrixd::mult was the most used method:
    1367 Matrixd::Mult
    1080 Matrixd::makeidentity
    982   Group Traverse

    With KDTree on here is how the numbers stand:
    1305 Group::Traverse
    1228 Matrix::mult
    990 Compute Bound
    776 Transform::Compute Bound
    728 MatricsD::Make Identity

    So we can see how the KDTree has brought down the number of Matrixd::Mults, and so now Group Traverse can do more iterations.


    James Killian
    ----- Original Message ----- From: "Robert Osfield" <robert.osfield at gmail.com>
    To: "OpenSceneGraph Users" <osg-users at lists.openscenegraph.org>
    Sent: Saturday, July 12, 2008 10:46 AM
    Subject: Re: [osg-users] KdTree support now checked in



    Hi Adrian,

    It's great to hear you getting better performance.  How much is down
    to more efficient intersections vs other changes to the OSG I cannot
    say - you'd need to profile the relative costs of intersections/cull
    and draw traversals etc.

    KdTree are only used in intersections, so it doesn't change the cull
    and draw traversals at all.  It's not something that is likely to help
    much anyway, as the OpenGL pipeline is geared up to handling a
    moderate number of relatively large sets of geometry, and rarely is
    the actual geometry a bottleneck so it doesn't pay to just a do fine
    grained view frustum culling.  Intersections a completely different
    matter - ray intersection strongly favour fine grained
    representations, hence why KdTree work so well.

    Robert.

    On Sat, Jul 12, 2008 at 4:41 PM, Adrian Egli OpenSceneGraph (3D)
    <3dhelp at gmail.com> wrote:

      Hi Robert,

      i tested the whole afternoon with a really big terrain database (city of
      cannes). i rebuild our internet based visualisation plugin with latest
      openscenegraph (SVN of this morning) and the performance with
      the kdTree datastructure enabled is much better than with elder OSG version.
      i don't yet understand why the performance is much faster, of course the new
      database pager concept could be responsable for the behaviour but i don't
      think so. now the frame rate is really constant, no longer view dependent
      for our motion model, also for the terrain manipulator. each of this motion
      model are using intersection visitor, may this was the reason why the frame
      rate was never constant, was view angle dependant. one pixel changed and the
      frame could dorp down or vise versa. but know the frame rate is nearly
      constant, for this huge database. of course still view dependant, but little
      change doesn't no longer change the frame rate (60/20) between small
      changes, this isn't question of culling,... i guess this was the
      intersection test, if we passed through a huge object, the fps drops down.
      this is greate.

      next question. do you use the KDTree to cull objects against the frustum.
      big objects (Triangles could better culled) if we can intersect easely a
      plane against the kdtree.

      /adrian

      2008/7/12 Robert Osfield <robert.osfield at gmail.com>:


        Hi J-S,

        On Sat, Jul 12, 2008 at 1:09 AM, Jean-Sébastien Guay
        <jean-sebastien.guay at cm-labs.com> wrote:
        > I think I may be able to help a bit regarding the higher-level setup > and
        > bookkeeping changes needed to speed things up on that regard. One thing
        > I
        > noticed before is that creating a new Intersector and
        > IntersectionVisitor
        > each time is costly, and instead keeping static or cached instances and
        > using the reset() and setStart()/setEnd() methods is faster. There may
        > be
        > some other similar things that can be done too, we'll see what I can > dig
        > up.

        It's interesting how different bottlenecks pop up, in this case
        creating objects on the heap is clearly showing itself as a bottleneck
        whereas the old brute force intersection code was so slow that this
        wasn't a significant factor.

        Caching visitors and intersectors can certainly help, although one
        does need to be careful about threading issues with doing this, as the
        IntersectionVisitor and Intersectors aren't thread safe, so you'd need
        a cached instance per thread.

        Optimization could possibly be done with the data structure used to
        store the intersection results, this would unfortunately break the API
        compatibility.  Changing that Intersector's are cloned might also help
        performance when dealing with scene graphs have transform - the clone
        is required to move the intersector into the local coordinate system
        of transforms subgraph.

        There other things one can do like grouping intersectors, or using
        intersection coherency.

        Robert.
        _______________________________________________
        osg-users mailing list
        osg-users at lists.openscenegraph.org
        http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org




      --
      ********************************************
      Adrian Egli
      _______________________________________________
      osg-users mailing list
      osg-users at lists.openscenegraph.org
      http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org



    _______________________________________________
    osg-users mailing list
    osg-users at lists.openscenegraph.org
    http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org

    _______________________________________________
    osg-users mailing list
    osg-users at lists.openscenegraph.org
    http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org




  -- 
  ********************************************
  Adrian Egli 


------------------------------------------------------------------------------


  _______________________________________________
  osg-users mailing list
  osg-users at lists.openscenegraph.org
  http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openscenegraph.org/pipermail/osg-users-openscenegraph.org/attachments/20080717/ee0de38f/attachment-0003.htm>


More information about the osg-users mailing list