Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (498)
Games in Android Showcase (115)
games submitted by our members
Games in WIP (563)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Communication between two heirarchies  (Read 2741 times)
0 Members and 1 Guest are viewing this topic.
Offline darkprophet

Senior Member




Go Go Gadget Arms


« Posted 2006-10-07 23:26:29 »

Hi all,
I have a heirarchy of nodes where a leaf is a geometrical representation (opengl, so thats vertices, normals, indices...etc); each node/leaf has a container that is used for frustum culling...and that works fine. Lets call any node/leaf in this heirarchy a "spatial". Another heirarchy is my render state heirarchy; each node in this heirarchy represents a state change and each node also contains a list of spatials that are associated with that render state.

The problem is mixing the two. I want to do frustum culling on the first heirarchy, and the ones that are culled to not appear in the second. Then, traverse the render state tree and enable state -> render spatials -> recurse for all child render states -> disable state. This may seem simple, but there are a few restrictions.

a) I cant have a boolean in spatial representing whether the spatial has been culled or not as I can insanatiate alot of small renderers everywhere and they have their own culling mechanism and those renderes are mulithreaded.

b) I can't keep a reference to the render state that the spatial is attached to because it could be attached to multiple render states for multiple pass rnedering and for the multiple rendering mechanism.

With that in mind, anyone have any ideas on how I can communicate the results of the frustum culling with the second heirarchy ?

DP Smiley

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Offline darkprophet

Senior Member




Go Go Gadget Arms


« Reply #1 - Posted 2006-10-12 23:34:11 »

Anybody ?

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Offline pepijnve

Junior Member




Java games rock!


« Reply #2 - Posted 2006-10-13 09:40:11 »

A hash table or something similar?
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline cylab

JGO Ninja


Medals: 49



« Reply #3 - Posted 2006-10-13 15:41:46 »

Quote
With that in mind, anyone have any ideas on how I can communicate the results of the frustum culling with the second heirarchy ?
Add "named" render state references to the spatial (using a map or fixed array-index lookup) and pass that "name" to the spatial tree traversal

Mathias - I Know What [you] Did Last Summer!
Offline darkprophet

Senior Member




Go Go Gadget Arms


« Reply #4 - Posted 2006-10-13 16:43:40 »

Thanks for your replies...

Unfortunetly, a hashmap is too slow as this algorithm is done per frame...a hashlookup per frame per object is just too much.

cylab, what do you mean by a "named render state reference" ?


Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Offline pepijnve

Junior Member




Java games rock!


« Reply #5 - Posted 2006-10-13 18:55:36 »

I think he means named as in some identifier of choice, for instance an integer. Each renderer could have it's own private state object in each spatial. So during the culling traversal each renderer stores it's required data in the spatial and reads it back during the rendering pass.
At least that's how I interpreted it Smiley
Offline Mr_Light

Senior Member


Medals: 1


shiny.


« Reply #6 - Posted 2006-10-13 20:31:01 »

Thanks for your replies...

Unfortunetly, a hashmap is too slow as this algorithm is done per frame...a hashlookup per frame per object is just too much.

cylab, what do you mean by a "named render state reference" ?

interesting that they claim over here that collections are hardly ever a bottleneck.

a hashmap is too slow as this algorithm is done per frame... get map implementation that doesn't suffer from this?

It's harder to read code than to write it. - it's even harder to write readable code.

The gospel of brother Riven: "The guarantee that all bugs are in *your* code is worth gold." Amen brother a-m-e-n.
Offline darkprophet

Senior Member




Go Go Gadget Arms


« Reply #7 - Posted 2006-10-13 21:15:31 »

An ArrayList/LinkedList are different from maps. Maps have an O(log n) performance time *per* get. Now imagine a large scene with alot of shapes...the algorithm/design is going to be putting and removing from the this map every frame in the render state heirarchy.

Implementing another Map is going to be just too much hassle for what this is supposed to be. And most probably, i can't do much better than O(log n)....

Regarding the identifier business; storing any information regarding culling status is really not feasible. The API supports small renderers everywhere, for example, each Light has a renderer for depth rendering for shape maps, storing a reference to each of those breaks encapsulation of data.

