Tile Culling -- SlopeWalk alg. explained

[paul424]

Occlusion Culling aka http://en.wikipedia.org/wiki/Hidden_surface_determination is important thing in CG when you want to keep high fps in your program. Culling a tiles on regular 2D gird seems to be extremly simple to implement, as you can easily precompute boundary of visible set of tiles in the camera view and by walking around that boundary you can disable enable proper tiles. What is the shape of such tile set cut by camera planes ? Well it is Quadrilateral , except we are in the quantized space http://en.wikipedia.org/wiki/Quantization , so the sides of that q-l is not straight line , but rather up and down >> stairs << .
Previous tile culling alg. was flawed because it was working only for some special case ( case being the positional relation of our four points ) .
Currently I try to impment the most general polygon rasterizing algorithm , that is :
1. We choose the max and min points due to their Y value .
2. We sort all the points by the angle value in it's polar representation ( that is going , by visiting them clockwise due to the center of the polygon )
3. Now we have two paths from which we can walk from top to down vertices : call them left and right .
4. Between each following pair of vertices we can establish a >> slope << , which is just the the "a" in the eq. of linear form y = ax + b
5. Now start drawing our polygon Row by Row From top to bottom . Each Row has given the most left and rightmost tile due to use of both paths prepared before -- Left path for tracing the most Leftmost Tile , Right path teh most Rightmost Tile in each .

EDIT : Bertram , Could you merge in your branch into 'development' one ?
EDIT: I UNBURIED THAT THREAD SO WE CAN DISCUSS CULLING AGAIN

[Bertram]

Hi Paul,

Thanks for the explanations. The development branch and SVN have now got my latest changes. We're in sync.

[paul424]

So could you have a look of my implementation , Bertram ?
Or could we discuss it on IRC ?
Opposite to previous implementation , this new one crashes on camera move so far ...

[Bertram]

Hi Paul,

Sorry, not seriously yet. But I will.
Do you know where it crashes btw?

[paul424]

Fixed and now at least it does not crash on camera move. For some angles it gives black hole :\ . Probably rthe Vertexes are wrongly sorted or read ....

[paul424]

Seems it can start and work with any angle , camera angle rotation is what it starts fooling the most ... >_> ....

[Bertram]

Ok.
Btw, why did you revert my work here, I don't see meaningful reason to do so, and it reverted mostly headers addition and indentation cleanups?
http://sourceforge.net/p/opendungeons/g ... 347953e90/

[paul424]

Well, I own you apologization , I didn't notice your change, I was testing in separation my algorithms and than I copied over and overwrite the improper ( or proper as I thought ) files.

[Bertram]

Hi again,

Well, I own you apologization , I didn't notice your change, I was testing in separation my algorithms and than I copied over and overwrite the improper ( or proper as I thought ) files.

Thus, please have a look at your changes with "git diff" and "git status" BEFORE you commit. And to prevent breaking the development branch too often, you should push your changes in your own synced branch, and request some testing from others before pushing to development.
This way, other devs like hwoarangmy won't have problems trying their own changes while you test yours.

Could you readd the copyright headers and the indentation fix in a new commit?

Thanks and regards,

[paul424]

Sorry for making troubles, I think you would be more agile in fixing this than me ...

EDIT : IT seems I know why SlopeWalk fails , this is due to ( currently ) discarding fraction values on Y Axis and treating them as Unit -- "1.0" value .

[Bertram]

Seems you're not far, then?

[paul424]

Yeap : Discarding fraction values on Y Axis , plus not enough large precision , which must be at least int_128 >_> would fix the issue it seems .....
I regret we don't have code monkey , someone who could type the simplest code == >> labour coders << .

[Bertram]

Eh eh, well, you know there is no such thing as a code monkey. Or if you prefer, we all are code monkeys.

[Danimal]

Yes, you are

[paul424]

Code monkey may refer to:

Code monkey, a term derived from the saying Monkey see, monkey do, but in reference to an unskilled computer programmer who can only perform programming tasks by copying examples, usually where they do not truly understand how the example works.
Code monkey, a derogatory term for an unskilled computer programmer who can only perform trivial or repetitive programming tasks or a reference to a job that treats even experienced programmers in a way that trivializes their problem-solving abilities. Can also be used as a derogatory term to express "even a monkey could write this code", which is often resented by computer programmers as it trivializes the complexity of programming. This term also draws an analogy from the infinite monkey theorem involving monkeys typing ad infinitum to produce Hamlet.


