Autor Wątek: kolizja odcinków w przestrzeni  (Przeczytany 8477 razy)

Offline kedan

  • Użytkownik

# Lipiec 25, 2006, 16:51:55
Czy ktoś wie jak sprawdzić czy istnieje punkt przecięcia dwóch odcinków w przestrzeni, i jak wyznaczyć jego  współrzędne?
Choć w sumie to chodzi raczej o metode śledzenia odległości między odcinkami.
Pomyslałem że można zrobić tak:
odcinek a [a1, a2]
odcinek b [b1 ,b2]

vec_a = a1 - a2
vec_b = b1 - b2

vec_t1 = a2 - b1
vec_t2 = a2 - b2

u = vec_a x vec_b
n = vect_t1 x vec_t2

float cos = (u * v)/(u.Length * v.Length)
if((1-fabs(cos))<TOLERANCE) { kolizja }

sęk w tym, że nawet jesli to zadziała to nie daje mi wspórzędnych punktu...
« Ostatnia zmiana: Lipiec 25, 2006, 17:30:56 wysłana przez kedan »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Lipiec 25, 2006, 17:09:20
Nie wiem, co piszesz, ale najprawdopodobniej kombinujesz coś nie tak. Z powodu zaokrągleń na FPU, odcinki najprawdopodobniej się nie przetną idealnie, więc musisz poszukać innego rozwiązania problemu, albo dopuścić pewien błąd (wykrywać kolizje "pogrubionych" odcinków). :)

Offline kedan

  • Użytkownik

# Lipiec 25, 2006, 17:16:24
oczywiście - rozumiem że nie dostane dokładnego punktu - starczy mi jakieś przybliżenie - tylko jak to osiągnąć?
podzielić odcinek na "ileśtam" sfer ograniczających o promieniu dr i sprawdzać "każda z każdą"?

metoda którą opisałem powyżej działa elegancko. Do szczęścia potrzebne mi są tylko współrzędne...
« Ostatnia zmiana: Lipiec 25, 2006, 17:30:37 wysłana przez kedan »

Offline gryzoń

  • Użytkownik

# Lipiec 25, 2006, 19:05:29
jeśli wiesz jak sie oblicza przecięcie prostej (reprezentowanej przez wektor) z płaszczyzną, to zrób sobie dowolną płaszczyznę na podstawie pierwszego wektora (współrzędne 3 punktu dowolne) i oblicz przecięcie z drugim wektorem - w połączeniu z twoim testem powinno działać

Offline Yarek

  • Użytkownik

# Lipiec 25, 2006, 21:21:50
Najpierw musisz sprawdzić czy dwa odcinki się przecinają:
#define SGN(x)       (((x) >= 0) ? 1 : -1)      // Dla: x>=0 zwraca 1, x<0 zwraca -1
#define SGNZ(x)      (((x) == 0) ? 0 : SGN(x))  // Dla: x==0 zwraca 0, x>0 zwraca 1, x<0 zwraca -1


double licz_wyznacznik(int a, int b, int c, int d, int e, int f, int g, int h, int i)
{
// Liczy wyznacznik dla:
// |a   b   c|
// |d   e   f|
// |g   h   i|
 return(a*e*i+b*f*g+d*h*c-c*e*g-b*d*i-f*h*a);
}
//------------------------------------------------------------------------------

bool przeciecie(int Ax, int Ay, int Bx, int By, int Cx, int Cy, int Dx, int Dy)
{
// Funkcja sprawdza czy odcinki AB i CD się przecinają
// Odcinki się przecinają gdy punkty A i B leżą po przeciwnej stronie odcinka CD
// i gdy punkty C i D leżą po przeciwnej stronie odcinka AB
//
// Pubnkty A i B leżą po przeciwnej stronie CD gdy (pseudokod):
// SGNZ( wyznacznik(C, D, A)) != SGNZ( wyzncznik(C, D, B))
//
// Pubnkty C i D leżą po przeciwnej stronie AB gdy:
// SGNZ( wyznacznik(A, B, C)) != SGNZ( wyzncznik(A, B, D))

if( SGNZ( licz_wyznacznik(Cx, Cy, 1, Dx, Dy, 1, Ax, Ay, 1)) != SGNZ( licz_wyznacznik(Cx, Cy, 1, Dx, Dy, 1, Bx, By, 1)))
if( SGNZ( licz_wyznacznik(Ax, Ay, 1, Bx, By, 1, Cx, Cy, 1)) != SGNZ( licz_wyznacznik(Ax, Ay, 1, Bx, By, 1, Dx, Dy, 1)))
    return(true);
else
    return(false);

}

Gdy się przecinają traktujesz obydwa odcinki jako proste i liczysz punkt przecięcia prostych (przypomne funkcje: y = ax+b ;) ).

Offline Reg

  • Administrator
    • Adam Sawicki - Home Page

