Variants on ROAM Priority Computations


The method I suggest anyone try first is to do the full view projection
of the wedgie thickness segment for the center of a triangle.  The
reason for this is not to speed up the computation.  I suggest it
because it is fast to write the code, with little room for mistakes, and
it is good for doing sanity checks on faster or more accurate methods
you might try later, such as the method you are using, or the ones I've
outlined.

[Seumas]
> TriZDist = the camera space Z distance of the center of the triangle's
> hypotenuse (I pick this rather than the tri center since the
> hypotenuse center must be computed to find the coordinates of the
> children, if passing triangle vertices on the stack in a recursive
> function).

Any point will work, and your choice is fast.  I choose the center-point
because it gets distorted the least in the worst case compared to the
rest of the representatives you might choose.  Again, I was going for
reliability in that suggestion for the first thing to try, not speed.

The method I suggest for fast direction-sensitive priority computations
is something like the first-order approximation that I posted a few days
ago.  This gives a tighter measurement of the actual errors than using
thickness>Z*chicken_sacrifice, but takes more number crunching (the
expensive stuff like square roots is replaced with fast look-up tables,
and you only end up doing part of a projection, but is is obviously more
expensive than a multiply and compare).  The chicken_sacrifice method
trades away quality to gain speed.  In other words, you might be using
20-50% more triangles to get the same accuracy.  This is fine if you
have the triangle budget to burn, of course.  But you also take more
time because you are dealing with more triangles for the same quality.
If your bottleneck is the priority computation, then this is a win, but
with frame-coherence acceleration this is not the bottleneck, so the
higher-quality priority is worth it.

Before I begin answering your questions requesting ROAM paper clarification,
let me suggest a simpler metric that is fairly robust and can get you going
quickly.  Take the mid-point of your triangle, and create two points, one at
the top of the wedgie and the other at the bottom.  If your centerpoint is
(x,y,z), and the wedgie thickness is e_T, then the two points are
(x,y,z+e_T) and (x,y,z-e_T).  Send these two points through your view
transform, perspective and all, into pixel space.  Let's call these two
points (sx0,sy0) and (sx1,sy1).  Next compute the distance between them,
se=sqrt((sx1-sx0)^2+(sy1-sy0)^2).  Call se your priority and you will
*almost* have a working system.  In a recent post I described how to deal
with the occasional child that has a higher priority than its parent--you
will need that fix for this simple bound estimate.  The main reason for
using this is that it is very close to what you would get with the more
robust bound, but is really fast to code and can be used to debug (do a
sanity check) on the more complex things you might try later.

I actually switch between two different priority computations,
one slow and robust and the other fast but sometimes wrong.

A priority ideally is a tight upper bound on how far any point
on the triangle is from where it should be (with respect to the
finest-resolution surface), measured in pixels.  This priority
can be tweeked of course to add detail near an object sitting on
a terrain, for example, so it sits right.  Note that the pixel
distance errors are zero if you are looking straight down at
a terrain triangle in the middle of the screen, regardless of how
bad the height error is.  The error goes up as the triangle goes
towards the edges of the screen, or if it is rotated so you aren't
looking straight down.  The error becomes largest when you
look at the triangle edge-on, i.e. when the triangle is right
on a silhouette edge.  This gives higher priority exactly where
it counts visually.

