PDA

View Full Version : Is this a correct way to compute the scissor rectangle?



Java Cool Dude
06-09-2005, 07:31 PM
A while ago when I was implementing shadow volumes in my rendering engine I came up with an algorithm to compute a given light's bounding screen-rectangle. According to my tests, it works pretty darn well, however, having said that I'm still wondering if there are cases out there that could break it.
Anyway here it is, I would appreciate any commments:


Tuple4i Renderer::getScissorRect(const Tuple3f &lightPosition,
float lightRange)
{
Tuple4i scissor;

//Retrieve the current view port to extract the screen width and height
glGetIntegerv(GL_VIEWPORT,viewport);

//Get the camera world position
Tuple3f cameraPosition = getCameraPosition(),
lightPos = lightPosition,
diagonal;

//If the camera distance to the light source is lesser than
//the light range, return the description of the whole screen
if(cameraPosition.getDistance(lightPos) - lightRange <= EPSILON)
return viewport;

//Retrieve the projection matrix, we will use it later to project
//our corners points onto the screen
glGetFloatv(GL_PROJECTION_MATRIX, projectionMatrix);

//Retrieve the modelview matrix, we will extract the up and right
//vectors from it
glGetFloatv(GL_MODELVIEW_MATRIX , modelviewMatrix);

/**************************************/
/* + Upper corner */
/* / */
/* / */
/* / */
/* / */
/* / */
/* / */
/* ( ) Light position */
/* / */
/* / */
/* / */
/* / */
/* / */
/* / */
/* + Lower corner */
/**************************************/

//Multiply the light range by square root of two since we will compute
//the corners of square
lightRange *= 1.42f;

diagonal.set(modelviewMatrix[0] + modelviewMatrix[1],
modelviewMatrix[4] + modelviewMatrix[5],
modelviewMatrix[8] + modelviewMatrix[9]);
diagonal *= lightRange;

//Compute the lower corner
corners[0].set(lightPosition.x - diagonal.x,
lightPosition.y - diagonal.y,
lightPosition.z - diagonal.z,
1.0f);

//Compute the upper corner
corners[1].set(lightPosition.x + diagonal.x,
lightPosition.y + diagonal.y,
lightPosition.z + diagonal.z,
1.0f);

//Project both onto the screen surface
for(int i = 0; i < 2; i++)
{
corners[i] *= modelviewMatrix;
corners[i] *= projectionMatrix;
corners[i] /= corners[i].w;
corners[i].x = viewport[0] + float(viewport[2])*(corners[i].x + 1.0f)/2.0f;
corners[i].y = viewport[1] + float(viewport[3])*(corners[i].y + 1.0f)/2.0f;
corners[i].z = 0.5f*corners[i].z + 0.5f;
}

//Set up the scissor info
scissor[0] = int(corners[0].x);
scissor[1] = int(corners[0].y);
scissor[2] = int(corners[1].x);
scissor[3] = int(corners[1].y);

scissor[0] = scissor[0] < 0 ? 0 : scissor[0];
scissor[1] = scissor[1] < 0 ? 0 : scissor[1];

return scissor;
}

knackered
06-10-2005, 02:52 AM
Get rid of the glGet's.

Java Cool Dude
06-10-2005, 04:32 AM
Why would I :p ?
I know by doing so it might incur a performance hit, but keep in mind that they're called once a frame which doesn't matter that much if any at all.
Seriously though, what do you think of this approach? Is it flawed or what?

Humus
06-10-2005, 02:40 PM
If I understand what you're doing correctly, you're basically seeing the light as a 2D billboard at the light's position so to speak, and figuring out the extents of that in screenspace. If that's the case, then it's flawed. That's what I tried first too, until I realized it doesn't work when you get close to the light. It will return a slightly smaller rectangle than you need. I'd draw a picture if I wasn't too lazy.

Java Cool Dude
06-10-2005, 03:44 PM
You're correct, my approach is to consider the light's scissor-rectangle as a billboard centered around the source.
Now regarding the glitch that you mentioned, a simple check on the distance from the viewer to the light source could easily prevent it ;)


if(cameraPosition.getDistance(lightPos) - lightRange <= EPSILON)
return viewport;

SirKnight
06-10-2005, 08:55 PM
Or this http://www.gamasutra.com/features/20021011/lengyel_06.htm

