C++ - Codice estremamente lento

**XWolverineX** · 26-04-2008, 14:35

Salve a tutti.
Ho un pezzo di codice che non mi convince per niente.
Ho scritto una funzione che, da un array di floats contenente un VertexBuffer, rimuove tutti i duplicati e genera un IndexBuffer adeguato.

Per chi non lo sapesse, il VertexBuffer è un array di float che contiene informazioni sui vertici di una geometria (Posizione, Normali, Coordinate di Texture) e l'indexBuffer un arrai di indici.

Ora io ho un array di float con diversi vertici, tra i quali ci sono duplicati. Per diminuire il consumo di memoria, si usa creare un index buffer: ossia eliminare tutti i duplicati dal vertex buffer e segnare sull'indexbuffer la posizione dei vertici.
Così, invece di avere un quadrato formato da 6 vertici

A-B-C & A-C-D

Basterà avere un vertex buffer
ABCD e un Indexbuffer
0-1-2-0-2-3

Ho scritto questa funzione,che richiede però oltre 18 secondi, un tempo inammissibile, mentre di solito l'operazione viene effettuata a runtime in un paio di secondi.

codice:

		std::vector<float> OrigVertices;
		std::vector<float> NewVertices;

	std::vector<unsigned int> OptIndices;

	for (UINT i = 0; i < this->ColladaBuffer.Indici;i++)
	{
		Indices[i] = i;
	}

	OptIndices.insert(OptIndices.begin(),Indices,Indices + this->ColladaBuffer.Indici);
	OrigVertices.insert(OrigVertices.begin(),buffer,buffer + bufsize);
	NewVertices.insert(NewVertices.begin(),OrigVertices.begin(),OrigVertices.begin() + 9);


	{
		D3DVECTOR Vx,Nx,Tx;
		D3DVECTOR VxN,NxN,TxN;

		int OrigVertIdx, NewVertIdx;

		bool DuplicateV;

		for (int i = 9; i < (OrigVertices.size());i += 9)
		{
			OrigVertIdx = i/9;

			Vx.x = OrigVertices[i];
			Vx.y = OrigVertices[i+1];
			Vx.z = OrigVertices[i+2];
			Nx.x = OrigVertices[i+3];
			Nx.y = OrigVertices[i+4];
			Nx.z = OrigVertices[i+5];
			Tx.x = OrigVertices[i+6];
			Tx.y = OrigVertices[i+7];
			Tx.z = OrigVertices[i+8];

			DuplicateV = false;

			for (int j = 0; j < (NewVertices.size());j +=9 )
			{
				VxN.x = NewVertices[j];
				VxN.y = NewVertices[j+1];
				VxN.z = NewVertices[j+2];
				NxN.x = NewVertices[j+3];
				NxN.y = NewVertices[j+4];
				NxN.z = NewVertices[j+5];
				TxN.x = NewVertices[j+6];
				TxN.y = NewVertices[j+7];
				TxN.z = NewVertices[j+8];

				if (fabs(Vx.x-VxN.x) < Epsilon && fabs(Vx.y-VxN.y) < Epsilon && fabs(Vx.z-VxN.z) < Epsilon)
				{
					NewVertIdx = j/9;
					OptIndices[OrigVertIdx] = NewVertIdx;
					DuplicateV = true;

					break;
				}
			}

			if (!DuplicateV)
			{
				NewVertIdx = (NewVertices.size())/9;
				NewVertices.push_back(Vx.x);
				NewVertices.push_back(Vx.y);
				NewVertices.push_back(Vx.z);
				NewVertices.push_back(Nx.x);
				NewVertices.push_back(Nx.y);
				NewVertices.push_back(Nx.z);
				NewVertices.push_back(Tx.x);
				NewVertices.push_back(Tx.y);
				NewVertices.push_back(Tx.z);
				OptIndices[OrigVertIdx] = NewVertIdx ;
			}
		}
	}

Sapreste come ottimizzarla in modo estremo?

