Trójkąt Sierpińskiego, ocena algorytmu i kilka pytań.

Question

Hej, napisałem w C++/SFML dla odprężenia mały program generujący znany fraktal, może nie jest to duży projekt ale uznałem że uzyskany efekt jest dość ciekawy:

oto kod programu:

#include <SFML/Graphics.hpp>
#include <vector>
#include <array>

//-----------------------------------------------------------------------------------

void generateTriangles(int deepth, std::array<sf::Vector2f, 3> vertex, std::vector<sf::Vertex>& points) {
	
	if (deepth <= 0) return; 

	sf::Vector2f rs = (vertex[0] + vertex[1]) / 2.f;
	sf::Vector2f bs = (vertex[1] + vertex[2]) / 2.f;
	sf::Vector2f ls = (vertex[2] + vertex[0]) / 2.f;

	points.emplace_back(rs, sf::Color(0, 0, 0, 255));
	points.emplace_back(bs, sf::Color(0, 0, 0, 200));
	points.emplace_back(ls, sf::Color(0, 0, 0, 145));

	generateTriangles(deepth - 1, { vertex[1], bs, rs }, points);
	generateTriangles(deepth - 1, { bs, vertex[2], ls }, points);
	generateTriangles(deepth - 1, { rs, ls, vertex[0] }, points);
}

//-----------------------------------------------------------------------------------

constexpr unsigned SurfaceWidth = 900u;
constexpr unsigned SurfaceHeight = 900u;

//-----------------------------------------------------------------------------------

int main() {

	sf::RenderWindow window(sf::VideoMode(SurfaceWidth,SurfaceHeight), "window", sf::Style::Close); 
	window.setKeyRepeatEnabled(false);

	///----------------------------------------------------------------------------

	std::array<sf::Vector2f, 3> startedVertex = {
		(sf::Vector2f(0.f, 0.f) + sf::Vector2f(float(window.getSize().x), 0.f) / 2.f ),
		sf::Vector2f(float(window.getSize().x), float(window.getSize().y)),
		sf::Vector2f(0.f, float(window.getSize().y))
	}; // masę rzutowań na float by uniknąć ostrzeżeń...

	std::vector<sf::Vertex> triangle;
	triangle.emplace_back(startedVertex[0], sf::Color(2, 225, 119, 255));
	triangle.emplace_back(startedVertex[1], sf::Color(2, 225, 119, 255));
	triangle.emplace_back(startedVertex[2], sf::Color(2, 225, 119, 255));

	generateTriangles(7, { startedVertex[0], startedVertex[1], startedVertex[2] }, triangle);

	///----------------------------------------------------------------------------

	sf::RenderTexture surface;
	surface.create(SurfaceWidth, SurfaceHeight);
	surface.setSmooth(true);

    while (window.isOpen()) { 

		sf::Event event;
		while (window.pollEvent(event)) {

			if (event.type == sf::Event::Closed)
				window.close();

			if (event.type == sf::Event::KeyPressed) {

				if (event.key.code == sf::Keyboard::S) { //screenshot
					surface.clear(sf::Color::Black);
					surface.draw(&triangle[0], triangle.size(), sf::Triangles);
					surface.display();
					surface.getTexture().copyToImage().saveToFile("result.jpg");
				}
			}
		}

		window.clear(sf::Color(0, 0, 0));
		window.draw(&triangle[0], triangle.size(), sf::Triangles);
		window.display();
	}
}

Algorytm jest rekurencyjny, na początku tworzymy duży trójkąt ( jego trzy wierzchołki ) a następnie już w funkcji mniejszy trójkąt mający swoje wierzchołki w połowie boków większego. Pozostaną wtedy 3 mniejsze figury, dla każdej wywołujemy funkcje ponownie. Dla efektu wewnętrzne trójkąty mają różne stopnie przeźroczystości dla swoich wierzchołków.

Czy mógłbym coś poprawić? Zrobić łatwiej/wydajniej?

Chciałbym zrobić też animację niekończącego się przybliżenia ( jak tu ).

Jak jest najlepsza metoda żeby to zrobić? Myślę o czymś takim żeby wykonać trójkąt bardzo szczegółowy ( do np. 8 poziomu rekurencji ). Przybliżać do pewnego momentu ( aż na ekranie będzie widoczny tylko jeden "pod-trójkąt trójkątów" ;) ) a potem znowu w mgnieniu oka oddalić na sam początek.

Będę wdzięczny za wszelkie wskazówki, zaznaczam że pierwszy raz bawię się fraktalami i jest to do tej pory dla mnie mega frajda ;)

Comments

Fajnie wyszło ;) Mógłbyś użyć konstruktora konwertującego sf::Vector2<> żeby trochę ujednolicić zapis i uniknąć rzutowania funkcyjnego.

Answer 1

#include <SFML/Graphics.hpp>
#include <cstddef>
#include <vector>
#include <array>

//-----------------------------------------------------------------------------------