(This is also in Eric's 'Math for 3d game prog & comp gfx' book).

-SirKnight

Java Cool Dude
06-10-2005, 09:02 PM
Thanks for the link mate, but I've already touched on that and figured that my method is simpler and requires far less computations ;)

SirKnight
06-10-2005, 09:04 PM
Oh and knackered's advice is good, glGet really should be taken out. For debugging/prototyping it's fine, but once your algorithm is working, rip those things out. If you were doing your 3d in software, say using MESA, then using glGet is fine. However, in hardware, functions like glGet have a pretty big cost with them and should not be used in production code.

-SirKnight

M/\dm/\n
06-11-2005, 12:31 AM
Kinda wild guess, but arn't modelview/modelviewprojection matrices stored on CPU side, at least one copy???

Humus
06-11-2005, 02:45 PM
Originally posted by Java Cool Dude:
You're correct, my approach is to consider the light's scissor-rectangle as a billboard centered around the source.
Now regarding the glitch that you mentioned, a simple check on the distance from the viewer to the light source could easily prevent it ;)


if(cameraPosition.getDistance(lightPos) - lightRange <= EPSILON)
return viewport;What's the value of EPSILON? Something close to zero I guess? Then you're only taking care of the case where you're within the light radius. It's actually broken regardless of distance, though in practice it may work when you're far from the light.

This is what I mean:
http://www.humus.ca/temp/flaw.png

The dashed line with what you get, while the solid line is what you want.

Java Cool Dude
06-11-2005, 07:36 PM
You got me there :p

knackered
06-12-2005, 10:02 AM
Originally posted by M/\dm/\n:
Kinda wild guess, but arn't modelview/modelviewprojection matrices stored on CPU side, at least one copy???In reality that's a possibility, but it's a server state not a client state, so it's just as possible that it's not cached in system memory. Imagine if an implementation decided to take advantage of the T&L bits on the card to accelerate matrix stack multiplications, in that case it would be impossible to keep a system memory cache of the current matrix stack.

Ventura
06-12-2005, 10:14 PM
The simplest method i used before, without having to get my head round lengyels method, was to keep a global list of sample points (~12) on the front side of a unit sphere.

Then manually scale and transform these points to where your light is, and then transform into screen space, and assemble and clip a rectangle from it.

You can be adaptive with your sample count at distance, but you have to be careful about -ve projections and stuff.

This method worked perfectly for my stencil shadow engine, its not as elegant as lengeyls but iirc he had a few sqrt's in there too. It also will result in a larger scissor rect in some cases.

fpo
06-14-2005, 08:19 AM
Originally posted by SirKnight:
Or this http://www.gamasutra.com/features/20021011/lengyel_06.htm

