• Advertisement
Sign in to follow this  

sorting floats with index

This topic is 1840 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi,

I'm struggling with something which sounds fairly simple... although..

 

- I have a int array containing incices of meshes, say Meshes[5] = { 3, 1, 4, 9, 2};

- these indices point to objects (meshes) with a member 'distance' (float)

- say the meshes with indices above have: 10, 30, 40, 50, 15 as distance

 

What I want to achieve is the new index (int array) sorted on the descending order of the member floats..

 

I got so far to be able to sort the int array without the floats, and I got that far to sort the floats as an array (distances).

Simply don't know how to complete this goal...

 

Here's the code that partially does this.

Can someone help me out?

 

	float *dists = new float[mNrD3dMeshesBlended];
	for(oc=0;oc<mNrD3dMeshesBlended;++oc) dists[oc] = mD3dMeshes[mMeshIndexBlended[oc]].mDistToCam;

	float elements = sizeof(dists) / sizeof(dists[0]); 
	std::sort(dists, dists+mNrD3dMeshesBlended, std::greater<float>());

//	int elements = sizeof(mMeshIndexBlended) / sizeof(mMeshIndexBlended[0]); 
//	std::sort(mMeshIndexBlended, mMeshIndexBlended+mNrD3dMeshesBlended, std::greater<int>());

 

 

Share this post


Link to post
Share on other sites
Advertisement

I'd create a struct that holds the original index and the distance. Add an operator > which compares the distance members. Populate a std::vector with instances of the struct for each mesh index/distance combination you need. Then use std::sort on the vector, and voila :-)

Share this post


Link to post
Share on other sites
I'd create a struct that holds the original index and the distance. Add an operator > which compares the distance members. Populate a std::vector with instances of the struct for each mesh index/distance combination you need. Then use std::sort on the vector, and voila :-)

As a bonus (slightly briefer) approach, you can use a std::pair<float, int> instead of the custom struct, and the default comparison operator will do the right thing (i.e. compare the float first).

Share this post


Link to post
Share on other sites

Thanks for the quick reactions, I guess I'll have to dig into pairs/vectors (till now not used that much :))

Keeping in mind that this function will run each frame I render, is this the most efficient way to do this?

(looking at memory allocation for the pairs or structs)

Share this post


Link to post
Share on other sites
Keeping in mind that this function will run each frame I render, is this the most efficient way to do this?
(looking at memory allocation for the pairs or structs)

 

As long as you keep the std::vector around between frames, there shouldn't be much allocation going on (only when the vector's length grows significantly). Your struct (or std::pair, for that matter) should be a very thin wrapper class, and created on the stack - no real cost to those allocations, and copying them into the vector should be similarly cheap.

 

Ideally, the sort itself should dominate the performance cost here. I presume you are not sorting a huge number of items?

Share this post


Link to post
Share on other sites

You can also use a custom predicate that sorts the indices by comparing the distance values at the corresponding indices.

 

The C++11 way:

std::sort(mMeshIndexBlended, mMeshIndexBlended+mNrD3dMeshesBlended, [&](int a, int b) {return dists[a]<dists;});

 

Or the pre-C++11 way:

struct pred {
    pred(float *values) : values(values)
    {}
    
    bool operator()(int a, int b)
    { return values[a] < values; }

    float *values;
}; ... std::sort(mMeshIndexBlended, mMeshIndexBlended+mNrD3dMeshesBlended, pred(dists));

Share this post


Link to post
Share on other sites
Wow, that looks easy (although I have do dig in and read/ study it to understand:))
But it compiles directly, thanks :)

The result is not exacly as expected, but nearly there.
It's sorting but not yet as I'd expect.

Array before sorting:

Render: 1 ,dist to cam: 163.554
Render: 3 ,dist to cam: 136.565
Render: 5 ,dist to cam: 111.131
Render: 7 ,dist to cam: 88.6002
Render: 9 ,dist to cam: 71.7635
Render: 11 ,dist to cam: 159.844
Render: 13 ,dist to cam: 132.098
Render: 15 ,dist to cam: 105.594
Render: 17 ,dist to cam: 81.5475
Render: 19 ,dist to cam: 62.849
Render: 21 ,dist to cam: 154.11
Render: 23 ,dist to cam: 150.167
Render: 25 ,dist to cam: 152.151
Render: 27 ,dist to cam: 46.3681
Render: 29 ,dist to cam: 39.37

After sort:

Render: 27 ,dist to cam: 46.3681
Render: 29 ,dist to cam: 39.37
Render: 25 ,dist to cam: 152.151
Render: 15 ,dist to cam: 105.594
Render: 17 ,dist to cam: 81.5475
Render: 19 ,dist to cam: 62.849
Render: 21 ,dist to cam: 154.11
Render: 23 ,dist to cam: 150.167
Render: 1 ,dist to cam: 163.554
Render: 5 ,dist to cam: 111.131
Render: 13 ,dist to cam: 132.098
Render: 3 ,dist to cam: 136.565
Render: 9 ,dist to cam: 71.7635
Render: 11 ,dist to cam: 159.844
Render: 7 ,dist to cam: 88.6002 Edited by cozzie

