C - Generare adiacenze

[XWolverineX]

Salve a tutti, vi chiedo una mano per elaborare un algoritmo.

Avvertenze - Non sono compiti di scuola, di università o cose di lavoro.
L'algoritmo serve semplicemente ad un'altra serie di algoritmi per elaborare, da un modello 3D, la sua silhouette(si scrive cosi?), per poi calcolarne l'ombra tramite una tecnica...bla bla...jada jada...

Avendo un array di UINT, contententi dei numeri interi, ove ogni 3 numeri interi formano un triangolo, dovrei elaborare un algoritmo che trovi le adiacenze del triangolo.
Un triangolo è adiacente ad un altro se hanno almeno un lato in comune.

Ogni triangolo ha massimo 3 adiacenze.


Dovrei quini cercare, per ogni tripla di indici, un'altra tripla che condivide almeno 2 indici.
Le dimensioni del buffer (già si sa), dovranno raddoppiare per conterene i nuovi dati.

Altra cosa pallosa è il contenere i dati nuovi.
Guardando l'immagine sopra, i dati dovranno essere contenuti in modo che, in ogni 6 posizioni dell'array, nelle posizioni pari ci siano i vertici originali del triangolo, nei dispari i 3 vertici delle adiacenze.

Io ci sto proprio perdendo la testa, ho abbozzato una specie di ciclo, ma non so proprio cosa scrivere dentro....

Avede un'idea anche solo teorica di come risolvere questo problema?

[XWolverineX]

lo so, è difficile

[XWolverineX]

Ho cominciato a scrivere del codice

void CMesh::GenerateAdjacency()
{
	UINT *pAdjacency = new UINT[2 * this->MeshData.ColladaBuffer.Indici];

	for (unsigned int i = 0; i < this->MeshData.ColladaBuffer.Indici; i++)
	{
		for (unsigned int z = 0; i < this->MeshData.ColladaBuffer.Indici; z++)
		{
			if ((this->MeshData.Indices[i] == this->MeshData.Indices[z]) && (this->MeshData.Indices[i+1] == this->MeshData.Indices[z+1]) && (this->MeshData.Indices[i+2] == this->MeshData.Indices[z+2]))
			{
				//Sto leggendo lo stesso indice, vai avanti.
				continue;	
			}
			else
			{
				if (this->MeshData.Indices[i] == this->MeshData.Indices[z])
				{
					if (this->MeshData.Indices[i+1] == this->MeshData.Indices[z+1])
					{
						//Edge
						continue;
					}

					if (this->MeshData.Indices[i+1] == this->MeshData.Indices[z+2])
					{
							//Edge
							continue;
					}			

					if (this->MeshData.Indices[i+2] == this->MeshData.Indices[z+1])
					{
						//Edge
						continue;
					}			
					
					if (this->MeshData.Indices[i+2] == this->MeshData.Indices[z+2])
					{
						//Edge
						continue;
					}			


				}

				if (this->MeshData.Indices[i+1] == this->MeshData.Indices[z])
				{
					if (this->MeshData.Indices[i+2] == this->MeshData.Indices[z+1])
					{
						//Edge
						continue;
					}

					if (this->MeshData.Indices[i+2] == this->MeshData.Indices[z+2])
					{
						//Edge
						continue;
					}			

					if (this->MeshData.Indices[i-1] == this->MeshData.Indices[z+1])
					{
						//Edge
						continue;
					}			

					if (this->MeshData.Indices[i-2] == this->MeshData.Indices[z+2])
					{
						//Edge
						continue;
					}			


				}


			}
		}
	}

	delete[] pAdjacency;
	}

La logica c'è, ma sembra che tutti quest if (che non sono ancora finiti) possano essere raggruppati in un unico ciclo for...che ne dite?

[Navimel]

guarda devi usare un grafo come struttura dati per rappresentare le adiacenze, altrimenti non ne esci piu, adesso non ho molto tempo ma ho degli esempi in C che puoi facilmente utilizzare.

una struttura base che ti puo andare bene puo essere questa:

typedef struct triangolo{

char *nome;
int visited; /*Per la visita sui triangoli...*/
struct lista_adiacenze * lista_adc; /*Lista di adiacenza del triangolo corrente*/

}triangolo;

typedef struct lista_adiacenze{
struct triangolo* adiacente; /*Il triangolo adiacente*/
struct lista_adiacenze* next; /*prossimo elemento nella lista di adiacenza*/
struct lista_adiacenze* prev; /*precedente elemento della lista di adiacenza*/
}lista_adiacenze;

http://it.wikipedia.org/wiki/Grafo


comunque ci sarebbe molto altro che si potrebbe fare per rendere il tutto piu veloce...questo è solo l'inizio

[Vincenzo1968]

Il calcolo combinatorio potrebbe essere d'aiuto:

#include <stdio.h>

