Unfortunately, my CELX practising has become a bit rusty and, correspondingly, I have nothing ready to throw at you...Yet I know pretty well, how the stars are organized in Celestia's C++ code. Notably, there is a crucial culling, based on the so-called octree algorithmhttp://en.wikipedia.org/wiki/Octree
While the octree mechanism is a very general concept in computing and data handling, for Celestia it means that 3d space along with the stars it contains is partitioned into treelike arranged boxes, each with exactly eight sub-boxes (see image in http://en.wikipedia.org/wiki/Octree
) . The criterion determining the proper box for a given star is it's magnitude
apart from it's 3d coordinates. Hence in searches among the stars, the octree structure saves a lot of work given a certain magnitude window: most boxes may simply be ignored...
Sorry that a more concise reply would require actual work on your specific question, for which I don't have enough spare time. I promise however, that I'll keep "chewing" on this interesting issue and shall ring a bell whenever I have some respective idea ...
I am sure that DW (aka dirkpitt) will have something to say about it, too...
I don't think it's necessary for you to explain in any great detail how the code works. I'm not at all familiar with Celestia's codebase, but I understand B+ trees, so knowing that an octree is used is enough for me to surmise a (very rough) high-level idea of the algorithms used.
Just a couple of clarifications would be appreciated though... Firstly, although we've only discussed this with reference to stars, I assume that in fact ALL objects of any class (from galaxies down to asteroids, comets, and spacecraft) would have to be loaded / located in this octree.
Secondly, I'm a little confused how magnitude can also be catered for in the same octree when surely all eight leaves at each level would be required to index the eight sub-quadrants required for "spatial partitioning". (You don't have to answer this really because for my purposes I wouldn't be concerned with magnitude anyway.)
To cut to the chase, I imagine that this mechanism is probably some of the first code that Chris ever wrote when he first created Celestia as it's critical to it's rendering function. Given that, it's fair to say that it has been "well exercised" over the years, and most of the kinks have been ironed out as a result. So, I imagine that it is also well encapsulated, and therefore that it might be straightforward to expose some or all of it's interface to a CELX function or functions.
Just so that we're on the same page, I assume that any instantiation of the observer object, as it moves through space, will reflect it's spatial position in the octree by traversing the nodes (ie. maintaining a pointer to the node representing it's current position in 3D space, perhaps also qualified by a reference frame).
On each render cycle, the render engine will need to know:
1. the observer's current node
2. The observer's orientation / velocity vector, and
3. The view window's current FOV
in order to construct a "view frustrum" intersecting with the correct subset of nodes from the octree.
4. The exact 3D coordinates of each of the objects (plus other properties), so that it can be rendered in the correct position on the screen relative to the observer.
I know this is probably a simplistic and possibly flawed description of what's going on, and there's probably a lot of optimization between frames as well, but it's just to give some background to what I would like to see in CELX, which is next.....
For the purposes of my original question, assuming the above is roughly correct, all I'd like to see is for some or all of the interface(s) of the appropriate C++ code to be exposed as CELX functions, so that for a given observer we could from CELX return a reduced table/list of objects within a specified FOV (less than the screen FOV) relative to direction the observer is facing / traveling.
eg. All the objects in a "view frustrum" defined as +/- 5degs from straight ahead.
So instead of passing all the objects in the screen's view frustrum to the render engine for rendering, we're returning a small subset of those objects as defined by the smaller view frustrum to a LUA wrapper function, for use in a CELX script. (The LUA function would specify the dimension of the frustrum, in terms of both FOV and linear extent.)
For the purpose of this discussion I'm assuming that the orientation of this view frustrum is the same as the observers orientation, but there's no reason why it couldn't be independently provided (perhaps even by a separate scripted orientation) as an extra third parameter to the new LUA function.