Jump to content
  • Advertisement
Sign in to follow this  
taz0010

Container independent algorithms

This topic is 2954 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

I have a bunch of math/geometry algorithms that I would like to make container independent. I figured I'd go the STL route and have them take iterators to the start() and end() of the container in question.

One of the main tasks performed is: Given a container filled with 3D coplanar vertex data, project the coords into 2D and operate on them as if the input were a set of 2D coordinates.

I'd like to remove the logic of iteration/interpreting coord layout from the algorithms in question, and instead pass in a "2d iterator" which is able to iterate over a range of different containers, regardless of the actual arrangement of data within.
My 2D algorithms currently operate on 4 different coordinate layouts:
- Vector of 2D coordinates (simplest arrangement possible)
- Vector of 3D coordinates, where the vector is "projected" into 2D by simply disregarding one of the xyz components of each coord.
- Vector of 3D coordinates as above, with additional data attached to each coord (normal, colour, etc).
- Link list of pointers to 3D coordinates, which are otherwise as above

I'm sure I can get away with only writing each algorithm once, and having it rely on iterators instead of a particular container with a particular layout. But what's the best way to do this?
Should I change my containers (which are mostly typedef'd to STL containers) so they inherit from the STL instead? And add variants of the begin() and end() methods to return custom iterators?
Should the custom iterators themselves inherit from std::iterator? I think all the algorithms require is a bidirectional iterator in order to function, if that makes any difference.

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by taz0010
I have a bunch of math/geometry algorithms that I would like to make container independent. I figured I'd go the STL route and have them take iterators to the start() and end() of the container in question.

One of the main tasks performed is: Given a container filled with 3D coplanar vertex data, project the coords into 2D and operate on them as if the input were a set of 2D coordinates.


One way of doing this would be to have a type of iterator that transforms a 3D vector in to a 2D vector via some kind of projection when that iterator is dereferenced. This means you won't have to write a special version of the algorithm that does a projection internally.

You should take care with this approach, though. If your algorithm would dereference each iterator multiple times, the cost of the projections might accumulate. But if you do take this approach, have a look at boost's transform_iterator.

Quote:

I'd like to remove the logic of iteration/interpreting coord layout from the algorithms in question, and instead pass in a "2d iterator" which is able to iterate over a range of different containers, regardless of the actual arrangement of data within.
My 2D algorithms currently operate on 4 different coordinate layouts:
- Vector of 2D coordinates (simplest arrangement possible)
- Vector of 3D coordinates, where the vector is "projected" into 2D by simply disregarding one of the xyz components of each coord.
- Vector of 3D coordinates as above, with additional data attached to each coord (normal, colour, etc).
- Link list of pointers to 3D coordinates, which are otherwise as above

I'm sure I can get away with only writing each algorithm once, and having it rely on iterators instead of a particular container with a particular layout. But what's the best way to do this?


This last sentence seems to imply that you can think of multiple ways of doing this. What are they? It's hard to guess what your thoughts are here. In other words, what's to stop you following the STL model?

Also, why do you think of 3D coordinates with additional data e.g. normals as a different kind of data?

Possibly you're thinking that there might be algorithms that need to construct new coordinates by some kind of interpolation. In that case, the algorithm could take a functor that performs this interpolation, which would take care of creating correctly interpolated colours, pressure, viscosity, or whatever else.

As for the linked list case, I don't see how that's any different. std::list exposes an interface for iterators and it's reasonably straight forward to add an interface to a custom linked list implementation, too.

Quote:

Should I change my containers (which are mostly typedef'd to STL containers) so they inherit from the STL instead?

The STL containers aren't designed to be used as base classes. I don't think you need to touch them if all you care about are sequences of 3D points.

However, some algorithms might need additional information inherent to more graph-like structures (3D meshes). In that case, you might look at the general approach taken by the algorithms in CGAL. They have an STL flavour, but make concessions and introduce extensions needed to perform algorithms effectively on connected 3D structures.

Quote:

And add variants of the begin() and end() methods to return custom iterators?

Not needed. See my comments about boost::transform_iterator.

Quote:
Should the custom iterators themselves inherit from std::iterator?

They should at least implement the functionality and include the nested types expected of STL iterators. The easiest way to do this is to inherit from an instantiation of std::iterator<>.

Quote:
I think all the algorithms require is a bidirectional iterator in order to function, if that makes any difference.


The only thing your algorithms need to do is document that requirement. The best way of doing this is to have a static assert that checks the iterators passed to the algorithm are indeed forward iterators (at least). If your iterators follows the STL conventions and define an iterator_category typedef, or specialize std::iterator_traits appropriately then that won't be a problem. This is one of the things that inheriting from std::iterator<> gives you.

Share this post


Link to post
Share on other sites
Quote:
You should take care with this approach, though. If your algorithm would dereference each iterator multiple times, the cost of the projections might accumulate. But if you do take this approach, have a look at boost's transform_iterator.

The vector version of the iterator will probably store pointers to the projected x and y coords. Incrementing the iterator is simply a matter of adding sizeof(Container) bytes to each.
Two parallel dereferences are needed to construct and return a 2D coord. e.g. return Vec2(*pProjX, *pProjY). The iterators are const by the way, so a value is returned, not a mutable reference.
The link list iterator will be more expensive to dereference. Two dereferences and 2 additions probably.

Quote:
This last sentence seems to imply that you can think of multiple ways of doing this. What are they? It's hard to guess what your thoughts are here. In other words, what's to stop you following the STL model?

If by "follow the STL model", you mean either roll my own transform_iterator or use Boost, then this is probably what I'll do.

Quote:
Also, why do you think of 3D coordinates with additional data e.g. normals as a different kind of data?

Because you can't iterate over a std::vector<CoordWithAdditionalData> using an iterator constructed from a std::vector<Coord>. This can be resolved by making the iterator parameters template types. i.e. the iterator type is: std::vector<T>::iterator where T is a format which possesses x and y coords. But then there's still the need to transform each element into the desired state, which is required in most cases.

Share this post


Link to post
Share on other sites
Quote:
Original post by taz0010
Quote:
You should take care with this approach, though. If your algorithm would dereference each iterator multiple times, the cost of the projections might accumulate. But if you do take this approach, have a look at boost's transform_iterator.

The vector version of the iterator will probably store pointers to the projected x and y coords. Incrementing the iterator is simply a matter of adding sizeof(Container) bytes to each.
Two parallel dereferences are needed to construct and return a 2D coord. e.g. return Vec2(*pProjX, *pProjY). The iterators are const by the way, so a value is returned, not a mutable reference.
The link list iterator will be more expensive to dereference. Two dereferences and 2 additions probably.

The reason I mentioned the cost of dereferencing/projection was because in theory, it might be cheaper to construct a vector of 2D objects upfront and apply the algorithm to that, depending on how expensive projection really is.

The cost of incrementing the iterator is less relevant because you'd have to do that whether or not you were to make a copy first.

Quote:

Quote:
Also, why do you think of 3D coordinates with additional data e.g. normals as a different kind of data?

Because you can't iterate over a std::vector<CoordWithAdditionalData> using an iterator constructed from a std::vector<Coord>.

True, but why can't you use a std::vector<CoordWithAdditionalData>::iterator?


Quote:
This can be resolved by making the iterator parameters template types. i.e. the iterator type is: std::vector<T>::iterator where T is a format which possesses x and y coords. But then there's still the need to transform each element into the desired state, which is required in most cases.


Perhaps the answer to my previous question lies in here, but I can't quite work out what you mean.

Share this post


Link to post
Share on other sites
Quote:
True, but why can't you use a std::vector<CoordWithAdditionalData>::iterator?


Do you mean like this:


struct Coord{
float x,y,z;
};
struct CoordWithAdditionalData : public Coord{
float otherStuff, textureData, etc;
}
std::vector<CoordWithAdditionalData> vertices;
someFunctionThatGeneratesVertices(vertices);
bool result = someAlgorithm(vertices::begin(), vertices.end());

// someAlgorithm
template<class IterType>
bool someAlgorithm(IterType vBegin, IterType vEnd){
// Use iterators as if they were std::vector<Coord>::iterator even if they're not, provided that they have (*vBegin).x, (or y or z)
}


The above works in some cases, but not in the cases where the coords are projected, which require a more versatile iterator type. e.g. transform_iterator.

So this is what I'm looking at:
- Have all algorithms take begin() and end() iterators, which are template types
- If the algorithm requires 3D coords, containers of Coord and CoordWithAdditionalData simply use the STL container::iterator
- If the algorithm requires 2D projected coords, and the container has 3D coords, use a custom iterator solution

I found out about boost::iterator_facade, which looks very promising. Rolling two, maybe 3 custom iterator objects should be fairly easy.

Share this post


Link to post
Share on other sites
Quote:
Original post by taz0010
I have a bunch of math/geometry algorithms that I would like to make container independent. I figured I'd go the STL route and have them take iterators to the start() and end() of the container in question.

One of the main tasks performed is: Given a container filled with 3D coplanar vertex data, project the coords into 2D and operate on them as if the input were a set of 2D coordinates.


Hold on.

Each coordinate is projected separately?

There is already an algorithm provided for "Do X to each element of the container". It is called std::for_each(). All you do is substitute a "project into 2D" function for X.

Share this post


Link to post
Share on other sites
Quote:
Original post by taz0010
So this is what I'm looking at:
- Have all algorithms take begin() and end() iterators, which are template types

Presumably you mean the algorithms are template functions, rather than the iterators necessarily having to be template instantiations themselves. If so, that sounds fine.

Quote:

- If the algorithm requires 3D coords, containers of Coord and CoordWithAdditionalData simply use the STL container::iterator
- If the algorithm requires 2D projected coords, and the container has 3D coords, use a custom iterator solution


Sounds fine.

Share this post


Link to post
Share on other sites
Quote:
Presumably you mean the algorithms are template functions, rather than the iterators necessarily having to be template instantiations themselves. If so, that sounds fine.


Yeah that's what I meant.

I got Boost's iterator_facade up and running. It's very easy to use and doesn't require you to define 15+ operators like when you create an iterator class from scratch.

Thanks for the help here

Share this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!