**shodan** · 26-04-2008, 16:31

Una prima ottimizzazione che farei è questa. (Però non credo sia quella la causa.)

codice:

        // qui si costuisce il vector lungo quanto serve.
	std::vector<unsigned int> OptIndices(this->ColladaBuffer.Indici);
	for (UINT i = 0; i < this->ColladaBuffer.Indici;i++)
	{
		OptIndices[i] = i;
	}

        // qui in fase di dichiarazione si creano i due vector necessari, 
        // risparmiando l'operazione di insert

	std::vector<float> OrigVertices(buffer,buffer + bufsize);
	std::vector<float> NewVertices(OrigVertices.begin(),OrigVertices.begin() + 9);

	{
		D3DVECTOR Vx,Nx,Tx;
		D3DVECTOR VxN,NxN,TxN;

		int OrigVertIdx, NewVertIdx;

		bool DuplicateV;
	
                // si calcola una volta sola la lunghezza e non ad ogni ciclo.
		int OrigVertSize = OrigVertices.size();
		for (int i = 9; i < OrigVertSize;i += 9)
		{
			OrigVertIdx = i/9;

			Vx.x = OrigVertices[i];
			Vx.y = OrigVertices[i+1];
			Vx.z = OrigVertices[i+2];
			Nx.x = OrigVertices[i+3];
			Nx.y = OrigVertices[i+4];
			Nx.z = OrigVertices[i+5];
			Tx.x = OrigVertices[i+6];
			Tx.y = OrigVertices[i+7];
			Tx.z = OrigVertices[i+8];

			DuplicateV = false;

                        // si calcola una volta sola la lunghezza e non ad ogni ciclo.
			int NewVertSize = NewVertices.size(); 
			for (int j = 0; j < NewVertSize;j +=9 )
			{
				VxN.x = NewVertices[j];
				VxN.y = NewVertices[j+1];
				VxN.z = NewVertices[j+2];
				NxN.x = NewVertices[j+3];
				NxN.y = NewVertices[j+4];
				NxN.z = NewVertices[j+5];
				TxN.x = NewVertices[j+6];
				TxN.y = NewVertices[j+7];
				TxN.z = NewVertices[j+8];

                                // mi sballava l'identazione :)
				if (fabs(Vx.x-VxN.x) < Epsilon && 
                                    fabs(Vx.y-VxN.y) < Epsilon && 
                                    fabs(Vx.z-VxN.z) < Epsilon)
				{
					NewVertIdx = j/9;
					OptIndices[OrigVertIdx] = NewVertIdx;
					DuplicateV = true;

					break;
				}
			}

			if (!DuplicateV)
			{
				NewVertIdx = NewVertSize/9;
				NewVertices.push_back(Vx.x);
				NewVertices.push_back(Vx.y);
				NewVertices.push_back(Vx.z);
				NewVertices.push_back(Nx.x);
				NewVertices.push_back(Nx.y);
				NewVertices.push_back(Nx.z);
				NewVertices.push_back(Tx.x);
				NewVertices.push_back(Tx.y);
				NewVertices.push_back(Tx.z);
				OptIndices[OrigVertIdx] = NewVertIdx ;
			}
		}
	}

**MacApp** · 26-04-2008, 16:39

Posta codice compilabile ;-)

**XWolverineX** · 26-04-2008, 17:17

L'ottimizzazione proposta è senza dubbio buona (questa, accoppiata ad una mia precedente, mi hanno fatto guadagnare ben 0.5 secondi

)

Io penso di aver strutturato proprio male l'algoritmo, per questo cercavo una soluzione.

Un mio amico, addirittura usando le list del .NET e C#, sostiene che a lui ci mette 2 secondi, e con valore di Epsilon ancor piu' piccolo del mio(0.5 mio contro 0.001, che vuol dire cicli ancor piu' lunghi): ecco da dove nasce il mio dubbio.
Cercherò di sgraffignarmi il suo codice,intanto se avete idee....