Share this post


Link to post
Share on other sites

From your initial set of indices, I get the impression now that your indices are not sequential. In that case, my method won't work. It assumes that index n has the distance value dists[n], while it seems like you have a set of index/distance pairs (n, dist) with arbitrary n and dist, and that has to be sorted by dist. If that's the case, then the structure approach suggested earlier will work.

Share this post


Link to post
Share on other sites

too bad, I'll have to get into that then.

Thanks for the help.

 

My gut feeling that there must be a easy way was not true then :)

Share this post


Link to post
Share on other sites
Stick the distances and indices in a std::map<float, int> then, with the float as the key. Then when you iterate through the map you will get the indices back in order of increasing float key.

Share this post


Link to post
Share on other sites
My gut feeling that there must be a easy way was not true then smile.png

It's really not that complicated...

std::vector< std::pair<float, int> > data;

data.push_back( std::make_pair(0.5, 12) );
data.push_back( std::make_pair(1.75, 14) );
data.push_back( std::make_pair(1.5, 4) );
data.push_back( std::make_pair(0.25, 7) );

std::sort(data.begin(), data.end());

Share this post


Link to post
Share on other sites
Stick the distances and indices in a std::map<float, int> then, with the float as the key. Then when you iterate through the map you will get the indices back in order of increasing float key.

 

This is dangerous if you might have identical distances, as one will stomp the others. You might prefer a std::multimap instead, but even then, the cost of building the tree, traversing it, and maintaining sorted order during inserts/removes is going to clobber your speed compared to just stuffing things into a vector and sorting once.

Share this post


Link to post
Share on other sites

Well, thinking about it a bit more, you can actually use my approach with some modifications: add an additional order-array and add an additional level of referencing to the comparison.

 

int *order = new int[mNrD3dMeshesBlended]; // fill this one with values from 0 and up to mNrD3dMeshesBlended-1 ... std::sort(     order,     order+mNrD3dMeshesBlended,     [&](int a, int b) {         return dists[mMeshIndexBlended[a]]<dists[mMeshIndexBlended];     } );

The array order can, after sorting, be used to traverse the index arrays in sorted order based on distance.

Share this post


Link to post
Share on other sites

Great!

 

try a little modification

struct pred {
    pred(d3dMesh *values) : values(values)
    {}
    
    bool operator()(int a, int b)
    { return values[a].mDistToCam < values[b].mDistToCam; }
    d3dMesh *values;
};
...
std::sort(mMeshIndexBlended, mMeshIndexBlended+mNrD3dMeshesBlended, pred(mD3dMeshes));

 

 

You can also use a custom predicate that sorts the indices by comparing the distance values at the corresponding indices.

 

The C++11 way:

 

std::sort(mMeshIndexBlended, mMeshIndexBlended+mNrD3dMeshesBlended, [&](int a, int b) {return dists[a]<dists[b];});

 

 

Or the pre-C++11 way:

 

struct pred {
    pred(float *values) : values(values)
    {}
    
    bool operator()(int a, int b)
    { return values[a] < values[b]; }
    float *values;
};
...
std::sort(mMeshIndexBlended, mMeshIndexBlended+mNrD3dMeshesBlended, pred(dists));

 

Share this post


Link to post
Share on other sites

I might have read it wrong and filled the int array with the non-sorted index, just filled it with just 0, 1, 2 etc. up to mNrD3dMeshesBlended.

Error is gone now, and here's the result up till now:

 

Before sort:

Order org: 1 ,dist to cam: 163.554
Order org: 3 ,dist to cam: 136.565
Order org: 5 ,dist to cam: 111.131
Order org: 7 ,dist to cam: 88.6002
Order org: 9 ,dist to cam: 71.7635
Order org: 11 ,dist to cam: 159.844
Order org: 13 ,dist to cam: 132.098
Order org: 15 ,dist to cam: 105.594
Order org: 17 ,dist to cam: 81.5475
Order org: 19 ,dist to cam: 62.849
Order org: 21 ,dist to cam: 154.11
Order org: 23 ,dist to cam: 150.167
Order org: 25 ,dist to cam: 152.151
Order org: 27 ,dist to cam: 46.3681
Order org: 29 ,dist to cam: 39.37
 

 

After sort:

Order: 12
Order: 13
Order: 14
Order: 7
Order: 8
Order: 9
Order: 10
Order: 11
Order: 6
Order: 4
Order: 1
Order: 3
Order: 0
Order: 5
Order: 2
 

Probably this is the order based on the new int array being 0 up to mNrD3dMeshesBlended.

Now probably have to link them all together.

Share this post


Link to post
Share on other sites

