Only rendering objects in a field of view.

[Pixel_Outlaw]

I'm sort of working on a very primitive 3D effect and I need some assistance.

I have a very basic camera object that has a field of view. The direction of the field of view is just a floating point variable in degrees. The field of view extends 90 degrees on both sides of the direction of the camera. I can calculate the direction to any object but my problem lies on finding out which objects are in the field of view. That is to say which objects are behind the player. I need to only render objects that are within 90 degrees of the camera's direction. I'm not quite sure how to tell if the angle to the camera from the object is within 90 degrees of the camera and therefore in the field of view. It seems like a simple subtraction but the degree system wraps back to 0.

So say if the camera was facing 0 degrees an object at 270 degrees SHOULD be rendered but it would not since 0-270 is not within 90 degrees of the direction by simply taking the difference with subtraction.

[Jim]

In this case, if you get an answer < 0, just add 360 and compare with 90.

Jim

[Pixel_Outlaw]

Thanks Jim! I'll try it when I get up. It is a bit of 2:23 am here time for bed. It seems so trivial but the abrupt change in the degree system makes some otherwise simple calculations hard.

[Shockwave]

Try something like this mate.

Code: [Select]

ANGLE=Int( ATan2 (PLAYER_X-TREE_X,PLAYER_Y-TREEY_Y) Mod 360)

To return the angle between camera and tree/whatever.

[Pixel_Outlaw]

Thanks again Shockwave!

This is just a sort of test to learn something new. I plan to do a distance check first to only draw close objects. Then if they are close enough I''ll do a field of view check.

[hellfire]

atan is rather expensive and unstable when one of the coordinates gets near zero (because of the division).
better construct two lines along the border of your camera and test on which side your object is (requires just a dot-product).
see point/line-distance.

[relsoft]

atan is rather expensive and unstable when one of the coordinates gets near zero (because of the division).
better construct two lines along the border of your camera and test on which side your object is (requires just a dot-product).
see point/line-distance.

Yeah, you could like use the normal projection for that.

Check if dot < 0 or > 0.

Code: [Select]


''Angle between vectors using the dot product formula
''relsoft 2k8

const PI as single= 3.141593


type vector2d
    x       as single
    y       as single
end type


function dot(byval a as vector2d,byval  b as vector2d) as Single
   return (a.x*b.x + a.y*b.y )
end function

sub normalize (byref v as vector2d)
    dim leng as single
    leng = sqr(v.x * v.x + v.y * v.y )
    v.x = v.x / leng
    v.y = v.y / leng
end sub

   
function get_2dnormal ( byval x1 as single, byval y1 as single,_
                        byval x2 as single, byval y2 as single,_
                        byval s as integer) as vector2d
   
    dim normal as vector2d
    if s then
        normal.x = -(y2-y1)  'negate to get the other normal
        normal.y =  (x2-x1)  'erase negatio here if you want the other
                                    'normal
    else
        normal.x =  (y2-y1)  'negate to get the other normal
        normal.y = -(x2-x1) 'erase negatio here if you want the other
                                    'normal
    end if
    normalize (normal)
    return normal
   
end function

function midpoint  ( byval x1 as single, byval y1 as single,_
                     byval x2 as single, byval y2 as single) as vector2d

dim p as vector2d
p.x = (x2+x1)/2
p.y = (y1+y2)/2
   
    return p
   
end function

function rad2deg(byval rad as single) as single
    return rad*180/PI
end function

dim pnt1 as vector2d     '1st point of line
dim pnt2 as vector2d     '2nd point of line

pnt1.x = 200
pnt1.y = 300

pnt2.x = 539
pnt2.y = 300

dim as vector2d p,d,v

p.x = pnt2.x - pnt1.x
p.y = pnt2.y - pnt1.y
normalize(p)


screen 18,32,2,0

screenset 1, 0

