On Apr 28, 2008, at 10:14 AM, Keren Lasker wrote: > CGAL might be very useful for various tasks such as grid manipulation, > motion planning, dimensionality reduction and more. > However, I really do not think it should be part of IMP kernel , > which should provide basic functionality common to most tasks. I am not saying CGAL should be part of the kernel. I am saying that the kernel should use CGAL (and any other external library that is easily available and saves us work). Anything which has builds for linux, mac os and windows covers basically all users should probably be fair game as a dependency. Some libraries will provide core functionality (like boost) and so IMP can't be build without them, while others, such as CGAL currently, simply improve IMP and so are optional.
> Two points: > 1. We should have definition of what goes or does not go into the > kernel - I think that now pretty much everything is part of the kernel > ( other the embed lib) I think there are a number of question in here: - The first one, which is just semantic, is what is the "IMP Kernel"? On reasonable answer is that it is everything defined in IMP/*.h (and internal dependencies). - The second is, what should be built into the IMP package (i.e. installed by a single install command). My answer to that is that it should include everything that is likely to be supported as long as IMP is supported. So something that is specific to a particular project and will probably not be picked up by anyone else when the implementer leaves should not be.
> 2. Daniel - can you please elaborate more on the algorithmic > differences between your "improved implementation" and the CGAL one? I > can not help wondering why a simple geometric hashing (~5 c++ classes) > can not help here.
The current grid code uses a list of grids for different sized particles and then takes each particle and searches for collisions in the other grids. Nothing is that complicated, but there are a lot of constants to be messed which with affect the speed. It would make sense to use an octtree instead of the list of grids and various other optimizations like that, but that is more work.
The CGAL code does a plane sweep through space using interval trees and reports the intersections as they arrive.
BTW, I think my attributing the nonlinearity of the grid to the radius spread was not probably not accurate. The spread should be pretty much constant in my timing code. I suspect it has more to do with the increasing number of grid cells searched, perhaps due to constants being balanced wrong or perhaps due to increased memory usage and having to use slower memory. Not sure, and I don't want to investigate now, which is my main point....