Sign in to follow this  
Waterlimon

Is it ok to use casting in this case?

Recommended Posts

I have the following classes:

class OctreeBase
{
//Each derieving class has a function like this. The octreebase doesnt have this function!
virtual DoStuff(void* object)
{
Node* node=static_cast<Node*>(object)
derievedOctree.typeSpecificOperation(node.typeSpecificFunction(),derievedOctree.privateTypeSpecificFunction())
}
}

class Node //Each class derieved from octreebase has its own class to represent a node containing whatever members the octree needs
{

}

class OctreeIterator //only 1 of these, not templated or anything
{
OctreeBase* tree
void* node
void DoStuff()
{
tree->DoStuff(node)
}
}



OctreeIterator uses the same tree for its whole life cycle.

The user gets the octreeiterator by calling OctreeBase*->Root(), which sets the tree member.


However i dont like having void pointers and casting, is there any way i could do this in a prettier way? Currently i have the octreeiterator as a template but i need to have just a single type to use it the way i want. Edited by Waterlimon

Share this post


Link to post
Share on other sites
I would try to make an abstract class that define the DoStuff method's interface. Each class inheriting from it will define the method with different content. The tree will have pointers defined as if they point to the abstract class but you assign objects of classes that inherited from the abstract class.

Share this post


Link to post
Share on other sites
I dont understand.

I have a tree class, derieving from OctreeBase, and each tree class has a node class which carries data specific to the derieved octree class.

The OctreeIterator needs to be able to use any class derieved from OctreeBase, and hold a temporal reference/pointer to the current node its at (as the octree can find the child node faster if it gets the parent node)

I cant make the nodes inherit from the same base class, because:
1.It adds vtable i think, which takes memory
2.The operation needs derieved class specific data and functions, so i would need to pass the derieved octree class to the node through a virtual method, which gives me the same problem (would need to pass a void pointer and cast in the function)

Share this post


Link to post
Share on other sites
If you mean making the node derieve from a base class, that just adds overhead and doesnt remove the problem. I still would need to pass a void*, but this time from the octree to the node.

Im wondering if i really should just use a void*, as i cant really see any other options.


The only option i see is to make the iterator polymorphic, so i would return a IteratorBase* instead of Iterator from Octree.Root(), but that forces me to use new to allocate it, so i dont want to do it when i already have a solution which doesnt require me to allocate stuff. Edited by Waterlimon

Share this post


Link to post
Share on other sites
This template class might work for you but I haven't tried it.
[url="http://nomis80.org/code/octree.html"]http://nomis80.org/code/octree.html[/url]

Share this post


Link to post
Share on other sites
No i dont have a problem with making the octree work for different types, i have a problem with making the iterator work with different octrees without templates, unnecessary waste of space and preferrably without void*, though that might be the real solution.

Technically there shouldnt be a problem if i derieved different iterators from the same base, as theyre all going to be the same size. But c++ is designed to assume that theyre not always the same size and thus i would need to return a pointer to the iterator and not the value if i used polymorphism with them (which requires new).

Share this post


Link to post
Share on other sites
If you mean that i should use polymorphism with the iterator, how can i make copies of the iterator properly, or return such an iterator, without using any allocation when the client will only use IteratorBase*/& to contain the iterators.

Share this post


Link to post
Share on other sites
Like dawoodoz I would use template metaprogramming in this case.
Make a generic Octree container against which you can issue spatial queries.
Then you can do whatever you want with the returned data.

Share this post


Link to post
Share on other sites
No i need to traverse the octree through an iterator, and the iterator needs to work with any octree. Since the iterator will be going to neighbor or child nodes, it needs to keep track of the last node it was in and give it to the octree so the octree can start the search from that node. But the nodes need to maintain octree specific data, the iterator needs to use void* because the node can be of whatever type, and the iterator doesnt really even need to know the type of the node. Its like if the octree asked the iterator to keep a number so it can identify the iterator and know which node it was at.

Or something.

Ill just go with void*

Share this post


Link to post
Share on other sites
The claases serieved from octreebase (an abstract class) handle storage of the nodes differently. One might store them in a vector so the node contains an index to it. Another might use several buckets so the node contains a bucket index AND a normal index.

So each octree type has a corresponding node class.

To create a node one would do:
1.Iterator=OctreeBase->Root()
2.Iterator2=Iterator.AddChildNode(true,true,true) //x,y,z

Iterator AddChildNode(x,y,z)
{
nodePointer=octreeRef.AddChildNode(x,y,z,nodePointer)
}

virtual void* OctreeBase::AddChildNode(x,y,z,void* n)
{
specificNodeType& node=staticcastTospecificNodeType(n)
this.nodes[node.specificMember].DoStuff()
}

