it works for OpenGL .Code:struct point3D { int x; int y; int z; };
I was thinking to let my program only represent points that exist in the 3D space, since there are many more slots than the number of the points in the 3D space. However, if I declare a struct like above, it seems that I would lose the ability to check if a particular point in the 3D space has any neighbors in the space, since the indices of the struct provide no clue about the spatial relationships of the points.
If I group the points in a more complicated data structure like a tree, the speed is not as fast as a 3D array.
Last edited by cybernike; 06-27-2007 at 09:31 AM.
Well, in your 3d array to find a neighbor "near" a point you would have to specify some sort of spherical radius around the point to find the neighbor. If you put a bunch of point3D's in an array or vector, you can simply search the array to find points that lie within the specified radius of one point. With the 3d array you would just have to calculate indexes, but you take up much more space.
With what you said, let the radius be 1.
I'd like to know if a point with coordinates (1,1,1) has any particles right next to it. I would have to check if any particle would have the coordinates (0,1,1), (2,1,1), (1,0,1), (1,2,1), (1,1,0), or (1,1,2). The trouble is I would probably have to look through the whole array of struct to see which particle has such coordinates, unless there is some kind of sorting that tells me which particles are closest to the particle that I am interested; that would slow things down quite a bit.
But which tradeoff is larger, doing a search for a few points through a vector that most likely won't reach 1000x1000x1000 point3D's in size, or always have a 1000x1000x1000x8-bit sized array no matter how many points you may have. What if you want to represent a larger area in space?
Pllus your search would most likely be short circuit execution. If one arameter is not within the boundary you would ignore the entire entry. Still slow but the alternative is having a large file.
Also, how are you going to refer to these points in 3d space with an array?
If you simply store the points that have something, you can organize them into a tree, therefore allowing reasonable (log n) search time, but saving massive amounts of memory.
Programming Your Mom. http://www.dandongs.com/
Doing a search for a few points through a vector? why only a few points? do you mean you have done some kind of sorting that would tell us the nearest neighbors of a particular particle?
I really can't sacrifice any speed since my fully implemented program with about 1000 particles in a 1000x1000x1000 space would require a whole week to finish the simulations of the trajectories of the particles.
I don't really care which point is which; I only care if a particle has any neighbors right next to it, so I would check the truth values of the 6 sets of coordinates that are next to the particle interested.
Last edited by cybernike; 06-27-2007 at 12:03 PM.
but then somewhere you are still generating/storing a list of particles to check, unless you intend to check every particle location, in which case that check will take far longer than just having a list of particles that do exist and running a distance check with every other particle to check for proximity. There are optimizations for checking locality that are much faster than calculating the geometric distance, check out some good books on game programming, they usually have an entire chapter on collision detection, which deals heavily with proximity of objects.
In any case, you either have to put up with having a huge memory requirement, or having a huge processing requirement. The choice is up to you, there is no magical third choice.
With only 1000 particles, I dont see how ANY calculation of trajectories would take a whole week. Perhaps you could elaborate on exactly what you are calculating.
Last edited by abachler; 06-27-2007 at 01:12 PM.
Thanks, I will definitely try to get some ideas from game programming.
If I have to choose between memory and speed, speed is definitely more important.
I have not specified the time scale; in each time unit, there are about 6*1000 jumps of the particles. In each simulation run, there are about 2^22 time units. So there are about 6*1000*2^22 hops. Also, I need to at least run the simulation for 5 to 10 times to get an average. Therefore, there are many many many calculations, even though each calculation may not be too complicated. I haven't even mentioned the data analysis in the program.
Voxel data can easily be represented by a 4D vector.
Your voxel extents are:Code:struct Voxel { float cx; //center X float cy; //center Y float cz; //center Z float size; //size of voxel }; Voxel *pVoxelData=new Voxel[size];
cx-size,cy-size,cz-size
cx+size,cy+size,cz+size
In a 3D game you would frustum cull based on this diagonal and test against the frustum, or you could do a more expensive six plane test. It would not be a good idea to cull at the voxel level and perhaps a quad tree voxel system would work best. Those voxels that fall within a certain volume of space would be calculated. So you would have sections of voxels or, if you will, larger voxels containing sub-voxel data.
Keep in mind if the voxel position data does not change and therefore will never cross a quad-tree boundary, you can use an array instead of std::vector. This looks like a 2D tree but it is actually a volumetric quad-tree structure.Code:#define QTREE_ROOT 1 #define QTREE_NODE 2 #define QTREE_LEAF 3 struct Vector3 { float x; float y; float z; }; struct VoxelQuadTree { std::vector<Voxel *> pVoxels; //list of voxels belonging to this voxel int iType; //Is this the root, a node, or a leaf? Vector3 Max; //Max Extents of this volume - for bounds check Vector3 Min; //Min Extents of this volume VoxelQuadTree *pUpperLeft; //Upper left neighbor VoxelQuadTree *pUpperRight; //Upper right neighbor VoxelQuadTree *pLowerLeft; //Lower left neighbor VoxelQuadTree *pLowerRight; //Lower right neighbor };
Rules for frustum culling:
- If current node is out, all of the node's neighbors are too and do not need to be checked. The entire node and all it's associated neighbors can be discarded.
- If current node is in, all of the node's neighbors are also in and do not need to be checked. The entire node and all it's neighbors can be added to a render list or update list.
- If current node is partially in, you must check all of it's neighbors to also see if they are in or out. Check until you get all in or all out.
- Do not worry about sub-voxels that may be partially in and partially out. Cull at the voxel volume level and not at the sub-voxel level.
With an approach like this you could eliminate hundreds or thousands of voxels in about 2 recursions through the tree.
Whatever way you approach it what we are all saying is there is a much better way to store your data in memory than what you have chosen.
Last edited by VirtualAce; 06-28-2007 at 12:48 AM.
Let me state the problem more clearly. In a 1000x1000x1000 space, there are 1000 particles. We can only move one particle at a time, and the particle can move in one of the six directions by 1 unit as long as it is not blocked by the other particles.
I am sure there are more efficient ways to represent the data in terms of space.
However, please let me ask your opinion on this. Is there any other way that is faster or as fast as using a 3D-matrix to determine if a move is allowed. As I said, I wouldn't want to sacrifice any speed.
Think again.Let me state the problem more clearly. In a 1000x1000x1000 space, there are 1000 particles.
"If you tell the truth, you don't have to remember anything"
-Mark Twain
If you only have 1000 particles you do not need a 1000x1000x1000 array to represent them. An array of 1000 vertices or particles will suffice. You can do a sphere check to see if the particles can move or not. But you don't want to test each of the 1000 particles against all 999 other particles to do the movement. You will need some type of spatial partitioning system. It does not make sense to test whether particle 1 comes into contact with particle 999 if particle 1 is thousands of units away from particle 999. It also does not make sense to test particles colliding if they are not moving, or if they are not moving toward each other. Two particles that are moving away from each other will never collide and therefore testing whether they will or not is a waste of time.
You can use this sphere test:
To determine if two particles are heading towards or away from one another you can compute the dot product of the two velocity vectors. You only need to worry about the sign of the result. You do not need to worry about normalizing the vectors here because the sign will not be affected.Code:bool SphereTest(Vector3 vec1,Vector3 vec2,float fDistSquared) { float diffx=vec1.x-vec2.x; float diffy=vec1.y-vec2.y; float diffz=vec1.z-vec2.z; float diffx2=diffx*diffx; float diffy2=diffy*diffy; float diffz2=diffz*diffz; float fTotalDistSquared=diffx2+diffy2+diffz2; if (fTotalDistSquared<fDistSquared) { //We have a proximity hit return true; } else return false; }
Result is:Code:float DotProduct(Vector3 vec1,Vector3 vec2) { return ((vec1.x*vec2.x)+(vec1.y*vec2.y)+(vec1.z*vec2.z)); }
- >0 - Vectors are basically pointing in same direction
- =0 - Vectors are perpendicular
- <0 - Vectors are basically pointing in opposite directions
To further illustrate the dot product here is a Java app I found. Just follow the instructions on the page.
http://www.falstad.com/dotproduct/
Last edited by VirtualAce; 06-28-2007 at 01:37 AM.
It is true that using a 1000x1000x1000 matrix will give you a general O(1) algorithm, because you will have direct indexing, which of course is blazingly fast. We all know that, and we are not denying that.
What many people before me are saying, and what I am about to say, is that there are better ways to do it that use much less memory, and are still very very fast, even if they don't qualify as O(1). How do you think advanced games such as Doom 3, Quake 4, or HalfLife would do this kind of thing? They certainly don't store a 970 MB boolean array in your computer's memory. That is absurd to think about....yet....these games still run incredibly fast...so how did they do it? Well...they used many of the principles that have already been mentioned above.
Now, I would like to suggest an alternative method that might be kind of out of the ordinary, but it might work. It is based on the idea of using a binary tree, which has already been suggested. My idea is basically to further that same idea, and use a map. A map just uses a binary tree on the back end anyways. Like someone as already stated, it will give you O(log n) time in your algorithm, which is still incredibly fast.
All you will have to do is check to see if a certain point is contained in the map. For example:
First initialize all of your 1000 points that youCode:struct Point3D { int x; int y; int z; }; map < Point3D, bool > myPointMap;
say that you have...that's fairly simple to do.
Then, just iterate through all those points, and
initialize your map:
Now your map is completely set up. Anytime you move a point,Code:myPointMap[ myPoint3D[i] ] = true;
you can go to that point in the map, and do a simple spherical
radius check of the points around that point. If nothing
blocks it, set that point in the map to false, and move it
to the new point.
log n time using a map.