C++: member classes of the same type

[Structural Integrity]

Bugger, I expected this to work just like that.
What I'm trying to do is make a recursed list of nodes, so my class requires to have members of it's own type.
MS VC++ comes back with an error: error C2079: 'children' uses undefined class 'CTerrainNode'

class CTerrainNode;

class CTerrainNode
{
public:
	CTerrainNode* getChild(int); //returns pointer to a child
	CTerrainLeaf* getLeaf(); //returns the leaf that is connected to the node....
									

private:
	bool isEndNode;				//is this node an endnode? Meaning that there are no nodes below it
	CTerrainLeaf *leaf;		//pointer to the leaf that is in the node.... only applies if it's an endnode
	int ID;					//ID of the node
	CTerrainNode children[4]; //the four children of this node. Only applies if this is NOT an endnode
};

How can I get this to work?!

[Pitchfork]

	CTerrainNode *children[4]; //the four children of this node. Only applies if this is NOT an endnode

[pablissimo]

It'd be nice an easy if it were a binary tree with 2 nodes per subtree, pointers ahoy etc.

This for BSP stuff?

[Structural Integrity]

Originally posted by pablissimo
It'd be nice an easy if it were a binary tree with 2 nodes per subtree, pointers ahoy etc.

This for BSP stuff?

Something like that... it's for a quadtree for my terrain "engine".

Pitchfork, I don't really feel like using pointers..., it'd require me to prebuild the childnodes.... oh.... wait.... I can do that with "new", no, and then pointer to it....

[pablissimo]

Originally posted by Structural Integrity
Something like that... it's for a quadtree for my terrain "engine".

Pitchfork, I don't really feel like using pointers..., it'd require me to prebuild the childnodes.... oh.... wait.... I can do that with "new", no, and then pointer to it....

It also saves having to have the isEndNode var, you can just check the references to the 4 children are all null like you would binary style (though at a performance hit I guess)

[Structural Integrity]

Originally posted by pablissimo
It also saves having to have the isEndNode var, you can just check the references to the 4 children are all null like you would binary style (though at a performance hit I guess)

Nah, I won't do that. The tree is built at startup, so no nodes will be added when running the app. And having to check four pointers for each node is more that checking a single bool, although it's minimal compared to the sheer overhead of rendering the whole thing.

[Pitchfork]

Originally posted by Structural Integrity
Pitchfork, I don't really feel like using pointers..., it'd require me to prebuild the childnodes.... oh.... wait.... I can do that with "new", no, and then pointer to it....

If your constructor works as a constructor is supposed to work, you can ofc do: this->children[0] = new CTerrainNode(whatever);

Originally posted by Structural Integrity
And having to check four pointers for each node is more that checking a single bool, although it's minimal compared to the sheer overhead of rendering the whole thing.

If you can assure that if a CTerrainNode is not an endnode all children are set you only have to check for one pointer. Another point is that an if(children[0]&&children[1]&&children[2]&&children[3]) returns false as soon as the first pointer is null. That means if children[0] == NULL, the other pointers are not checked because the condition is false anyway.

Edit:
Anyway you will have to use pointers here, because what you are trying to do is that every instance of CTerrainNode reserves 4 more instances of CTerrainNode. You don't have endless memory, do you?

[Structural Integrity]

Originally posted by Pitchfork

Edit:
Anyway you will have to use pointers here, because what you are trying to do is that every instance of CTerrainNode reserves 4 more instances of CTerrainNode. You don't have endless memory, do you?

OI FS.... You're right.... I hadn't looked at it that way.
"Infinite recursive memory claiming" is bad mmkay.

=/

[pablissimo]

Originally posted by Structural Integrity
OI FS.... You're right.... I hadn't looked at it that way.
"Infinite recursive memory claiming" is bad mmkay.

=/

Lies, just have a constant stream of DDR ram and a motherboard with an infinite number of slots for it and you'll be 'fine' =))

[Raging.Retard]

Originally posted by Structural Integrity
Nah, I won't do that. The tree is built at startup, so no nodes will be added when running the app. And having to check four pointers for each node is more that checking a single bool, although it's minimal compared to the sheer overhead of rendering the whole thing.

Yes, but if your intent is spatial enumeration, then you may (read should) want to have the possibility of only 1 of the children being a pointer to a new child, and the rest end nodes.

[Structural Integrity]

Originally posted by Raging.Retard
Yes, but if your intent is spatial enumeration, then you may (read should) want to have the possibility of only 1 of the children being a pointer to a new child, and the rest end nodes.