On my phone so hopefully that wasnt too unclear to show how i would do it currently.

Share this post


Link to post
Share on other sites
Consider that there is no std::arbitrary_iterator that you can point at any container. There is wisdom in this design decision. Why do you think you need a common iterator type work with any octree implementation? Are you planning on choosing the octree implementation at runtime?

Share this post


Link to post
Share on other sites
I wanted to be able to have a bucketed octree which stores the nodes in buckets, and the buckets in another octree (so nearby nodes are in same buckets).

And, i felt like making it be able to scale at runtime based on the amount of nodes. so i could make something like BucketedOctree(BucketedOctree(NormalOctree))

I probably wont ever have the need for that but i think it gets me better design if its flexible.

(i cant do this if the iterator is a template)



Though i have another problem now. The iterator cannot point directly to the node as they might get rearranged when adding and removing nodes. The iterator does have the node position so it can be looked up, but that requires traversing from the top so i dont want to do that more than once every time i do some operation lets say draw a ball inside the octree.

The solution i came up with:

Each octree has a vector of iterators. Each node contains an index to this vector. Iterators only contain the node theyre at, so no more than 1 iterator is needed for a node and can be shared between multiple users. If the node is moved, the iterator is updated. When an user want an iterator to a node currently not pointed at by iterators, an iterator is added to the vector and pointed to by the node, and returned to the user. When the iterator is not used anymore (its reference counted), the space is freed in the vector.

Pros:
-I can rearrange the nodes as much as i want
-When i move a node i only need to update the object pointing at it if it actually exists (with a redirection vector with all the nodes i always need to update it)
-The less iterators at a time i intend to have, the less space is taken.
-I dont need an index for every single node like in a redirection vector, only for each iterator.

Cons:
-The amount of iterators i can have is limited unless i use a resizeable vector and 32/64 bit indexes in the nodes to it (which is still good)
-Iterators need to be accessed through references :c
-Each node needs a few bits to index the iterator vector (though the space added would be tiny compared to the overall size of the nodes)

If theres no space for a new iterator, it could somehow throw old ones away and when theyre used the next time, they need to find the node using the absolute position of the node or something overly complex like that (another layer on top of the iterators? :D) but thats just a possibility, not needed as long as i index the iterators using ints.


Does that sound awesome enough?

I know i would probably be fine with hardcoding it to work for what i want but i dont really have a goal and im still learning to use c++ so i might as well just think about a perfectly flexible design for everything so i dont have to remake it when i need to do something different (which i certainly would need to some day)

Share this post


Link to post
Share on other sites
[quote]
[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif][size=3][left][background=rgb(250, 251, 252)]The iterator cannot point directly to the node as they might get rearranged when adding and removing nodes.[/background][/left][/size][/font][/color]
[/quote]
The standard library approaches this problem by introducing the concept of [i]iterator invalidation[/i], along with the rules for which operations can cause invalidation. For example, std::vector<T>::erase(std::vector<T>::iterator) invalidates iterators. The API helps by returning a new valid iterator to the next element, or the end iterator if no such element exists.

Share this post


Link to post
Share on other sites
[quote name='rip-off' timestamp='1339602422' post='4948842']
[quote]
[left][background=rgb(250, 251, 252)]The iterator cannot point directly to the node as they might get rearranged when adding and removing nodes.[/background][/left]

[/quote]
The standard library approaches this problem by introducing the concept of [i]iterator invalidation[/i], along with the rules for which operations can cause invalidation. For example, std::vector<T>::erase(std::vector<T>::iterator) invalidates iterators. The API helps by returning a new valid iterator to the next element, or the end iterator if no such element exists.
[/quote]

Doesnt that only work for the iterator doing the operation? I only allow deleting and adding child nodes, so the iterator doesnt break, but if the octree decides to move other nodes around to add or remove the child, i have a problem if i use pointers. And there might be other iterators too (other threads? o,e), and the tree might rearrange itself at any time to save space or optimize.

Share this post


Link to post
Share on other sites
It depends on your definition of "work". Iterator invalidation works, as a design decision, because it disallows those kind of cases. I'm not sure what you can do to solve the case of multiple iterators into the same node in the tree, where one decides to structurally modify the tree such that element pointed to is deleted.

Thread safety is only going to add more difficulty on top. Generally, iteration is achieved in a two-step process - a test to see if the iterator has more elements and then accessing the elements. If other threads are allowed to modify the tree asynchronously, then there can be an inconsistency between these steps.

I would encourage you to consider a high level view on the multi-threading here. An external lock to manage the octree and all iterators is one approach. Another is to duplicate the information into each thread that needs it - thus preventing concurrent editing.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this