Skip to main content
GameDev.net gamedev.net
🔒 Locked

ROAM engine...

Started by kill Jun 28, 2000 at 8:42 PM 15 replies 900+ views
Original Post
kill
kill
Hi. I''ve read the ROAM paper, and all the articles I could find about it. I couldn''t understand two things. 1. How do you calculate the error based on the camera transformation matrix? If you simply figure out how bumpy the terrain is, and base your decision whether to split/merge on that, your mesh would completely depend on the heightfield. How does the camera matrix effect the decision(for example, the further it is, the less detail you need). 2. Can someone explain how the priority for split/merge queues is calculated? Thanx a lot.
bishop_pass
bishop_pass
Each triangle in the bintree is contained within a wedge. The thickness of the wedge is defined in terms of the thickness ofits two children, which is in terms defined in terms of their children...

Oh, its hard to explain. I'm just going to post some code I developed about a year ago. Ask about what you don't understand.
Basically, I'm doing here just what is described in section 6.2 of the ROAM paper.

T is the triangle...
e1, e2, e3, and tv are 3d vectors to be initialized...and transformed to eye space
        

// here is where we have a triangle and calculate its distortion


GetEyeVector (&e1, T->leftx, T->lefty, GetZ (T->leftx, T->lefty));
GetEyeVector (&e2, T->rightx, T->righty, GetZ (T->rightx, T->righty));
GetEyeVector (&e3, T->topx, T->topy, GetZ (T->topx, T->topy));
GetEyeThickness (&tv, T0->thickness);

T->distortion = Distortion (&e1, &e2, &e3, &tv);

// here are the support functions



void GetEyeVector (Vector *e, int x, int y, int z)
{
	e->x = x;
	e->y = y;
	e->z = z;

	TransformVertex (e);
}

void GetEyeThickness (Vector *t, unsigned int thickness)
{
	t->x = 0.0f;
	t->y = 0.0f;
	t->z = thickness;

	TransformVector (t);
}

float Distortion (Vector *e1, Vector *e2, Vector *e3, Vector *tv) 
{
	float nearest, farthest;
	float p, p2, p3;
	float q, q2, q3;
	float qaa, qbb;
	float d;

	/* find nearest corner of wedge */
	nearest = e1->z;
	if (e2->z > nearest)
		nearest = e2->z;
	if (e3->z > nearest)
		nearest = e3->z;
	
	/*
	fprintf (xfile, "Distortion: nearest before: %f\n", nearest);
	*/
	
	if (tv->z < 0.0)
		nearest -= tv->z;
	else
		nearest += tv->z;
	
	if (nearest >= YonPlane) {
		/* nearest is behind the YonPlane */
		/* find farthest corner of wedge */
		farthest = e1->z;
		if (e2->z < farthest)
			farthest = e2->z;
		if (e3->z < farthest)
			farthest = e3->z;
		if (tv->z < 0.0)
			farthest += tv->z;
		else
			farthest -= tv->z;
		
		fprintf (xfile, "Distortion: nearest = %f, farthest = %f YonPlane = %f\n", nearest, farthest, YonPlane);		
		
		if (farthest < NearPlane)
			return FLT_MAX;
		else
			return -1.0f;
	}

	/*
	fprintf (xfile, "nearest = %f\n", nearest);
	fprintf (xfile, "e1-z = %f e2->z = %f e3->z = %f tv->z = %f\n", 
		e1->z, e2->z, e3->z, tv->z);
	*/
	
	p = e1->z * e1->z - tv->z * tv->z;
	p2 = e2->z * e2->z - tv->z * tv->z;
	if (p2 < p)
		p = p2;
	p3 = e3->z * e3->z - tv->z * tv->z;
	if (p3 < p)
		p = p3;

	/*
	fprintf (xfile, "p = %f tv->x = %f tv->y = %f\n", p, tv->x, tv->y);
	*/
	qaa = tv->x * e1->z - tv->z * e1->x;
	qbb = tv->y * e1->z - tv->z * e1->y;
	q = qaa * qaa + qbb * qbb;
	qaa = tv->x * e2->z - tv->z * e2->x;
	qbb = tv->y * e2->z - tv->z * e2->y;
	q2 = qaa * qaa + qbb * qbb;
	if (q2 > q)
		q = q2;

	qaa = tv->x * e3->z - tv->z * e3->x;
	qbb = tv->y * e3->z - tv->z * e3->y;
	q3 = qaa * qaa + qbb * qbb;
	if (q3 > q)
		q = q3;

	d = (2.0f / p) * sqrt (q);
	/*
	fprintf (xfile, "distortion = %f\n", d);
	*/
	return d;
}

void TransformVertex (Vector *V)
{
	float x, y, z;

	x = M[0] * V->x + M[4] * V->y + M[8] * V->z + M[12];
	y = M[1] * V->x + M[5] * V->y + M[9] * V->z + M[13];
	z = M[2] * V->x + M[6] * V->y + M[10] * V->z + M[14];

	V->x = x;
	V->y = y;
	V->z = z;
}

