it works for OpenGL ;).Code:
If I group the points in a more complicated data structure like a tree, the speed is not as fast as a 3D array.
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.
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.
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.
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.
Voxel data can easily be represented by a 4D vector.
Your voxel extents are:Code:
float cx; //center X
float cy; //center Y
float cz; //center Z
float size; //size of voxel
Voxel *pVoxelData=new Voxel[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
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.
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.
Let me state the problem more clearly. In a 1000x1000x1000 space, there are 1000 particles.
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)
//We have a proximity hit
} else return false;
float DotProduct(Vector3 vec1,Vector3 vec2)
- >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.
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:
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.