Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / 3D Theory & Graphics / newbie...clip a point Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
Newbie

July 27, 1999, 04:34 PM

Hi all
a simple question...for a big problem
I've got a frustum defined by Znear,Zfar,left,right,top and bottom(I'm writing an OpenGL like interface fo my engine :)
well how to determinate if a 3Dpoint(x,y,z) is inside the frustum?(the fastest way...)

thanks you
Al

 
Luke

July 27, 1999, 04:43 PM



Newbie wrote:
>>Hi all
>>a simple question...for a big problem
>>I've got a frustum defined by Znear,Zfar,left,right,top and bottom(I'm writing an OpenGL like interface fo my engine :)
>>well how to determinate if a 3Dpoint(x,y,z) is inside the frustum?(the fastest way...)

Plug the X,Y,Z point into the plane equation where (A,B,C) is the normal of the plane and D is the distance away from the origin. This will give you distance away from the plane

distance = Ax + By + Cz - D

If distance is negitive the point is on the back side of the plane, and obviously if positive, its on the front side.

Make sure that your frustum planes are all aligned so that the front side of all the planes are pointing to the inside of the frustum. Then you can test the point against all the planes, and if you find a negitive distance, the point is outside.

This is the method that I use, except I have no Znear or Zfar. Just the left, right, top, bottom. Same rules still apply.

I won't claim that this is the fastest method, but it works.

Hope this helps

-Luke

 
Raven

July 27, 1999, 04:58 PM

>>I won't claim that this is the fastest method, but it works.
This is the fastest method. There can't be anything faster than this for true 3D planes

- Raven

 
Newbie

July 27, 1999, 05:20 PM



Luke wrote:
>>
>>
>>Newbie wrote:
>>>>Hi all
>>>>a simple question...for a big problem
>>>>I've got a frustum defined by Znear,Zfar,left,right,top and bottom(I'm writing an OpenGL like interface fo my engine :)
>>>>well how to determinate if a 3Dpoint(x,y,z) is inside the frustum?(the fastest way...)
>>
>>Plug the X,Y,Z point into the plane equation where (A,B,C) is the normal of the plane and D is the distance away from the origin. This will give you distance away from the plane
>>
>>distance = Ax + By + Cz - D
>>
>>If distance is negitive the point is on the back side of the plane, and obviously if positive, its on the front side.
>>
>>Make sure that your frustum planes are all aligned so that the front side of all the planes are pointing to the inside of the frustum. Then you can test the point against all the planes, and if you find a negitive distance, the point is outside.
>>
>>This is the method that I use, except I have no Znear or Zfar. Just the left, right, top, bottom. Same rules still apply.
>>
>>I won't claim that this is the fastest method, but it works.
>>
>>Hope this helps
>>
>>-Luke

thanks you a lot Luke!
but how to find the plane equation starting from left, right, top, bottom etc...?
I'm quite confused about it.

Al

 
Newbie

July 27, 1999, 05:20 PM



Luke wrote:
>>
>>
>>Newbie wrote:
>>>>Hi all
>>>>a simple question...for a big problem
>>>>I've got a frustum defined by Znear,Zfar,left,right,top and bottom(I'm writing an OpenGL like interface fo my engine :)
>>>>well how to determinate if a 3Dpoint(x,y,z) is inside the frustum?(the fastest way...)
>>
>>Plug the X,Y,Z point into the plane equation where (A,B,C) is the normal of the plane and D is the distance away from the origin. This will give you distance away from the plane
>>
>>distance = Ax + By + Cz - D
>>
>>If distance is negitive the point is on the back side of the plane, and obviously if positive, its on the front side.
>>
>>Make sure that your frustum planes are all aligned so that the front side of all the planes are pointing to the inside of the frustum. Then you can test the point against all the planes, and if you find a negitive distance, the point is outside.
>>
>>This is the method that I use, except I have no Znear or Zfar. Just the left, right, top, bottom. Same rules still apply.
>>
>>I won't claim that this is the fastest method, but it works.
>>
>>Hope this helps
>>
>>-Luke

