Thank you Martin for your quick answer !<br><br><div class="gmail_quote">---------- Forwarded message ----------<br>From: <b class="gmail_sendername">Martin Schreiber</b> <span dir="ltr"><<a href="mailto:schreiberx@googlemail.com" target="_blank">schreiberx@googlemail.com</a>></span><br>
Date: 2009/2/20<br>Subject: Re: Ray tracing<br>To: Olivier Tournaire <<a href="mailto:olitour@gmail.com" target="_blank">olitour@gmail.com</a>><br>Cc: <a href="mailto:libkdtree-devel@lists.alioth.debian.org" target="_blank">libkdtree-devel@lists.alioth.debian.org</a><br>
<br><br>hi olivier!<br>
<br>
i think that libkdtree is not the thing you are searching for because it<br>
operates point-wise only. it's possible to improve the intersection with<br>
kdtrees but it's not as good as other methods. there's no explicit<br>
method for ray intersection within a kdtree.<br>
<br>
to compute an efficient ray intersection with triangles, usually a bsp<br>
trees or octtree is used:<br>
<a href="http://en.wikipedia.org/wiki/Binary_space_partitioning" target="_blank">http://en.wikipedia.org/wiki/Binary_space_partitioning</a><br>
<a href="http://en.wikipedia.org/wiki/Octtree" target="_blank">http://en.wikipedia.org/wiki/Octtree</a><br>
<br>
i used octtrees by myself because it's quite easy to implement it<br>
(building up the octtree) as well as computing the intersections with<br>
the cells.<br><br>OK, that seems to be a good choice ;-) Do you have a pointer to a good C++ implementation ? Or, are you willing to share some code, as I do not want to reinvent the wheel ...<br><br>Best regards,<br><br>
Olivier<br><br>
<br>
feel free to ask further questions or correct me if i misunderstood you.<br>
<br>
greez,<br>
martin<br>
<div><div></div><div><br>
<br>
<br>
<br>
On Fri, 2009-02-20 at 17:39 +0100, Olivier Tournaire wrote:<br>
> Hi all,<br>
><br>
> I recently discovered libkdtree++ and it seems to be really<br>
> interesting. However, before using it in one of my project, I need a<br>
> few questions and I hope you could help me.<br>
> I need to index triangles for fast intersection with rays computing.<br>
> So, I think I have to write two classes, one for 3d points, another<br>
> for 3d triangles which contains 3 points as members. First question:<br>
> which operators do I have to define in order to buil a kdtree to index<br>
> my triangles ? Next, how do I instanciate the KDTree class ?<br>
> Then, I would like to know, once the kdtree is built, which cells are<br>
> intersected by a given 3d ray. How can I achieve this ? Last, once I<br>
> know which cells the ray goes through, I would like to access the<br>
> triangles contained in. Any tip ?<br>
><br>
> Hope I am clear enough to get some help ...<br>
><br>
> Best regards,<br>
><br>
> Olivier<br>
><br>
> --<br>
> Olivier Tournaire<br>
> MATIS - Institut Géographique National<br>
> 73, Ave de Paris<br>
> 94165 St Mandé cedex, France<br>
><br>
> tel: (+33) 1 43 98 80 00 - 71 25<br>
> fax: (+33) 1 43 98 85 81<br>
</div></div>> _______________________________________________<br>
> libkdtree-devel mailing list<br>
> <a href="mailto:libkdtree-devel@lists.alioth.debian.org" target="_blank">libkdtree-devel@lists.alioth.debian.org</a><br>
> <a href="http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel" target="_blank">http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel</a><br>
<br>
</div><br><br clear="all"><br>-- <br>Olivier Tournaire<br>MATIS - Institut Géographique National<br>73, Ave de Paris<br>94165 St Mandé cedex, France<br><br>tel: (+33) 1 43 98 80 00 - 71 25<br>fax: (+33) 1 43 98 85 81<br>