Spatial enumeration?
Please explain, I have never heard of that.

[Raging.Retard]

Spatial enumeration is the act of dividing up world space to increase rendering speeds. Ie you can quickly throw away large proportions of the world by checking parent nodes then skipping children if need be.

I presumed this was what you were intending? That is what I would use a quad/octtree for. (Or have I completely misunderstood?)

[Structural Integrity]

Originally posted by Raging.Retard
Spatial enumeration is the act of dividing up world space to increase rendering speeds. Ie you can quickly throw away large proportions of the world by checking parent nodes then skipping children if need be.

I presumed this was what you were intending? That is what I would use a quad/octtree for. (Or have I completely misunderstood?)

nono, you are right. I didn't know they also called it spatial enumeration.
Anyway, at the moment I don't have any leafs in the tree that contain less polygons.
I have a heightmap at the moment with an equally spaced grid. I simply divide it untill the size reaches a certain value.

[Raging.Retard]

Surely all you have ended up with then is a equally squared grid? You could have acheived the same effect without a tree and just some simple maths.

The idea is you recusrively divide each subnode to your desired threshold. This means each subnode can be a different depth, or have no depth at all, hence the fact using NULL pointers to represent no children makes sense. Rather than a single boolean for all children, as that implies all children have to be equal, ie nodes or not nodes.

[Structural Integrity]

Yes, maths could have solved the problem, but I wanted to make this tree to gain experience in this area. I have never made a quadtree before, so I found this a good exercise.

I don't know what I should think about the other point you made.
Ofcourse the tree can be inequal and have various depths, but if a node has children it ALWAYS has four of them, because it's a quadtree. If it doesn't have children it draws something to the screen. That's where I use the boolean for.
Or is this wrong?

[pablissimo]

Originally posted by Structural Integrity
Yes, maths could have solved the problem, but I wanted to make this tree to gain experience in this area. I have never made a quadtree before, so I found this a good exercise.

I don't know what I should think about the other point you made.
Ofcourse the tree can be inequal and have various depths, but if a node has children it ALWAYS has four of them, because it's a quadtree. If it doesn't have children it draws something to the screen. That's where I use the boolean for.
Or is this wrong?

I don't think its wrong particularly, it could save you work later on though (from the point of view of remembering to set isEndNode, whereas if you use a null reference the property is inherent to the node object). I only suggested null because of the way I've been taught to do binary trees, as long as it works though, does it matter?

[Raging.Retard]

Originally posted by Structural Integrity
If a node has children it ALWAYS has four of them, because it's a quadtree. If it doesn't have children it draws something to the screen.

Yes but.... Although every node that has children has 4, not every node has to have children. Imagine a square divided into quarters, but then only the top left quater was divided again. That would mean 3/4 nodes of the square had no children, and one did. How do you propose your single boolen indicates what is what?

[Raging.Retard]

Actually I think I see what you are doing. If there are no more children, you are still adding a CTerrainNode child with the boolean flag set? It would be clearer to just have used a NULL pointer imo (and more efficient).

That would have saved one byte per tree node, and decrese the depth of your try by one. That may not sound like much, but each level of your tree increases its size by a power of 4 as your quading. So thats quite a significant difference. Eg a tree depth of say say 6 (which isnt very deep), (4^6 - 4^5) is a saving of 3072 nodes.

[Structural Integrity]

Yes, indeed... if there are no more children I set the flag, but at the same time, I also set a pointer to a CTerrainLeaf object, which contains all the data that I need to draw the terrain.
So, either the top node would need a four pointers to leafs, or I add another node, that has one pointer to a leaf.

Terrain.h file:

class CTerrainLeaf
{
public:
	int numvertices;
	float terrain[			((LEAFSIZE/STEPSIZE)+1)*((LEAFSIZE/STEPSIZE)+1)*2][3];
	float terrainnormals[	((LEAFSIZE/STEPSIZE)+1)*((LEAFSIZE/STEPSIZE)+1)*2][3];
	float terraincolors[	((LEAFSIZE/STEPSIZE)+1)*((LEAFSIZE/STEPSIZE)+1)*2][4];
	float terraintexcoords[	((LEAFSIZE/STEPSIZE)+1)*((LEAFSIZE/STEPSIZE)+1)*2][2];
private:
};


class CTerrainNode
{
public:
	CTerrainNode() { }
	~CTerrainNode();
	bool isEnd();			//returns the value if isEnd
	CTerrainNode* getChild(int); //returns pointer to a child
	Vector3D getCoordinate(int);	//returns a coordinate of the node.
									//0 = left-front corner
									//1 = right-front
									//2 = right-far
									//3 = left-far
	CTerrainLeaf* getLeaf(); //returns the leaf that is connected to the node....
									
