🔒 Locked

O(2) optimizations

Started by Metus Dec 20, 2004 at 4:20 AM 6 replies 800+ views

Original Post

Dec 20, 2004 at 4:20 AM

hi. last night i've exporter a mesh from maya (yaaay.. happy me) and stripped stripped out all the unused vertices and rebuild the indexbuffer. However, these methods are veery slow so i'll turn here for some help. This is the method where i extract the used vertices:


for(std::size_t i = 0; i < vertex_data.size(); ++i)
{
	bool duplicate = false;

	vertex_x = vertex_data.x;
	vertex_y = vertex_data.y;
	vertex_z = vertex_data.z;

	normal_x = normal_data.x;
	normal_y = normal_data.y;
	normal_z = normal_data.z;

	for(std::size_t j = 0; j < final_vertex_data.size(); ++j)
	{
		if( final_vertex_data[j].x == vertex_x && final_vertex_data[j].y == vertex_y && final_vertex_data[j].z == vertex_z && 
		final_normal_data[j].x == normal_x && final_normal_data[j].y == normal_y && final_normal_data[j].z == normal_z)
		duplicate = true;
	}

	if(!duplicate)
	{
	final_vertex_data.push_back(MPoint(vertex_x, vertex_y, vertex_z));
	final_normal_data.push_back(MVector(normal_x, normal_y, normal_z));
	}
}

and where i rebuild my indices


for(std::size_t orig_index = 0; orig_index < index_data.size(); ++orig_index)
{
	vertex_x = vertex_data[index_data[orig_index]].x;
	vertex_y = vertex_data[index_data[orig_index]].y;
	vertex_z = vertex_data[index_data[orig_index]].z;

	normal_x = normal_data[index_data[orig_index]].x;
	normal_y = normal_data[index_data[orig_index]].y;
	normal_z = normal_data[index_data[orig_index]].z;

	for(std::size_t j = 0; j < final_vertex_data.size(); ++j)
	{
		if( final_vertex_data[j].x == vertex_x && final_vertex_data[j].y == vertex_y && final_vertex_data[j].z == vertex_z && 
		final_normal_data[j].x == normal_x && final_normal_data[j].y == normal_y && final_normal_data[j].z == normal_z)
		final_index_data.push_back(static_cast<int>(j));
	}
}

there methods were really quick-coded and not so very optimized (as you might see ;)) and I won't ask you to optimize my code, just give me som optimization hints. I tried to format my code as good as I could

darookie

121

darookie

Dec 20, 2004 at 4:52 AM

Very simple optimisation:
change

for(std::size_t j = 0; j < final_vertex_data.size(); ++j)

for(std::size_t j = 0, n = final_vertex_data.size(); j < n && !duplicate; ++j)

Next add your (final) vertices to a sorted data structure . This will reduce look-up time from linear O(n) to logarithmic O(log(n)).

You can do that with std::map (you map the indices from vertices to final_verts and add a compare-function that compares the actual content at the given index).

Good luck,
Pat.

ketek

Dec 20, 2004 at 5:21 AM

Simple cycle optimization won't solve your problem
i faced this problem when i've started importing massive models
the time took was far too much for a complex model
another kind of function was needed and after some
research i've come across a pretty method wich is LINEAR in time
both for removing unused vertices and redundant as well another
kind of optimizations.
All of this stuff i will soon release in an open source
sdk for fine tuning a mesh.

darookie

121

darookie

Dec 20, 2004 at 5:27 AM

I agree with ketek - micro-optimisation will not help. The runtime will still be O(n²).

You can also combine index rebuilding and duplicate removal into a single loop. This will slightly improve your algorithm's runtime as well.

Zahlman

257

Zahlman

Dec 20, 2004 at 5:41 PM

Q. How do I remove duplicates from a list of objects in less than O(N^2) time?

A. First, sort the list - O(N lg N), then reject any element which is equal to the previously accepted one (accepting the first) - one pass, O(N), making O(N lg N) overall.

Caveat: this requires that elements can be sorted (i.e. have a strict weak ordering), while the problem statement only implies comparability. Of course, you can usually *impose* a strict weak ordering of some kind or another. In your case, you might consider elements ordered in terms of x, then y, then z; or in terms of (x^2 + y^2 + z^2), or a host of other options.

Oh, and for the sake of readability, please move the comparison code into your vertex/normal structs/classes. All of this splitting-up work takes a lot of writing - and generates temporaries that you don't really need.

iMalc

182

iMalc

Dec 21, 2004 at 1:57 AM

I came across the exact same issue of duplicate removal today, for a different purpose.

1. O(n*n) as above turns out to be way too slow.

2. Sorting first using an O(n*log(n)) algorithm is better.

3. Using radix sort instead, could provide an even faster O(n*log(k)) solution. However that doesn't work well for all data types, certainly not 3D points & normals.

Or... (what I just thought of...)

4. Use a hash table (with seperate chaining). You first hash all items, which is O(n).
Then you go through the list checking for hash collisions O(n) (i.e. more than one item in a single hash chain).
The items in each hash chain are then checked to see if any of them are in fact equal and deal with apropriately O(m).
This will end up O(n+n*m) where m is the average number of duplicate hashes,
which is effectively O(n*m), and m should be small.
The challenge is to pick a good hash table size and hashing function.

Methinks I'll be going with option four.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.