Frustum Culling Problem; Everything works except top.

[Anteara]

Hi all, I've got a problem with frustum culling. Basically, I'm trying to make a level editor by implementing a small engine, that I will later use to make the game the level editor makes the levels for.

At the moment, as a test, I'm drawing 250,000 tiles (overkill, I know; I did it to test my culling.)
It only renders the tiles within the viewport, so I get a solid 60 FPS.
However, as I move the view right, it works, as I move it left, it works, as I move it down, it works. When a single tile moves up, off the viewport, the ENTIRE 250,000 tiles disappear. They only reappear when I move it back down in to the viewport. Here's a video:


Here's the code for the program:

#include <SFML/Window.hpp>
#include <SFML/Graphics.hpp>
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include "Windows.h"
#define SIZE 500
using namespace std;
typedef struct {
        sf::Sprite sprite;
        sf::FloatRect bounds;
} grid;

bool SpriteClicked(sf::Sprite &sprite, sf::RenderWindow &window)
{

        if(sf::Mouse::isButtonPressed(sf::Mouse::Left))
        {
                // transform the mouse position from window coordinates to world coordinates
                sf::Vector2f mouse = window.mapPixelToCoords(sf::Mouse::getPosition(window));

                // retrieve the bounding box of the sprite
                sf::FloatRect bounds = sprite.getGlobalBounds();

                // hit test
                if (bounds.contains(mouse))
                {
                        return true;
                }
        }
        return false;
}

bool SpriteHovered(sf::Sprite &sprite, sf::RenderWindow &window)
{

                // transform the mouse position from window coordinates to world coordinates
                sf::Vector2f mouse = window.mapPixelToCoords(sf::Mouse::getPosition(window));

                // retrieve the bounding box of the sprite
                sf::FloatRect bounds = sprite.getGlobalBounds();

                // hit test
                if (bounds.contains(mouse))
                {
                        return true;
                }
       
        return false;
}

void InitButtons(sf::Sprite & okBtn, sf::Sprite &zoomBtn, sf::Sprite &unzoomBtn, sf::Sprite &refreshBtn, sf::Texture & texture, sf::Texture &zoomTex, sf::Texture &unZoomTex, sf::Texture &refreshTex)
{
        //load textures
        texture.loadFromFile("C:\\Users\\Kevin Mallinson\\Documents\\Visual Studio 2012\\Projects\\MapMaker\\MapMaker\\btn.png");
        zoomTex.loadFromFile("C:\\Users\\Kevin Mallinson\\Documents\\Visual Studio 2012\\Projects\\MapMaker\\MapMaker\\zoom.png");
        unZoomTex.loadFromFile("C:\\Users\\Kevin Mallinson\\Documents\\Visual Studio 2012\\Projects\\MapMaker\\MapMaker\\unzoom.png");
        refreshTex.loadFromFile("C:\\Users\\Kevin Mallinson\\Documents\\Visual Studio 2012\\Projects\\MapMaker\\MapMaker\\refresh.png");
        //ok button
        okBtn.setTexture(texture);
        okBtn.setScale(sf::Vector2f(0.2f, 0.2f)); // absolute scale factor
        okBtn.setPosition(sf::Vector2f(1450, 815));
        //zoom button
        zoomBtn.setTexture(zoomTex);
        zoomBtn.setPosition(sf::Vector2f(1450, 715));
        //unzoom button
        unzoomBtn.setTexture(unZoomTex);
        unzoomBtn.setPosition(sf::Vector2f(1450, 615));
        //refresh button
        refreshBtn.setTexture(refreshTex);
        refreshBtn.setPosition(sf::Vector2f(1450, 515));
}

void MoveView(sf::View &view)
{
        sf::Event event;
        if (sf::Keyboard::isKeyPressed(sf::Keyboard::Left))
                view.move(5, 0);
        if (sf::Keyboard::isKeyPressed(sf::Keyboard::Right))
                view.move(-5, 0);
        if (sf::Keyboard::isKeyPressed(sf::Keyboard::Up))
                view.move(0, 5);
        if (sf::Keyboard::isKeyPressed(sf::Keyboard::Down))
                view.move(0, -5);
}

int main()
{
        //Variable declarations//
        sf::Font MyFont;
        MyFont.loadFromFile("arial.ttf");
        sf::Texture texture, gridTex, zoomTex, unZoomTex, refreshTex;
        gridTex.loadFromFile("grid.png");
        sf::Sprite okBtn, zoomBtn, unzoomBtn, refreshBtn;
        auto gridArray = new grid[SIZE][SIZE]();
        static float FPS;
        static float nextSecond;
        static float prevSecond;
        sf::FloatRect collider;

        sf::Text atext;
        atext.setFont(MyFont);
        atext.setCharacterSize(50);
        atext.setStyle(sf::Text::Bold);
        atext.setColor(sf::Color::Red);
        atext.setPosition(1250, 100);
        sf::Clock clock;
        char tempstr[50];
        //Variable declarations//
        //I start at 1 simply so i can use these variables in my arithmatic, as something * 0 is 0
        for (int i = 1; i <= SIZE; i++)
        {
                for (int j = 1; j <= SIZE; j++)
                {
                        gridArray[i-1][j-1].sprite.setTexture(gridTex);
                        gridArray[i-1][j-1].sprite.setPosition(sf::Vector2f(i*40, j*40));
                        gridArray[i-1][j-1].bounds = gridArray[i-1][j-1].sprite.getGlobalBounds();
                }
        }
        ///////////////////////////////
        sf::RenderWindow window(sf::VideoMode(1600, 900), "Level Editor");
        window.setFramerateLimit(60);
        ///////////////////////////////
        sf::View gridView(sf::Vector2f(800, 450), sf::Vector2f(1600, 900));
        sf::View editorView(sf::Vector2f(1400, 450), sf::Vector2f(420, 900));
        gridView.setViewport(sf::FloatRect(0, 0, 0.7f, 1));
        editorView.setViewport(sf::FloatRect(0.7f, 0, 0.3f, 1));
        ///////////////////////////////
        InitButtons(okBtn, zoomBtn, unzoomBtn, refreshBtn, texture, zoomTex, unZoomTex, refreshTex);

        bool test = false;
        while (window.isOpen())
        {
                int tilesDrawn = 0;
                window.setView(gridView);
                // check all the window's events that were triggered since the last iteration of the loop
                sf::Event event;
                while (window.pollEvent(event))
                {
                        // "close requested" event: we close the window
                        if (event.type == sf::Event::Closed)
                                window.close();
                }
                sf::FloatRect screenRect(sf::Vector2f(gridView.getCenter().x - (gridView.getSize().x)/2, gridView.getCenter().y - (gridView.getSize().y)/2) , gridView.getSize());
                window.clear(sf::Color::White);

                FPS++;
                nextSecond = GetTickCount() * 0.001f;  
                if(nextSecond - prevSecond > 1.0f)
                {
                        prevSecond = nextSecond;
                        sprintf(tempstr, "FPS: %d ", (int)FPS);
                        FPS = 0;
                }

                //horizontal
                for (int i = 0; i < SIZE; i++)
                {                      
                        for (int j = 0; j < SIZE; j++)
                        {
                                collider = sf::FloatRect(gridArray[j][i].sprite.getGlobalBounds().left, gridArray[j][i].sprite.getGlobalBounds().top, 40, 40);
                                if (gridArray[i][j].sprite.getGlobalBounds().intersects(screenRect))
                                {
                                        window.draw(gridArray[i][j].sprite);
                                        tilesDrawn++;
                                        if (SpriteHovered(gridArray[i][j].sprite, window))
                                                gridArray[i][j].sprite.setColor(sf::Color(0, 255, 0));
                                        else
                                                gridArray[i][j].sprite.setColor(sf::Color(255, 255, 255));
                                }
                                else
                                {
                                        break;
                                }
                        }
                }



                std::cout << "Tiles Drawn: " << tilesDrawn << std::endl;
                MoveView(gridView);
               




                window.setView(editorView);

                window.draw(okBtn);
                window.draw(zoomBtn);
                window.draw(unzoomBtn);
                window.draw(refreshBtn);

                atext.setString(tempstr);

                //draw the string
                window.draw(atext);


                if (SpriteClicked(okBtn, window))
                        window.close();
                if (SpriteClicked(unzoomBtn, window))
                        gridView.zoom(1.02f);
                if (SpriteClicked(zoomBtn, window))
                        gridView.zoom(0.98f);
                if (SpriteClicked(refreshBtn, window))
                        window.close();





                window.display();



        }

        return 0;
}

