Dark Bit Factory & Gravity
PROGRAMMING => General coding questions => Topic started by: Pixel_Outlaw on March 16, 2009
-
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.
-
In this case, if you get an answer < 0, just add 360 and compare with 90.
Jim
-
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.
-
Try something like this mate.
ANGLE=Int( ATan2 (PLAYER_X-TREE_X,PLAYER_Y-TREEY_Y) Mod 360)
To return the angle between camera and tree/whatever.
-
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.
-
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 (http://mathworld.wolfram.com/Point-LineDistance2-Dimensional.html).
-
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 (http://mathworld.wolfram.com/Point-LineDistance2-Dimensional.html).
Yeah, you could like use the normal projection for that.
Check if dot < 0 or > 0.
''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
-
I wish I had known that when I was converting battlezone a few years ago!
-
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 :updance:
-
crossproduct works too
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.
-
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 (http://en.wikipedia.org/wiki/Kd-tree) and the BSP Tree (http://en.wikipedia.org/wiki/BSP_tree).
-
There was a specific type of tree I'm thinking of (maybe called a 2d-tree)
Are you looking for quad-trees (http://en.wikipedia.org/wiki/Quadtree) ?
-
There was a specific type of tree I'm thinking of (maybe called a 2d-tree)
Are you looking for quad-trees (http://en.wikipedia.org/wiki/Quadtree) ?
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.
(http://diablosdevil.googlepages.com/2d-tree.jpg)
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.