namespace {

constexpr std::size_t SurfaceWidth = 900;
constexpr std::size_t SurfaceHeight = 900;
constexpr std::size_t FractalDepth = 9;

//-----------------------------------------------------------------------------------

// Naive constexpr powr(...)
constexpr std::size_t cstPower(std::size_t value, std::size_t pow) {
    std::size_t result = 1;
    for(std::size_t idx = 0; idx <= pow; ++idx) {
        result *= value;
    }
    return result;
}

//-----------------------------------------------------------------------------------

constexpr std::size_t numOfTriangles(std::size_t dept) {
    std::size_t result = 0;
    for(std::size_t idx = 0; idx < dept; ++idx) {
        result += cstPower(3, idx);
    }
    return result + 3;
}

//-----------------------------------------------------------------------------------

template<typename T, typename Container>
inline void drawOn(T& canvas, const Container& container) {
    canvas.clear(sf::Color::Black);
    canvas.draw(&container[0], container.size(), sf::Triangles);
    canvas.display();
}

} // anonymous namespace

//-----------------------------------------------------------------------------------

void generateTriangles(std::size_t deepth, std::array<sf::Vector2f, 3> vertex, std::vector<sf::Vertex>& points) {

    if (deepth == 0) return;

    sf::Vector2f rs = (vertex[0] + vertex[1]) / 2.f;
    sf::Vector2f bs = (vertex[1] + vertex[2]) / 2.f;
    sf::Vector2f ls = (vertex[2] + vertex[0]) / 2.f;

    points.emplace_back(rs, sf::Color(0, 0, 0, 255));
    points.emplace_back(bs, sf::Color(0, 0, 0, 200));
    points.emplace_back(ls, sf::Color(0, 0, 0, 145));

    generateTriangles(deepth - 1, { vertex[1], bs, rs }, points);
    generateTriangles(deepth - 1, { bs, vertex[2], ls }, points);
    generateTriangles(deepth - 1, { rs, ls, vertex[0] }, points);
}

//-----------------------------------------------------------------------------------

int main() {

    sf::RenderWindow window(sf::VideoMode(SurfaceWidth,SurfaceHeight), "window", sf::Style::Close);
    window.setKeyRepeatEnabled(false);

    ///----------------------------------------------------------------------------

    std::array<sf::Vector2f, 3> startedVertex = {{
        {window.getSize().x / 2.F, 0.F},
        {static_cast<float>(SurfaceWidth), static_cast<float>(SurfaceHeight)},
        {0.F, static_cast<float>(SurfaceHeight)}
    }};

    sf::Color color1{2, 255, 119, 255};
    sf::Color color2{128, 255, 119, 255};
    sf::Color color3{255, 155, 119, 255};

    std::vector<sf::Vertex> triangle{
        {startedVertex[0], color1},
        {startedVertex[1], color2},
        {startedVertex[2], color3}
    };

    triangle.reserve(numOfTriangles(FractalDepth));

    generateTriangles(FractalDepth, { startedVertex[0], startedVertex[1], startedVertex[2] }, triangle);

    ///----------------------------------------------------------------------------

    sf::RenderTexture surface;
    surface.create(SurfaceWidth, SurfaceHeight);
    surface.setSmooth(true);

    while (window.isOpen()) {

        sf::Event event;
        while (window.pollEvent(event)) {

            if (event.type == sf::Event::Closed)
                window.close();

            if (event.type == sf::Event::KeyPressed) {

                if (event.key.code == sf::Keyboard::S) { //screenshot
                    drawOn(surface, triangle);
                    surface.getTexture().copyToImage().saveToFile("result.jpg");
                }
            }
        }

        drawOn(window, triangle);
        window.display();
    }
}

Ot tak na szybko mi przyszły następujące dodatki... Derekursywację zostawiam już Tobie.

Comments

@mokrowski

Zgodnie z propozycją zaimplementowałem samemu kilka zmian:

#include <SFML/Graphics.hpp>
#include <vector>
#include <array>
#include <cstddef>

//-----------------------------------------------------------------------------------

const unsigned SurfaceWidth = sf::VideoMode::getDesktopMode().width;
const unsigned SurfaceHeight = sf::VideoMode::getDesktopMode().height;
const unsigned RecursionDeepth = 10;

//-----------------------------------------------------------------------------------

constexpr std::size_t CstPower(std::size_t value, std::size_t pow) {
	if (pow == 0)
		return 1;
	return value * CstPower(value, pow - 1);
}

//-----------------------------------------------------------------------------------

constexpr std::size_t GetNumberOfTriangleVertex(std::size_t recursionDeepth) {
	std::size_t result = 0;
	for (std::size_t i = 1; i <= recursionDeepth; ++i) {
		result += CstPower(3, i);
	}
	return result + 3;
}

//-----------------------------------------------------------------------------------

template <typename Canvas, typename Container>
inline void drawOn(Canvas& canvas, const Container& container) {
	canvas.clear(sf::Color(0, 0, 0));
	canvas.draw(&container[0], container.size(), sf::Triangles);
	canvas.display(); 
}

//-----------------------------------------------------------------------------------