void TransformVector (Vector *V)
{
	float x, y, z;

	x = M[0] * V->x + M[4] * V->y + M[8] * V->z;
	y = M[1] * V->x + M[5] * V->y + M[9] * V->z;
	z = M[2] * V->x + M[6] * V->y + M[10] * V->z;

	V->x = x;
	V->y = y;
	V->z = z;
}

// get the matrix to transform


void SetViewpoint ()
{
	glGetFloatv (GL_MODELVIEW_MATRIX, M);
}



Edited by - bishop_pass on June 28, 2000 11:53:05 PM
_______________________________
"To understand the horse you'll find that you're going to be working on yourself. The horse will give you the answers and he will question you to see if you are sure or not."
- Ray Hunt, in
kill
kill
Thanx for the reply and for the code.

I still have questions though. Here''s my idea of doing things:

For each triangle, calculate the difference between the real heightfield value, and the midpoint of the base. Also go into the triangle recursively, and calculate the same thing for all the children. Then average these values. It will give you the rough estimate of how "bumpy" the terrain is in that triangle. Once you have that, compare this value to the predifined error, and it is higher then the error you find appropriate, split the triangle. You can lower the predifined error depending on how far the triangle is from the camera. This is my idea.

I don''t really understand the source code, because I can''t understand the concept behind it. I understand what the wedgies are(thanx), but how do they affect the decision whether the triangle should be split or not, and how does the camera matrix affect the wedgies?

Thanx.
Jrz
Jrz
Where can I read about ROAM?
khawk
You can read about it in the reference section.

Kevin
Admin for GameDev.net.
bishop_pass
bishop_pass
The wedges and camera space are very significant. The whole idea of ROAM is subdivide the triangles most which are either very close to the viewer OR triangles that are viewed edge on and have large elevation changes.

Here are three examples of triangles likely to be split:

We''re looking straight down from above on a triangle that has a high elevation change. This triangle should be split because its mountain peaks are right there almost touchable by us while its perimeter is far away. Perspective creates distortion and the triangle needs to be split, because unsplit, the texture applied to the triangle will not result in the appearance of the peak being close.

We are standing on the ground looking out thowards the horizon. Triangles under aour feet and nearby need to be split, simply because they are close to us.

We are anywhere, looking out towards the horizon. Just about any triangle, near or far, that has some degree of elevation change which is viewed edge on (i.e. the ridgeline presents a silhoette to us) should be split.

The distortion calculation requires camera position to calculate this distortion value.

Also, you mention something about a ''rough'' estimate of bumpiness. It is NOT a ''rough'' estimate, but rather a bounding container which is guaranteed to completely enclose the potential bumpiness of the triangle.
_______________________________
"To understand the horse you'll find that you're going to be working on yourself. The horse will give you the answers and he will question you to see if you are sure or not."
- Ray Hunt, in
kill
kill
Ok, it's starting to click. Thanx a lot. I still have a question about the priority queues, though. Can you explain how these work?

Again, thanx for your time.

