Mesh - siatka dla obiektów 2D

Witam!
Chciałbym napisać program do generowania meshu dla obiektów 2D.
W programie wyświetlany byłby sprajt GameObjectu, a użytkownik poprzez kliknięcia myszą wskazywałby kolejne punkty dla siatki mesh. Jak generować mesh z podanych punktów ?

czy siatka ma się składać z prostokątów, czy niekoniecznie?

ja robiłem prostokątną: https://looptile.netlify.app/
takie coś robiłem, że dzieliłem cały teren np. na 20x20 siatkę złożoną z prostokątów. I potem obliczałem wierzchołki kolejnych prostokątów. A następnie tworzyłem ścianki. I jeden prostokąt to np. 2 trójkąty (w rzeczywistości tam jeden prostokąt dzieliłem na 4 trójkąty, żeby wydzielić środek).

natomiast siatka była generowana na początku (i potem tylko użytkownik mógł podnosić/opuszczać teren). Ty chyba chcesz tak zrobić, żeby użytkownik mógł dodawać teren horyzontalnie? I czy geometria siatki może być pod spodem prostokątna czy ma być całkowicie dowolna? (już nie chodzi mi o rendering/wygląd ostateczny, bo to kwestia shadingu, że jest kanciaste u mnie, ale chodzi mi o samą naturę geometrii).

Najlepiej jakby siatka generowała trójkąty. Potrzebuję jej do tego by móc zaznaczać obiekty w Edytorze.

tBane napisał(a):

Potrzebuję jej do tego by móc zaznaczać obiekty w Edytorze.

No to jak w końcu — potrzebujesz generować mesh dla obiektów 2D, czy zaimplementować narzędzie zaznaczania obiektów? Pisz wprost czego oczekujesz, jak to ma wyglądać, jak to ma działać itd. Przerzucanie się abstrakcyjnymi pojęciami niczemu nie służy, wręcz wszystko utrudnia.

Potrzebuję wygenerować siatkę trójkątów z podanego zbioru punktów.

A co to ma wspólnego z zaznaczaniem obiektów w mapie? Pachnie mi to problemem XY, dlatego pytam.

Bo potrzebuję te trójkąty do detekcji kolizji. W każdym razie nie wiem jak wygenerować siatkę trójkątów z podanych punktów.

Najlepiej jakby siatka generowała trójkąty. Potrzebuję jej do tego by móc zaznaczać obiekty w Edytorze. A do tego potrzebuję jakieś kolizje.

zaraz, bo można się zaplątywać w algorytmy do generowania siatek, ale tutaj być może inny problem próbujesz rozwiązać.

żeby sprawdzić kolizje możesz np. najpierw posprawdzać, czy prostokąty kolidują, a jak kolidują, to sprawdzać, czy piksele kolidują (uwzględniając przezroczystość). Nie potrzebujesz sprawdzać tego po trójkątach.

inna technika, to możesz stworzyć teksturę dużą jak ekran i renderować scenę do tej tekstury (renderować w pamięci, off-screen), ale specjalnym shaderem. I chodzi o to, że ten shader by renderował każdy obiekt nieco innym kolorem. A potem tylko sprawdzasz np. współrzędne myszy z kolorem na tej specjalnej teksturze (to o tyle fajne, że też klikanie obiektów 3D można w ten sposób obsłużyć, bez bawienia się w jakieś ręczne obliczenia).

tBane napisał(a):

Bo potrzebuję te trójkąty do detekcji kolizji.

Czemu akurat trójkąty? Twoja mapa jest czysto dwuwymiarowa, więc jedyne czego potrzebujesz to testów na prostokątach. Natomiast jesli interesuje Cię obszar zaznaczania o niestandardowym kształcie, to wystarczy algorytm testowania punkt vs wielokąt, albo prostokąt vs wielokąt. Algorytmy znajdziesz w sieci bez problemu.

Biorąc pod uwagę to, że prostokąt też jest wielokątem, jednego algorytmu możesz użyć do implementacji narzędzia zaznaczania z obszarem prostokątnym, obszarem w kształcie wielokąta (punkty osobno wyklikane przez użytkownika), a nawet narzędzia w stylu lasso (jak w MS Paint, czyli trzymasz LMB i ręcznie rysujesz obszar). Wszystko sprowadza się do listy punktów i testowania czy jakiś punkt (wierzchołek obiektu) znajduje się wewnątrz wielokąta opisanego tą listą punktów.

Algorytm testowania części wspólnej będzie jeden, a jedyne co będzie zaznaczania odróżniać to sposób podawania punktów wielokąta, czyli kwestia obsługi inputu i uzupełniania/modyfikowania listy wierzchołków wielokąta.

Chat GPT pomógł :

struct Triangle {
    sf::Vector2f a, b, c;
};

std::vector <sf::Vector2f> points;
std::vector <Triangle> triangles;

// Funkcja pomocnicza sprawdzająca, czy punkt P leży wewnątrz trójkąta ABC
bool isPointInTriangle(sf::Vector2f A, sf::Vector2f B, sf::Vector2f C, sf::Vector2f P) {
    float w1 = (A.x * (C.y - A.y) + (P.y - A.y) * (C.x - A.x) - P.x * (C.y - A.y)) /
        ((B.y - A.y) * (C.x - A.x) - (B.x - A.x) * (C.y - A.y));
    float w2 = (P.y - A.y - w1 * (B.y - A.y)) / (C.y - A.y);
    return w1 >= 0 && w2 >= 0 && (w1 + w2) <= 1;
}

// Funkcja sprawdzająca, czy trójkąt (A, B, C) jest uchem
bool isEar(const std::vector<sf::Vector2f>& vertices, int i, int prev, int next) {
    sf::Vector2f A = vertices[prev];
    sf::Vector2f B = vertices[i];
    sf::Vector2f C = vertices[next];

    // Sprawdź, czy trójkąt jest wypukły
    float crossProduct = (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
    if (crossProduct <= 0) return false; // Trójkąt jest wklęsły, nie jest uchem

    // Sprawdź, czy inne wierzchołki leżą wewnątrz trójkąta
    for (size_t j = 0; j < vertices.size(); j++) {
        if (j != i && j != prev && j != next && isPointInTriangle(A, B, C, vertices[j])) {
            return false; // Trójkąt zawiera inne wierzchołki, nie jest uchem
        }
    }
    return true; // Trójkąt jest uchem
}

// Funkcja do triangulacji wielokąta metodą Ear Clipping
std::vector<Triangle> triangulate(std::vector<sf::Vector2f>& vertices) {
    std::vector<Triangle> triangles;
    std::vector<int> indices(vertices.size());
    for (int i = 0; i < vertices.size(); i++) {
        indices[i] = i;
    }

    int n = vertices.size();
    while (n > 3) {
        bool earFound = false;

        for (int i = 0; i < n; i++) {
            int prev = (i + n - 1) % n;
            int next = (i + 1) % n;

            if (isEar(vertices, indices[i], indices[prev], indices[next])) {
                // Dodaj trójkąt do listy meshu
                triangles.push_back({ vertices[indices[prev]], vertices[indices[i]], vertices[indices[next]] });

                // Usuń ucho z listy
                indices.erase(indices.begin() + i);
                n--;
                earFound = true;
                break;
            }
        }

        // Jeśli nie znaleziono ucha, zakończ (uniknięcie nieskończonej pętli)
        if (!earFound) break;
    }

    // Dodaj ostatni pozostały trójkąt
    if (n == 3) {
        triangles.push_back({ vertices[indices[0]], vertices[indices[1]], vertices[indices[2]] });
    }

    return triangles;
}