**MacApp** · 26-04-2008, 17:27

Se postassi del codice compilabile, le probabilità che qualche anima pia possa cercare di risolvere il tuo problema aumenterebbero di molto, non credi?

I test li fai in modalità debug o ottimizzata e a che livello d'ottimizzazione?

**XWolverineX** · 26-04-2008, 19:21

E' difficile dare codice compilabile, poichè dovrei anche darvi un file con un enorme elenco di vertici, nessun problema per me.

Sto compilando in modalità debug ( e lo fa anche lui)
Cercherò di postare una prova completa e un file da importare di esempio.

**XWolverineX** · 26-04-2008, 19:32

Ecco fatto, si è mosso qualcosa.
Ho caricato in un file .txt con un intero modello al suo interno, eccolo numeri qui
Attenzione è grosso, 1,4 mega circa
Il file è formato da svariati numeri, ogni 9 numeri è un vertice completo (3 numeri per la posizione, 3 per la normale, 3 per le coordinate di texture).

Dovete semplicemente caricarlo in un grosso array di float, e poi provare questo codice

codice:

#include <vector>
const unsigned int Indici = 13992;

UINT *Indices = new UINT[Indici];

//Creazione IndexBuffer

if (Epsilon != 0.0f)
{
		std::vector<float> OrigVertices;
		std::vector<float> NewVertices;

	std::vector<unsigned int> OptIndices;

	for (UINT i = 0; i < Indici;i++)
	{
		Indices[i] = i;
	}

	OptIndices.insert(OptIndices.begin(),Indices,Indices + this->ColladaBuffer.Indici);
	OrigVertices.insert(OrigVertices.begin(),buffer,buffer + bufsize);
	NewVertices.insert(NewVertices.begin(),OrigVertices.begin(),OrigVertices.begin() + 9);


	{
		D3DVECTOR Vx,Nx,Tx;
		D3DVECTOR VxN,NxN,TxN;

		int OrigVertIdx, NewVertIdx;

		bool DuplicateV;

		for (int i = 9; i < (OrigVertices.size());i += 9)
		{
			OrigVertIdx = i/9;

			Vx.x = OrigVertices[i];
			Vx.y = OrigVertices[i+1];
			Vx.z = OrigVertices[i+2];
			Nx.x = OrigVertices[i+3];
			Nx.y = OrigVertices[i+4];
			Nx.z = OrigVertices[i+5];
			Tx.x = OrigVertices[i+6];
			Tx.y = OrigVertices[i+7];
			Tx.z = OrigVertices[i+8];

			DuplicateV = false;

			for (int j = 0; j < (NewVertices.size());j +=9 )
			{
				VxN.x = NewVertices[j];
				VxN.y = NewVertices[j+1];
				VxN.z = NewVertices[j+2];
				NxN.x = NewVertices[j+3];
				NxN.y = NewVertices[j+4];
				NxN.z = NewVertices[j+5];
				TxN.x = NewVertices[j+6];
				TxN.y = NewVertices[j+7];
				TxN.z = NewVertices[j+8];

				if (fabs(Vx.x-VxN.x) < Epsilon && fabs(Vx.y-VxN.y) < Epsilon && fabs(Vx.z-VxN.z) < Epsilon)
				{
					NewVertIdx = j/9;
					OptIndices[OrigVertIdx] = NewVertIdx;
					DuplicateV = true;

					break;
				}
			}

			if (!DuplicateV)
			{
				NewVertIdx = (NewVertices.size())/9;
				NewVertices.push_back(Vx.x);
				NewVertices.push_back(Vx.y);
				NewVertices.push_back(Vx.z);
				NewVertices.push_back(Nx.x);
				NewVertices.push_back(Nx.y);
				NewVertices.push_back(Nx.z);
				NewVertices.push_back(Tx.x);
				NewVertices.push_back(Tx.y);
				NewVertices.push_back(Tx.z);
				OptIndices[OrigVertIdx] = NewVertIdx ;
			}
		}
	}

	delete[] buffer;

	bufsize = NewVertices.size();
	buffer = new float[bufsize];

	for (int i = 0; i < bufsize;i++)
		buffer[i] = NewVertices[i];



	for ( int h = 0; h < Indici;h++)
		Indices[h] = OptIndices[h];

D3DVector è una struttura che contiene 3 float: x y z.
Vedo se il mio amico mi da la sua implementazione del problema...grazie!

**MacApp** · 26-04-2008, 21:46

Originariamente inviato da XWolverineX
E' difficile dare codice compilabile, poichè dovrei anche darvi un file con un enorme elenco di vertici, nessun problema per me.

Un primo passo nell'otttimizzazione è proprio quello di trasformare il problema in un problema più piccolo.
In modo da poter compiere agevolmente test e modifiche. Se non ci riesci, allora l'ottimizzazione sarà più ardua.

Sto compilando in modalità debug ( e lo fa anche lui)
Cercherò di postare una prova completa e un file da importare di esempio.

I test di velocità sono significativi solo in modalità NON debug.

**XWolverineX** · 27-04-2008, 12:00

Proverò anche in release.
Sono riuscito a farmi dare l'implementazione che sembrerebbe metterci solo 2 secondi. E' fatta in C#

codice:

protected static void Triangulize(Model3D model)
        {
            int totalVertices = 0;
            int strideSize = model.Stride;
            float[] vertexTemp = new float[strideSize];
            List<float> newVerticesList = new List<float>();
            List<int> newIndexList = new List<int>();

            for (int i = 0; i < model.VertexCount; i++)
            {
                //per ogni vertice
                //salvo il vertice
                for (int j = 0; j < strideSize; j++)
                {
                    vertexTemp[j] = model.Data[i * strideSize + j];
                }

                //controlla se già esiste
                int currentVertex = -1;
                for (int j = 0; j < totalVertices; j++)
                {
                    //confronta il vertice attuale con quelli già inseriti
                    bool equal = true;
                    for (int k = 0; k < strideSize; k++)
                    {
                        if (Math.Abs(vertexTemp[k] - newVerticesList[j * strideSize + k])<epsilon)
                        {
                            equal = false;
                            break;
                        }
                    }

                    if (equal)
                    {
                        currentVertex = j;
                        break;
                    }
                }

                if (currentVertex == -1)
                {
                    //nuovo vertice, aggiungere
                    newIndexList.Add(totalVertices);
                    totalVertices++;
                    for (int j = 0; j < strideSize; j++)
                        newVerticesList.Add(vertexTemp[j]);
                }
                else
                {
                    //il vertice già esiste, aggiungere solo l'indice
                    newIndexList.Add(currentVertex);
                }
            }

            model.Data.Clear();
            model.Data.AddRange(newVerticesList);
            model.IndexData.Clear();
            model.IndexData.AddRange(newIndexList);
        }

Purtroppo nemmeno questo è codice compilabile. Sto cercando di capire un pò come fa.

**Paulin** · 27-04-2008, 17:12

Originariamente inviato da XWolverineX Un mio amico, addirittura usando le list del .NET e C#, sostiene che a lui ci mette 2 secondi, ...

Mi sembra strano perché .NET e C# possono essere solo più lenti del C++ standard, e non certo più veloci. Intanto, tu non stai compilando con l'opzione /CLR vero?

Un'altra cosa, hai caricato il file sulla memoria dinamica, prima di lavorare sul suo contenuto?

A quanto pare il tuo amico ha cercato di fare qualcosa di simile in questo modo:

List<float> newVerticesList = new List<float>();
List<int> newIndexList = new List<int>();

Sarà per questo che il suo codice risulta più veloce, ma con il C++ sicuramente si può fare di meglio.

Discussione: C++ - Codice estremamente lento

Strumenti discussione

Ricerca discussione

Visualizza

C++ - Codice estremamente lento

Permessi di invio