3D search

OK, before I start, yeah, this is for a game, but the reason I posted the question in here is because it's a tool I want to use in a game and has nothing to do with the actual game.

So here's the problem: I have lots of 3D points which are actually a series of struct's containing three floats: x,y and z. I also have a file which contains the information on these points.

Suppose I already have all these points in a big array (BIG means in the order of tens of thousands).

each "frame", which is actually about 1/30th of a second (at worst), I have another 3D position with two vectors defining direction and roll , all these actually make the viewer's position.

what I want to do is to know what points are useful for me to process (there are a lot of operations in here), which are actually defined by the 3D position, direction and roll of the viewer, and a clipping distance (the maximud distance I want to show), but I don't want to make lots of calculations for each point in order to see if it's of my interest EACH FRAME!, it would be really slow!

I want to find a way to find all these points without sacrificing game time (I'm willing to sacrifice loading time (like hashing, or something like that), but not game time)

does anybody know a way to do this, or at least enhance the "stupid" method?

Oskilian

hi there,
you just study the various searching methods.
i know some best searching methods that i feel that best for you .
these are,
hash table searching method.
bfs

bye.

It seems like you shouldn't have to test every point to see if it's of interest every frame.

Let's say your array is 60000 elements. Every frame you could check 4000 of those elements, so every .5 seconds, the entire list would be updated.

This has the problem of you changing your position and some of the points are not marked as usefull to process, but that should not be a problem if you make the decision that a point is usefull to process or not, giving it enough slack so that the player would not be able to move far enough to need any new points in that time limit.

The problem with including these extra points is that you're gonna end up having more points marked as important, which will probably mean more processing afterwards. Still, let's say that your graphics get clunky when they process more than 200 points, but the previous function left 2000 points marked as important. Then you could have a second level of importance, which is given by a second function, and this second function only operates on those 2000 points, every frame. So now you've cut down to processing 6000 points per frame.

These numbers are probably somewhat unrealistic, I don't really know, but still I think that such a divide-and-conquer solution, with each function cutting down more and more on the number of marked points, would help out a lot.

Use a BSP tree, with an extra dimension for vertical. You can use it to manage your vertices and cull the ones that our outside your viewing frustrum. By default, you don't worry about the nodes outside your view, and the ordering of planes is automatically oriented so you don't overlap incorrectly.

Simply build the level, hash it to build your BSP, and save the BSP table.

Culling is performed by simply walking the tree in reverse-- no if's, and's, or but's. Virtually no testing required, it's very fast. In fact, the only testing necessary is for clipping at the edges and to determine what side of a plane (wall) you're on (using a dot product and vector normal) so you know which texture to draw.

Very fast and effecient.

The most important point is that you orient your wall segments so that one edge is always the start edge, and the other edge is the arrow-head edge.

For example:

typedef struct
{
float x;
float y;
float z;
}vertex;

typedef struct
{
float normal; /* marks one side of your wall */
vertex startPoint;
vertex endPoint;
}vector;

---

It's a lot of fun, surprisingly easy in light of other methods, and extremely poweful. You can thank John Carmack of idgames (creator of DOOM) for realizing the power of BSP trees.

I'm vry good at searching, I did a numerical modification of the hash table to do something like this, but with 2D, I've done the math, and if I wanna do the same thing for 3D, I'll have an awful lot of calculations per second

The closest I've ever been is by using a dynamic modification of the KD-trees algorithm, but It's too expensive (in calculation numbers), well, not as expensive as the hash table.

Divide and conquer in a direct way wouldn't work because the points are not necesarilly distributed uniformely, and what criteria should I use to determine if I might like this point? (x, y or z, none of them would work)

as for these BSP trees, are they binary trees? If so, I'd never thought of it, I'll do the math and tell you how I go, but (what criteria should I use to deterime which branch should I use?

Oskilian

BSP = Binary Space Partition Trees. Essentially it is a Binary tree, and the way it builds is this---

BSP trees are very effecient because essentially whatever room you are in (your POV- Point of View) is the node in the tree you are in. To draw the level, you simply draw all the walls (no testing required) describe by each parent leading up that branch to the root node. Only the walls that are visible to the player will be drawn, and in the correct order.

The only clipping necessary is to clip some of the walls that overlap the viewing frustrum to the left, right, top or bottom. Most however require no clipping at all.

In fact, here is an intro web page you can look at--

http://www.geocities.com/pcgpe/bsp.html