Triangle - Teste Intersection Triangle

Question

Eu gostaria de saber se existe aí algum tutorial ou guia para compreender e implementar um teste de intersecção Triângulo Triângulo em um ambiente 3D. (I não precisa saber preciso onde a intersecção aconteceu, mas apenas que uma interseção ocorreu)

Eu estava indo para implementá-lo seguindo um pdf teórico, mas estou muito preso no

1. equação do plano Compute do triângulo 2.
2. Rejeitar tão trivial se todos os pontos de triângulo 1 estão no mesmo lado.
3. equação do plano Compute do triângulo 1.
4. Rejeitar tão trivial se todos os pontos de triângulo 2 estão no mesmo lado.
5. Compute linha de intersecção e projeto para maior eixo.
6. Compute os intervalos para cada triângulo.
7. Intersect os intervalos.

ponto 5 deste guia. Eu realmente não sei o que está pedindo (todo 5,6 e 7). XD

Como eu não tenho conhecimento elevado em matemática, por favor tente ser o mais simples possível com (bem, eu sei, tanto o casal de exames na universidade me (eu sou um XD programador raw) dado) mim. : D (eu tentei procurar no google, mas a maioria dos links apontam para algumas 4-5 páginas cheias de fórmulas I realmente não me importo de saber e eu não entendo.)

Obrigado pela ajuda

Answer 1

Você disse:

Eu gostaria de saber se existe lá fora algum tutorial ou guia para entender e implementar um triângulo Triângulo teste de interseção em um ambiente 3D.

E então você disse:

A maioria dos links apontam para alguns 4-5 páginas cheio de fórmulas eu realmente não cuidado de saber

Faço notar que essas duas declarações totalmente contraditórias. Então, qual é? Você quer entender como funciona interseção triângulo de triângulo, ou você só quer uma implementação que funciona, mas você não entende isso?

Não é como se todas as páginas web estão cheios de desnecessário de matemática. Toda a matemática é necessário para a compreensão de como o algoritmo de intersecção funciona. Comece no início e aprender como tudo funciona.

As etapas 5, 6 e 7 são simples de entender uma vez que você sabe o que as palavras significam. A linha de intersecção é a linha feita pela intersecção dos dois planos. Cada triângulo encontra-se em um avião. Existem três casos:

• os aviões são paralelos e não se cruzam. Os triângulos, obviamente, não se cruzam.
• os aviões estão no mesmo plano. Os triângulos pode atender ou não.
• os aviões são dois planos diferentes que se encontram em uma linha. Se os triângulos se cruzam, eles obviamente deve se cruzam nessa linha.

Suponha que estamos no terceiro caso. Calcula-se o segmento da linha de intersecção que está contida no primeiro triângulo. Calcula-se o segmento da linha de intersecção que é na segunda triângulo. A questão agora é "fazer esses segmentos se sobrepõem?"

Você pode resolver isso projetando os segmentos em um eixo conveniente, e ver se os segmentos de linha em que se sobrepõem eixo. Basicamente, funciona assim: imagine que você está brilhando uma luz sobre os segmentos de linha, de modo que suas sombras cair sobre um eixo. Se as sombras na intersecção do eixo, em seguida, os segmentos de linha devem se cruzar. Se existe uma diferença entre as sombras sobre o eixo, em seguida, claramente que deve haver um intervalo entre os segmentos de linha, e, por conseguinte, os triângulos não se intersectam.

Se você quiser entender como isso funciona, então não há como contornar o fato de que você está indo para necessidade de compreender todas este material - toda a álgebra que funciona como os aviões cruzam e como os projetos para um trabalho eixo. É tudo necessário. E tudo isso é blocos básicos de construção dos quais transformações mais complexas, projeções, e assim por diante, será construído, então compreender os conceitos básicos bem se você quiser ir mais longe.

Answer 2

A minha resposta é simples ... este problema é difícil em uma arbitrária sistema de coordenadas, então mudar para algo que faz com que o problema fácil. A classe Matrix em XNA tem uma função CreateLookAt que pode ser usado para criar uma transformação útil em todos os vértices.