# Lipiec 25, 2006, 21:31:49
Na pewno dzielenie na kawałki i sprawdzanie każdego z każdym to nie jest dobry pomysł :)

Mnie przychodzi do głowy coś takiego: Odcinek to fragment prostej, więc pewnie będzie tu do rozpatrzenia kilka przypadków. Trzebaby sprawdzić najpierw odległość między prostymi, a potem jakoś wyznaczyć, czy punkty na tych prostych, między którymi ta odległość wyszła leżą na tych odcinkach. Jeśli tak, to koniec, a jeśli nie, to sprawdzamy odległość do najbliższego temu punktowi końca takiego odcinka.

Offline gryzoń

  • Użytkownik

# Lipiec 25, 2006, 23:35:53
Gdy się przecinają traktujesz obydwa odcinki jako proste i liczysz punkt przecięcia prostych (przypomne funkcje: y = ax+b ;) ).

y = ax + b to raczej dla 2 wymiarów, a jak to będzie dla 3?

poza tym trzeba chyba jakiś układ równań rozwiązać w tej metodzie

Wydaje mi sie że mój pomysł ma pare zalet, bo zawsze nam wyliczy jakiś punkt, więc nie trzeba się martwić o niedokładności obliczeń, no chyba że zrobimy płaszczyznę równoległą do drugiego odcinka (szczególny przypadek), poza tym powinno działać, bo wyobraźcie sobie płaszczyznę obracaną wokół osi (którą jest pierwszy odcinek), nieważne jak ta płaszczyzna jest obrócona, jeżeli tylko drugi odcinek przecina się z pierwszym (osią) to pozostaje nam tylko wyliczenie punktu. Pozostaje kwestia stwierdzenia czy odcinki rzeczywiście się przecinają. Można to na przykład stwierdzić sprawdzając odległości między p1 pierwszego odcinka z pkt przecięcia i p2 pierwszego odcinka również z pkt przecięcia, jeśli suma tych odległości jest w przybliżeniu równa odległości między p1 i p2 to odcinki się przecinają. Można też sprawdzać kąty, albo inaczej wykombinować

co o tym myślicie?? ciekaw jestem czy dobrze myśle

ps. poprzednio miałem na myśli odcinki a nie wektory
« Ostatnia zmiana: Lipiec 25, 2006, 23:38:50 wysłana przez gryzoń »

Offline Spider100

  • Moderator
    • Strona domowa

# Lipiec 25, 2006, 23:55:19
Witam !

http://www.partow.net/projects/fastgeo/index.html
Proponuje przejrzeć źródła i po kłopocie test przecięcia odcinków w 2d i 3d rozwiązany (nawet znajdujemy odległość między nimi).
Dla mniej spostrzegawczych dodam że jak zwykle w kolizjach chodzi o rzutowanie :).
Druga metoda która przychodzi na myśl to zabawa z osiami separacji (tylko że nie warto pisac całego algorytmu dla testu odcinków choć pewnie działałoby to szybko) tzw. metoda SAT na googlach można wyszukać trochę o tym wiec odsyłam :).

Pozdrawiam !
Spider ^*^

Offline kedan

  • Użytkownik

# Lipiec 26, 2006, 00:20:09
Mnie osobiście najbardziej podoba się metoda gryzonia, choć szczerze mówiąc to nie wiem jak sie zabrać do wyznaczenia tego punktu.
W tablicach znalazłem coś takiego (punkt przecięcia prostej z płaszczyzną):

x0 = x1 - p*s
y0 = y1 - r*s
z0 = z1 - q*s

s = (Ax1 + By1 + Cz1 + D)/(A*p + B*q + c*r)

gdzie, jak mniemam x1, y1, z1 to współrzędne dowolnego punktu na płaszczyźnie , R[p,q,r] to wektor równoległy do prostej.
A, B, C, D wyznacze sobie z postaci trójpunktowej płaszczyzny (policzyć wyznacznik, pogrupować i coś powinno z tego wyjść).

Dzięki Spider za linka - na pewno się przyda. Obawiam się jednak że zapoznawanie się z tym zajęłoby mi więcej czasu niż wymyślanie "swojej" metody a czasu to niestety nie mam ;)
Próbowałem się już bawić z rzutowaniem i najmniejszą odległością dwóch prostych, ale nie wyszło...
« Ostatnia zmiana: Lipiec 26, 2006, 00:31:22 wysłana przez kedan »

Offline yorp

  • Użytkownik
    • ProfessionGG Project

# Lipiec 26, 2006, 00:24:22
rozwiazanie jest bardzo proste:
zakladasz ze odcinek to poruszajacy sie pkt w przestrzeni i ukladasz sobie rownanie

P1 + a*V1 = Pp

i dla drugiej prostej

P3 + b*V2 = Pp