I can't find the relation yet between the output and the corresponding index of the original index/ array. The code now looks like this (please don't mind al the local variables, will pick this up later when I get the aimed output)

 

	std::ofstream before("blaorg.txt");
	for(int j=0;j<mNrD3dMeshesBlended;++j)
		before << "Unsorted: " << mMeshIndexBlended[j] << " ,dist to cam: " << mD3dMeshes[mMeshIndexBlended[j]].mDistToCam << std::endl;
	before.close();

	float *dists = new float[mNrD3dMeshesBlended];
	for(oc=0;oc<mNrD3dMeshesBlended;++oc) dists[oc] = mD3dMeshes[mMeshIndexBlended[oc]].mDistToCam;

	int *order = new int[mNrD3dMeshesBlended]; // fill this one with values from 0 and up to mNrD3dMeshesBlended
	for(oc=0;oc<mNrD3dMeshesBlended;++oc) order[oc] = oc; //mMeshIndexBlended[oc];

	std::sort(order, order+mNrD3dMeshesBlended, [&](int a, int b) { return dists[mMeshIndexBlended[a]]<dists[mMeshIndexBlended[b]]; });

	std::ofstream after("bla.txt");
	for(int j=0;j<mNrD3dMeshesBlended;++j)
		after << "Sorted: " << order[j] << std::endl; // << " ,dist to cam: " << mD3dMeshes[mMeshIndexBlended[j]].mDistToCam << std::endl;
	after.close();

 

The output of this in the reply above, before and after sorting.


When I look at it, it's probably bad that the indices in the "order" int array don't match up with the distances in the float array.

Shouldn't I fill the "order" int array with the unsorted index? (although giving an access violation at the moment)

 

Share this post


Link to post
Share on other sites

I apologize for my previous attempts at trying to get this right. I have partly read your question too quick, and partly been evaluating it with the wrong set of values and not seen the obvious errors. However, third times a charm; is this what you want? This time I'm even using your exact values and not some made-up test bench.

int main()
{
    int order[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
    int indices[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29};
    int values[] = {163.554, 136.565, 111.131, 88.6002, 71.7635, 159.844, 132.098, 105.594, 81.5475, 62.849, 154.11, 150.167, 152.151, 46.3681, 39.37};
   
    std::sort(
        order,
        order+15,
        [&](int a, int b){
            return values[a]<values;
        }
    );
    
    for(int i : order) {
        std::cout << "(" << indices << ", " << values << ")" << std::endl;
    }
}

The idea is to forget about the index-values of the vector you want to sort, and just do an index-sort on the vector values directly. As long as the contents of values is unchanged, the vector indices maintains its correspondence to the vector values.

Share this post


Link to post
Share on other sites

Thanks Bob, I really appreciate your help.

I tried it out right away and it looks like it's working, last steps to get the right data on the right place will definitely work out.

 

Here's the code I have now and the output.

I'll go work on getting the arrays in my class, to prevent all the memory allocation for each rendered frame.

 

Thanks again.

 

	int *order = new int[mNrD3dMeshesBlended]; 
	for(oc=0;oc<mNrD3dMeshesBlended;++oc) order[oc] = oc; 

	int *indices = new int[mNrD3dMeshesBlended];
	for(oc=0;oc<mNrD3dMeshesBlended;++oc) indices[oc] = mMeshIndexBlended[oc];

	int *dists = new int[mNrD3dMeshesBlended];
	for(oc=0;oc<mNrD3dMeshesBlended;++oc) dists[oc] = mD3dMeshes[mMeshIndexBlended[oc]].mDistToCam;

	std::sort(order, order+mNrD3dMeshesBlended, [&](int a, int b) { return dists[a]<dists[b]; });

Unsorted output:

 0 Unsorted: 1 ,dist to cam: 95.6556
1 Unsorted: 3 ,dist to cam: 105.594
2 Unsorted: 5 ,dist to cam: 152.151
3 Unsorted: 7 ,dist to cam: 46.3681
4 Unsorted: 9 ,dist to cam: 39.37
 

Sorted:

Sorted: 4  39
Sorted: 3  46
Sorted: 0  95
Sorted: 1  105
Sorted: 2  152

Share this post


Link to post
Share on other sites

Yeeeehaaa, all done.

Here's the result:

 

void CD3dscene::SortBlendedMeshes(D3DXVECTOR3 pCamPosition)
{
	for(oc=0;oc<mNrD3dMeshesBlended;++oc)
	{
		mD3dMeshes[mMeshIndexBlended[oc]].mDistToCam = CoordToCoordDist(pCamPosition, mD3dMeshes[mMeshIndexBlended[oc]].mWorldPos);
	}

	int *order = new int[mNrD3dMeshesBlended]; 
	for(oc=0;oc<mNrD3dMeshesBlended;++oc) order[oc] = oc; 

	for(oc=0;oc<mNrD3dMeshesBlended;++oc) mMeshIndexTemp[oc] = mMeshIndexBlended[oc];
	for(oc=0;oc<mNrD3dMeshesBlended;++oc) mMeshDistToCam[oc] = mD3dMeshes[mMeshIndexBlended[oc]].mDistToCam;

	std::sort(order, order+mNrD3dMeshesBlended, [&](int a, int b) { return mMeshDistToCam[a]>mMeshDistToCam[b]; });

	for(oc=0;oc<mNrD3dMeshesBlended;++oc) mMeshIndexBlended[oc] = mMeshIndexTemp[order[oc]];

	SafeDelete(order);
}

 

The only thing I doubt is if I also should make the order int array a class member, since it's created (and released/deleted to) each frame.

What do you think?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement