[osg-users] KdTree support now checked in

Adrian Egli OpenSceneGraph (3D) 3dhelp at gmail.com
Thu Jul 17 00:27:12 PDT 2008


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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openscenegraph.org/pipermail/osg-users-openscenegraph.org/attachments/20080717/ed2bfbf4/attachment-0003.htm>


More information about the osg-users mailing list