gdzie P1 i P3 to poczatki odcinkow, V1 i V2 to odcinki zapisane za pomoca wektorow ( P2 - P1 jesli P2 i P1 to konce odcinkow), a i b to skalar.. rozdzielasz to teraz na uklad x i y i dostajesz takie cos

P1x + a*V1x = P3x + b*V2x
P1y + a*V1y = P3y + b*V2y

teraz wystarczy rozwiazac uklad rownan (sprowadz go najlepiej do postac gdzie po lewej stronie jest w pierwszym rownaniu a i w drugim rownaniu b) i gotowe.. jesli liczba a i b sa z przedzialu <0,1> to jest kolizja, a jak policzyc punkt przeciecia juz powinies wiedziec

Pozdrawiam, Krzysiek

//EDIT: aha jak masz 3 wymiary to musisz zrobic to rowniez dla z i bedziesz mial 3 rownania wszystkie skalary musza byc w zakresie <0, 1> -- maly edit, nawiasy <, > sa umowne ;)

//EDIT2: mozesz zanim zaczniesz liczyc sprawdzic czy odcinek sie tnie za pomoca tego wyznacznika ktory podal Yarek... przyspieszysz troche algorytm - w wiekszosci sytuacji odcinki sie nie przecinaja ;)

//EDIT3: stosowanie y=ax + b odradzam wykrzaczy sie jak odcinki beda szly rownolegle do osi y, lepiej uzyc rownania prostej Ax + By + Cz = D
« Ostatnia zmiana: Lipiec 26, 2006, 00:31:21 wysłana przez Yunior^Pro »

Offline gryzoń

  • Użytkownik

# Lipiec 26, 2006, 00:43:17
szczerze mówiąc to nie wiem jak sie zabrać do wyznaczenia tego punktu

wkleję Ci gotowca (OpenGL programowanie gier :))

class CVector
{
public:
    scalar_t x;
    scalar_t y;
    scalar_t z;    // składowe x,y,z

public:
    // konstruktor
    CVector(scalar_t a = 0, scalar_t b = 0, scalar_t c = 0) : x(a), y(b), z(c)
    {}
    CVector(const CVector &vec) : x(vec.x), y(vec.y), z(vec.z)
    {}

    // podstawienie wektora
    const CVector &operator=(const CVector &vec)
    {
        x = vec.x;
        y = vec.y;
        z = vec.z;

        return *this;
    }

    // równość wektorów
    const bool operator==(const CVector &vec) const
    {
        return ((x == vec.x) && (y == vec.y) && (z == vec.z));
    }

    // nierówność wektorów
    const bool operator!=(const CVector &vec) const
    {
        return !(*this == vec);
    }

    // dodawanie wektorów
    const CVector operator+(const CVector &vec) const
    {
        return CVector(x + vec.x, y + vec.y, z + vec.z);
    }

    // dodawanie wektorów
    const CVector operator+() const
    {
        return CVector(*this);
    }

    // dodawanie wektorów
    const CVector& operator+=(const CVector& vec)
    {
        x += vec.x;
        y += vec.y;
        z += vec.z;
        return *this;
    }

    // odejmowanie wektorów
    const CVector operator-(const CVector& vec) const
    {
        return CVector(x - vec.x, y - vec.y, z - vec.z);
    }

    // odejmowanie wektorów
    const CVector operator-() const
    {
        return CVector(-x, -y, -z);
    }

    // odejmowanie wektorów
    const CVector &operator-=(const CVector& vec)
    {
        x -= vec.x;
        y -= vec.y;
        z -= vec.z;

        return *this;
    }

    // mnożenie wektora przez skalar
    const CVector &operator*=(const scalar_t &s)
    {
        x *= s;
        y *= s;
        z *= s;

        return *this;
    }

    // dzielenie wektora przez skalar
    const CVector &operator/=(const scalar_t &s)
    {
        const float recip = 1/s; // dla efektywności

        x *= recip;
        y *= recip;
        z *= recip;

        return *this;
    }

    // mnożenie wektora przez skalar
    const CVector operator*(const scalar_t &s) const
    {
        return CVector(x*s, y*s, z*s);
    }

    // mnożenie wektora przez skalar
    friend inline const CVector operator*(const scalar_t &s, const CVector &vec)
    {
        return vec*s;
    }

    */   // dzielenie wektora przez skalar
    const CVector operator/(scalar_t s) const
    {
        s = 1/s;

        return CVector(s*x, s*y, s*z);
    }

    // iloczyn wektorowy
    const CVector CrossProduct(const CVector &vec) const
    {
        return CVector(y*vec.z - z*vec.y, z*vec.x - x*vec.z, x*vec.y - y*vec.x);
    }

    // iloczyn wektorowy
    const CVector operator^(const CVector &vec) const
    {
        return CVector(y*vec.z - z*vec.y, z*vec.x - x*vec.z, x*vec.y - y*vec.x);
    }

