Cell(s) and Portal(s)

Hi!



I'm interested in your source code. Yes portal culling may help on GPU limited PCs. The problem is that maybe you should have tested your implementation on more various cases.



Did you have a look at my very limited implementation? Do you try to reduce the size of the frustum used for the culling at runtime? Do you use only square-based frusta?

I've not really looked into your source code.



Yes, I reduce the size of the frustum, that's why I need an extra method + field in the spatial class.

But currently, there is still an improvent, as you could reduce the frustum further.

And the test results are WITHOUT reducing the size of the frustum!



Yes I use only square-based frusta, and i'm currently not going to implement other frusta? (or is there any significant speed gain?)

tim8dev said:

Yes I use only square-based frusta, and i'm currently not going to implement other frusta? (or is there any significant speed gain?)

There is only a very little speed gain in special cases, it is not worth implementing such things on my view. Let me know when you plan to release your source code, it would help me a lot and I would like to test it on old machines. Maybe I could give you some help if I find some time as I need anti-portals too.

Okay, than I will put other frusta on the very end of my "implementatio-queue" :smiley:



I've look into your source code and I think you're implementation is somehow more complicated than mine,

but I don't think I've more features implemented than you. :wink:



Don't know if you could help me, but what does the Camera do except frustum culling?

(I want to implement a Camera only for Frustum culling use.)

tim8dev said:

Okay, than I will put other frusta on the very end of my "implementatio-queue" :D

I've look into your source code and I think you're implementation is somehow more complicated than mine,
but I don't think I've more features implemented than you. :wink:

Don't know if you could help me, but what does the Camera do except frustum culling?
(I want to implement a Camera only for Frustum culling use.)

My implementation requires an heavy precomputation and only supports levels with orthogonal walls, it is extremely limited. The camera is only used for frustum culling as far as I know. Does your implementation require a precomputation?
My implementation requires an heavy precomputation and only supports levels with orthogonal walls, it is extremely limited. The camera is only used for frustum culling as far as I know. Does your implementation require a precomputation?

Yes, my Version requires precomputation, but not much, if it is integrated into Spatial/Node. (see patch)

UDPATE:
My Version requires orthogonal Walls, too. But I think I'll implement more flexibility.

As I see, that the jME-2.0 stable has been release now,
I want to ask whether a Committer / Developer could apply my patch for Spatial.java and Node.java when it's released
(or could I get commiting rights, as there might be further improvements / bug fixes?)

I removed the patch, because I found two bugs to fix before comitting...

How does your pre-computation work? What are the data in and out? Do you process directly the JBIN files? Do you use only the JME tree or a graph?

I don't really now what the JBIN files are.

It uses only the jME tree, I thought about graphs, too, but why make it more complicate?



I'm not sure how to describe it here, so it's easy to understand but here:

// I didn't write the implementation details, if you want them I'll mail you my source



Cell-and-portal:

  • A short description of my (cell-and-portal) algorithm.
  • My Version first check where the Camera is.
  • If it is in the Level, it checks in wich Cell it is.
  • If it is outside the Level, it checks whether you can see a Cell through a (outer) portal.
  • Then it starts culling from the Cells, it checks all other Portals against the frustum (and culls them if possible)
  • If a portal is inside/intersects the frustum, it invoke culling in the following Cell with a reduced Frustum.
  • After that the childs check themselves against the Frustum and store the result.
  • Then the onDraw() methods are called…



    If anything is unclear, please post!
tim8dev said:

It uses only the jME tree, I thought about graphs, too, but why make it more complicate?

Using graphs is necessary to handle such examples:

If you handle such levels as trees, you won't store all paths, you won't use the shortest path to go from a cell to another one.

tim8dev said:

I'm not sure how to describe it here, so it's easy to understand but here:
// I didn't write the implementation details, if you want them I'll mail you my source

Cell-and-portal:
* A short description of my (cell-and-portal) algorithm.
* My Version first check where the Camera is.
* If it is in the Level, it checks in wich Cell it is.
* If it is outside the Level, it checks whether you can see a Cell through a (outer) portal.
* Then it starts culling from the Cells, it checks all other Portals against the frustum (and culls them if possible)
* If a portal is inside/intersects the frustum, it invoke culling in the following Cell with a reduced Frustum.
* After that the childs check themselves against the Frustum and store the result.
* Then the onDraw() methods are called...

If anything is unclear, please post!

It is clear but I wonder how you handle a special case: a tree cannot contain a loop but several rooms can be connected together.

In mine, I prefer being never outside any Level to avoid your step "If it is outside the Level, it checks whether you can see a Cell through a (outer) portal" but I do almost the same thing (the outdoor is itself a Cell).

I want to could be outside of a Level… e.g. if you have a house (wich is represented as a Level) that has windows.

You could be outside of the House and only render the cells you could see through the portals.

But, for now it's not implemented, as it's not of high priority to me.



For the graph or tree question:

I have a Level (Node), wich contains all Cells and Portals in the normal chilren ArrayList of a Node.

And each Cell contains all the Portals wich are there spatially. (so, yes that is a graph.)



What do you exactly mean by

the shortest path to go from a cell to another one.


Do you use your algorithm for AI, or what do you mean?

Until now, you have to use factory methods to create portals and cells.



Like:

Level house = new Level("house");
Cell room0 = house.createCell("room0", Spatial.. spatials);
Cell room1 = house.createCell("room1");
house.createPortal(room0, room1);
house.createPortal("room0", "room1"); // with the names.

tim8dev said:

For the graph or tree question:
I have a Level (Node), wich contains all Cells and Portals in the normal chilren ArrayList of a Node.
And each Cell contains all the Portals wich are there spatially. (so, yes that is a graph.)

What do you exactly mean by
the shortest path to go from a cell to another one.


Do you use your algorithm for AI, or what do you mean?

JME is based on a tree. There is a risk of infinite loop if a single node appears in several lists of children whereas a single Cell (room) can be bound to several Cells. I use breadth-first search. I think that you have implemented something to allow a Level to behave like a node of a graph and not like a node of a tree; therefore, it is very close to my implementation except that my portals are not in the lists of children.

How do you compute your cells and your portals? I tried to generalize my algorithm some months ago but I obtained something a bit complicated.
tim8dev said:

Until now, you have to use factory methods to create portals and cells.

Like:

Level house = new Level("house");
Cell room0 = house.createCell("room0", Spatial.. spatials);
Cell room1 = house.createCell("room1");
house.createPortal(room0, room1);
house.createPortal("room0", "room1"); // with the names.




Ok. Does it mean that you have not yet implemented anything to build cells and portals automatically from a given Spatial for example?

Yes. But I don't know how to make this generalized, so I will provide enough Factory Methods like

createRoundRoom() or something like that, so it wouldn't make a Game much more complicated.

tim8dev said:

Yes. But I don't know how to make this generalized, so I will provide enough Factory Methods like
createRoundRoom() or something like that, so it wouldn't make a Game much more complicated.

At first, this is not what people expect from a system allowing spatial partitioning. Developers want to use their existing levels with such a system without additional efforts. Your factory should be able to return a Level by taking a Spatial in parameter, for example :


Level level = Level.createLevel( spatial );
root.attachNode( level );



Secondly, if your portal culling really works fine, it is a good thing :D How do you project a portal onto the near plane of the frustum?

After that, now you know why my source code is more complicated, it contains an attempt of generalization and it is already able to generate automatically several files containing the models of the walls and the data needed to load these models as elements of a graph (Level, Network, Cell, Portal). I didn't put my thread in this section because it requires a lot more work.

Finally, the guys working on Poisonville have implemented portal culling, it would be fine to convince them to put it into JME 2.0.
At first, this is not what people expect from a system allowing spatial partitioning. Developers want to use their existing levels with such a system without additional efforts. Your factory should be able to return a Level by taking a Spatial in parameter, for example :
Code:

Level level = Level.createLevel( spatial );
root.attachNode( level );




I know that they want to use their existing Levels and I know your source code is complicated because of this thing. :wink:

But for me, it's okay to have the technique I use for now and if you could explain me more of how you generate the cell-and-portal graph from a spatial, it would be very nice and will help me implementing it and generalize it to more different kinds of rooms.

When is the generating done? (At loading time or before contribution time?)
tim8dev said:

I know that they want to use their existing Levels and I know your source code is complicated because of this thing. :wink:

But for me, it's okay to have the technique I use for now and if you could explain me more of how you generate the cell-and-portal graph from a spatial, it would be very nice and will help me implementing it and generalize it to more different kinds of rooms.

When is the generating done? (At loading time or before contribution time?)

The attempt of generalizing the previous algorithm is in the package jme.portalizer. For the moment, I use a map represented by a GIF file, it is parsed, it computes some voxels, etc... look at the class TilesGenerator and CellsGenerator. The generation is done offline because it requires a lot of memory (one of the steps requires 1.5 GB) and it would be a bottleneck on low end machines. The graph is rebuilt during the loading, it is short as the game doesn't need to recompute the space partitioning, the relationships are stored and loaded.

On my view, your source code could be very useful to fix my portal culling and then, we could work together on the generalization. You have to know that such tasks may require months of work.
The attempt of generalizing the previous algorithm is in the package jme.portalizer. For the moment, I use a map represented by a GIF file, it is parsed, it computes some voxels, etc... look at the class TilesGenerator and CellsGenerator. The generation is done offline because it requires a lot of memory (one of the steps requires 1.5 GB) and it would be a bottleneck on low end machines. The graph is rebuilt during the loading, it is short as the game doesn't need to recompute the space partitioning, the relationships are stored and loaded.

Okay, now that's clear for me, but my idea for generation was, that the user provide a Node, wich contains all Cells and Portals, and you then compute the Graph from them. This is, at least i think this is, the way a developer wants his spatial sorting computed. For me, I wouldn't create a GIF file for each map.

Another reason for integrating the Cell-and-Portal into core, is, that the community can focus on their way of generating a cell-and-portal graph and not on bugfixing a non working frustum-size-reducing.

I would like to play with a cells-and-portals system that I could pass the data onto, without it being generated, so I could for example build a tree, defining myself where the cells and portals go, pass that tree onto such a system and receive a graph thats ready to be used.



Is that possible? I am working at implementing a loader that can pass extra data instead of just a batch of polygons. If its possible that the scenegraphs that my loader generates can contain special markers and shapes for portals etc, and perhaps bounding boxes for cells then we are in business with quick and easy generation of the actual graphs. That way we can leave the definition up to the artist without having the computer have to precompute it.

I would like to play with a cells-and-portals system that I could pass the data onto, without it being generated, so I could for example build a tree, defining myself where the cells and portals go, pass that tree onto such a system and receive a graph thats ready to be used.


That's excactly the way I want to do it.
Of course, one way would be that you mark them with it's name. Like, if it should be a portal, the name should be "portalXXXXX" or sth like that.

Then the portal is automaticly generated by the given spatial. (The portal is defindes -at least in my implementation- through an OrientedBoundingBox)