Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Let's say I have a large number of conceptual objects of some kind, each of which occupies a pre-known set of points in a Cartesian 3-space.

1) What is the best combination of data structure (for modeling these objects, their occupied points, and/or the enclosing space) and algorithm for the purpose of being able to retrieve only the point within each object that lies closest to an arbitrarily selected point, with speed the first concern and memory footprint secondary (but still important)?

2) Let's say that that a point may be visually occluded with respect to another point, according to a black-box true/false rule, and I now want to retrieve the closest visible point of each object. Asking the same question as in #1, is the answer the same or is something else now advisable?

3) Let's say that the pre-known set of points for each conceptual object may potentially change somewhat frequently, enough so for computational expense in data structure management to be a concern. Are the answers to #1 and #2 still good, or are they expensive enough in setup/teardown to be likely to cause problems under this condition?

(I really do want to know the answers to these items separately, if they have distinct answers. Mega bonus points for any answers that generalize well to a Cartesian 4-space.)

share|improve this question
    
The points are voxels with a fixed depth, width and height? –  Maik Semder May 31 '11 at 21:33
    
@Maik Semder: May be treated as such if you like. –  chaos Jun 1 '11 at 0:18
    
So, I'm curious. Is the selection of 3/4-space geometrically motivated, or is operating on a data space that represents something else? For 1, are the arbitrary points inside or outside the hulls of the data points? For 2, closest visible point with reference to what? For 3, change in an arbitrary or pre-determined fashion (as in, do the objects have known configurations, or are you dealing with new points adding/subtracting)? And lastly, why would you want a 4-space generalization? Are you doing something with time or density as a dimension? Thanks for any clarification! –  ChrisE Jun 7 '11 at 3:38
    
@ChrisE: Geometrically motivated. Could be either but typically outside. With reference to the same arbitrary point we're "looking" from in #1. Potentially arbitrary; points would typically not add/subtract but there will be cases where they will. I'm doing something with a 4th spatial dimension (ana/kata, W axis); it's not the main thing I want this for but it'd be helpful if my solution here generalized to it. –  chaos Jun 7 '11 at 14:05
add comment

3 Answers 3

up vote 2 down vote accepted
+50

I'd suggest a kd tree.

The nearest neighbour search is O(log Npoints) for randomly distributed points and you can easily extend the nearest neighbour search to account for occlusion.

However it's not ideal if lots of points move frequently. This may or may not make the kd-tree more expensive than other options depending on how often you need to rebuild it vs how many queries are done.

It will generalize to N dimensions.

share|improve this answer
add comment

I will point you to the page, which is one of the best resources in NN-search (Nearest Neighbors). It contains slides and links to other resources. But KD-tree is probably best solution (but there are many variants):

http://simsearch.yury.name/

There are great on-topic slides from Data structures of computer graphics course on CTU in Prague, by Vlastimil Havran:

http://dl.dropbox.com/u/5034466/dpg0904.pdf

share|improve this answer
1  
kD trees my be problematic, if you want to move your points. (3) Let's say that the pre-known set of points for each conceptual object may potentially change somewhat frequently) –  zacharmarz Jun 4 '11 at 7:43
    
Than maybe GPGPU (if possible) sorting along the view axis will be solution (and should be realtime) –  Notabene Jun 4 '11 at 8:27
add comment

1) Since speed is a concern, you may want to take a look at approximate nearest neighbor algorithms. I've used ANN in the past and it performed very well for around 12 dimensions. It lets you adjust desired precision so that you can have a trade off between speed and precision and find what works best.

2) Since your visual occlusion is a black-box one (I'm assuming unpredictable moving obstacles), I'm not sure if you have much of a choice other than doing occlusion tests on the points that the NN algorithm returned.

3) I don't believe ANN supports points changing, but I'm not sure since I didn't need that. It seems Cgal and Pastel support dynamic sets, but in terms of insertion/removal of points. Perhaps the papers here would also provide some insight.

I don't know if you need this advice, but I found that reusing libraries for such problems almost always is a better idea. There are so many pitfalls one can fall into while implementing the details. Good luck!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.