Re: Clojure code for detecting overlap of 3d shapes (specifically tetrahedra)?
On Feb 16, 2014, at 5:07 PM, Karsten Schmidt wrote: Yer welcome please do let me know how this works out for you! I've updated the gist[1] to delay more parts of the whole computation and replace most occurrences of `reduce` with `loop` - altogether leading to an almost 2x faster result for the worst case scenario where all test clauses are checked. K. [1] https://gist.github.com/postspectacular/9021724 Hi Karsten, I've noticed that intersect-tetrahedra? is sometimes asymmetric. Here's an example with randomly generated irregular tetrahedra, but I've noticed it for regular tetrahedra as well: (def t1 [[166 560 158] [889 160 1] [95 683 998] [445 779 516]]) (def t2 [[292 823 490] [868 167 651] [190 869 459] [208 591 753]]) (intersect-tetrahedra? t1 t2) = true (intersect-tetrahedra? t2 t1) = nil Do you have any idea why this might be or how it could be fixed? Thanks, -Lee -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Clojure code for detecting overlap of 3d shapes (specifically tetrahedra)?
Hah! What a classic mistake (not yours)! The bug fix is a single letter change in the last call to `check-faces-b`. The reference point to check against should be the 2nd point in tetra `q`. It currently uses the 1st point `qa`, whereas it should be `qb`. Thanks for testing! Also just updated the gist once more... I verified symmetric results of your test case and also compared once more with the C version. https://gist.github.com/postspectacular/9021724/revisions Hth! K. On 25 February 2014 20:21, Lee Spector lspec...@hampshire.edu wrote: On Feb 16, 2014, at 5:07 PM, Karsten Schmidt wrote: Yer welcome please do let me know how this works out for you! I've updated the gist[1] to delay more parts of the whole computation and replace most occurrences of `reduce` with `loop` - altogether leading to an almost 2x faster result for the worst case scenario where all test clauses are checked. K. [1] https://gist.github.com/postspectacular/9021724 Hi Karsten, I've noticed that intersect-tetrahedra? is sometimes asymmetric. Here's an example with randomly generated irregular tetrahedra, but I've noticed it for regular tetrahedra as well: (def t1 [[166 560 158] [889 160 1] [95 683 998] [445 779 516]]) (def t2 [[292 823 490] [868 167 651] [190 869 459] [208 591 753]]) (intersect-tetrahedra? t1 t2) = true (intersect-tetrahedra? t2 t1) = nil Do you have any idea why this might be or how it could be fixed? Thanks, -Lee -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Karsten Schmidt http://postspectacular.com | http://toxiclibs.org | http://toxi.co.uk -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Clojure code for detecting overlap of 3d shapes (specifically tetrahedra)?
Yer welcome please do let me know how this works out for you! I've updated the gist[1] to delay more parts of the whole computation and replace most occurrences of `reduce` with `loop` - altogether leading to an almost 2x faster result for the worst case scenario where all test clauses are checked. K. [1] https://gist.github.com/postspectacular/9021724 On 15 February 2014 17:25, Lee Spector lspec...@hampshire.edu wrote: On Feb 15, 2014, at 11:49 AM, Karsten Schmidt wrote: Hi Lee, I've already implemented the algorithm described in this paper and it will be part of my upcoming geometry library. To not keep you waiting for the release, I've extracted the relevant code and put up here: https://gist.github.com/postspectacular/9021724 [etc] Hi Karsten, Wow! That is *extremely* helpful! Thank you so much. I will experiment with it as soon as I can and let you know if I run into any issues, but it looks like you've done a fantastic job here, and I'm really grateful that you've done the work and released this part early. Thanks!! -Lee -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Karsten Schmidt http://postspectacular.com | http://toxiclibs.org | http://toxi.co.uk -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Clojure code for detecting overlap of 3d shapes (specifically tetrahedra)?
Hi Lee, I've already implemented the algorithm described in this paper and it will be part of my upcoming geometry library. To not keep you waiting for the release, I've extracted the relevant code and put up here: https://gist.github.com/postspectacular/9021724 I had quite a few problems to get this working reliably (even the original C code). It turned out the algorithm expects the vertices of the tetrahedra to be in a certain ordering or else produces wrong results. I've removed this need and added a function which ensures this expected ordering and in my tests it seems to work all now. Also, since the original C version wasn't very friendly to the Clojure way, I've implemented some of the functions in more Clojuresque way, which actually makes the code much more legible, but also does a little bit more work in some cases than the C version with its endless quick-fail-if-statements... Most of it though is pretty much the same and I've tried to make it as lazy as possible. Any improvements ++welcome though! Hope that helps! K. On 13 February 2014 23:02, Lee Spector lspec...@hampshire.edu wrote: Can anyone point to Clojure code for detecting when two 3d shapes overlap, when given the [x y z] vertices of the two shapes? The specific case I care about will always involve two regular tetrahedra (each of which is specified by 4 vertices), which may allow for special simplifications or efficiencies, but I'd be happy to have a more general solution as long as it's not weirdly slow. I know that there are some sophisticated algorithms for doing this sort of thing (e.g. [1]), but the the algorithms I've found aren't trivial and the only source code I've found is pretty messy and would take some work to translate (e.g. from C). And I figure that if anybody is doing 3d stuff in Clojure then the code for this is probably floating around somewhere... but I haven't been able to find it. Does anyone know of (or want to write :-) code for this? I guess that a Java solution would also be workable, if I the interop is straightforward enough, but it'd be nicer to have a working algorithm in Clojure. Thanks, -Lee [1] Fast tetrahedron-tetrahedron overlap algorithm. F. Ganovelli, F. Ponchio and C. Rocchini August 11, 2002. http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=862BA3F999652E3B0BC1E7A6A3E04D49?doi=10.1.1.114.2540rep=rep1type=pdf -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Karsten Schmidt http://postspectacular.com | http://toxiclibs.org | http://toxi.co.uk -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Clojure code for detecting overlap of 3d shapes (specifically tetrahedra)?
On Feb 15, 2014, at 11:49 AM, Karsten Schmidt wrote: Hi Lee, I've already implemented the algorithm described in this paper and it will be part of my upcoming geometry library. To not keep you waiting for the release, I've extracted the relevant code and put up here: https://gist.github.com/postspectacular/9021724 [etc] Hi Karsten, Wow! That is *extremely* helpful! Thank you so much. I will experiment with it as soon as I can and let you know if I run into any issues, but it looks like you've done a fantastic job here, and I'm really grateful that you've done the work and released this part early. Thanks!! -Lee -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Clojure code for detecting overlap of 3d shapes (specifically tetrahedra)?
Can anyone point to Clojure code for detecting when two 3d shapes overlap, when given the [x y z] vertices of the two shapes? The specific case I care about will always involve two regular tetrahedra (each of which is specified by 4 vertices), which may allow for special simplifications or efficiencies, but I'd be happy to have a more general solution as long as it's not weirdly slow. I know that there are some sophisticated algorithms for doing this sort of thing (e.g. [1]), but the the algorithms I've found aren't trivial and the only source code I've found is pretty messy and would take some work to translate (e.g. from C). And I figure that if anybody is doing 3d stuff in Clojure then the code for this is probably floating around somewhere... but I haven't been able to find it. Does anyone know of (or want to write :-) code for this? I guess that a Java solution would also be workable, if I the interop is straightforward enough, but it'd be nicer to have a working algorithm in Clojure. Thanks, -Lee [1] Fast tetrahedron-tetrahedron overlap algorithm. F. Ganovelli, F. Ponchio and C. Rocchini August 11, 2002. http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=862BA3F999652E3B0BC1E7A6A3E04D49?doi=10.1.1.114.2540rep=rep1type=pdf -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
