It is currently Mon, 18-12-17, 18:42 GMT

All times are UTC




Post new topic Reply to topic  [ 11 posts ] 
Author Message
PostPosted: Mon, 11-02-13, 1:00 GMT 
Offline
User avatar

Joined: Fri, 03-04-09, 8:21 GMT
Posts: 217
(This is a duplicate of a post I made at shatters)

Does anyone know of any celX method(s) that would enable the efficient identification of all stars in a narrow section of sky (let's say a 1 deg FOV) out to a specified distance?
Imagine pointing the hubble space telescope at an empty section of sky... how can we find out which stars (perhaps too faint or too distant to be rendered) are in that cone of space out to thousands or even millions of parsecs.

By "efficient", I mean fast enough to execute within a render cycle. ie, without iterating through celestia:stars()

I believe that internally Celestia must have efficient "spatially aware" data-structures / methods which would allow this, but I don't believe they are exposed to CELX.
For example, when moving or rotating the observer, Celestia clearly knows which stars are in the FOV and is able to re-calculate and re-display their positions in real time, without processing the entire stars database on each render-cycle.

_________________
CITIZENS OF CM - JOIN THE REVOLUTION
...black out your avatar
THE AVATARS ARE REVOLTING !!!


Top
 Profile  
 
 Post subject:
PostPosted: Tue, 12-02-13, 13:15 GMT 
Offline
User avatar

Joined: Fri, 03-04-09, 8:21 GMT
Posts: 217
PS. I expect that Fridger will be intimately familiar with the relevant code as it's clearly fundamental to Celestia's core observer-object functionality. :wink:

_________________
CITIZENS OF CM - JOIN THE REVOLUTION
...black out your avatar
THE AVATARS ARE REVOLTING !!!


Top
 Profile  
 
 Post subject:
PostPosted: Tue, 12-02-13, 21:01 GMT 
Offline
Site Admin
User avatar

Joined: Fri, 31-08-07, 7:01 GMT
Posts: 4514
Location: Hamburg, Germany
chuft-captain wrote:
PS. I expect that Fridger will be intimately familiar with the relevant code as it's clearly fundamental to Celestia's core observer-object functionality. :wink:


;-)

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 algorithm

http://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...

Fridger


Top
 Profile  
 
 Post subject:
PostPosted: Wed, 13-02-13, 14:34 GMT 
Offline
User avatar

Joined: Tue, 04-09-07, 2:32 GMT
Posts: 430
Location: South Korea
Fridger is correct, Celestia culls objects that don't intersect with the view frustrum (i.e., are out of view), or are too dim or small.
Some objects outside the view frustrum may also be included, if they are calculated to cast enough light on objects within the frustrum.
Culling is done recursively for every child in the octree of every nearby solar system.
The code is Renderer::buildRenderLists() and the renderList is stored internally in Renderer.
However, there is nothing in celx currently to expose the renderList or any arbitrary FOV.


Top
 Profile  
 
 Post subject:
PostPosted: Wed, 13-02-13, 14:52 GMT 
Offline
User avatar

Joined: Fri, 03-04-09, 8:21 GMT
Posts: 217
t00fri wrote:
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 algorithm

http://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...

Fridger

Hi Fridger,

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.

CC

_________________
CITIZENS OF CM - JOIN THE REVOLUTION
...black out your avatar
THE AVATARS ARE REVOLTING !!!


Top
 Profile  
 
 Post subject:
PostPosted: Wed, 13-02-13, 15:34 GMT 
Offline
User avatar

Joined: Fri, 03-04-09, 8:21 GMT
Posts: 217
dirkpitt wrote:
Fridger is correct, Celestia culls objects that don't intersect with the view frustrum (i.e., are out of view), or are too dim or small.
Some objects outside the view frustrum may also be included, if they are calculated to cast enough light on objects within the frustrum.
Culling is done recursively for every child in the octree of every nearby solar system.
The code is Renderer::buildRenderLists() and the renderList is stored internally in Renderer.
However, there is nothing in celx currently to expose the renderList or any arbitrary FOV.

Hi DW,

You cross-posted while I was constructing my very long description, so I didn't see your post until afterwards.
You may want to read my post (after yours) but it looks like you understood perfectly what I'm asking for even without my very long description. :lol:

Do you think it would be difficult to expose an overloaded version of buildRenderLists() to CELX? -- (I assume this would be the way to go.)

The tricky part of this I suspect would be avoiding the in-efficiency of a second culling for the reduced frustrum (given that it's likely contained within the rendered frustrum, it would be ideal to build both lists at the same time without re-traversing the octree.)

_________________
CITIZENS OF CM - JOIN THE REVOLUTION
...black out your avatar
THE AVATARS ARE REVOLTING !!!


Top
 Profile  
 
 Post subject:
PostPosted: Wed, 13-02-13, 15:56 GMT 
Offline
Site Admin
User avatar

Joined: Fri, 31-08-07, 7:01 GMT
Posts: 4514
Location: Hamburg, Germany
Hi CC,

certainly stars and DSOs are organized and culled via octrees. ChrisL wrote the one for stars. Toti and I wrote the one for DSOs. Since the sizes and magnitudes are vastly different for DSOs and stars, one needs separate octrees for them.

Fridger


Top
 Profile  
 
 Post subject:
PostPosted: Sat, 16-02-13, 16:41 GMT 
Offline
User avatar

Joined: Tue, 04-09-07, 2:32 GMT
Posts: 430
Location: South Korea
CC,

After reading your initial post, I'm not sure that the renderLists would suit what you're looking for.
If it's just all the objects that are visible within a particular FOV, then the renderLists are not suitable at all because as I said the renderLists also culls objects within the frustrum if they are too small or dim. Moreover, the renderLists also contain some objects outside the frustrum whose light might cause significant illumination on objects inside the frustrum.

To get a list of all objects (even those that are too faint or distant) within an FOV, and only those within the FOV, requires new C++ code that would only be called when the script requests it.
It would be like buildRenderLists, except it would not cull dim or small objects and would only include objects that are visible within the view frustrum.
There should be a version of this code for every octree (stars and DSOs).

Could you go into more detail about what you want to use this functionality for?


Top
 Profile  
 
 Post subject:
PostPosted: Wed, 20-02-13, 23:10 GMT 
Offline
User avatar

Joined: Fri, 03-04-09, 8:21 GMT
Posts: 217
dirkpitt wrote:
CC,

After reading your initial post, I'm not sure that the renderLists would suit what you're looking for.
If it's just all the objects that are visible within a particular FOV, then the renderLists are not suitable at all because as I said the renderLists also culls objects within the frustrum if they are too small or dim. Moreover, the renderLists also contain some objects outside the frustrum whose light might cause significant illumination on objects inside the frustrum.

To get a list of all objects (even those that are too faint or distant) within an FOV, and only those within the FOV, requires new C++ code that would only be called when the script requests it.
It would be like buildRenderLists, except it would not cull dim or small objects and would only include objects that are visible within the view frustrum.
There should be a version of this code for every octree (stars and DSOs).
If it's possible to easily expose the renderlists to LUA, then I think that would be a very good start. It would at the very least allow some proof-of-concept work to decide whether it's worthwhile going to the next step and writing the new C++ code required for a customizable frustrum.

At least for proof-of-concept work, I don't think it matters that some distant objects are excluded, and some on the boundary are included.
If you consider that a typical FOV in Celestia is often something like 35deg, then having access to even the standard renderlists, would immediately I think result in an efficiency improvement by factor of at least ~ 100x, when compared with iterating through celestia:stars() which returns all stars, 99% of which won't even be in the FOV.

Given that most of what Celestia is all about is: "what can be seen", then it makes sense to only deal with what's in the FOV at any given point. From a practical point of view this is crucial if our script is designed to do it's processing within a render-cycle. (Of course, not all scripts need to be this efficient, and most of course don't care about the FOV, or the render-cycle, at all, -- but for those that do, it's crucial).

dirkpitt wrote:
Could you go into more detail about what you want to use this functionality for?
It's primarily about enabling CELX with the performance required to process objects in real-time. This is currently a bit of a struggle in CELX, because the fast data-structures utilized by the C++ code are not well-exposed to LUA.

Exposing these renderlists would allow CELX scripts better access to the efficiencies that the C++ code benefits from, and would therefore enable new enhancements taking advantage of this speed to be written in CELX, leveraging off the ability to process items within the render-cycle.

For an example of the style of script which might benefit from access to this performance level, have a look at my Lagrange Points addon: http://shatters.net/forum/viewtopic.php?f=23&t=17129&p=132411#p132411. Imagine a hypothetical version of this addon which labelled Lagrange Points auto-magically as they came into the FOV. :)
(I don't think this particular addon would in fact gain any significant performance advantage from the renderlists, as it 's not dealing with objects which are stored in octrees (ie. stars and DSO's), but it's an example of the type of "render-cycle based" script that would benefit from the performance if it had to process a lot of stars, instead of Lagrange Points. )

Incidentally, I've recently been re-writing this script in a way which has highlighted exactly the sort of issues that arise when objects cannot be accessed efficiently from CELX: http://shatters.net/forum/viewtopic.php?f=9&t=17240.
This can then require less than ideal workarounds such as object-caching in LUA in order to achieve any semblance of a reasonable FPS.
(It appears that moons and other solar-system bodies are not stored in octrees at all, or not from LUA's viewpoint anyway.)

_________________
CITIZENS OF CM - JOIN THE REVOLUTION
...black out your avatar
THE AVATARS ARE REVOLTING !!!


Top
 Profile  
 
 Post subject:
PostPosted: Mon, 25-02-13, 17:31 GMT 
Offline
User avatar

Joined: Tue, 04-09-07, 2:32 GMT
Posts: 430
Location: South Korea
Hi CC,

Yes, if the aim is optimizing performance of render-cycle based scripts, then it maybe a good start to expose the existing renderlist.
The biggest concern then is whether adding such new features to Celestia at this point is really worth it, seeing as development is in hibernation.
I've done some thinking about this, and I'm convinced now that interim bug fixes and new features are still worth it and could in some cases benefit both Celestia and Celestia.Sci seeing as they were once based on the same code.

Cheers,
DW


Top
 Profile  
 
 Post subject:
PostPosted: Fri, 01-03-13, 7:39 GMT 
Offline
User avatar

Joined: Fri, 03-04-09, 8:21 GMT
Posts: 217
I think Chris has said some years ago (ever since people such as Hank, Vincent, etc. developed the idea of a LUA hook) that he saw LUA as a good way to enhance or extend Celestia's capabilities (at effectively IMHO zero risk to the core C++ code), and I think he fully supported it because it allows other people to develop new capabilities which I guess could be considered as "addons" in the sense that they would only work in the presence of a LUA Hook.
So IMO there is no cause for any concern, because LUA extensions don't impact the core distributable, and it is precisely because development of the C++ code is in hibernation that more features should be exposed to LUA, because that opens new possibilities for enhancements in the LUA/CelX space to be created by a larger number of people, at a time when nothing much is happening in the C++ space.
As far as C++ development is concerned, I'm not entirely surprised that it is stalled what with Chris being less active. I guess he is fairly satisfied that Celestia has become quite a mature piece of software, and maybe has less motivation than he used to have to spend as much time on it. After 10 years, I would say he's entitled to some time off from Celestia development.

_________________
CITIZENS OF CM - JOIN THE REVOLUTION
...black out your avatar
THE AVATARS ARE REVOLTING !!!


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 11 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB® Forum Software © phpBB Group