    // iloczyn skalarny
    const scalar_t DotProduct(const CVector &vec) const
    {
        return x*vec.x + y*vec.y + z*vec.z;
    }

    // iloczyn skalarny
    const scalar_t operator%(const CVector &vec) const
    {
        return x*vec.x + y*vec.y + z*vec.z;
    }


    // długość wektora
    const scalar_t Length() const
    {
        return (scalar_t)sqrt((double)(x*x + y*y + z*z));
    }

    // wektor jednostkowy
    const CVector UnitVector() const
    {
        return (*this) / Length();
    }

    // normalizacja wektora
    void Normalize()
    {
        (*this) /= Length();
    }

    // operator modułu (długości) wektora
    const scalar_t operator!() const
    {
        return sqrtf(x*x + y*y + z*z);
    }

    // zmienia długość wektora
    const CVector operator | (const scalar_t length) const
    {
        return *this * (length / !(*this));
    }

    // zmienia długość wektora
    const CVector& operator |= (const float length)
    {
        return *this = *this | length;
    }

    // zwraca kąt, który tworzą wektory
    const float inline Angle(const CVector& normal) const
    {
        return acosf(*this % normal);
    }

    // tworzy odbicie wektora względem powierzchni zdefiniowanej przez normalną
    const CVector inline Reflection(const CVector& normal) const
    {
        const CVector vec(*this | 1);     // normalizuje wektor
        return (vec - normal * 2.0 * (vec % normal)) * !*this;
    }
};


class CPlane
{
public:
    CVector N;      // wektor normalny do płaszczyzny
    double  D;      // stała przesunięcia płaszczyzny

    // konstruktory

    // Ax + By + Cz - D = 0
    CPlane(double a = 1, double b = 0, double c = 0, double d = 0)
    {
        N = CVector(a, b, c);
        D = d;
    }

    // tworzy obiekt płaszczyzny na podstawie wektora normalnego
    // i stałej przesunięcia płaszczyzny D=d
    CPlane(const CVector& normal, double d = 0)
    {
        N = normal;
        D = d;
    }

    // tworzy kopię obiektu płaszczyzny plane
    CPlane(const CPlane& plane)
    {
        N = plane.N;
        D = plane.D;
    }

    // tworzy obiekt płaszczyzny na podstawie współrzędnych trzech jej punktów
    CPlane(const CVector& vertexA, const CVector& vertexB, const CVector& vertexC)
    {
        CVector normalA((vertexC - vertexA) | 1.0);  // wektor normalny jednostkowy C - A
        CVector normalB((vertexC - vertexB) | 1.0);  // wektor normalny jednostkowy C - B

        N = (normalA ^ normalB) | 1.0;    // normalizuje iloczyn skalarny
        D = -vertexA % N;                 // wyznacza odległość
    }

    // operator podstawienia
    const CPlane& operator=(const CPlane& plane)
    {
        N = plane.N;
        D = plane.D;

        return *this;
    }

    // operator porównania
    const bool operator==(const CPlane& plane) const
    {
        return N == plane.N && D == plane.D;
    }

    // operator porównania
    const bool operator!=(const CPlane& plane) const
    {
        return !(*this == plane);
    }

    // sprawdza, czy punkt point leży na płaszczyźnie
    const bool inline PointOnPlane(const CVector& point) const
    {
        return DistanceToPlane(point) == 0;
    }

    // zwraca odległość punktu od płaszczyzny
    const double inline DistanceToPlane(const CVector& point) const
    {
        return N % point + D;
    }

    // zwraca punkt przecięcia płaszczyzny przez promień
    const CVector inline RayIntersection(const CVector& rayPos, const CVector& rayDir) const
    {
        const double a = N % rayDir;
        if (a == 0)
            return rayPos;     // promień jest równoległy do płaszczyzny

        return rayPos - rayDir * (DistanceToPlane(rayPos) / a);
    }
};


z tym że do RayIntersection podajesz nie wsp. początku i końca odcinka, ale początek odcinka i wektor skierowany na koniec odcinka

Offline kedan

  • Użytkownik

# Lipiec 26, 2006, 00:49:26
fantastycznie :D
Gryzoń masz u mnie piwo :)

Offline gryzoń

  • Użytkownik

# Lipiec 26, 2006, 00:52:30
trzymam za słowo

Offline kedan

  • Użytkownik

# Lipiec 26, 2006, 21:05:27
dla dwóch odcinków metoda działa.
Dla dwóch sześcianów opisanych odcinkami już nie..
no i kibel...

---------------------------------------------------------------------

fajne rozwiązanie znalazłem tutaj:
http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline3d/

« Ostatnia zmiana: Maj 10, 2007, 21:24:58 wysłana przez kedan »