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.
Updated June 13, 2001