(This is also in Eric's 'Math for 3d game prog & comp gfx' book).

-SirKnightThanks for the reference SirKnight. Implemented it and it works fine. Just equation 29 has C instead of L in fromula. But I have a quesion ... what value of 'e' must we use in eq 39? I'm using 1.2 and work ok but 1.0 will fail and clip more than it should. He does not say much about the 'e' parameter...

SirKnight
06-14-2005, 09:32 AM
You know I'm confused about 'e' too. :) I thought it might have been the near clip plane distance b/c of what that one diagram shows 'e' to be.

EDIT: Oh yeah you're right, eq 29 is wrong. I never noticed that in this webpage article. In his book he has it right however.

-SirKnight

castano
06-14-2005, 10:03 AM
I've used the formulas from the gamasutra article without problems. It's true that they are more complex than they need to be, but it's been working fine for me.

Also, don't forget to compute also the depth bounds and use NV_depth_bounds to safe fillrate. On non nvidia hardware you can also use the near and far clip planes, but in that case you will have to adjust them to avoid z fighting or use polygon offset instead.


/**
* Compute the screenspace bounds of the light.
*
* This is just Eric Lengyel scissor optimization:
* http://www.gamasutra.com/features/20021011/lengyel_06.htm
*
* The equations in the Gamasutra article, while correct, are more complicated
* than they need to be. Equation (38) can be replaced by the much simpler
* formula P = L - rN. If you have the second edition of Mathematics for 3D
* Game Programming and Computer Graphics, an updated derivation appears in
* Section 10.7.*
* -- Eric Lengyel
*
* Hmm.. I only have the first edition, but the derivation should be pretty
* easy. In any case this doesn't seem to be an important optimization.
**/
bool PiLight::ComputeLightBounds(const PiViewport * viewport, BBox * box) const {
piDebugCheck( viewport != NULL );
piDebugCheck( viewport->cam != NULL );
piDebugCheck( box != NULL );

Vec3 l; l.Sub( origin, viewport->cam->pos );

float D = l.Length();

// Compute depth bounds.
float z = Vec3DotProduct( l, viewport->cam->dir );
box->mins.z = z - radius;

if( type != PI_LTP_VOLUMETRIC ) {
box->maxs.z = z + radius;
}

if( D <= radius ) {
// camera inside light
return true;
}

// Transform L to eye space
Vec3 L;
viewport->cam->eye.TransformVec3( l, L );


// Vertical planes: T = <Nx, 0, Nz, 0>
D = (SQ(L.x) - SQ(radius) + SQ(L.z)) * SQ(L.z);
if( D >= 0 ) {

const float Nxa = (radius * L.x - sqrt(D)) / (SQ(L.x) + SQ(L.z));
const float Nza = (radius - Nxa * L.x) / L.z;
const float Pza = (SQ(L.x) + SQ(L.z) - SQ(radius)) / (L.z - (Nza / Nxa) * L.x);

// Tangent a
if( Pza < 0 ) {
float xa = 2 * Nza / (Nxa * viewport->cam->width);
xa = viewport->window.x0 + (xa+1) * 0.5f * (viewport->window.x1 - viewport->window.x0);

float Pxa = - Pza * Nza / Nxa;

if( Pxa > L.x ) {
box->maxs.x = piMax( box->mins.x, xa );
}
else {
box->mins.x = piMin( box->maxs.x, xa );
}
}

const float Nxb = (radius * L.x + sqrt(D)) / (SQ(L.x) + SQ(L.z));
const float Nzb = (radius - Nxb * L.x) / L.z;
const float Pzb = (SQ(L.x) + SQ(L.z) - SQ(radius)) / (L.z - (Nzb / Nxb) * L.x);

// Tangent b
if( Pzb < 0 ) {
float xb = 2 * Nzb / (Nxb * viewport->cam->width);
xb = viewport->window.x0 + (xb+1) * 0.5f * (viewport->window.x1 - viewport->window.x0);

float Pxb = - Pzb * Nzb / Nxb;

if( Pxb > L.x ) {
box->maxs.x = piMax( box->mins.x, xb );
}
else {
box->mins.x = piMin( box->maxs.x, xb );
}
}
}

if( box->mins.x >= box->maxs.x ) {
return false;
}


// Horizontal planes: T = <0, Ny, Nz, 0>
D = (SQ(L.y) - SQ(radius) + SQ(L.z)) * SQ(L.z);
if( D >= 0 ) {

const float Nya = (radius * L.y - sqrt(D)) / (SQ(L.y) + SQ(L.z));
const float Nza = (radius - Nya * L.y) / L.z;
const float Pza = (SQ(L.y) + SQ(L.z) - SQ(radius)) / (L.z - (Nza / Nya) * L.y);


// Tangent a
if( Pza < 0 ) {
float ya = 2 * Nza / (Nya * viewport->cam->height);
ya = viewport->window.y0 + (ya+1) * 0.5f * (viewport->window.y1 - viewport->window.y0);

float Pya = - Pza * Nza / Nya;

if( Pya > L.y ) {
box->maxs.y = piMax( box->mins.y, ya );
}
else {
box->mins.y = piMin( box->maxs.y, ya );
}
}

const float Nyb = (radius * L.y + sqrt(D)) / (SQ(L.y) + SQ(L.z));
const float Nzb = (radius - Nyb * L.y) / L.z;
const float Pzb = (SQ(L.y) + SQ(L.z) - SQ(radius)) / (L.z - (Nzb / Nyb) * L.y);

// Tangent b
if( Pzb < 0 ) {
float yb = 2 * Nzb / (Nyb * viewport->cam->height);
yb = viewport->window.y0 + (yb+1) * 0.5f * (viewport->window.y1 - viewport->window.y0);

float Pyb = - Pzb * Nzb / Nyb;

if( Pyb > L.y ) {
box->maxs.y = piMax( box->mins.y, yb );
}
else {
box->mins.y = piMin( box->maxs.y, yb );
}
}
}

if( box->mins.y >= box->maxs.y ) {
return false;
}

return true;
}

fpo
06-14-2005, 10:57 AM
Your code looks good to me, just like the one I did.

But why do you use 'e' as 2/viewport->cam->height ??

float xa = 2 * Nza / (Nxa * viewport->cam->width);
xa = viewport->window.x0 + (xa+1) * 0.5f * (viewport->window.x1 - viewport->window.x0);Then you multiply xa in the second line by width again (viewport->window.x1 - viewport->window.x0) canceling the multiplication from the first line.

Using 'e' as 2 in my code makes scissor much bigger than it could be. Using 1.2 works fine for my simple test scene with 3 different lights.

SirKnight
06-14-2005, 01:40 PM
This demo here does some calcs to compute the scissor box and it looks pretty good. Here is the link: http://developer.nvidia.com/object/fast_shadow_volumes.html

I don't think they are using eric's method, at least it doesn't look like it to me with a quick glance. I'm not sure if this demo does all of the methods possible to have the fastest shadow volume rendering but I know it does quite a bit and does run good.

-SirKnight

Java Cool Dude
06-14-2005, 03:22 PM
For some reason the method described in your link, SirKnight, returns a bounding rectangle a bit bigger than what it should be. Have you tried it?

fpo
06-14-2005, 06:39 PM
Ok, here is my code based on Eric's article and I must say it works fine and generate quite small scissor rectangles. Should be easy to copy/paste into your own code as it only uses standard C objects (apart for the 4 component pVector object... replace with your own vector object there).


int set_light_scissor(const pVector&amp; lightpos,int sx,int sy,float aspect)
{
int rect[4]={ 0,0,sx,sy };
float d;

float r=lightpos.w; // ligth radius
float r2=r*r; // squared radius

pVector l=lightpos; // light position
pVector l2=lightpos*lightpos; // squared position

float e1=1.2f;
float e2=1.2f*aspect;

d=r2*l2.x - (l2.x+l2.z)*(r2-l2.z);
if (d>=0)
{
d=sqrtf(d);

float nx1=(r*l.x + d)/(l2.x + l2.z);
float nx2=(r*l.x - d)/(l2.x + l2.z);

float nz1=(r - nx1*l.x)/l.z;
float nz2=(r - nx2*l.x)/l.z;

float e=1.25f;
float a=aspect;

float pz1=(l2.x + l2.z-r2)/(l.z - (nz1/nx1)*l.x);
float pz2=(l2.x + l2.z-r2)/(l.z - (nz2/nx2)*l.x);

if (pz1>=0 &amp;&amp; pz2>=0)
return 0; // discard light

if (pz1<0)
{
float fx=nz1*e1/nx1;
int ix=(int)((fx+1.0f)*sx*0.5f);

float px=-pz1*nz1/nx1;
if (px<l.x)
rect[0]=max(rect[0],ix);
else
rect[2]=min(rect[2],ix);
}

if (pz2<0)
{
float fx=nz2*e1/nx2;
int ix=(int)((fx+1.0f)*sx*0.5f);

float px=-pz2*nz2/nx2;
if (px<l.x)
rect[0]=max(rect[0],ix);
else
rect[2]=min(rect[2],ix);
}

if (rect[2]<=rect[0])
return 0; // discard light
}

d=r2*l2.y - (l2.y+l2.z)*(r2-l2.z);
if (d>=0)
{
d=sqrtf(d);

float ny1=(r*l.y + d)/(l2.y + l2.z);
float ny2=(r*l.y - d)/(l2.y + l2.z);

float nz1=(r - ny1*l.y)/l.z;
float nz2=(r - ny2*l.y)/l.z;

float pz1=(l2.y + l2.z-r2)/(l.z - (nz1/ny1)*l.y);
float pz2=(l2.y + l2.z-r2)/(l.z - (nz2/ny2)*l.y);

if (pz1>=0 &amp;&amp; pz2>=0)
return 0; // discard light

if (pz1<0)
{
float fy=nz1*e2/ny1;
int iy=(int)((fy+1.0f)*sy*0.5f);

float py=-pz1*nz1/ny1;
if (py<l.y)
rect[1]=max(rect[1],iy);
else
rect[3]=min(rect[3],iy);
}

if (pz2<0)
{
float fy=nz2*e2/ny2;
int iy=(int)((fy+1.0f)*sy*0.5f);

float py=-pz2*nz2/ny2;
if (py<l.y)
rect[1]=max(rect[1],iy);
else
rect[3]=min(rect[3],iy);
}

if (rect[3]<=rect[1])
return 0; // discard light
}

int n=(rect[2]-rect[0])*(rect[3]-rect[1]);
if (n==sx*sy)
{
// render light fullscreen, no need for scissor
glDisable(GL_SCISSOR_TEST);
return sx*sy;
}

// render light with scissor
glScissor(rect[0],rect[1],rect[2]-rect[0],rect[3]-rect[1]);
glEnable(GL_SCISSOR_TEST);
return n;
}