What I was thinking was maybe traversing the render state tree, obtaining the children in the current render state. Then recursively find its parent until you get to the base node. From there, do frustum culling, then somehow mask the ones that aren't to be rendered in the render state heirarchy....

DP

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Offline Mr_Light

Senior Member


Medals: 1


shiny.


« Reply #8 - Posted 2006-10-14 16:45:20 »

(having actually given some tauth)

I would do the culling differendly in the sence that I would mark that which should be painted not what shouldn't. since the positive result is a tree and the negative result is an collection of fallen off branches. (this hold true wenn if we marked the parent as culled the childs are implicated to be too.) since it would be a collection of references it shouldn't be cost and creating one could be parallel.

not sure how your render structure is set up (as in value of the nodes)

It's harder to read code than to write it. - it's even harder to write readable code.

The gospel of brother Riven: "The guarantee that all bugs are in *your* code is worth gold." Amen brother a-m-e-n.
Offline cylab

JGO Ninja


Medals: 49



« Reply #9 - Posted 2006-10-14 17:20:50 »

cylab, what do you mean by a "named render state reference" ?

If I understand your problem right, you can't reference the render state from the spatial because there could be more than one render state corresponding to a spatial node (multiple views/renderers/passes), so my suggestion was to just hold multiple references to all render states.

This references have to be "named" to find the right render state to update on culling (or other traversals). There are multiple ways to to this. One is using a map and another would be to use an array. Since there won't be much renderers, every node can use a fixed size array (e.g. size of 4) to store the render state references. the fastest way to resolve the right reference would be to use an integer as "name" and use this "name" as array-index to find the right render state corresponding to the spatial node.

Mathias - I Know What [you] Did Last Summer!
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline darkprophet

Senior Member




Go Go Gadget Arms


« Reply #10 - Posted 2006-10-15 00:19:18 »

Mr_Light: The current system culls away the non-visible stuff leaving a flat, list like structure called a RenderBin. In a RenderBin, it contains leaf nodes (Shapes), those shapes can then be sorted in a specific manner, for example, to get correct transperancy, you need to sort back to front. Even if I kept the tree intact; it would be in the manner that the user set it up (for example, octree) and not in the RenderState tree...

cylab: Typically speaking, each renderer would have its own render state tree. The way I have implemented it so far (not fully, as this problem is annoying me) is that you have a singleton stack on which you can push and pop root render state. The top most render state tree gets rendered. What this allows is for a Light to push its own agenda on the render state stack, render, pop back to the original render state that the user created (think shadows and post process effects, even deferred shading). So if there are 100 lights through out the scene, there could be a potential 100 renderers....

But i feel uncomfortable introducing any sort of reference inside spatial as this, in my mind, breaks encapsulation....The Shape shouldn't know what it looks like in terms of textures, lights, any shaders. What it does know about is a bound, a transform and a potential Geometry encapsulation.

So I guess the question has changed to "How can I combine a a tree that contains a set of spatials with another tree that has a portion of that set ?"

DP

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Offline cylab

JGO Ninja


Medals: 49



« Reply #11 - Posted 2006-10-15 11:18:42 »

I am afraid you can't without recreating the render trees every frame. You could do some fancy statistical caching to avoid full recreation (of the tree... not yourself Wink), but that's it (IMHO).

Mathias - I Know What [you] Did Last Summer!
Offline pepijnve

Junior Member




Java games rock!


« Reply #12 - Posted 2006-10-16 07:13:25 »

But i feel uncomfortable introducing any sort of reference inside spatial as this, in my mind, breaks encapsulation....The Shape shouldn't know what it looks like in terms of textures, lights, any shaders. What it does know about is a bound, a transform and a potential Geometry encapsulation.

I don't think that necessarily breaks encapsulation. The spatial nodes don't need to know anything about the render state itself. It can be completely opaque. In the end you're still going to need to make some sort of relationship between the render state and the spatial. Maybe an alternative would be to have a dedicated render state tree. This would have same structure as the spatial tree, but now each node would contain a reference to a spatial and collection of associated render states...
Offline darkprophet