do
   
    dim as integer x, y, buttons
    GETMOUSE x, y,, buttons
   
    d.x = x
    d.y = y
   
    v.x = d.x - pnt1.x
    v.y = d.y - pnt1.y
   
    dim dot_projection as single
   
    dot_projection = dot(v,p)
   
   
       
    line(0,0)-(639,479),0,bf
   
   
   
    circle(d.x,d.y),5,rgb(255,255,255)
   
    circle(pnt1.x,pnt1.y),5,rgb(255,255,255)
    circle(pnt2.x,pnt2.y),5,rgb(0,255,255)
   
   
    '' vector representation
    '' vector to project
    line(pnt1.x,pnt1.y)-(d.x,d.y),rgb(255,255,0)
    '' vector from the 2 original points
    line(pnt1.x,pnt1.y)-(pnt2.x,pnt2.y),rgb(0,255,0)
   
   
    '' draw projection
    dim nv as vector2d
    dim n_proj as vector2d
   
   
    nv.x = p.x
    nv.y = p.y
    normalize(nv)
   
    n_proj.x = nv.x*dot_projection
    n_proj.y = nv.y*dot_projection
   
    line(pnt1.x,pnt1.y)-(pnt1.x + n_proj.x,pnt1.y + n_proj.y),rgb(255,0,0)
    circle(pnt1.x + n_proj.x,pnt1.y + n_proj.y),5,rgb(0,0,255)
   
    '' draw the perpendicular
    line(d.x,d.y)-(pnt1.x + n_proj.x,pnt1.y + n_proj.y),rgb(255,0,255),,12345
   
   
   
   
    dim as single mags = sqr(v.x^2 + v.y^2)*sqr(p.x^2 + p.y^2)
    locate 1,1
    print "Interactive dot product"
    print "relsoft 2k8"
    print
    print "angle between the two vectors:";rad2deg(acos(dot_projection/mags))
    print "length of projection(dot product) of v onto p:";dot_projection
    print "sign of the dot product:"; sgn(dot_projection)
   

    screensync
    sleep 1
    screencopy
   
           
loop until inkey<>""


end



[Shockwave]

I wish I had known that when I was converting battlezone a few years ago!

[TinDragon]

Oh battlezone, now there was a classic

If you think about how expensive it is to compute things like atan, even sin and cos to some extent even on todays hardware, you soon realize that back on the old 8bit computers and even the 16bit ones, they were for the most part not computing them every frame or loop but must have been using lots of lookup tables and other maths like rel's example. Really makes you wonder how they managed some of the stuff they did Damn clever folk is all I can say 

[rain_storm]

crossproduct works too

Code: [Select]

    crossproduct = (camX-objX)*(viewY-objY) - (viewX-objX)*(camY-objY)

that will return a negative value if the object is on one side of the line and a positive value if its on the other, which means if the left side returns a positive value and the right side returns a negative value the object is visible

dot product works on a similar theme but it checks the line perpendicular to the feild of view that points towards the object while crossproduct calculates area.

[JL235]

Am I right in thinking you'll be doing this check between the camera and every object? It doesn't sound that efficient. It might be better to store the objects in a data structure which will allow you to only need to iterate over a small section of the objects rather then all of them, and so perform less checks. I'm thinking of some sort of tree where each node holds one of these objects and they are connected according to their x or y co-ordinate. The axis to use alternates between nodes (so one node uses x, the next y, the next x, etc).

The idea is that by navigating the tree you could rule out whole sub-trees of objects (because that sub-tree is too far along the x or y axis to be in view). That way you might only be checking say half of the objects rather then all of them.

There was a specific type of tree I'm thinking of (maybe called a 2d-tree) but the best I can find on Wikipedia is the KD-Tree and the BSP Tree.

[hellfire]

There was a specific type of tree I'm thinking of (maybe called a 2d-tree)

Are you looking for quad-trees ?

[JL235]

There was a specific type of tree I'm thinking of (maybe called a 2d-tree)

Are you looking for quad-trees ?

No. Quad trees have children in all 4 directions, the '2d-tree' I was thiking of only has children in two directions and alternates between using the x or y axis for this direction (I saw it in a university lecture once). However the Quad tree is probably a better example from Wikipedia then my tree examples.

If I get time today then I'll draw a picture.

Edit: This is my 2d-tree and on the right I have overlaid a camera. Thinking about it I don't think the tree is as efficient as I thought because there are lots of nodes outside the cameras field of view that link to nodes that might be in the cameras field of view.

However the blue area contains nodes that are behind the camera and so their whole branch can be skipped.

Other trees might allow you to divide the area up better, but my main point is that by using some sort of tree you should be able to exclude large areas of the scene when rendering.