void generateTriangles(std::size_t deepth, std::array<sf::Vector2f, 3> vertex, std::vector<sf::Vertex>& points) {
	
	if (deepth <= 0) return; 

	sf::Vector2f rs = (vertex[0] + vertex[1]) / 2.f;
	sf::Vector2f bs = (vertex[1] + vertex[2]) / 2.f;
	sf::Vector2f ls = (vertex[2] + vertex[0]) / 2.f;

	points.emplace_back(rs, sf::Color(0, 0, 0, 255));
	points.emplace_back(bs, sf::Color(0, 0, 0, 200));
	points.emplace_back(ls, sf::Color(0, 0, 0, 145));

	generateTriangles(deepth - 1, { vertex[1], bs, rs }, points);
	generateTriangles(deepth - 1, { bs, vertex[2], ls }, points);
	generateTriangles(deepth - 1, { rs, ls, vertex[0] }, points);
}

//-----------------------------------------------------------------------------------

int main() {

	sf::RenderWindow window(sf::VideoMode(SurfaceWidth,SurfaceHeight), "window", sf::Style::Close); 
	window.setKeyRepeatEnabled(false);
	window.setFramerateLimit(60);

	sf::RenderTexture surface;
	surface.create(SurfaceWidth, SurfaceHeight);
	surface.setSmooth(false);

	sf::View v = window.getView();

	std::array<sf::Vector2f, 3> startedVertex = {{
		{ window.getSize().x / 2.f, 0.f },
		{ (static_cast<float>(SurfaceWidth - SurfaceHeight) / 2.f) + SurfaceHeight, static_cast<float>(SurfaceHeight) },
		{ static_cast<float>(SurfaceWidth - SurfaceHeight) / 2.f, static_cast<float>(SurfaceHeight) }
	}};

	std::vector<sf::Vertex> triangle{
		{ startedVertex[0], sf::Color{203, 20, 66, 255} },
		{ startedVertex[1], sf::Color{203, 20, 66, 255} },
		{ startedVertex[2], sf::Color{203, 20, 66, 255} }
	};

	triangle.reserve(GetNumberOfTriangleVertex(RecursionDeepth));
	generateTriangles(RecursionDeepth, startedVertex, triangle);

	float deltaTime = 1/60.f;
    sf::Clock clock;

    while (window.isOpen()) { 

		float frameStart = clock.getElapsedTime().asSeconds(); 

		sf::Event event;
		while (window.pollEvent(event)) {

			if (event.type == sf::Event::Closed)
				window.close();

			if (event.type == sf::Event::KeyPressed) {

				if (event.key.code == sf::Keyboard::S) { //screenshot
					surface.setView(v); 
					drawOn(surface, triangle);
					surface.getTexture().copyToImage().saveToFile("result.jpg");
				}
			}
		}

		if (sf::Keyboard::isKeyPressed(sf::Keyboard::A)) {
			v.zoom(0.9f);
			window.setView(v);
		} if (sf::Keyboard::isKeyPressed(sf::Keyboard::D)) {
			v.zoom(1.1f);
			window.setView(v);
		}

		static constexpr float speed = 100; 
		if (sf::Keyboard::isKeyPressed(sf::Keyboard::Left)) {
			v.move(sf::Vector2f(-speed, 0) * deltaTime);
			window.setView(v);
		} if (sf::Keyboard::isKeyPressed(sf::Keyboard::Right)) {
			v.move(sf::Vector2f(speed, 0) * deltaTime);
			window.setView(v);
		} if (sf::Keyboard::isKeyPressed(sf::Keyboard::Up)) {
			v.move(sf::Vector2f(0, -speed) * deltaTime);
			window.setView(v);
		} if (sf::Keyboard::isKeyPressed(sf::Keyboard::Down)) {
			v.move(sf::Vector2f(0, speed) * deltaTime);
			window.setView(v);
		}

		drawOn(window, triangle);

		deltaTime = clock.getElapsedTime().asSeconds() - frameStart;
	}
}

Funkcje obliczającą potęgi zrobiłem rekursywną:

constexpr std::size_t CstPower(std::size_t value, std::size_t pow) {
	if (pow == 0)
		return 1;
	return value * CstPower(value, pow - 1);
}

tak z ciekawości, C++ nie ma jeszcze w bibliotece standardowej własnych funkcji mogących się wykonywać w czasie kompilacji?

Derekursywację zostawiam już Tobie.

Sugerujesz żebym zamienił rekurencyjną funkcje generateTriangles() na wersje iteracyjną?

---

Jeszcze nie ma funkcji matematycznych z constexpr w standardzie. Jeśli jednak jest to konieczne, jest kilka implementacji zewnętrznych (pierwsza z brzegu a wyszukiwarka da Ci dalsze... ): https://github.com/kthohr/gcem

Rekurencja w C++ nie jest ujęta w standardzie. To twórcy kompilatorów, ze swojej uprzejmości ją implementują oraz ew. dodają optymalizacje tail recursion. Kod bez rekurencji możesz lepiej kontrolować (pomijam dyskusję o paradygmacie funkcyjnym) a jest często zabroniona w standardach produkcyjnych.