Re: [Algorithms] Fast picking against triangle soup

[Luis V. <lui...@mi...>]

There are different ways to speed up the construction process, but you need=
 to understand first how it is being constructed now.  Better heuristics do=
 not necessarily mean higher construction times.  There were some papers pr=
esented on RT06 on this specific topic (i.e. using Adaptive Error Bounded H=
euristics)

As somebody else mentioned on another post, if the construction process end=
s up being too expensive to be done at load time you can probably do it at =
a different stage of the pipeline (i.e. asset import time)

Building some kind of stat reporting into the Kd-tree traversal code would =
help you better understand the problem: tree depth, node count, average tri=
angles per-node, ray/triangle intersections performed for a ray cast, etc.

Luis Villegas

-----Original Message-----
From: gda...@li... [mailto:gdalgorithms-=
lis...@li...] On Behalf Of Robert Blum
Sent: Wednesday, January 31, 2007 9:09 AM
To: Game Development Algorithms
Subject: Re: [Algorithms] Fast picking against triangle soup

> How are you building your kd-tree and how often?  How big is the
> data set you are working with?

Once, at load time. (And they get squirreled away in a cache, since
they're not cheap to build). Can't tell you how we're building them -
just inherited the code yesterday. Still digging through it. Data set
size is somewhere from ~100 tri's to 100,000 tris - depending on the
object.
>
> The symptoms you are describing are not typical for kd-trees, so
> your construction heuristics could be better or your traversal code
> is doing something is not supposed to.

I'm blaming the traversal code. With a semi-reproducible case (i.e. I
keep picking till it's bad), if you break execution, you're about 100
calls or so deep in the callstack. Im just not sure if I want to fix
that, or if there's a better structure around. The loose octree
sounds tempting, and it's not going to take much time to rig up a
test case for it.

> Investing on good construction heuristics can improve performance
> dramatically.

Yes, but aren't they usually negatively impacting construction time?

> Take a look at the real time ray tracing notes for SIGGRAPH 05 and
> 06, and RT06:

Thanks for the pointers - will dig through it.

  - Robert

-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share you=
r
opinions on IT & business topics through brief surveys - and earn cash
http://www.techsay.com/default.php?page=3Djoin.php&p=3Dsourceforge&CID=3DDE=
VDEV
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188