Monkey sometimes used with adjectives other than Code:

"adjective" monkey, a non-derogatory term for a skilled programmer who is tasked with performing a more trivial or repetitive computer programming task in addition to projects more consistent with their skill set.


Danimal . Bertram, : I think in this regard we are not >>code monkeys << as we can code non-trivial things in c++ .... If the team would draw some c++ novices which we could drive through ... "a dream of a cutted head" , as we say in polish

[Bertram]

Hi Paul,

Thanks for the references.
I must say I still believe such ones must have been written by elitist and corporate people to describe their lessen paid workers for the task the latter usually do.
In volunteers projects there is no such things as a code monkey but more as you described, a project novice. After all, there is no master here, so there is no slave either.

And I still do think that a few months are sufficient for a noob to turn himself into a true programmer if he has the will and the wits to do it.
And it's a good thing, as you can help the people who have more difficulties than you do, and you can learn from the ones that have a better level than you do.

Yet, I understand your will to see more people come and happily code on this project. It is already happening (isn't it hwoarangmy? ;]) and that's why I keep telling you (and everyone coding) that you should bear in mind the team commit policy, and the code guidelines when working on this project, to show respect for others who are also working on it, and not break the common branch.

It isn't a dream for beheaded men, it is happening. Keep faith.

[Danimal]

Hehe, dont take it wrong, im way worse than you guys, i learned programming basics but vanished it long ago to the oblivion when i discovered the joy that is being an artist. I really appreciate the effort everyone is putting in here, by using our free time and skills to recreate something we love into an open source incarnation, each of us doing our best in our respective fields.

"a dream of a cutted head" thats is something scary i dont get at all; but im sure, once we can present a tech demo that includes core basic gameplay, a bit of refinement and some easiness of use, we can start a campaign of recruitement, someone is bound to hop in and stay for long; but we need candy for that, thats our duty at the moment and once im done with my fucking Uni tests and Bertram finish the rooms code i plan a rehaul of texture and models for them, even if they are useless now, they will be ingame and looking pretty.
So dont desperate and have faith, just remember we are ones of the few that has stuck along since the Svend era

[paul424]

Bertram : Could you watch my implementation ? , what is more important now , my git repo is behind the origin one , how do I merge in so everyone is content with that ( especially you ) .

[Bertram]

Hi Paul,

Bertram : Could you watch my implementation ? , what is more important now , my git repo is behind the origin one , how do I merge in so everyone is content with that ( especially you ) .

I guess you mean your local repo?

The simplest way to get back in sync properly is to do:

{l Code}: {l Select All Code}

git pull --rebase

This will make your repo in sync with the remote one, putting your newest commits on top.
Don't forget to check the commits states before pushing so you don't forget any missing file, and broken stuff (indentation, something displeasing you, ...).
Compile the beast, play a bit, and you're good to go.

Regards,

[paul424]

So it does crashes, when rotating in some fairly marginal cases.
Question is , do we want other people to have started with tileculling enable and try it out ( and maybe debug it ) ? WIth Open Source model every bug is shallow .
So , could be call CullingManger :: starttileculling at the startup ?

[Bertram]

No, you mustn't. A feature should not be added/made active if it's easy to make it crash. (To me the crashes aren't marginal when the tile culling is enabled, sorry).

When you do a release, alpha/beta or whatever, you should try to make as much stable as possible.

But as release notes, we could add a few comments on how to enable it, so people willing to try, and only them, will see the culling in action.

It's a QA rule I'd like us to follow, never commit unfinished/broken stuff, and never activate by default an unstable feature, to prevent ruining the player's experience, but also other dev's one, when they are trying to implement their own feature. It's hard enough to debug one's own work without adding to it.

[paul424]

Occlusion Culling aka http://en.wikipedia.org/wiki/Hidden_sur ... ermination is important thing in CG when you want to keep high fps in your program. Culling a tiles on regular 2D gird seems to be extremly simple to implement, as you can easily precompute boundary of visible set of tiles in the camera view and by walking around that boundary you can disable enable proper tiles. What is the shape of such tile set cut by camera planes ? Well it is Quadrilateral , except we are in the quantized space http://en.wikipedia.org/wiki/Quantization , so the sides of that q-l is not straight line , but rather up and down >> stairs << .
Previous tile culling alg. was flawed because it was working only for some special case ( case being the positional relation of our four points ) .
Currently I try to impment the most general polygon rasterizing algorithm , that is :
1. We choose the max and min points due to their Y value .
2. We sort all the points by the angle value in it's polar representation ( that is going , by visiting them clockwise due to the center of the polygon )
3. Now we have two paths from which we can walk from top to down vertices : call them left and right .
4. Between each following pair of vertices we can establish a >> slope << , which is just the the "a" in the eq. of linear form y = ax + b
5. Now start drawing our polygon Row by Row From top to bottom . Each Row has given the most left and rightmost tile due to use of both paths prepared before -- Left path for tracing the most Leftmost Tile , Right path teh most Rightmost Tile in each .

EDIT : Bertram , Could you merge in your branch into 'development' one ?
EDIT: I UNBURIED THAT THREAD SO WE CAN DISCUSS CULLING AGAIN

[Bertram]

Thanks for the give-info post.

I'll make sure to read all that, and later match it against what is currently done to try and detect flaws and/or design problems.

EDIT : Bertram , Could you merge in your branch into 'development' one ?

I guess you want me to merge my fork repo on the sourceforge development branch?
Well, if that's the case, I'd like to make it clear we are no more working using sourceforge as a git remote repository handler.
We've fully moved to github, and my fork is no longer the main repository, but "just a fork" aimed at creating PRs (Pull requests) for review before merging them back to the main one.

Thus, if you want to participate in resuming the development of OD, you will have to fork the reference repository, by logging on github there:
https://github.com/OpenDungeons/OpenDungeons

and clicking on the "fork" button. A few seconds later, your fork should be ready to be cloned, using a command such as:

{l Code}: {l Select All Code}

git clone git@github.com:tomluchowski/OpenDungeons.git development

To make things clear, you should never commit directly to the main repo, and I won't provide you direct write access to it since I'd rather want everybody,
including Danimal and me to use forks and PR to see code updated in the repo.
I'll also ask that you don't auto-merge your own PR without the ok of another reviewer, or without doing code review + some test of another one's PR.
If you have doubts, just ask. I'm certain hwoarangmy, oln, Akien and me will be happy to help.

Danimal had a bit of struggles because of his high access level and I guess he sometimes regrets it.

EDIT: I UNBURIED THAT THREAD SO WE CAN DISCUSS CULLING AGAIN

Sure. While now, we should first determine how we're going to do implement fog of war, first, IMHO.

Regards,

[oln]

I've said this before:
Ogre already does culling, and it's being improved in ogre 2.0. I don't see why we should use time on making a custom culling setup, I highly doubt we are going to manage to make anything more efficient than what is already there.

[Bertram]

Heya oln,

I've said this before:
Ogre already does culling, and it's being improved in ogre 2.0. I don't see why we should use time on making a custom culling setup, I highly doubt we are going to manage to make anything more efficient than what is already there.

Then, there is something I don't understand. Why was a culling manager envisioned in the first place? (Seems to me the different Ogre culling management methods were added since a few Ogre versions already.)

Btw, what you say about Ogre 2.0 is true from what I could read so far, as their culling management will take rendering parallelization in mind if I'm correct, making it faster. Even if that's only promises as long as we haven't tested it ourselves.

@everyone:
Here, I'll ask everyone to make a clear vote on this with proper arguments, because we're going back and forth and it's hurting our focus.

Seems to me:
Paul and Danimal wants a custom culling management. Paul says it will be faster. I don't know the actual reason for Danimal.

oln tells is useless because already done by Ogre and will be faster in the future.
hwoarangmy and him say that there is a high change for it to be broken with the use of the client/server paradigm.
I must say I tend to agree with them as it sounds the most reasonable road, while I wouldn't like to drop code without a good reason.

To take a decision here, I'd propose this:
1. Paul/Tom forks openDungeons on github and create a custom branch where he keeps the culling manager code.
2. Then, we can remove it and focus on code simplifications as it seems to me to be a reasonable step to remove an early optimization.
3. If Paul/Tom is really sure he can win the match with his culling manager, then he'll be able to upgrade and finish his code, and make a PR for review and tests.

What do you think about my proposal?

Best regards,