thanks you a lot Luke!
but how to find the plane equation starting from left, right, top, bottom etc...?
I'm quite confused about it.

Al

 
Luke

July 27, 1999, 06:30 PM


>>but how to find the plane equation starting from left, right, top, bottom etc...?
>>I'm quite confused about it.
>>

Ok, i'm gonna get into a bunch of math, so if there is still something you don't understand or need clarification on, just post another message and i'll see what i can do.

Here's how I build my frustum. The basic idea is to set you top, right, bottom, and left planes so that they pass through the edges of the screen at the Z value where things are first visible after your perspective transformation.

I do perspective transformation like this:
xscreen = (point_x * perspective_scalar) / point_z + screen_middle_x
yscreen = (point_y * perspective_scalar) / point_z + screen_middle_y

(you can optimize this by getting rid of some of the divides....)

xscreen, yscreen is the point that ends up on the screen. (point_x, point_y, point_z) is your 3d point that has been transformed from world space into screen space. screen_middle_x and screen_middle_y are the center of the screen. All basic stuff. The perspective_scalar is a value that is used to set the field of view. It comes from this equation

perspective_scalar = screen_width / (2 * tan(field_of_view / 2))

screen_width is the width of the screen in pixels, and field_of_view is the size in degrees (radians actually) of your view. A good number is 85 degrees. After 90 degrees, you get a fish-eye effect on the screen.

So how does this help us? well it turns out the perspective_scalar is the z value of the first point that could possibly end up on the screen. So now we can build our frustum planes. And how do you do that, you might ask? I'll tell ya. You need 3 non-colinear points to define a plane. The equation to find a plane from 3 non-colinear points is as follows:

lets say we have points v1, v2, v3 (all of which have x,y,z components....)
we will define the plane as 3D vector p and distance d. point_x and point_y are
temporary 3D vectors.

point_x = v3 - v2
point_y = v1 - v2
p = cross_product( point_x, point_y )
normalize(p)
d = dot_product(v1, p)

so in the plane equation Ax + By + Cz - D = 0,
A = p.x
B = p.y
C = p.z
D = d

Not to insult you intelligence or anything, but just for clarity's sake:

dot_product(a, b) = a.x * b.x + a.y * b.y + a.z * b.z

cross_product(a, b) (c is returned)
c.x = (a.y * b.z) - (a.z * b.y)
c.y = (a.z * b.x) - (a.x * b.z)
c.z = (a.x * b.y) - (a.y * b.x)

normalize(p)
one_over_length = 1 / sqrt(p.x * p.x + p.y * p.y + p.z * p.z)
p.x = one_over_length * p.x
p.y = one_over_length * p.y
p.z = one_over_length * p.z

Now we can find these oh so useful and fashionable plane equations. Use the following points to build your frustum planes. half_x and half_y is your screen size in pixels divided by 2.

origin = (0,0,0)
lower_left = (-half_x, -half_y, perspective_scalar)
upper_left = (-half_x, half_y, perspective_scalar)
upper_right = (half_x, half_y, perspective_scalar)
lower_right = (half_x, -half_y, perspective_scalar)

Then the planes are build using the points:

left_plane = plane_equation( origin, lower_left, upper_left)
top_plane = plane_equation( origin, upper_left, upper_right)
right_plane = plane_equation( origin, upper_right, lower_right)
bottom_plane = plane_equation( origin, lower_right, lower_left)

If you plug the points into the plane equations as given in the order given, the planes will be in the correct orientation, with the front side of the plane facing the interior of the frustum.

Phew. Now after all that work, you have your frustum. =)

Why this setup is useful:
1) When you clip your faces to the frustum planes, you end up having part of no part of the face be off the screen after perspective transformation.
2) you can cull everything away that isn't in the frustum before you do any transformations on it. Do this by reversing your transformation you would normally do on the points, apply it to the points of the frustum, rebuild the planes, and clip and cull.

Happy Coding =)
-Luke

PLEASE NOTE: I personally use the y value as going positive into the screen, but I wrote this using z going into the screen, I think i swapped all my y's and z's correctly, but if anyone sees that i screwed up, please post a message. Thanks.

 
This thread contains 6 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.