StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>How best to approach this for your problem depends on several factors that you have not described: - Will the same hypersphere arrangement be used for many particle collision calculations? - Are the hyperspheres uniform size? - What is the movement of the particle (e.g. straight line/curve) and is that movement affected by the spheres? - Do you consider the particle to have zero volume?</p> <p>I assume that the particle does not have simple straight line movement as that would be the relatively fast calculation of finding the closest point between a line and a point, which is likely going to be about the same speed as finding which of the boxes the line intersects with (to determine where in the n-tree to examine).</p> <p>If your hypersphere positions are fixed for a lot of particle collisions then computing a <a href="http://en.wikipedia.org/wiki/Voronoi_diagram" rel="nofollow noreferrer">voronoi decomposition/Dirichlet tessellation</a> would give you a fast way of later finding exactly which sphere is closest to your particle for any given point in the space.</p> <p>However to answer your original question about octrees/quadtrees/2^n-trees, in n dimensions you start with a (hyper)-cube that contains the area of space that you are interested in. This will be subdivided into 2^n hypercubes if you deem the contents to be too complicated. This continues recursively until you have only simple elements (e.g. one hypersphere centroid) in the leaf nodes. Now that the n-tree is built you use it for collision detection by taking the path of your particle and intersecting it with the outer hypercube. The intersection position will tell you which hypercube in the next level down of the tree to visit next, and you determine the position of intersection with all 2^n hypercubes at that level, following downwards until you reach a leaf node. Once you reach the leaf you can examine interactions between your particle path and the hypersphere stored at that leaf. If you have collision you have finished, otherwise you have to find the exit point of the particle path from the current hypercube leaf and determine which hypercube it moves to next. Continue until you find a collision or entirely leave the overall bounding hypercube.</p> <p>Efficiently finding the neighbouring hypercube when exiting a hypercube is one of the most challenging parts of this approach. For 2^n trees Samet's approaches {1, 2} can be adapted. For kd-trees (binary trees) an approach is suggested in {3} section 4.3.3.</p> <p>Efficient implementation can be as simple as storing a list of 8 pointers from each hypercube to its children hypercubes, and marking the hypercube in a special way if it is a leaf (e.g. make all pointers NULL).</p> <p>A description of dividing space to create a quadtree (which you can generalise to n-tree) can be found in Klinger & Dyer {4}</p> <p>As others have mentioned kd-trees may be more suited than 2^n-trees as extension to an arbitrary number of dimensions is more straightforward, however they will result in a deeper tree. It is also easier to adapt the split positions to match the geometry of your hyperspheres with a kd-tree. The description above of collision detection in a 2^n tree is equally applicable to a kd-tree.</p> <p>{1} <a href="http://portal.acm.org/citation.cfm?id=322267&dl=ACM&coll=ACM" rel="nofollow noreferrer">Connected Component Labeling, Hanan Samet, Using Quadtrees Journal of the ACM Volume 28 , Issue 3 (July 1981)</a></p> <p>{2} <a href="http://portal.acm.org/citation.cfm?id=65329" rel="nofollow noreferrer">Neighbor finding in images represented by octrees, Hanan Samet, Computer Vision, Graphics, and Image Processing Volume 46 , Issue 3 (June 1989)</a></p> <p>{3} <a href="http://people.bath.ac.uk/ensab/G_mod/Distances/" rel="nofollow noreferrer">Convex hull generation, connected component labelling, and minimum distance calculation for set-theoretically defined models, Dan Pidcock, 2000</a></p> <p>{4} Experiments in picture representation using regular decomposition, Klinger, A., and Dyer, C.R. E, Comptr. Graphics and Image Processing 5 (1976), 68-105.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload