Bug?: Polygon drawing + outline fail

[Valeour]

I apologise in advance about the title, couldn't think of anything suitable.

Okay, so I'm not sure if this is a bug, or some error on my part, but considering the method, I'm pretty sure it's SFML.

So I have a vector of points, and I add all the points into a sf::Shape, then I set the properties such as colour, outline, etc.

Now, when I draw the polygon, I get some weird results;


Can you see where the outline doesn't match the sudden straight line of colour?

Now, the outline is definitely correct, but that random stretch of gray isn't.

Considering that the outline is draw with the polygon itself, it can't be an error on my part because I'm not manually drawing them seperately.

Unless I'm a total idiot and missing something, I'm not entirely sure what it is.

It is a tiny bit of a problem obviously, because it's plain as day in some generations.

Here's the code; (Please be warned that alot of it is debug code, it was me just messing around with some ideas and fractal generation)

Code: [Select]

#include <SFML\Graphics.hpp>
#include <time.h>
#include <Vector>

sf::VideoMode VMode(800, 600,32);
sf::RenderWindow Window(VMode, "ProcGen");

void Generate();
void Draw();
void Clear();

static const float w = float(Window.GetWidth());
static const float h = float(Window.GetHeight());
float Displacement;
float MidPoint;
int Split;

sf::Shape Polygon;

std::vector<sf::Vector2f> Points;



int  main()
{
srand(time(0));

Clear();
Generate();

while (Window.IsOpened())
{
sf::Event Event;
while (Window.PollEvent(Event))
{
switch (Event.Type)
{
case sf::Event::Closed:
Window.Close();
break;

case sf::Event::KeyPressed:
Clear();
Generate();
break;

default:
break;
}
}

Window.Clear(sf::Color(0, 255, 255));
Draw();
Window.Display();


}

return 0;
}


void Generate()
{
std::vector<sf::Vector2f>::iterator It;
int j;

for (int i = 0; i < 7; i++)
{
Split = Split/2;
for(It = Points.begin(), j = 0; It != (Points.end() - 1); It++, j++)
{
sf::Vector2f Temp((Points[j].x+Points[j+1].x)/2,(Points[j].y+Points[j+1].y)/2);
Temp.y = Temp.y - (rand() % (Split*2) - Split);

Points.insert(It+1, Temp);

It = Points.begin();
for (int k = 0; k <= j; k++)
It++;

j++;
}
}

sf::Shape temp;

for (unsigned int i = 0; i < Points.size(); i++)
temp.AddPoint(Points[i]);

temp.SetColor(sf::Color(128,128,128));
temp.SetOutlineThickness(2.0f);

Polygon = temp;
}

void Draw()
{
//for (unsigned int i = 0; i < Points.size()-1; i++)
// Window.Draw(sf::Shape::Line(Points[i], Points[i+1], 2.0f, sf::Color::Black));

Window.Draw(Polygon);
}

void Clear()
{
Displacement =  rand() % 200 + 300;
    MidPoint = Displacement/2;
Split = MidPoint;
Points.clear();
Points.push_back(sf::Vector2f(0,h));
Points.push_back(sf::Vector2f(rand() % 400 + 200,h-Displacement));
Points.push_back(sf::Vector2f(w,h));
}

[luiscubal]

SFML Shape documentation states that it represents *convex* shapes.
Your example uses a concave shape

[Valeour]

That couldn't have gone over my head even more if you tried.

I'm off to google what you mean.

But still, isn't this worth pointing out? I mean the outline works fine, but the 'filling' doesn't.

Edit:
Oh, I see what you mean about the concave thing... so... what can I do for a work around? I just wanted to add points and fill the space in the middle.

[Groogy]

The outlining works because it's just a line drawn from point to point.

The  concave/convex part applies for the actual polygon which is shown as the filling. What you can do is divide the entire shape into several smaller shapes or you could do the filling manually by manipulating an image pixels.

[Haikarainen]

The thor-lib contains a module for both concave/convex shapes.

[Valeour]

I get the whole outline going to points thing, but shouldn't it follow the whole convex thing instead?

There's no way in hell I could even do something like splitting it up into parts then putting them together, that's way out of my league.

I guess I'll have a look into the thor-lib then.

So many libraries...