The slow priority computation takes your precomputed maximum
height error for a triangle and produces guaranteed upper bounds
on the screen error in pixels.  This is described in fair detail in the
ROAM paper (http://www.llnl.gov/graphics/ROAM/).  In short,
you take the maximum numerator divided by the minumum
denominator for the three triangle vertice's perspective-transform
error.  This works in all cases except when the denominator goes
to zero (this is avoided by setting priority to max when the triangle
ventures inside the near clipping plane).

David Smith wrote:

> [snip]  I want
> to understand the principle before I understand the
> speed up.
>
> "Let (p,q,r) be the camera-space coordinates of a point
> w(v) without perspective."
>
> I think I understand this, basically take a point
> an pass it through my camera position and orientation
> transform.

Yes, translate the camera position to the origin, then rotate so that p is
the screen-right direction, q is the screen-down direction, and r is the
screen-into direction (for a right-hand coordinate system).

>
>
> You then talk about the perspective transform letting
> s = (p/r, q/r)  but you never use s. Curious, why?

 I define s(v) two paragraphs before the sentence you quote.  I mention it
in this sentence so you know where the formula hat(dist)(v)=...etc... is
coming from.  You don't actually need s in the code you write.

>
>
> Now,
>
> "Let (a,b,c) be the camera-space vector corresponding
> to world-space thickness vector (0,0,et)....."
>
> Does this last paragraph of section 6.2 mean substitute
> the three vertices of the triangle with the additional
> error, et, tacked onto their height component converted
> into screen space and substituted into equation (3)?
>
> I am getting a couple of negative distances and that can't
> be right.  So I still must be missing something.
>
> -DaveS

The sentence before the one you mention is the key to understanding the
formula.  I indicate the screen-space distortion at a corner vertex is
bounded by projecting the thickness segment--this is the simple method I
suggested at the beginning of this message, applied now at the triangle
corners.  What we need to do to get the robust bound is split up this
projection into two steps, (1) into camera space (without perspective), then
(2) bound in screen space.  Let's say your world-space (x,y,z) goes to
camera-space (x',y',z').  Take the two endponts of a thickness segment,
(x0,y0,z0) and (x1,y1,z1), and these transformed to (x0',y0',z0') and
(x1',y1',z1').  What we need in the formula is the vector between these,
(a,b,c)=(x1'-x0',y1'-y0',z1'-z0').  Note that (a,b,c) will be the same
regardless of where you move the thickness segment, as long as its direction
and length remain constant.  In effect you only need to perform the rotation
part of your camera transform (and some scaling), ignoring the translation,
on the vector (0,0,e_T).  So the bottom line is that (a,b,c) depends only on
your rotation matrix (and perhaps scaling) and the wedgie thickness, and is
the same for all three triangle vertices.

So now for three vertices you have three (p,q,r)'s and one (a,b,c).  In your
code you compute 2/(r^2-c^2) three times (once per vertex), and take the max
of the three.  You also compute ((ar-cp)^2+(br-cq)^2) three times and take
the max.  You then take the first max times the square root of the second
max as your distortion bound and priority.

The one major caveat here is that you need to make sure r^2>c^2, or you
could get divide-by-zero or negative "bounds".  If
r^<=c^2+tiny_positive_number, then set the priority to an artificially large
value.  Also make sure your near clipping plane is as far forward as your
application allows (this makes good sense for other reasons as well, like
good use of finite depth-buffer precision).  This way the "artificially
prioritized" triangles quickly get culled outside the view frustum.  You
never need to compute the priority of a triangle labeled OUT, and you and up
without any artificially-prioritized triangles after a few splits.  NOTE:
what I describe here is better than what I put in the paper--the method
there causes terrain intersecting the near clipping plane to be subdivided
to the finest resolution at the expense of all the other visible terrain
(which I consider to be a bug :).

The fast method, not described in the paper, is a good approximation
to the slow method when the triangle is small and far from the
eyepoint.  It is a first-order approximation taken at the center of
the triangle.  You take the derivative of the projected pixel error as
the length of your height error increases from zero.  You then
scale this derivative by the actual height error to get the approximate
projected error.  Here is a totally cryptic code fragment implementing
this:

        x0=q->cp[0]; y0=q->cp[1]; z0=q->cp[2];
        x1=m[0][0]*x0+m[0][1]*y0+m[0][2]*z0+m[0][3];
        y1=m[1][0]*x0+m[1][1]*y0+m[1][2]*z0+m[1][3];
        z1=m[2][0]*x0+m[2][1]*y0+m[2][2]*z0+m[2][3];
        w1=m[3][0]*x0+m[3][1]*y0+m[3][2]*z0+m[3][3];
        m32=m[3][2]/(w1*w1);
        dx=m[0][2]/w1-m32*x1;
        dy=m[1][2]/w1-m32*y1;   // FIXED 06-13-01: Thanks Dimitris P.!
        dz=m[2][2]/w1-m32*z1;   // ditto
        e2=q->e;
        r=e2*e2*(dx*dx+dy*dy+dz*dz)*100.0;
        ri=(int)floor(r*(double)QCELL_RITAB);
        if (ri<0) ri=0; if (ri>=QCELL_RITAB) ri=QCELL_RITAB-1;
        iq=qcell_ritab[ri];

This is maybe ten times as fast as the slow method, so it is worth
decyphering.  The variables are:

    q -- the bintree triangle data structure
    cp[0..2] aka (x0,y0,z0) -- the triangle center point
    m[0..3][0..3] -- the 4x4 view transform matrix
    (dx,dy,dz) -- the derivative of the projected errors
    q->e -- the "wedgie thickness" precomputed height error
    r -- the projected error squared, scaled up a bit
    ri -- r converted to fixed point int for table lookup
    iq -- finally the priority, obtained from a table lookup
        that does the square root and perhaps a log() and scaling.
        This is an int in a range from 0..QIMAX (e.g. QIMAX=2047).

Now you've got an iq priority index, and are ready to queue
your triangle.
 
 

Hi Kallen,

Glad to hear you've made such good progress on your ROAM
implementation.

You wrote:

> I have my ROAM implementation almost complete but I'm stuck on the priority
> computation part. My implementation is straight from the paper except I
> support paging of bin_trees.
>
> Your paper has a formula that goes dist(v)=| |s(v)-sT(v)| |. Now to my
> understanding this a typical LOD distortion calculation.  Do I use this
> formula for distortion? I assume not as it does not use the wedgie
> thickness' I spent so long computing.  If its not distortion then what is it
> used for or is it used at all?

The formula you mention is the exact error measure per surface point v
(the distance in pixels between the position of the point on the finest-
resolution terrain and the position of the point on the approximate
terrain triangulation T).  This is not used directly in an implementation
(since you would have to use it an infinite number of times to get
a guaranteed bound...).  Instead you typically compute a conservative
upper bound on this error measure.  The wedgie bounds you precomputed
help with this.  Ideally you would find the thickest part of the projected
wedgie and use that.  Unfortunately the thickest part of the wedgie can
be anywhere on the wedgie boundary.  So we end up with the formula
with the p,q,r's and a,b,c's in it to get a conservative upper bound on the
distortion.  Why a conservative upper bound you ask?  This is the only
kind of guarantee you can get that you don't get significant and
unacceptable errors if you are unlucky.  If you are willing to relax this
requirement a bit, you can get much faster priority computations where
you sometimes get unlucky or just don't know for sure how bad the
distortions are.  In fact in my implementation I typically turn on
a kind of first-order approximation for all triangles that are fairly
small and far away from the camera point (which is the vast majority
of triangles you are processing).  My code is rather cryptic and takes
some decoding and deduction, but here is what my computation
looks like:
 

int qcell_priority(qcell q)
{
    int iq,k,ri;
    qter qt;
    qcell qp;
    qlos ql;
    qlosref qlr,qlrx;
    vmatmat m;
    double r,x0,y0,z0,x1,y1,z1,w1,dx,dy,dz,*cp,m32,e2;

    qt=q->qt;
    if (q->l>=qt->tm_l) return 0;

    // update line-of-site list
    while (q->losref_list) qlosref_destroy(q->losref_list);
    if (qp=q->qp) {
        for (qlr=qp->losref_list;qlr;qlr=qlr->qlr1)
            { ql=qlr->ql; if (qlos_overlap(ql,q)) qlrx=qlosref_create(q,ql); }
    }else{
        for (ql=qt->los_list;ql;ql=ql->ql1)
            { if (qlos_overlap(ql,q)) qlrx=qlosref_create(q,ql); }
    }
    if (q->losref_list) return QTER_QUEUEN-1;
 

    if (q->l<3) return qcell_priority_good(q);
    if (q->flags&QCELL_IN0) {
        m=qt->vm->m; cp=q->cp;
        x0=cp[0]; y0=cp[1]; z0=cp[2];
        x1=m[0][0]*x0+m[0][1]*y0+m[0][2]*z0+m[0][3];
        y1=m[1][0]*x0+m[1][1]*y0+m[1][2]*z0+m[1][3];
        z1=m[2][0]*x0+m[2][1]*y0+m[2][2]*z0+m[2][3];
        w1=m[3][0]*x0+m[3][1]*y0+m[3][2]*z0+m[3][3];
        m32=m[3][2]/(w1*w1);
        dx=m[0][2]/w1-m32*x1;
        dy=m[1][2]/w1-m32*y1;    // FIXED 06-13-01: Thanks Dimitris P.!
        dz=m[2][2]/w1-m32*z1;    // ditto
        e2=q->e;    // fixed 06-01-13
        r=e2*e2*(dx*dx+dy*dy+dz*dz)*100.0;
        ri=(int)floor(r*(double)QCELL_RITAB);
        if (ri<0) ri=0; if (ri>=QCELL_RITAB) ri=QCELL_RITAB-1;
        iq=qcell_ritab[ri];
    }else iq=QTER_QUEUEN-1;
    return iq;
}
 

I'll give a bit of guidance as to what some of this is.  The data structure for

a bintree triangle is a qcell.  This is attached to a terrain data structure
qter.  The priority computation proceeds by checking for line-of-sight
corrections (ignore this), falling back on the fully conservative, expensive
and slow priority computation (qcell_priority_good()) if the triangle is large,

setting the priority to max if the wedgie is not completely behind the near
clipping plane, and otherwise computing the first-order approximation
I mentioned.

The 4x4 matrix m is the view transform.  I perform a differential transform
(compute
the derivative of the projection for the center point of the triangle), giving
vector
(dx,dy,dz).  I then scale this vector by the wedgie thickness and compute the
magnitude squared.  I use a table look-up to convert this to a priority index.
QCELL_RITAB is 1meg, and QTER_QUEUEN is 2048.

>
>
> Then there is the second large formula that uses (p,q,r) and (a,b,c). But I
> thought this formula was for computing an upper bound.  Is this the formula
> for computing distortion?  If not then why must I have an upper bound.
>
> I'm confused can you help me clarify which of these formulas is the
> distortion.
>
> Lastly, in implementing the deferred priority computation lists your first
> sentence states
> "Given a velocity bound on the viewpoint".  What does this mean?

Really what you are shooting for here is a prediction of when a triangle will
be split or merged at the earliest.  You need to estimate or bound two
quantities
to do this.  One is the change of the crossover priority over time (the
crossover
priority is the priority that, if given as a tolerance, would produce the
output
mesh you obtain--think of running the queue optimization with only a tolerance
as the termination condition and not a triangle count).  The second quantity is

the priority of the triangle over time.  If you think of a 1-D plot of these
two
quantities over time, you will get two cones widening to the right that
eventually
intersect.  The point of intersection is the earliest time that a merge or
split
could happen.  So everything comes down to bounding crossover and triangle
priorities over time.

The crossover priority we just measured empirically and observed that less
than 1% change occurs per frame in our application.  For the triangle priority,

just consider all the possible camera motions that could possibly happen over
time.  If your camera can jump around arbitrarily, then no bound is possible.
Typical motion is constrained, however, to some finite maximum speed of
the camera position.  This is enough to allow you to compute a cone-shaped
bound on priority over time for a given wedgie (by "priority" here I really
mean
the conservative upper bound on priority or the differential estimate, whatever

you choose to use).  Think for example of fixing your reference frame to be
that of the camera, and think of the motion as occurring entirely by the
wedgie.
Then the wedgie will move by at most the maximum velocity per second, so
and point in the wedgie will lie in a sphere whose radius grows linearly over
time.  You can work out the math on what this means for the wedgie bound
or differential projection (it is a pretty simple relationship).

A slight modification you might consider to the reasoning above is to allow
very high rates of change to camera orientation, but still have a finite bound
on the velocity of the camera position.  In this case you consider a different
projected error: project the errors onto a sphere.  Now the errors are
rotationally
invariant.  The reasoning above continues to work if you now always imagine
your camera as pointing straight towards the wedgie.
 


Contact Information

Mark A. Duchaineau -- duchaineau1@llnl.gov


Updated June 13, 2001