Edited by - kill on June 29, 2000 1:26:48 PM
bishop_pass
bishop_pass
ROAM is a very elegant and powerful algorithm. The way it is presented on Gamasutra (I think) is a 'lite' version. The real ROAM algorithm (the one I'm talking about) is more powerful. It is also more complex, becuase it uses the priority queues.

Someone made the comment that the ROAM paper was not very easy to understand or not well written. That's not true, it's simply presented technically and without implementation specific details, which is how most all tech papers are. Learning to understand a paper like this is tough, but goes a long way towards your ability to problem solve.

I'll be honest with you, I understand the priority queues, but got sidetracked before I implemented them.

The reason I answer questions like yours, is because it is rewarding for me to share what I am interested in and feel I understand, and because it helps me organize my own understanding of the problem itself.

With that said, we can explore the ROAM concept together.

The split queue is a sorted list of all triangles in the current mesh, based on their distortion the last time distortion was calculated. The split list is updated (resorted) everytime we recalculate distortion for the triangles, which is often, but probably not every frame. Calculating distortion for every frame would be better, if we have the CPU power. The split list is also updated everytime we split a triangle and need to insert the two new children into the split list. How we determine which triangle to split is simply pulling the top triangle off of the split list. After all, the whole point of the split list is to order the triangles in the mesh from greatest distortion to least distortion.



Edited by - bishop_pass on June 29, 2000 4:36:09 PM
_______________________________
"To understand the horse you'll find that you're going to be working on yourself. The horse will give you the answers and he will question you to see if you are sure or not."
- Ray Hunt, in
Cthulhu
Cthulhu
In my ROAM implementation, I use a very simple way of calculating priorities. I just scale triangle''s variance based on angle between the triangle and the view direction. Then I divide that value by the distance from viewpoint.

Seems to work fine when targetting 2000-3000 triangles. Less triangles might require more intelligent method.
kill
kill
Chtulu: how does the angle from the viewpoint to the traingle affect the variance? The bigger the angle, the bigger the variance, or the opposite, and why?
bishop_pass
bishop_pass
It sounds like Cthulhu is basing his splitting on whether he is looking at the triangles edge on. In other words, if the triangle is parallel with the table your monitor sits on then it has a high split priority. This is pretty good, but there is a major problem with it.

If you are standing on a mountain top and looking straight down and the triangle is not split, then it could thousands of feet below you, or far away. It won''t get split like it should. And so, the texture which reperesents the mountain summit will appear to be far away. That''s a problem.

The distortion calculation in the ROAM paper handles this.
_______________________________
"To understand the horse you'll find that you're going to be working on yourself. The horse will give you the answers and he will question you to see if you are sure or not."
- Ray Hunt, in
bishop_pass
bishop_pass
It sounds like Cthulhu is basing his splitting on whether he is looking at the triangles edge on. In other words, if the triangle is parallel with the table your monitor sits on then it has a high split priority. This is pretty good, but there is a major problem with it.

If you are standing on a mountain top and looking straight down and the triangle is not split, then it could thousands of feet below you, or far away. It won''t get split like it should. And so, the texture which reperesents the mountain summit will appear to be far away. That''s a problem.

The distortion calculation in the ROAM paper handles this.
_______________________________
"To understand the horse you'll find that you're going to be working on yourself. The horse will give you the answers and he will question you to see if you are sure or not."
- Ray Hunt, in
kill
kill
Bishop: he is basing his calculations on three things.

1. The distance from the viewpoint to the triangle.
2. The angle between the line of sight and the triangle.
3. The bumpiness of the triangle.

He calculates how "bumpy" the triangle is by averaging the difference between the unsplit triangle and the real heightfield height for all the chilren in the triangle. Then he scales this variance value based on the distance and the angle.

I believe this solves the problem you''re talking about. If it doesn''t, you could make very high angles a special case, so if the camera looks down from a large distance, you could split the triangle.
bishop_pass
bishop_pass
Cthulhu''s algorithm doesn''t really solve it in a consistent way. Like he says, it basicaly works, but it will fail.

Example:
1) V = variance is very high.
2) A = angle between view direction and triangle normal near zero.
3) D = distance from viewer is moderate.

V = 100.0
A = 0.001
D = 20.0
priority = (V * A) / D;
priority = (100 * .001) / 20 = 0.005;

The real way to calculate distortion is to calculate the breadth of the wedge''s thickness as it is projected to eye space. This will account for close triangles, mountainous triangles viewed edge on, and mountainous triangles viewed from above where the summit is near, but the base is far.
_______________________________
"To understand the horse you'll find that you're going to be working on yourself. The horse will give you the answers and he will question you to see if you are sure or not."
- Ray Hunt, in
Cthulhu
Cthulhu
Now that I think of it, there IS a problem. Fortunately, in practice it causes very little trouble unless view direction is straight down.

Is the ''real'' priority computation really so time-consuming as it looks? Maybe I should just limit view direction to some angle and live with small perspective errors.

BTW. There is an optimization to bishop_pass''s code. Shouldn''t this:

d = (2.0f / p) * sqrt (q);

be like this:

dd = (4.0f / (p*p)) * q;

Squares of distortions can be compared with same result.
kill
kill
Bishop, can you explain real fast the equasions for calculating the "real" priority for the triangle splits?

Also, what if you just scase the roughness of the terrain based on the distance from the camera only, and ignora the angle between the line of sight and the triangle''s normal? Will that solve the problem?
bishop_pass
bishop_pass
Cthulhu, yeah, I guess your optimization is correct. Thanks. As for the top part of my Distortion function, I think it could be simpler by forgetting about the Yonplane. Here was the idea:

----------------Far plane


Most of what you see is here




----------------Yon plane

----------------Near plane

If a triangle spans the Yon and Near plane it is given super high priority: FLT_MAX

If a triangle resides between Near nad Far, calculate distortion as normal.

If a triangle is in front of Yon plane, don''t bother calculating distortion and set it to -1.0.

I don''t know if this is necessary, as we could just set any triangle which spans the Near plane to a distortion of FLT_MAX.

As for it being time consuming, we have to transform 3 vertices and 1 vector and then do all that calculation you see in the heart of the distortion function.

The idea is to possibly only recompute distortion every 5 or 10 frames. I don''t know if this works well or not.

Here is an explanation of my code, but remember, I did this a year ago and I have to go back and re-understand it.

Equation 3 of section 6.2 of the ROAM paper:

distortion = 2 / p * q

p = r^2 - c^2
q = qaa^2 * qbb^2

If you look closely at my code, you will see how this is an implemetation of that equation.











_______________________________
"To understand the horse you'll find that you're going to be working on yourself. The horse will give you the answers and he will question you to see if you are sure or not."
- Ray Hunt, in

Topic Locked

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

Sign in to reply to this topic.