[Groogy]

No it won't follow the convex thing. Because the outline are several lines drawn between several points. More exactly the points you specify. Each line between two points are a separate shape in OpenGL(the API that draws this behind the scene). While the filling is the actual shape and is represented as a whole polygon in OpenGL and I don't know why but it's common practice that polygons have to be convex.

If you missed, I also proposed that you manipulate an image directly while generating instead of a shape. It's a lot easier than it sounds. It's like writing to a 2D array with sf::Color objects.

[Valeour]

Hmm... I guess I need to go look at some image functions then. Thanks.

Me being lazy; is there a 'fill' function or anything? That's the only real thing I'm after. Before I just drew a line, all I wanted to do was fill the bottom half of the screen.

[Groogy]

No but it's fairly easy to implement. Check out the flood-fill algorithm.

[Valeour]

That's pretty hot, thanks.

I always wondered how 'fill' works, it just seems so quick on paint and stuff, but using an algorithm like that just looks like it'd take forever.

I really need to give processors more credit. xD

Also, I guess this topic can be closed now.

[Valeour]

Okay, sorry for the double post but;

I've tried a flood fill algorithm, but it's just so slow! It takes like 5 minutes to even do it!

So how the hell does paint do it so fast?

Here's my code anyway;

Code: [Select]


void FloodFill(sf::Vector2i Pixel, sf::Color SelectedColour, sf::Color TargetColour)
{
std::queue<sf::Vector2i> FillQueue;

if (Mountain.GetPixel(Pixel.x, Pixel.y) != TargetColour)
return;

FillQueue.push(Pixel);

while (!FillQueue.empty())
{
sf::Vector2i n (FillQueue.front());

if (Mountain.GetPixel(n.x, n.y) == TargetColour)
                {
Mountain.SetPixel(n.x, n.y, SelectedColour);

if (n.x - 1 > 0)
FillQueue.push(sf::Vector2i(n.x-1, n.y));

if (n.x + 1 < 800) //800 being window width.
FillQueue.push(sf::Vector2i(n.x+1, n.y));

if (n.y - 1 > 0)
FillQueue.push(sf::Vector2i(n.x, n.y-1));

if (n.y + 1 < 599) //800 being window height, except 600 caused crashing.
FillQueue.push(sf::Vector2i(n.x, n.y+1));

               }
                FillQueue.pop();

std::cout << FillQueue.size() << std::endl;
//Draw();
}

return;
}


The reason Draw was there, was so I can see what happens when it does it, (Cool effect of it spreading out, but obviously this makes the whole thing slower, so i commented it out). cout is there just so I could see that it was doing something and how many pixels are left to change... This just keeps going up.

If I remove all 4 of these;

Code: [Select]

if (Mountain.GetPixel(n.x, n.y+1) == TargetColour
this speeds it up the cycles tremendously, but then also doubles the amount of pixels it's checking.

How can I speed up this operation so it's as fast as paint? Is it because I'm constantly using an sf::Image (Mountain) to check for pixels? I can't find any other way to check the pixels of the thing even through Sprite or Texture.

This is becoming a real pain in the backside, because I have no idea!

EDIT!
Okay, I managed to speed it up by half, but it still takes a really long time, I've updated the code above with what I have.

EDIT2!
Er... okay... I removed std::cout... and it's instant....
...anyone care to explain why...?
Also, fairly obvious, but debug takes 2-3 seconds to achive what I want to do, but release is fairly instant. It's quite cool how much difference it makes.

[luiscubal]

okay... I removed std::cout... and it's instant....

Generally, I/O can be a LOT slower than writing to memory, so if you do it for every pixel of your image it'll definitively slow things down. And since endl is being used, tricks to make things faster like buffers can't be used here.

If flood-fill is still too slow for you, there are other algorithms you could try such as scanline fill. But if in release mode it is "instant", then I'm not sure you should even bother.

[Valeour]

Sorry, I know "instant" is a bit of a bad term, but I kind of meant "it's so fast, that you barely notice a delay".

And that is interesting to know, thank you.

Also scan fill kinda scared me, and like you said, this works, so I may as well stick to it.

It's not like I'm using this in anything important right now, I'm just literally collecting 'knowledge' as it were.

Thanks for all the help guys