Senior Member




Go Go Gadget Arms


« Reply #13 - Posted 2006-10-16 23:18:45 »

After much thought, I dont see how that inbetween tree would help. The idea behind the render state tree is that I can traverse the render state tree and render whats inside each node in that render state tree; thus saving state changes.

The "inbetween tree" wouldn't allow me to minimise state changes...which is what this was about.

If I could bring myself to break the encapsulation; I'll add a List<RenderState> to Shape; when traversing, if the Spatial is frustum culled, it would remove itself from the List<Spatial> inside RenderState, thus when rendering the state tree, it wouldn't be there. But I would have to live with the memory increase in Spatial (as opposed to just Shape, which is a leaf node) if I was to implement a more classic Appearance class that Shape would encapsulate...

Anyways, thanks for all your answers; I was hoping for an elegant solution, but there doesn't seem to be one.

PD


Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Offline pepijnve

Junior Member




Java games rock!


« Reply #14 - Posted 2006-10-17 06:44:49 »

After much thought, I dont see how that inbetween tree would help. The idea behind the render state tree is that I can traverse the render state tree and render whats inside each node in that render state tree; thus saving state changes.

I think I'm messing up some terminology here Smiley
The idea I had was to make three distinct trees:
  • a tree of render states
  • a tree of spatials
  • a tree connecting the two (call it foobar for clarity Wink)
Instead of making references from render states to spatial (as you initially described), you would make references to foobar nodes. The foobar tree nodes would contain any renderer specific information (such as 'isCulled'). Then you perform a cull pass on the foobar tree, storing any required information in the nodes. After that you render using the render state tree. So basically it adds an extra level of indirection and pulls the render info (isCulled, ...) out of the spatial nodes without losing the optimized rendering. The tradeoff is memory usage and the extra indirection.
Offline cylab

JGO Ninja


Medals: 49



« Reply #15 - Posted 2006-10-17 10:05:21 »

If I could bring myself to break the encapsulation; I'll add a List<RenderState> to Shape; when traversing, if the Spatial is frustum culled, it would remove itself from the List<Spatial> inside RenderState, thus when rendering the state tree, it wouldn't be there. But I would have to live with the memory increase in Spatial (as opposed to just Shape, which is a leaf node) if I was to implement a more classic Appearance class that Shape would encapsulate...

You will run in trouble anyway, since this approach cannot cull whole subtrees without traversing them to remove all spatials from the render tree. I think you will be better of to generate a render list from a spatial tree and sort them to minimize state changes.

Mathias - I Know What [you] Did Last Summer!
Offline darkprophet

Senior Member




Go Go Gadget Arms


« Reply #16 - Posted 2006-10-17 11:19:00 »

@cylab: Im already state sorting after traversal and doing it in such a way that the sorting is O(1) Tongue

There were other reasons for introducing the render state tree, primarily so that a few fixed render states can be used to render the entire scene (think post process effects here, or even shadows). A simple tree push, render the entire scene with the pushed render state tree, then pop to get back to the original state that the user has set the scene up is what I was aiming for. And doing it in such a way that is completely transperant to the user. Forcing a renderState through a static class might be a way to do that but isn't as elegant/original to me as the renderstate tree idea...

@pepijnve; good idea, but creating another tree that has a similar memory requirements as the spatial tree is just too much. Also like cylab mentioned, partial traversal can't be done using my method and it can't be done using yours. And frustum checking all those extra spatials is probably more expensive than a few render state changes...

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

radar3301 (11 views)
2014-09-21 23:33:17

BurntPizza (28 views)
2014-09-21 02:42:18

BurntPizza (19 views)
2014-09-21 01:30:30

moogie (20 views)
2014-09-21 00:26:15

UprightPath (27 views)
2014-09-20 20:14:06

BurntPizza (30 views)
2014-09-19 03:14:18

Dwinin (47 views)
2014-09-12 09:08:26

Norakomi (74 views)
2014-09-10 13:57:51

TehJavaDev (102 views)
2014-09-10 06:39:09

Tekkerue (50 views)
2014-09-09 02:24:56
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!