	CTerrainNode *children[4]; //the four children of this node. Only applies if this is NOT an endnode
	CTerrainLeaf *leaf;		//pointer to the leaf that is in the node.... only applies if it's an endnode

	bool isEndNode;				//is this node an endnode? Meaning that there are no nodes below it
	
	int ID;					//ID of the node
	int indexX, indexY;
	float x,y,w,h;

private:	
};

Render.cpp file:

void CRender::drawTerrainNode(CTerrainNode *t)
{
	int i;
	CTerrainLeaf *a;

//insert some frustum culling here

	if (!t->isEnd()) //if this is not an endnode (and it is in the frustum)
	{
		for (i=0; i<4; i++) //we iterate through the four childnodes
		{
			drawTerrainNode(t->getChild(i)); //we apply recursion
		}
	}
	else //if this node IS an endnode, then we have to draw it...
	{
		a=t->getLeaf();
		glVertexPointer(3,GL_FLOAT,0,	a->terrain);
		glColorPointer(4,GL_FLOAT,0,	a->terraincolors);

		glDrawArrays(GL_TRIANGLE_STRIP,0 , a->numvertices);
	}
}

I hope this makes it clear of what I'm doing. Some code is still a tad bogus and it need cleaning up. I wrote all this today so I need to fiddle a tad more with the structure.


Also: I will change the code a tad so that I use NULL pointers instead of a boolean though. You have convinced me that this is just as obvious and well implementable.

Anyway, to go a tad further:
At this moment my nodes and leafs are ONLY used for drawing the terrain, but I also read that it should be relatively simple to use it for collision detection. Do you have any ideas for this?
Perhaps I should add the heightmap to the leafs. I keep it in the global CTerrain object at the moment.

[Raging.Retard]

Originally posted by Structural Integrity
At this moment my nodes and leafs are ONLY used for drawing the terrain, but I also read that it should be relatively simple to use it for collision detection. Do you have any ideas for this?
Perhaps I should add the heightmap to the leafs. I keep it in the global CTerrain object at the moment.

In exactly the same way. In collision detection you bascially compare the object your checking for interesctions against every face in your world. The same way you would check a parent and discard its children if need be, can be applied to collision detection. When you get to the leaf node, all you are doing is checking for intersections instead of rendering.

[Structural Integrity]

Originally posted by Raging.Retard
In exactly the same way. In collision detection you bascially compare the object your checking for interesctions against every face in your world. The same way you would check a parent and discard its children if need be, can be applied to collision detection. When you get to the leaf node, all you are doing is checking for intersections instead of rendering.

I just had dinner and walked the dog, and I've given this thing some more thought. Ofcourse I COULD do triangle-triangle intersection with the quadtree, but wouldn't that be rather heavy? If I were to use the heightmap I could calculate an intersection of a point with one calculation, instead of checking all polys per possible intersection point.
Also, I never got my tri-tri intersection code to work

Another thing is that I use different levels of world building. My heightmap is a 1024*1024 raw file, but when I build the map, I intentionally get rid of some detail to improve performance. At this moment I only use 1/16th part of all heightpoints to draw the landscape, but I kept the map at its original level.

A DISADVANTAGE of this would be inaccurate looking physics, because the collision detection is not completely according to the drawn landscape.

I see I still have quite a few choices to make to get this to work.

[Raging.Retard]

Originally posted by Structural Integrity
I just had dinner and walked the dog, and I've given this thing some more thought. Ofcourse I COULD do triangle-triangle intersection with the quadtree, but wouldn't that be rather heavy?

Not really, to check for a plane intersection is just a dot product which if I recall can be done with 4 adds and 3 mulitplies. As you should *only* be checking against a limited number of polygons(you filtered most from your tree) then performance should be fine.

use an octree and an lod algorithm.

[Structural Integrity]

Originally posted by Raging.Retard
Not really, to check for a plane intersection is just a dot product which if I recall can be done with 4 adds and 3 mulitplies. As you should *only* be checking against a limited number of polygons(you filtered most from your tree) then performance should be fine.

ofcourse... plane intersection should be enough, as I already know above what poly the point is. tri-tri intersection is not even needed.

Idi, and octree would be an overkill. My map is mostly level terrain, with a few hills. I would get any performance increase with different LOD levels over the y axis. I do plan to get some LOD in there though, I'm just thingking of how I can do that most effectively (ie: several vertex arrays?)