typedef struct tagTriangle
{
	unsigned int a;
	unsigned int b;
	unsigned int c;
} Triangle;

void InitTriangleArray(int *p)
{
	p[0] = 0;
	p[1] = 2;
	p[2] = 4;

	p[3] = 0;
	p[4] = 1;
	p[5] = 2;

	p[6] = 2;
	p[7] = 4;
	p[8] = 3;

	p[9] = 4;
	p[10] = 5;
	p[11] = 0;
}

int Adiacenti(Triangle *p1, Triangle *p2)
{
	int k = 0;

	if ( (p1->a == p2->a) )
		k++;

	if ( (p1->a == p2->b) )
		k++;

	if ( (p1->a == p2->c) )
		k++;

	if ( (p1->b == p2->a) )
		k++;

	if ( (p1->b == p2->b) )
		k++;

	if ( (p1->b == p2->c) )
		k++;

	if ( (p1->c == p2->a) )
		k++;

	if ( (p1->c == p2->b) )
		k++;

	if ( (p1->c == p2->c) )
		k++;

	return k >= 2 ? 1 : 0;
}

int main()
{
	int k, y;
	Triangle T1, T2;

	unsigned int DimArray;
	unsigned int triangles[12];


	DimArray = (sizeof(triangles) / sizeof(triangles[0]));

	InitTriangleArray(triangles);

	k = 0;
	y = k + 3;
	while ( 1 )
	{
		if ( k == DimArray - 3 )
			break;

		T1.a = triangles[k];
		T1.b = triangles[k+1];
		T1.c = triangles[k+2];

		while ( 1 )
		{
			if ( y == DimArray )
				break;

			T2.a = triangles[y];
			T2.b = triangles[y+1];
			T2.c = triangles[y+2];	

			if ( Adiacenti(&T1, &T2) )
			{
			  printf("I triangoli (%d,%d,%d) e (%d,%d,%d) sono adiacenti\n",
				T1.a, T1.b, T1.c, T2.a, T2.b, T2.c);
			}
			else
			{
			  printf("I triangoli (%d,%d,%d) e (%d,%d,%d) non sono adiacenti\n",
				T1.a, T1.b, T1.c, T2.a, T2.b, T2.c);
			}

			y += 3;
		}

		k += 3;
		y = k + 3;
	}

	return 0;
}

[XWolverineX]

unsigned int i0, i1, i2;
	unsigned int j0, j1, j2;

	for(unsigned int i=0; i<this->MeshData.ColladaBuffer.Indici/3; i++)
	{
		i0 = this->MeshData.Indices[i*3+0];
		i1 = this->MeshData.Indices[i*3+1];
		i2 = this->MeshData.Indices[i*3+2];

		pAdj[i*6+0] = i0;
		pAdj[i*6+1] = 0xffffffff;
		pAdj[i*6+2] = i1;
		pAdj[i*6+3] = 0xffffffff;
		pAdj[i*6+4] = i2;
		pAdj[i*6+5] = 0xffffffff;
		for(unsigned int j=0; j<this->MeshData.ColladaBuffer.Indici/3; j++)
		{
			if( j != i ) // don't check a triangle against itself
			{
				j0 = this->MeshData.Indices[j*3+0];
				j1 = this->MeshData.Indices[j*3+1];
				j2 = this->MeshData.Indices[j*3+2];
				// check for i0 and i1
				if( j0 == i0 )
				{
					if(j1==i1) pAdj[i*6+1] = j2;
					else if(j2==i1) pAdj[i*6+1] = j1;
				} else if( j1==j0 )
				{
					if(j0==i1) pAdj[i*6+1] = j2;
					else if(j2==i1) pAdj[i*6+1] = j0;
				} else if( j2==i0 )
				{
					if(j0==i1) pAdj[i*6+1] = j1;
					else if(j1==i1) pAdj[i*6+1] = j0;
				}
				// check for i1 and i2
				if( j0 == i1 )
				{
					if(j1==i2) pAdj[i*6+3] = j2;
					else if(j2==i2) pAdj[i*6+3] = j1;
				} else if( j1==i1 )
				{
					if(j0==i2) pAdj[i*6+3] = j2;
					else if(j2==i2) pAdj[i*6+3] = j0;
				} else if( j2==i1 )
				{
					if(j0==i2) pAdj[i*6+3] = j1;
					else if(j1==i2) pAdj[i*6+3] = j0;
				}
				// check for i2 and i0
				if( j0 == i2 )
				{
					if(j1==i0) pAdj[i*6+5] = j2;
					else if(j2==i0) pAdj[i*6+5] = j1;
				} else if( j1==i2 )
				{
					if(j0==i0) pAdj[i*6+5] = j2;
					else if(j2==i0) pAdj[i*6+5] = j0;
				} else if( j2==i2 )
				{
					if(j0==i0) pAdj[i*6+5] = j1;
					else if(j1==i0) pAdj[i*6+5] = j0;
				}
			}
		}	
	}

	this->MeshData.ColladaBuffer.Indici *= 2;

