Little help with creature culling

Little help with creature culling

Postby paul424 » 30 Aug 2015, 16:30

Hello, I have written a simple Culling algorithm whihch uses tree Quads .
The main problem is attaching / detaching Creatures from/to Hand node as this fools the culling mechanism.
There are too many sites involved in creature pick up and drop , to have the algorithm updated to correctly handle Hand_node .

Maybe hwoarangmy could help a little, I could talk about it on our IRC channel ....
https://github.com/tomluchowski/OpenDungeons/tree/culling4

If someone have an idea how to approach that .
User avatar
paul424
OD Moderator
 
Posts: 643
Joined: 24 Jan 2012, 13:54

Re: Little help with creature culling

Postby Akien » 30 Aug 2015, 17:18

Sadly your branch is based on a veeeeery old code base: "This branch is 1 commit ahead, 1035 commits behind OpenDungeons:development."

I would advise you to just keep the patch somewhere ("git format-patch -1" will generate it), then delete your branch, recreate it based on Opendungeons/development, and then readd your code chunks by hand little by little.
User avatar
Akien
 
Posts: 734
Joined: 22 Feb 2014, 13:14

Re: Little help with creature culling

Postby hwoarangmy » 30 Aug 2015, 21:52

Could you please explain how it is supposed to work (I don't know the algorithm you use) in a few lines ?
Note that this explaination would fit very well in the code so that if someone reads it, a general idea of what is wanted is always a good thing. In any case, as Akien stated, you should try to keep your branch up to date.
hwoarangmy
 
Posts: 567
Joined: 16 Apr 2014, 19:13

Re: Little help with creature culling

Postby paul424 » 31 Aug 2015, 13:34

To trace the spatial position of Creatures I use https://en.wikipedia.org/wiki/Quadtree


{l Code}: {l Select All Code}
int CullingManager::cullCreatures()
{
    //cerr << "countnodes " << myCullingQuad.countNodes() <<endl;
    mMyCullingQuad.holdRootSemaphore();
    MortuaryQuad tmpQuad(mMyCullingQuad);

    mMyCullingQuad.releaseRootSemaphore();

    tmpQuad.cut(Segment(mOgreVectorsArray[1], mOgreVectorsArray[0]));
    tmpQuad.cut(Segment(mOgreVectorsArray[0], mOgreVectorsArray[3]));
    tmpQuad.cut(Segment(mOgreVectorsArray[3], mOgreVectorsArray[2]));
    tmpQuad.cut(Segment(mOgreVectorsArray[2], mOgreVectorsArray[1]));

    //cerr << "tmpQuad.countNodes() " << tmpQuad.countNodes() <<endl;

    std::swap(mCurrentVisibleCreatures, mPreviousVisibleCreatures);
    mCurrentVisibleCreatures = tmpQuad.returnCreaturesSet(mCurrentVisibleCreatures);
    //cerr << "currentVisibleCreatures  " << currentVisibleCreatures->size() <<endl;

    std::set<Creature*> intersection;
    std::set<Creature*> ascendingCreatures;
    std::set<Creature*> descendingCreatures;
    std::set_intersection(mPreviousVisibleCreatures->begin(), mPreviousVisibleCreatures->end(),
                          mCurrentVisibleCreatures->begin(), mCurrentVisibleCreatures->end(),
                          std::inserter(intersection, intersection.end()));

    std::set_difference(mCurrentVisibleCreatures->begin(), mCurrentVisibleCreatures->end(),
                        intersection.begin(), intersection.end(),
                        std::inserter(ascendingCreatures, ascendingCreatures.end()));

    std::set_difference(mPreviousVisibleCreatures->begin(), mPreviousVisibleCreatures->end(),
                        intersection.begin(), intersection.end(),
                        std::inserter(descendingCreatures, descendingCreatures.end()));

    for(std::vector<Creature*>::iterator it = tmpQuad.mMortuaryQuad.begin(); it != tmpQuad.mMortuaryQuad.end(); ++it)
        descendingCreatures.erase(*it); 


    for(std::set<Creature*>::iterator it = ascendingCreatures.begin(); it != ascendingCreatures.end(); ++it)
        (*it)->show();

    for(std::set<Creature*>::iterator it = descendingCreatures.begin(); it != descendingCreatures.end(); ++it)
        (*it)->hide();

    return 1;
}


On start of every frame I do int CullingManager::cullCreatures.



1. I make a copy of MortuaryQuad
{l Code}: {l Select All Code}
MortuaryQuad tmpQuad(mMyCullingQuad)
;
2. I have already prepared the cast of camera frustrum onto XY plane, having for points ( they mark what is visible from camera on that plane ) .
3. Now I cut away everything what's on the left side of each line ( or Segment) constructed from the already mentioned points

{l Code}: {l Select All Code}
  tmpQuad.cut(Segment(mOgreVectorsArray[1], mOgreVectorsArray[0]));
    tmpQuad.cut(Segment(mOgreVectorsArray[0], mOgreVectorsArray[3]));
    tmpQuad.cut(Segment(mOgreVectorsArray[3], mOgreVectorsArray[2]));
    tmpQuad.cut(Segment(mOgreVectorsArray[2], mOgreVectorsArray[1]));

[/code]

4. We prepare the previous visible creatures
{l Code}: {l Select All Code}
std::swap(mCurrentVisibleCreatures, mPreviousVisibleCreatures);
.

5. That way in tmpQuad are Creatures visible in current frame . I extract them to std::set with :
{l Code}: {l Select All Code}
    mCurrentVisibleCreatures = tmpQuad.returnCreaturesSet(mCurrentVisibleCreatures);




5. Ascending creatures are the creatures which are new in our Quadtree. In other words those are creatures :
in mCurrentVisibleCreatures and not in mPreviousVisibleCreatures.
That is : AscendingCreatures = mCurrentVisibleCreatures \ ( mCurrentVisibleCreatures ^ mPreviousVisibleCreatures. ) ^ --means inttersection
and the same for DescendingCreatures ( the ones which ought to be hidden )
AscendingCreatures = mPreviousVisibleCreatures. \ ( mCurrentVisibleCreatures ^ mPreviousVisibleCreatures. ) ^ --means inttersection

6. We compute intersection :

{l Code}: {l Select All Code}
    std::set_intersection(mPreviousVisibleCreatures->begin(), mPreviousVisibleCreatures->end(),
                          mCurrentVisibleCreatures->begin(), mCurrentVisibleCreatures->end(),
                          std::inserter(intersection, intersection.end()));


and set diffrences :

{l Code}: {l Select All Code}
    std::set_difference(mCurrentVisibleCreatures->begin(), mCurrentVisibleCreatures->end(),
                        intersection.begin(), intersection.end(),
                        std::inserter(ascendingCreatures, ascendingCreatures.end()));

    std::set_difference(mPreviousVisibleCreatures->begin(), mPreviousVisibleCreatures->end(),
                        intersection.begin(), intersection.end(),
                        std::inserter(descendingCreatures, descendingCreatures.end()));



We also register creatures which are dead , and which disapperence have nothing to do with culling, instead there are other mechanisms whcih care to remove them from the scneene ( rrDestroyCreature I suppose ) . Therefor we run the hook :


{l Code}: {l Select All Code}
    for(std::vector<Creature*>::iterator it = tmpQuad.mMortuaryQuad.begin(); it != tmpQuad.mMortuaryQuad.end(); ++it)
        descendingCreatures.erase(*it); 



Finnally we can iterate over the resulting sets , and hide and show proper Creatures :

{l Code}: {l Select All Code}
    for(std::set<Creature*>::iterator it = ascendingCreatures.begin(); it != ascendingCreatures.end(); ++it)
        (*it)->show();

    for(std::set<Creature*>::iterator it = descendingCreatures.begin(); it != descendingCreatures.end(); ++it)
        (*it)->hide();


As you see this algorithm does not account about creatures which get picked / dropped bby the Player. If anyone could have an idea, how do I extract what creatures are in Hand_node ...
User avatar
paul424
OD Moderator
 
Posts: 643
Joined: 24 Jan 2012, 13:54

Re: Little help with creature culling

Postby hwoarangmy » 31 Aug 2015, 15:23

To know if a creature is in hand, you can use Player::getObjectsInHand (you can get the player from the creature seat).
hwoarangmy
 
Posts: 567
Joined: 16 Apr 2014, 19:13

Re: Little help with creature culling

Postby paul424 » 31 Aug 2015, 19:47

See ? We can help each other in debugging programs.
User avatar
paul424
OD Moderator
 
Posts: 643
Joined: 24 Jan 2012, 13:54

Re: Little help with creature culling

Postby hwoarangmy » 31 Aug 2015, 22:12

Of course we can. And that's what we do during code review
hwoarangmy
 
Posts: 567
Joined: 16 Apr 2014, 19:13

Re: Little help with creature culling

Postby paul424 » 01 Sep 2015, 21:39

The creature culing is not what could really help in generating large FPS . The real helper is tile culling -- For large maps ( 400x400 ) I get speedup from 30fps to 44fps . By using the tile culling .
As you say hwarangmy , this needs to be commented first .
User avatar
paul424
OD Moderator
 
Posts: 643
Joined: 24 Jan 2012, 13:54

Re: Little help with creature culling

Postby paul424 » 03 Sep 2015, 13:31

@hwoarangmy : could you have a look at slightly refreshed branch cullingTiles ? I would serve answers if you have questions regarding it ...
User avatar
paul424
OD Moderator
 
Posts: 643
Joined: 24 Jan 2012, 13:54

Re: Little help with creature culling

Postby Akien » 03 Sep 2015, 14:05

The branch cullingTiles is also plainly outdated: "This branch is 2 commits ahead, 1037 commits behind OpenDungeons:development."

I've said it several times, working on such outdated code will only cause you issues when you will later try to merge it into the development branch. You should update your fork asap to avoid working on code that was most likely changed since December 2014.
User avatar
Akien
 
Posts: 734
Joined: 22 Feb 2014, 13:14

Re: Little help with creature culling

Postby hwoarangmy » 06 Sep 2015, 19:39

I've already said that IMHO, OD is a free time project and everybody is free to work on what he wants. If you want to give a try, I don't see any problem.
And, as I've already told you, Ogre might handle culling by itself with next versions and it is something I don't want to mess with until there is a need. If you need some clues or you have questions about the architecture, you can ask questions. But IMO, there are more important stuff to do like adding data to make OD a real game. Having a good culling is nice but if we have nothing to show, it is useless. For my part, I prefer adding new rooms, creatures or ingame logic rather than working on culling.
hwoarangmy
 
Posts: 567
Joined: 16 Apr 2014, 19:13

Who is online

Users browsing this forum: No registered users and 1 guest