#154069 - Rajveer - Thu Apr 10, 2008 2:06 pm
I'm doing frustum culling and when creating the frustum I need to multiply the 4x4 projection matrix against the 4x4 modelview matrix. I can't find how to retrieve the whole 4x4 modelview matrix, however what is the clip matrix? Is it the projection * modelview, so I can just retrieve this matrix and extract the frustum planes from it?
EDIT: Some research here
http://meraman.dip.jp/index.php?M3DSS_GBATEK_NDS
shows that the ClipMatrix = PositionMatrix*ProjectionMatrix. Now what's the position matrix, is it the whole 4x4 modelview matrix? If it is, shouldn't the ClipMatrix be Projection * Position since OpenGL is column major, and aren't the matrices in that link row-major?
Last edited by Rajveer on Thu Apr 10, 2008 2:29 pm; edited 1 time in total
#154070 - a128 - Thu Apr 10, 2008 2:28 pm
| Code: |
| glGetFixed(GL_GET_MATRIX_CLIP,&clip[0]) ; |
I did this in my frustum code
| Code: |
void CFrustum::CalculateFrustum()
{
int32 clip[4*4];
glGetFixed(GL_GET_MATRIX_CLIP,&clip[0]) ;
// Now we actually want to get the sides of the frustum. To do this we take
// the clipping planes we received above and extract the sides from them.
// This will extract the RIGHT side of the frustum
//Y+ up, X+ right, Z+ in screen
m_Frustum[RIGHT][A] = clip[ 3] - clip[ 0];
m_Frustum[RIGHT][B] = clip[ 7] - clip[ 4];
m_Frustum[RIGHT][C] = clip[11] - clip[ 8];
m_Frustum[RIGHT][D] = clip[15] - clip[12];
// Now that we have a normal (A,B,C) and a distance (D) to the plane,
// we want to normalize that normal and distance.
// Normalize the RIGHT side
NormalizePlane(m_Frustum, RIGHT);
// This will extract the LEFT side of the frustum
m_Frustum[LEFT][A] = clip[ 3] + clip[ 0];
m_Frustum[LEFT][B] = clip[ 7] + clip[ 4];
m_Frustum[LEFT][C] = clip[11] + clip[ 8];
m_Frustum[LEFT][D] = clip[15] + clip[12];
// Normalize the LEFT side
NormalizePlane(m_Frustum, LEFT);
// This will extract the BOTTOM side of the frustum
m_Frustum[BOTTOM][A] = clip[ 3] + clip[ 1];
m_Frustum[BOTTOM][B] = clip[ 7] + clip[ 5];
m_Frustum[BOTTOM][C] = clip[11] + clip[ 9];
m_Frustum[BOTTOM][D] = clip[15] + clip[13];
//
// Normalize the BOTTOM side
NormalizePlane(m_Frustum, BOTTOM);
// This will extract the TOP side of the frustum
m_Frustum[TOP][A] = clip[ 3] - clip[ 1];
m_Frustum[TOP][B] = clip[ 7] - clip[ 5];
m_Frustum[TOP][C] = clip[11] - clip[ 9];
m_Frustum[TOP][D] = clip[15] - clip[13];
// Normalize the TOP side
NormalizePlane(m_Frustum, TOP);
// This will extract the BACK side of the frustum
m_Frustum[BACK][A] = clip[ 3] - clip[ 2];
m_Frustum[BACK][B] = clip[ 7] - clip[ 6];
m_Frustum[BACK][C] = clip[11] - clip[10];
m_Frustum[BACK][D] = clip[15] - clip[14];
//
// Normalize the BACK side
NormalizePlane(m_Frustum, BACK);
// This will extract the FRONT side of the frustum
m_Frustum[FRONT][A] = clip[ 3] + clip[ 2];
m_Frustum[FRONT][B] = clip[ 7] + clip[ 6];
m_Frustum[FRONT][C] = clip[11] + clip[10];
m_Frustum[FRONT][D] = clip[15] + clip[14];
//
// Normalize the FRONT side
NormalizePlane(m_Frustum, FRONT);
}
inline void NormalizePlane(myf32 frustum[6][4], int side)
{
// Here we calculate the magnitude of the normal to the plane (point A B C)
// Remember that (A, B, C) is that same thing as the normal's (X, Y, Z).
// To calculate magnitude you use the equation: magnitude = sqrt( x^2 + y^2 + z^2)
int32 magnitude= sqrtf32(mulf32(frustum[side][A], frustum[side][A] )+
mulf32(frustum[side][B] , frustum[side][B]) +
mulf32(frustum[side][C], frustum[side][C] ));
// Then we divide the plane's values by it's magnitude.
// This makes it easier to work with.
frustum[side][A]= divf32(frustum[side][A], magnitude);
frustum[side][B]= divf32(frustum[side][B], magnitude);
frustum[side][C]= divf32(frustum[side][C], magnitude);
frustum[side][D]= divf32(frustum[side][D], magnitude);
} |
Last edited by a128 on Thu Apr 10, 2008 2:38 pm; edited 1 time in total
#154071 - Rajveer - Thu Apr 10, 2008 2:37 pm
Great post! Also I didn't know that normalizing a plane meant normalizing it's distance too, so thanks for everything :)
#154073 - silent_code - Thu Apr 10, 2008 3:23 pm
but it has to - plane equation (with normalized 'abc'):
0 = ax + by + cz + d
or
d = -ax - by - cz
so you need to treat both sides equally, or else it'll get messed up. ;^D
ps: check: http://mathworld.wolfram.com/Plane.html and also, more specific: http://mathworld.wolfram.com/HessianNormalForm.html (where you see that "p = d / magnitude(abc)") ;^)
Last edited by silent_code on Thu Apr 10, 2008 3:36 pm; edited 5 times in total
#154074 - Rajveer - Thu Apr 10, 2008 3:31 pm
D'uh! *smacks head*
:D
#154094 - Rajveer - Thu Apr 10, 2008 11:41 pm
I guess it doesn't make sense to start a new topic as this question is about frustum culling.
I'm recursively culling my octree AABB nodes, so what's the most efficient way to draw node triangles? I'm thinking of creating a large array of size POLYGON_DRAW_LIMIT (I'll define to be around 2000) which will store the model and triangle numbers to be drawn, and once I've completed culling I'll draw this list. Maybe I'll quickly sort the list according to the model number so I only have to call model texture and other calls once. Is this generally how it's done?
#154098 - elhobbs - Fri Apr 11, 2008 12:34 am
I think the answer really depends on the data. Are you switching textures a lot? Is the overhead of building a list and sorting it going to worth the savings gained by limiting the texture changes? sorting probably isn't needed, just a list for each texture. maybe a surf/model pointer on the texture and a next pointer on each surf/object that is cleared each frame. other threads indicate that the overhead of touching each object multiple times will probably slow things down - only testing will show which is best for your situation.
if you have not already done it you may want to take look at optimizing your frustum culling code. like only testing sides that need to be tested and optimizing your box side detection - like special cases for each of the 8 directions that your normal vectors may be pointing
#154104 - TwentySeven - Fri Apr 11, 2008 2:21 am
For a great example of optimized bbox culling, check the q3 source.
#154122 - M3d10n - Fri Apr 11, 2008 5:09 pm
I added boxtest()-based culling to my current project (angled overhead view) and it just made it slower. Maybe my scene isn't big enough to benefit from culling yet, but is boxtest() the fastest way to check a box against the frustum, or would be doing it by hand faster?
#154123 - silent_code - Fri Apr 11, 2008 7:12 pm
remember that boxtest() needs a few (few, ha!) cycles, so try to use this time and compute something *else*, while waiting for boxtest() to finish - that means between invoking it and retrieving the result. boxtest() runs in parallel, although i would check what restrictions (what hw can't be used while boxtesting) need to be kept in mind in that case.
such tests are best applicable on large scenes. if you have a rather small scene and everything is visible, you're just adding more instructions, thus reducing performance.
happy coding!
#154129 - Rajveer - Fri Apr 11, 2008 7:50 pm
My levels are huge compared to the player, they're all scaled down to fit -7.99 - 7.99 but I scale them up during calculations and rendering. Since my octree nodes are larger than v16 I can't use boxtest (hmm unless I scale my octree down too, then do my frustum culling and drawing within -7.99 - 7.99 and only do calculations and stuff scaled up for accuracy).
At the moment (and it's probably going to stay this way) each model can only have 1 texture, and levels are made up of multiple models. Taking your idea elhobbs of multiple lists, maybe I should make a list for each model...hmm thinking of ways I can do that.
OT: Ahh man, between how addictive Mario Kart Wii is and preparing for my damn job interviews next week, I shouldn't be thinking of this right now!
#154132 - a128 - Fri Apr 11, 2008 8:29 pm
| Rajveer wrote: |
My levels are huge compared to the player, they're all scaled down to fit -7.99 - 7.99 but I scale them up during calculations and rendering. Since my octree nodes are larger than v16 I can't use boxtest (hmm unless I scale my octree down too, then do my frustum culling and drawing within -7.99 - 7.99 and only do calculations and stuff scaled up for accuracy).
|
so if you scale the max. coord with 7.99f then the widht of the box is 7.99f*2 ....or is this wrong?
You must scale to 7.99/2 for boxtest because you have to push the width,heigt and depth into boxtest?!!!!!
#154137 - elhobbs - Fri Apr 11, 2008 9:33 pm
I render objects in texture order by having an object pointer on each texture and a next pointer on each object. I insert new objects at the head of the object list on each texture list as they pass visibilty tests. I then loop through the textures and render the objects then clear the object pointer on the texture for the next frame. I essentially stole the code from glquake1 which used this technique to deal with slow texture state changes on old 3d cards. I am not sure that it makes a big difference in rendering speed by not changing textures. The main benefit for me is that I am loading textures and objects from disk as needed into a cache. this way I only need to load each object or texture once per frame in the worst case.
#154164 - silent_code - Sat Apr 12, 2008 2:20 am
| Rajveer wrote: |
| OT: Ahh man, between how addictive Mario Kart Wii is and preparing for my damn job interviews next week, I shouldn't be thinking of this right now! |
good luck with your job interviews! :^D
#154390 - Rajveer - Tue Apr 15, 2008 4:31 pm
Cheers, both interviews went well :)
Now that I have some time I think I'm going to try a large array and changing the texture for every triangle, at least I can determine how quick this method will be. If not, then I'll implement something similar to your method elhobbs!
a128: Hmm, yeah you're right!
#154441 - TwentySeven - Wed Apr 16, 2008 9:44 am
Generally you're going to have CPU to burn, even if you're in the pathological worst case of needing to change texture every triangle.
I draw about 14 250 triangle models using about 5-10% cpu.
#154510 - M3d10n - Thu Apr 17, 2008 2:55 am
| Rajveer wrote: |
| My levels are huge compared to the player, they're all scaled down to fit -7.99 - 7.99 but I scale them up during calculations and rendering. Since my octree nodes are larger than v16 I can't use boxtest (hmm unless I scale my octree down too, then do my frustum culling and drawing within -7.99 - 7.99 and only do calculations and stuff scaled up for accuracy). |
The nice thing about the box test is that you can perform any scaling (and also translation and rotation) you would do to your models to it, that's what I do. All my meshes are normalized and store the scale values needed to render them at their original size. I just load that scale into the modelview matrix and do the boxtest() using a normalized box.
#154533 - Rajveer - Thu Apr 17, 2008 4:40 pm
So for each octree node I could transform and scale the modelview matrix according to the node's AABB, then perform the boxtest? That's cool, I'll look into using that! I'll have to do some testing between that method and my current one!
#154552 - Fling - Thu Apr 17, 2008 11:55 pm
Little bit of a problem here. I've taken the frustum calculation code that a128 posted but it doesn't quite work for me.. that is, when I try to test if say, a point, is inside the viewing frustum, the results are completely off. I feel like I'm pretty close, probably something really silly that I've missed.
Here's the relevant bits from the code I've got at the moment:
| Code: |
enum PLANE_SIDES
{
RIGHT = 0,
LEFT = 1,
BOTTOM = 2,
TOP = 3,
FAR = 4,
NEAR = 5
};
#define NUM_FRUSTUM_PLANES 6
typedef struct Plane
{
f32 a;
f32 b;
f32 c;
f32 d;
};
void Frustum::Calculate()
{
STACK_TRACE;
m4x4 clipMatrix;
glGetFixed(GL_GET_MATRIX_CLIP, &clipMatrix.m[0]);
viewing frustum
m_planes[RIGHT].a = clipMatrix.m[3] - clipMatrix.m[0];
m_planes[RIGHT].b = clipMatrix.m[7] - clipMatrix.m[4];
m_planes[RIGHT].c = clipMatrix.m[11] - clipMatrix.m[8];
m_planes[RIGHT].d = clipMatrix.m[15] - clipMatrix.m[12];
m_planes[LEFT].a = clipMatrix.m[3] + clipMatrix.m[0];
m_planes[LEFT].b = clipMatrix.m[7] + clipMatrix.m[4];
m_planes[LEFT].c = clipMatrix.m[11] + clipMatrix.m[8];
m_planes[LEFT].d = clipMatrix.m[15] + clipMatrix.m[12];
m_planes[BOTTOM].a = clipMatrix.m[3] + clipMatrix.m[1];
m_planes[BOTTOM].b = clipMatrix.m[7] + clipMatrix.m[5];
m_planes[BOTTOM].c = clipMatrix.m[11] + clipMatrix.m[9];
m_planes[BOTTOM].d = clipMatrix.m[15] + clipMatrix.m[13];
m_planes[TOP].a = clipMatrix.m[3] - clipMatrix.m[1];
m_planes[TOP].b = clipMatrix.m[7] - clipMatrix.m[5];
m_planes[TOP].c = clipMatrix.m[11] - clipMatrix.m[9];
m_planes[TOP].d = clipMatrix.m[15] - clipMatrix.m[13];
m_planes[FAR].a = clipMatrix.m[3] - clipMatrix.m[2];
m_planes[FAR].b = clipMatrix.m[7] - clipMatrix.m[6];
m_planes[FAR].c = clipMatrix.m[11] - clipMatrix.m[10];
m_planes[FAR].d = clipMatrix.m[15] - clipMatrix.m[14];
m_planes[NEAR].a = clipMatrix.m[3] + clipMatrix.m[2];
m_planes[NEAR].b = clipMatrix.m[7] + clipMatrix.m[6];
m_planes[NEAR].c = clipMatrix.m[11] + clipMatrix.m[10];
m_planes[NEAR].d = clipMatrix.m[15] + clipMatrix.m[14];
NormalizePlane(&m_planes[RIGHT]);
NormalizePlane(&m_planes[LEFT]);
NormalizePlane(&m_planes[BOTTOM]);
NormalizePlane(&m_planes[TOP]);
NormalizePlane(&m_planes[FAR]);
NormalizePlane(&m_planes[NEAR]);
}
BOOL Frustum::Test(Vector3 *vertex)
{
STACK_TRACE;
for (int p = 0; p < NUM_FRUSTUM_PLANES; ++p)
{
// Negative = behind plane, Positive = in front of plane
if ((mulf32(m_planes[p].a, vertex->x) +
mulf32(m_planes[p].b, vertex->y) +
mulf32(m_planes[p].c, vertex->z) +
(m_planes[p].d))
< inttof32(0))
return FALSE;
}
return TRUE;
}
inline void NormalizePlane(Plane *plane)
{
f32 length = sqrtf32(
mulf32(plane->a, plane->a) +
mulf32(plane->b, plane->b) +
mulf32(plane->c, plane->c)
);
plane->a = divf32(plane->a, length);
plane->b = divf32(plane->b, length);
plane->c = divf32(plane->c, length);
plane->d = divf32(plane->d, length);
} |
I'm guessing I've made a silly typo or something in one of the calculations that I'm just not seeing for whatever reason, but if anyone could provide any help I'd very much appreciate it!
#154562 - silent_code - Fri Apr 18, 2008 3:57 am
not a fix, but an idea: how about computing the reciprocal of the sqrt and multiplying instead of diving? i haven't tried it with fixed point, yet, so i'm just curious. ;^)
if you make some tests, please share the results! thanks!
also, that typedefine looks totally unnecessary, but i'm not a c/c++ lawyer. ;^) try giving the struct a typedef name, instead it being anonymous like this:
| Code: |
typedefine struct PLANE_STRUCT // PLANE_STRUCT isn't needed in that case
{
// ... data
} Plane; // here we go
|
or am i wrong and too much used to a certain practice? ("typedef old new;") i'm confued right now and it's 5:04 am... help please?
i remember it being the way around c's "struct Plane some_plane;", so one could declare variables in c++'s way "Plane some_plane;".
this means your version wouldn't be a problem in c++, but in c! iirc, that is. ;^)
Last edited by silent_code on Fri Apr 18, 2008 4:16 am; edited 5 times in total
#154563 - M3d10n - Fri Apr 18, 2008 4:04 am
| Rajveer wrote: |
| So for each octree node I could transform and scale the modelview matrix according to the node's AABB, then perform the boxtest? That's cool, I'll look into using that! I'll have to do some testing between that method and my current one! |
Just setup things as if you were going to draw the AABB, but use boxtest() instead (you can even rotate the boxes if you want). I think boxtest() actually sends a box made of quads down to the geometry pipeline and just checks if they are clipped or not, instead of drawing them.
#154586 - a128 - Fri Apr 18, 2008 4:10 pm
it must be <= 0
| Code: |
BOOL Frustum::Test(Vector3 *vertex)
{
STACK_TRACE;
for (int p = 0; p < NUM_FRUSTUM_PLANES; ++p)
{
// Negative = behind plane, Positive = in front of plane
if ((mulf32(m_planes[p].a, vertex->x) +
mulf32(m_planes[p].b, vertex->y) +
mulf32(m_planes[p].c, vertex->z) +
(m_planes[p].d))
<= inttof32(0)) //<= 0!!!!!!!!!!!!!!!!
return FALSE;
}
return TRUE;
}
|
What does STACK_TRACE?
#155098 - Fling - Fri Apr 25, 2008 12:13 am
Unfortunately that didn't do the trick. :(
STACK_TRACE is a macro that adds functions to my software debug stack tracing which gets displayed if an ASSERT fails. It actually doesn't do anything at the moment (the required #define isn't enabled, so it gets pre-processed to nothing), so that isn't affecting the results. It realistically isn't needed at all in that function, but is there more because it's become a habit of mine in my current project to immediately add it at the start of every function.
#155128 - a128 - Fri Apr 25, 2008 8:46 am
| Fling wrote: |
Unfortunately that didn't do the trick. :(
|
Here is my code...I have tested it some month ago...and it worked!
http://www.freewebtown.com/festival2005/frustumNDS.tgz
#155130 - a128 - Fri Apr 25, 2008 10:06 am
| Fling wrote: |
STACK_TRACE is a macro that adds functions to my software debug stack tracing which gets displayed if an ASSERT fails. It actually doesn't do anything at the moment (the required #define isn't enabled, so it gets pre-processed to nothing), so that isn't affecting the results. It realistically isn't needed at all in that function, but is there more because it's become a habit of mine in my current project to immediately add it at the start of every function. |
Oh yes thats a great idea
here is my implementation of STACK_TRACE....it just records the file+linenr. and prints the last traces if you call MY_ASSERT
| Code: |
#define DEPTH 8
char stacktrace[80*DEPTH];
unsigned stacktrace_counter=-1;
#include <string.h>
#define THIS_FILE ((strrchr(__FILE__, '/') ?: __FILE__ - 1) + 1)
#define STACK_TRACE \
if(stacktrace_counter<DEPTH) stacktrace_counter++; else stacktrace_counter=0;\
sprintf((char*)&stacktrace[stacktrace_counter*80],"%s %d\n",THIS_FILE,__LINE__);\
#define MY_ASSERT for(int i=0;i<=stacktrace_counter;i++) iprintf("%d.%s\n",i+1,(char*)&stacktrace[i*80]);assert(0);
|
Example :
| Code: |
void foo(){
STACK_TRACE;
//do some code here or even more STACK_TRACE
if(error)
MY_ASSERT;
}
|
NODE:
sprintf((char*)&stacktrace[stacktrace_counter*80],"%s %d\n",THIS_FILE,__LINE__);\
is bad code. it prevents iprintf() to work after you have called this method ...no idea why?!