I'm currently working on a ROAM (Real-Time Optimally Adapting Mesh) engine to produce terrain for a small flying game.

Part of the algorithm I have devised factors the view location into the mesh adaptation tesselation calculations to produce less detailed meshes (less triangles) at larger viewing distances.

The code is executed several thousand times per frame (once for each Triangle node in my binary tree structure to calculate distance for variance comparison)

At present I'm using the following code to calculate a distance metric:

[code]
float distance = sqrtf( SQR((float)centerX - m_ViewPosition.x) +
                            SQR((float)centerY - m_ViewPosition.y) );
[/code]

Where centerX and centerY represent the midpoint of the hypotenuse of the triangle node being assessed.

But this involves a root operation, and as the code is executed several thousand times per second... I'm looking for a more optimised metric for calculating distance.

I'm only factoring 2 dimensions into the equation (elevation is unimportant and would add extra processor load to process).

Does anyone have any ideas they could throw at me for a more efficient metric (preferably not involving a root or a division)?

#1: Why do you need to take the root at all - if you're just comparing this to limits like 100, 400, etc, you might as well compare it to 10000 and 160000 instead.

#2: Do you have to do it with floats - integers are usually faster?

#3: Maybe you could use Z-depth as the distance? You should be calculating that anyway?

Depth buffering is being handled in hardware, since I'm not implementing a software rasteriser. Not storing z-values directly is more efficient when using hardware T&L.

Floats are important for precision (dont want terrain suddenly "popping" up in front of you)

Your other idea has a lot of merit, and I'll see if I can work something around that, though using the values in that fashion directly in my algorithm would result in an exponential drop-off of terrain detail with distance.

The root eliminates the exponent and results in smooth decay, which is something I'm trying to acheive, but the root also eats comparatively huge amounts of processor cycles.

Also, the test isnt limit based... I'm using a dynamically tesselating mesh of triangles to approximate a high-resolution heightmap. The variation allowed before tesselation is ceased for any branch of the triangle tree is what the distance is used to calculate, so it is analog.

[quote author=EvilCheese link=board=23;threadid=2536;start=0#msg19752 date=1062454868]
Depth buffering is being handled in hardware, since I'm not implementing a software rasteriser. Not storing z-values directly is more efficient when using hardware T&L.

Floats are important for precision (dont want terrain suddenly "popping" up in front of you)

Your other idea has a lot of merit, and I'll see if I can work something around that, though using the values in that fashion directly in my algorithm would result in an exponential drop-off of terrain detail with distance.

The root eliminates the exponent and results in smooth decay, which is something I'm trying to acheive, but the root also eats comparatively huge amounts of processor cycles.

Also, the test isnt limit based... I'm using a dynamically tesselating mesh of triangles to approximate a high-resolution heightmap. The variation allowed before tesselation is ceased for any branch of the triangle tree is what the distance is used to calculate, so it is analog.
[/quote]
What are you using for your sqrt implementation? There are a number of "pretty fast" versions (at the cost of some accuracy) out there.

I'm using the standard run-time library sqrt implementation presently, though I'll have a look around to see if I can find a faster one.

A small loss of accuracy would be acceptable. The mesh accuracy drop-off doesnt need to be 100% smooth since it wont make a large visual difference... I would just like for it not to be exponential, since that WOULD make a large difference.

If it produces errors within acceptable bounds I can use geomorphing or vertex clamping to interpolate sudden jumps into something virtually unnoticeable over several frames.