View Full Version : Problems with frustum...

13-01-2006, 05:19 PM
Hi all,
I am having some problems with my frustum class, it cuts out a lot of triangles that are in view and leaves some that are not in view :(

Heres 2 screenshots, the first is without the frustum culling and the 2nd with:

with in the model rendering i have:

For j := 0 To nTriangles-1 Do
For k := 0 To 2 Do
With Triangles[TriangleIndices[j]] Do
Tri[k] := Vertices[VertexIndices[k]].Position;
If Not Frustum.TriangleInFrustum(Tri[0], Tri[1], Tri[2]) Then Continue;

function TxnFrustum.TriangleInFrustum(v1,v2,v3: TVertex3f): Boolean;
Result := (PointInFrustum(v1)) Or (PointInFrustum(v2)) Or (PointInFrustum(v3));

function TxnFrustum.PointInFrustum(Point: TVertex3f): Boolean;
i: Integer;
For i := 0 To 5 Do
If (fFrustum[i][0]*Point[0]+fFrustum[i][1]*Point[1]+fFrustum[i][2]*Point[2]+fFrustum[i][3] <= 0) Then
Result := False;
Result := True;

I have probably missed something out (always the way) :s

13-01-2006, 06:13 PM
because your tri-frustum intersection is wrong. a triangle with every point out of the frustum can still be on screen. Or maybe your frustum plane extraction is wrong?
Personally i wouldn't bother to cull each triangle in the scene and rather go with a spatial culling algorithm

13-01-2006, 06:14 PM
Point in frustum test looks ok, triangle in frustum is definitely wrong, triangles vertices might be outside of frustum, but part of the triangle still inside it. From the pictures I guess you change perspective matrix after extracting the frustum.
Not related to problem:
Don?_Tt try to cull all triangles, you?_Tre video drivers most likely do that for you :wink: it makes more sense to cull large polygon groups with their bounding boxes or any king of partitions. And immediate mode is evil.

14-01-2006, 01:26 AM
Yeah my graphics card does do it for me, i just thought it might be an easy way to sort the FPS out, when the character looks out to empty space of course the FPS is really good, but screws up all the animations and everything time based...

I tried looking at using threads to control all the timers but doesnt make any differences...

Im not sure which to use octree or bsp.. the game involves internal and external scenes, at a universe scale, so there will be huge amounts of geometry data...??

14-01-2006, 10:29 AM
If you need lots of geom then you should go with an octree. Bsp will make too many splits and will become huge in memory and cpu consumption

14-01-2006, 03:43 PM
Cool, thanx, i will look in to octrees :)

Is there any way i can use timers with out them being effected by the FPS?
Cause it looks stupid when the animation goes from steady to hyper speed lol

14-01-2006, 04:22 PM
function FexDx_frustumTriangleInside(_v1, _v2, _v3 : t_Vec;
_f : tFrustum): boolean;

// Warning: This function is very fast but in fact it is checking the whole rectangular area
// conformed by the 3 vertices.
// Also it will return TRue if the triangle is seen from behind.

var _i : longint;

for _i := 0 to 5 do
if (_f[_i].a * _v1[0] + _f[_i].b * _v1[1] + _f[_i].c * _v1[2] + _f[_i].d > 0) then continue;
if (_f[_i].a * _v2[0] + _f[_i].b * _v2[1] + _f[_i].c * _v2[2] + _f[_i].d > 0) then continue;
if (_f[_i].a * _v3[0] + _f[_i].b * _v3[1] + _f[_i].c * _v3[2] + _f[_i].d > 0) then continue;
// Outside
Result := false;
Result := true;

In my very personal opinion, i think the function "frustumTriangleInside" is a must in a 3d render engine; i found that in most forum the experts guys tend to advice assuming that one is using lastest expensive hardware from today which allmost do everything for you (culling, lighting, depth test, etc) so they consider that doing some pre-processing at triangle basis or doing some calcs your self is stupid, however for games that are going to be posted on internet (so the whole world has acces to it) i think programmers should consider not to program for lastest harware.

I am not saying that you have to check at triangle basis every triangle of your scene, I am agree that you must implement in your program an algorithm that reject as much triangles as posibles in just few calls, that can be done using for example rooms+partals, or BSp trees, or Quadtrees or octrees (it will depend of your type of game), you can also use shperes or boxes for bound your objects, movables, and then doing "Frustumspherinside" and "frustumboxinside" for totally reject the whole object in one call if none of his triangles are visible.

Once you have rejected everythign that obviusly it is too much to the left, to the right and behind of the camera then you have the scene/objects that are in front of you and are visibles or partial-visible but...still at this point you have some few triangles in the scene/objects at to the left/right/behind that still not visible, or they are in front of you but from his back (needs backculling), or are infront of you but they are too far away in the depth. At this point seems that most people advice "go ahead and send this batch and let videocard handle culling and depth and everithing..", but for me at this point i found hard not to go triangle by triangle doing some pre-proccesing; so for every triangle i do:

- I found that in my non-expensive videocard, i get better perfomance if i cull my self those nonvisible triangles using frustumtriangleinside and also culling those triangles which are in front of the camera but seen from behind; so i reject this triangle if it is not visible. if it is visible i go to the next step..

- checking if the triangle is suppost to be rendered with alpha effect (translucent), those triangle need to be rendered from back to front or the effect will not looks correct, and for doing that you need to calc the distance from the triangle to the camera first.

- Non ALPHA triangles dosent need to be sorted if they are going to be rendered turning ON the Zbuffer test, but i found that in my crapy videocard it is faster to have zbuffer Off, and render the triangles from back to front; i need to do that for alpha triangles anyway so why not include non alpha triangles?. So i calc the distance from the camera too.

- Becose i already have calculated the triangle- from-camera distance, from prior step i can also use that value for doing haze effect, (also called distant fog), this mean i colored the triangle vertices based on how far it is from the camera, so far objects are going to be seen using a smooth distance blend color. If the traingle is too far away i can decide to reject this triangle, the haze effect will hide depth "hole".

- Also knowing how far the triangle is from the camera, we can here implement a mipmaping texture feature, changing the triangle texture by a low resolution texture.

- end Lop.

After that loop i have just the real visible triangles in the scene, but before rendering we need to sort them, I am using the quicksort algorith, and i sort all the triangles at least by distance+texture/material; i also calc into the triangle list the amount of triangles of correlative texture/material so i can batch then by block.

Ok, thats it, i am sorry for doing a kind article thing instead and replying post things, :shock:

good luck.


14-01-2006, 06:51 PM
Thats great thanx tp... i will have a look at that asp..
Just curious, whats colours and distances would i use for the haze effects?

I want to make faces and objects go translucent when they are in between the camera and character.. this shouldnt effect this..?

14-01-2006, 08:57 PM
I'v implemented the code you gave me, i works with most positions, except it takes some triangles near the edge of the viewport and on some views it takes a lot of triangles.. heres some screens:



14-01-2006, 09:00 PM
lol typical, i found out what was causing the problem right after i posted :s
It was because i was translating the matrix after i updated the frustrum :s


14-01-2006, 09:03 PM
It could look like your frustum plane extraction is malfunctioning. To me it looks like the near plane is too long away. i suppose you don't frustum cull the character?

Edit: Okay i was close to :P Good to hear you your problem is solved

14-01-2006, 09:23 PM
No, i dont frustum cull the character, didnt see any need to..?