Ma non sembra ancora funzionare bene.

La tua soluzione invece è interessante.
Come faresti poi, per mettere nell'elemento 5 l'indice di adiacenza tra 0 e 2 e cosi via?

[mondobimbi]

sembrerebbe che usi il C++, prova a vedere se questa soluzione è conforme al tuo problema

#include <iostream>

typedef unsigned int UINT;

class TRIANGOLO
{

	UINT vx1;
	UINT vx2;
	UINT vx3;

	bool condivideVertice1 (TRIANGOLO t) {
		return (vx1 == t.vx1) || (vx1 == t.vx2) || (vx1 == t.vx3) ;
	}

	bool condivideVertice2 (TRIANGOLO t) {
		return (vx2 == t.vx1) || (vx2 == t.vx2) || (vx2 == t.vx3) ;
	}

	bool condivideVertice3 (TRIANGOLO t) {
		return (vx3 == t.vx1) || (vx3 == t.vx2) || (vx3 == t.vx3) ;
	}

public :

	TRIANGOLO (UINT * vet) :
		vx1(vet[0]), vx2(vet[1]), vx3(vet[2]) {
		}

	bool isAdiacent (TRIANGOLO t) {
		// è adiacente se condivide due vertici
		if ( (condivideVertice1(t) && condivideVertice2(t)) || (condivideVertice1(t) && condivideVertice3(t)) || (condivideVertice2(t) && condivideVertice3(t)) )
			return true;
		else
			return false;		
	}

};

int main ()
{

	UINT vet[] = {0, 1, 2, 2, 3, 4, 0, 2, 4, 0, 4, 5};

	UINT n_element = sizeof( vet ) / sizeof(UINT) ;
	UINT n_triangle = n_element / 3 ;

	for (int i = 0; i < n_triangle - 1; ++i) {
		// punta all'i-esimo triangolo
		TRIANGOLO t = vet + i * 3 ;
		for (int j = i + 1; j < n_triangle; ++j) {
			TRIANGOLO t1 = vet + j * 3 ;
			if ( t.isAdiacent(t1) ) {
				std::cout << "Triangolo " << i << " adiacente con " << j << std::endl;
			}
		}
	}


	return (0);

}

[Vincenzo1968]

Originariamente inviato da XWolverineX
Come faresti poi, per mettere nell'elemento 5 l'indice di adiacenza tra 0 e 2 e cosi via?

Non ho capito bene cosa devi fare. Se ti riferisci a quello che hai scritto sopra:

Guardando l'immagine sopra, i dati dovranno essere contenuti in modo che, in ogni 6 posizioni dell'array, nelle posizioni pari ci siano i vertici originali del triangolo, nei dispari i 3 vertici delle adiacenze.

si potrebbe utilizzare una variabile di tipo int come contatore e una lista concatenata come questa:

typedef struct tagLista
{
	Triangle a;
	Triangle b;
	struct tagLista *next;
} Lista;

Nel ciclo while più interno, se i due triangoli sono adiacenti, invece di stampare il messaggio a video, li aggiungiamo in coda alla lista e incrementiamo di uno il contatore.
Alla fine, creiamo un array di interi dinamicamente(la dimensione è data dal valore della variabile contatore moltiplicato per sei) e, scorrendo la lista aggiungiamo i valori(prima quelli di Lista.a e poi quelli di Lista.b).

[mondobimbi]

scusate non ho visto che il thread era andato avanti
ciao
sergio

[GreyFox86]

Io ti consiglierei di cambiare la struttura dati, perchè se mantieni un semplice array di triangoli per trovare le adiacenze la complessità diventa lineare nel numero dei triangoli.
Io userei una struttura dati che ho visto in un corso universitario, che ti permette di fare diverse query in tempo lineare rispetto al numero di elementi coinvolti (decisamente meno del totale quindi):
Memorizzi due tipi di entità: vertici e triangoli.
Ogni vertice ha l'indice di uno dei triangoli incidenti e le coordinate.
Ogni triangolo ha il riferimento ai 3 vertici ed ai 3 triangoli adiacenti. Ordina i triangoli T1 T2 e T3 adiacenti in modo che T1 sia quello opposto al vertice V1, T2 opposto a V2, T3 opposto a V3.

Le relazioni che ti permettono di ottenere i vertici dal triangolo e i triangoli adiacenti dal triangolo sono memorizzate. Puoi inoltre recuperare in tempo lineare rispetto al numero di entità coinvolte sia i triangoli incidenti in un vertice, sia i vertici adiacenti ad un vertice.

Spero di aver capito più o meno quello che ti serviva e di averti dato uno spunto buono.


edit: dimenticavo, ricordati che devi anche avere una convenzione sull'ordine di salvataggio dei vertici (in senso orario, o antiorario).