O exemplo a seguir não é otimizado, está escrito apenas para a compreensão da solução. As excepções e seus correspondentes instruções IF podem ser removidos, juntamente com algumas transformações do vector.

    public static bool CheckColision(Vector3 t1a, Vector3 t1b, Vector3 t1c, Vector3 t2a, Vector3 t2b, Vector3 t2c)
    {//rotates each edge of the first triangle to the Z axis and checks the second triangle against it then repeats with the second one against the first, and lastly checks to see if all points of the second triangle are on the same side as the first
        if(! CheckColisionLookAt(t1a, t1b, t1c, t2a, t2b, t2c))
            return false;
        if (!CheckColisionLookAt(t1b, t1c, t1a, t2a, t2b, t2c))
            return false;
        if (!CheckColisionLookAt(t1c, t1a, t1b, t2a, t2b, t2c))
            return false;

        if (!CheckColisionLookAt(t2a, t2b, t2c, t1a, t1b, t1c))
            return false;
        if (!CheckColisionLookAt(t2b, t2c, t2a, t1a, t1b, t1c))
            return false;
        if (!CheckColisionLookAt(t2c, t2a, t2b, t1a, t1b, t1c))
            return false;

        return CheckColisionAllOnOneSide(t1a, t1b, t1c, t2a, t2b, t2c);
    }

    public static bool CheckColisionAllOnOneSide(Vector3 t1a, Vector3 t1b, Vector3 t1c, Vector3 t2a, Vector3 t2b, Vector3 t2c)
    {//simply performs a transformation to check if all points on one triangle are on the same side of the other triangle
        Matrix m = Matrix.CreateLookAt(t1a, t1b, t1c - t1a);
        t2a = Vector3.Transform(t2a, m);
        t2b = Vector3.Transform(t2b, m);
        t2c = Vector3.Transform(t2c, m);
        if (t2a.X < 0 && t2b.X < 0 && t2c.X < 0)
            return false;
        if (0 < t2a.X && 0 < t2b.X && 0 < t2c.X)
            return false;
        return true;
    }

    public static bool CheckColisionLookAt(Vector3 t1a, Vector3 t1b, Vector3 t1c, Vector3 t2a, Vector3 t2b, Vector3 t2c)
    {//performs a transformation and checks if all points of the one triangle are under the other triangle after the transformation

        Matrix m = Matrix.CreateLookAt(t1a, t1b, t1c - t1a);
        t1a = Vector3.Transform(t1a, m);//  (0,     0,      0)
        if ( ZERRO < Math.Abs(t1a.X)|| ZERRO < Math.Abs(t1a.Y) || ZERRO < Math.Abs(t1a.Z))
            throw new Exception();
        t1b = Vector3.Transform(t1b, m);//  (0,     0,      maxZ)
        if (ZERRO < Math.Abs(t1a.X) || ZERRO < Math.Abs(t1a.Y))
            throw new Exception();
        t1c = Vector3.Transform(t1c, m);//  (0,     maxY,   someZ)
        if (ZERRO < Math.Abs(t1a.X))
            throw new Exception();
        t2a = Vector3.Transform(t2a, m);
        t2b = Vector3.Transform(t2b, m);
        t2c = Vector3.Transform(t2c, m);
        if (t2a.Y < 0 && t2b.Y < 0 && t2c.Y < 0)
            return false;
        return true;
    }

Answer 3

Aqui está um site que contém referências a uma série de cruzamentos:

Real-Time Rendering Objeto / Objeto Intersection Página

Aqui está o que eles lista para Tri / Tri:

Möller JGT 2 (2) ;
JGT Held 2 (4) ;
GTweb ;
Möller ;
GPG p.393;
GTCG p.539;
TGS ;
RTCD p.155,172;
Shen JGT 8 (1) ;
Guigue JGT 8 (1) ;
SoftSurfer ;
real-Time Rendering , 2nd Edition p.590;
real-Time Rendering, terceira edição p.757

Answer 4

Eu suponho que você tem o x, y coordenadas para os vértices do triângulo. eg.
para Triangle A:
1. Side A1: xa1, YA1 2. Side A2: xa2, ya2 3. Side A3: XA3, ya3 para Triangle B:
1. Side B1: XB1, YB1 B2 2. Side: XB2, YB2 B3 3. Side: XB3, Yb3

Os triângulos cruzam se qualquer combinação de suas linhas intercect. Ou seja, se intersecta A1 B1 ou B2 ou B3, ou se intersecta A2 B1 ou B2 ou B3, ou se intersecta A3 B1 ou B2 ou B3.

Então, você precisa o algoritmo que decects se duas linhas se cruzam. Aqui está o exemplo mais fácil que eu encontrei: http://www.mathopenref.com/coordintersection.html

Answer 5

O método que você postou parece que ele está usando algo semelhante a este algoritmo para detectar se polígono convexo se cruzam, com base no Axis Teorema de separação. Não é muito difícil de entender.

Se uma linha, chamada de eixo de separação, pode ser estabelecida entre dois polígonos, eles não se cruzam. Cada extremidade de cada polígono é um eixo de separação candidato. Os polígonos são projectadas sobre um vector perpendicular a esse eixo, e as extensões 1D são testados para sobreposição. Se não há sobreposição 1D, a borda de corrente é um eixo que separa os dois polígonos e não se intersectam. Se houver 1D sobreposição, os resultados são inconclusivos até que todas as bordas candidatos foram testados, momento em que conclui-se que os dois polígonos se cruzam. Note-se que dois polígonos são permitidos para compartilhar uma borda.