Here's only the culling code:

                for (int i = 0; i < SIZE; i++)
                {                      
                        for (int j = 0; j < SIZE; j++)
                        {
                                //collider = sf::FloatRect(gridArray[j][i].sprite.getGlobalBounds().left, gridArray[j][i].sprite.getGlobalBounds().top, 40, 40);
                                if (gridArray[i][j].sprite.getGlobalBounds().intersects(screenRect))
                                {
                                        window.draw(gridArray[i][j].sprite);
                                        tilesDrawn++;
                                        if (SpriteHovered(gridArray[i][j].sprite, window))
                                                gridArray[i][j].sprite.setColor(sf::Color(0, 255, 0));
                                        else
                                                gridArray[i][j].sprite.setColor(sf::Color(255, 255, 255));
                                }
                                else
                                {
                                        break;
                                }
                        }
                }

Does anyone know how I could do this? It's quite annoying
Also, I have an array with 250,000 elements, each with a tile. That's how I plan to render each individual tile. Is there any quicker, more efficient way to do that? (Note: In the actual game, I will NOT get 250,000 tiles in a single array, likely, 1000 for a town, 5000 for a temple, etc.)

Thanks.

[Laurent]

I don't know why you have this problem, but your culling algorithm could be much more efficient and simpler.

Since your map is a regular grid of tiles, the part which is visible on screen is an axis-aligned rectangular area. Therefore you can just compute the start/end x/y tile indices (based on the screen rect) and iterate on these ranges to render only the corresponding tiles. No need to iterate on the whole map and test each individual tile.

[Anteara]

Thanks. I think I understand what you mean. As such, I implemented this:

                startX = floor(screenRect.left / tileSize);
                startY = floor(screenRect.top / tileSize);
                endX = startX + 50;
                endY = startY + 50;
                cout << "Rendering starting from horizontal tile " << startX << " to tile " << endX << endl; //Outputs 0 to 50 at start, successfully iterates
                cout << "Rendering starting from vertical tile " << startY << " to tile " << endY << endl; // Outputs to 50 at start, successfully iterates
                //make sure we dont loop over indicies not in range (under)
                if (startX < 0)
                        startX = 0;
                //make sure we dont loop over indicies not in range (under)
                if (startY < 0)
                        startY = 0;
                //make sure we dont loop over indicies not in range (over)
                if (startX > SIZE)
                        startX = SIZE;
                //make sure we dont loop over indicies not in range (over)
                if (startY > SIZE)
                        startY = SIZE;

                for (startX; startX < endX; startX++)
                {                      
                        for (startY; startY < endY; startY++)
                        {
                                        window.draw(gridArray[startX][startY].sprite);
                                        //tilesDrawn++;
                                        //if (SpriteHovered(gridArray[startX][startY].sprite, window))
                                        //      gridArray[startX][startY].sprite.setColor(sf::Color(0, 255, 0));
                                        //else
                                        //      gridArray[i][j].sprite.setColor(sf::Color(255, 255, 255));
                               
                        }
                }

when I print out those values to the console, It looks right, for example, by default it says "Rendering 0 to 50", then if i move, it says "Rendering 1 to 51", etc. It LOOKS like it should work. That's why I'm not sure why it's not working.

Basically what it does, is only render all columns in the first row. IT doesn't render any of the other rows.

Here's a video to show you:



Do you have any idea how I can fix this? Thanks! I appreciate your help

Here's the entire code in case it helps

http://pastebin.com/0waBKtAU

Edit: I fixed it by changing my loop to

                for (int i = startX; i < endX; i++)
                {                      
                        for (int j = startY; j < endY; j++)
                        {

However I'm not sure why that fixes it, aren't they the exact same thing? O.o

Anyway, do you think my culling algorithm now is efficient and simpler?


Also, I haven't made a game before, so I'm not sure if I'm doing everything right, in particular, rendering each tile with a different sprite (I noticed here http://en.sfml-dev.org/forums/index.php?topic=7933.0 that the OP only renders one sprite, and just moves it around.)

Is the way that I'm doing it OK?