Hi. What's a FAST way of determining if a line between two points hits a polygon in a list of 3-vertex polygons. Also, hot to tell the 3D coords of the point of "impact". Thx.
Well, I dont know what language or platform u r using but this is a possible VB solution.
(for rendering ..... not necessary for seeking...
What you need to do is specify the co ordinate of the 'eye' Then, you have to determine the position of the target. The target will be a square plane. Then, you must do a loop
ie for a 800 x 600 image would go something like this ... and this code assumes a straightline (90 / 180 / 270 / 360) orientation with no angular translations.... it should give you the idea. Assume the target frame is 4 real units wide by say 3 realunits high. (This is the projection target) The rendered object is between the eye and the projection target. )
for y = topoftarget to bottomoftarget step (bottomoftarget - topoftarget)/600
for x = leftoftarget to rightoftarget step (rightoftarget-leftoftarget)/ 800
next you take your three points and average them ...
Now, if you translate the vertical/horizontal angle offset into a pixel deviation you can put a pixel on the screen above / below / left / right of the centre of the screen. If you want to include angular translations, do the same for the centre of the projection plane and then just subtract the two angles.
Now, you have the distance to the polygon, and its angle above/below/left/right of the centre of the projection axis. Next you 'bias' the avearge. Lets say your ray moved through the triangle, and it was half way between the centre of the trinagle and vertex number 1 then, the co ordinate would be say 150% of vertex 1 + 75% of vertex2 + 75% of vertex3's x,y,z co ords. Imagine 3lines fron the centre of the triangle to each of the three vertices. The length of that line represents 100% Now, put a point closer to vertices number one, and again draw three lines. You will see that the line between this point and vertex 1 is shorter. Therefore bias is linelengthnew / linelengthaverage ... This will give you the exact x,y,z co ord of the intersection ... and you will have the angle and range.
Placing an object at that co ord uses the reverse maths ...
ha = horizontal offset angle
va = vertical offset angle
'dim itargetrange, ixdif, iydif, itgan, itgang, ixn, iyn, ina
itargetrange = Sqr(ixdif ^ 2 + iydif ^ 2)
If iydif <> 0 Then itgan = Atn(ixdif / iydif) * 57.2958
If iydif = 0 And ixdif = 0 Then itgan = 0: itgang = 0
If iydif = 0 And ixdif < 0 Then itgan = 270
If iydif = 0 And ixdif > 0 Then itgan = 90
itgang = itgan
If iydif < 0 Then itgang = 180 + itgan
If ixdif < 0 And iydif > 0 Then itgang = 360 + itgan
itnang = ina + itgang
If itnang > 360 Then itnang = itnang - 360
If itnang < 0 Then itnang = itnang + 360
You can also look at the DX8 funtion called INTERSECT ... does the same ... but, ive given a the math behind the function ... But you will need some of the above math to determine in which direction to point the ray. ie, if you want a specific triangle, use the above ... if u want a tringle that is encountered by a ray ... use the command below. You can speed up the above by converting some of the functions to tables in an x/y/z matrix ... but it is pretty fast.
D3DX8.Intersect
Determines if a ray intersects with a mesh.
object.Intersect( _
MeshIn As D3DXMesh, _
RayPos As D3DVECTOR, _
RayDir As D3DVECTOR, _
retHit As Long, _
retFaceIndex As Long, _
retU As Single, _
retV As Single, _
retDist As Single)
Parts
object
Object expression that resolves to a D3DX8 object.
MeshIn
D3DXMesh object, representing the mesh to be tested.
RayPos
D3DVECTOR type, specifying the origin coordinate of the ray.
RayDir
D3DVECTOR type, specifying the direction of the ray.
retHit
If the ray intersects a triangular face on the mesh, this value is set to TRUE. Otherwise, this value is set to FALSE.
retFaceIndex
Index value of the face closest to the ray origin, if retHit is TRUE.
retU
Barycentric hit coordinate.
retV
Barycentric hit coordinate.
retDist
Ray intersection parameter distance.
Hope this helps, give a shout if u need more elaboration...
Once you have converted the angular offsets to x, y co ords, you can then establish if a ray will pass through a triangle or not. I put together this little qbasic program to show the math. It will draw a triangle on the screen and then tell you if a point falls inside or outside the triangle. You can move the point around with the arrow keys. This is the fastest way I know of. Transpose the vertical and horizontal angular offsets to x/y values and assign the three points as shown below to x1,y1 / y2,y2 / x3,y3 and the angular offset of the ray to xx,yy
' Qbasic program to test if a point falls within a traingle.
' www.cybermike3d.co.za
' mike@cybermike3d.co.za
SCREEN 9, 1
x1 = RND(1) * 400
y1 = RND(1) * 300
x2 = RND(1) * 400
y2 = RND(1) * 300
x3 = RND(1) * 400
y3 = RND(1) * 300
xx = 200
yy = 150
WHILE g$ <> CHR$(27)
LINE (x1, y1)-(x2, y2), 15
LINE (x2, y2)-(x3, y3), 14
LINE (x3, y3)-(x1, y1), 13
LINE (x1, y1)-(xx, yy), 8
LINE (x2, y2)-(xx, yy), 8
LINE (x3, y3)-(xx, yy), 8
CIRCLE (xx, yy), 10, 10
'---------------------------------- this is the calculation part
txt$ = "INSIDE"
Right, forget about the loop ... like i said above ... only use a loop if you want to render to a screen ... like a scanline raytrace renderer.
If you have a ray passing through space, it must have a x,y,z for the starting point and a direction specified as an x angle and a y angle ... where the x angle is the number of degrees left or right of the environemnts 'north' and the y is the number of degrees above or below the 'horizon'. If you do not have a direction for your ray, but a target co ordinate consisting of an x,y,z, you must resolve the angles first ... the routine below will translate the differences between the eye and targets x,y,x co cords and will return a value consisting of a vertical and horizontal offset in degrees plus a range (x',y',r) .
itargetrange = Sqr(ixdif ^ 2 + iydif ^ 2)
If iydif <> 0 Then itgan = Atn(ixdif / iydif) * 57.2958
If iydif = 0 And ixdif = 0 Then itgan = 0: itgang = 0
If iydif = 0 And ixdif < 0 Then itgan = 270
If iydif = 0 And ixdif > 0 Then itgan = 90
itgang = itgan
If iydif < 0 Then itgang = 180 + itgan
If ixdif < 0 And iydif > 0 Then itgang = 360 + itgan
itnang = ina + itgang
If itnang > 180 Then itnang = itnang - 360
If itnang < -180 Then itnang = itnang + 360
After you have tanslated the x,y,z realspace co cords of the 3 vertices into an angular x',y' and range value you can project x',y' onto an imaginary screen and throw away the range (for now)
If you have a ray, it must have a starting point in space. This is called the eye and it has an x,y,z co ordinate. Now, this ray(eye) must 'look' in a specific direction. This direction is specified either as a target co-cordinate or as an angular offset on the x,y axis. In other words, if your eye is looking due north at the horizon, the ray projection offset is 0 on the x' axis and 0 on the y' axis. in this case the eye will be at 0,0,0 and the target will be at say 0,0,10. and your x',y',r is 0',0',10
Then you ave your arbritary triangle. Lets say its coords are 5,0,10 : -5,-5,10 : -5,5,10. In this case, coord 1, is 45 degrees right, co ord 2 is 45 degrees left, and 45 degrees down, co ord 3 is 45 left and 45 degrees up of the ray. So, the coords translate into 45',0 : -45',-45' : -45',45' and the angular offset of your ray is 0,0. Now, if you use the sample program I gave you and use the values above for x1,y1:x2,y2:x3,y3 and xx,yy for the direction of the ray you will see that the ray passes inside the triangle. Make the rays target 10,0,0 and the angle of the ray will be 90 degrees to the right( 90':0':10), and 0 degrees above the horizon and the ray will pass outside the triangle.
When dtermining if a ray passes through an object, one has to have the point of origin of the ray, then, you have to get the direction of the ray, specified as a number of degrees left or right of north (in the range -180 to + 180) and above or below the horizon (+90 = straight up, -90 is straight down) Then get the direction to the target vertex ... Once you have the direction of the ray, and the direction of the points of your triangle (in both horizontal and vertical angular offsets) you use the algorithm in the sample qbasic program to determine if the ray is passing inside or outside the triangle.
The above algorithm works through the process of biased averaging. Ie. the position of the reference co ordinate along an axis is a percentage of cord 1 plus a percentage of cord 2 ... If you want the intersection distance, take the sample algorithm and use the distance paramater (range) and the range is say 10% of the range of coord1 and 90 % of the range of co cord 2 ... repeat the same for all three sides,sum the 3 values and dived by 3 and you will have the distance to the point at which the ray intersects the triangle. If you have the range and the x and y offset angles, you can then regenerate the x,y,z from the x':y':r using the algorithm
Like I aid, I dont know if there is a faster way of doing this ... but I use it and its plenty fast enuff for me ... if there is a better way ...I would like to see it.
Of course, you would need to test each polygon, but the above will indicate if a ray (line) between two points will intersect the face of an arbritary triangle and it will return the range from the eye to the intersection, from which one can generate the x:y:z co ords of the intersection.
0
madmanmarkauAuthor Commented:
I get it now... thanks.
How i used to do it (when I was desparate) was to make a whole new class for each polygon (SLOW!!!). so, thanks again.
0
Featured Post
Work with freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely, and get projects done right.
(for rendering ..... not necessary for seeking...
What you need to do is specify the co ordinate of the 'eye' Then, you have to determine the position of the target. The target will be a square plane. Then, you must do a loop
ie for a 800 x 600 image would go something like this ... and this code assumes a straightline (90 / 180 / 270 / 360) orientation with no angular translations.... it should give you the idea. Assume the target frame is 4 real units wide by say 3 realunits high. (This is the projection target) The rendered object is between the eye and the projection target. )
for y = topoftarget to bottomoftarget step (bottomoftarget - topoftarget)/600
for x = leftoftarget to rightoftarget step (rightoftarget-leftoftarge
next you take your three points and average them ...
posxave = (posx1 + posx2 + posx3)/3
posyave = (posy1 + posy2 + posy3)/3
poszave = (posz1 + posz2 + posz3)/3
ixdif = posxave - eyex
iydif = poszave - eyez
getcord
horizofsetangle = itnang
ixdif = itargetrange
iydif = posyave - eyey
getcord
vertoffsetangle = itnang
targetpolygonrange = itargetrange
Now, if you translate the vertical/horizontal angle offset into a pixel deviation you can put a pixel on the screen above / below / left / right of the centre of the screen. If you want to include angular translations, do the same for the centre of the projection plane and then just subtract the two angles.
Now, you have the distance to the polygon, and its angle above/below/left/right of the centre of the projection axis. Next you 'bias' the avearge. Lets say your ray moved through the triangle, and it was half way between the centre of the trinagle and vertex number 1 then, the co ordinate would be say 150% of vertex 1 + 75% of vertex2 + 75% of vertex3's x,y,z co ords. Imagine 3lines fron the centre of the triangle to each of the three vertices. The length of that line represents 100% Now, put a point closer to vertices number one, and again draw three lines. You will see that the line between this point and vertex 1 is shorter. Therefore bias is linelengthnew / linelengthaverage ... This will give you the exact x,y,z co ord of the intersection ... and you will have the angle and range.
Placing an object at that co ord uses the reverse maths ...
ha = horizontal offset angle
va = vertical offset angle
objx = eyeX + Sin(hma / rad) * Sin(vma / rad)* range
objy = eyeY + Cos(vma / rad) * range
objz = eyez + Cos(hma / rad) * Sin(vma / rad)* range
'------------ this routine is called GETCORD
'dim itargetrange, ixdif, iydif, itgan, itgang, ixn, iyn, ina
itargetrange = Sqr(ixdif ^ 2 + iydif ^ 2)
If iydif <> 0 Then itgan = Atn(ixdif / iydif) * 57.2958
If iydif = 0 And ixdif = 0 Then itgan = 0: itgang = 0
If iydif = 0 And ixdif < 0 Then itgan = 270
If iydif = 0 And ixdif > 0 Then itgan = 90
itgang = itgan
If iydif < 0 Then itgang = 180 + itgan
If ixdif < 0 And iydif > 0 Then itgang = 360 + itgan
itnang = ina + itgang
If itnang > 360 Then itnang = itnang - 360
If itnang < 0 Then itnang = itnang + 360
You can also look at the DX8 funtion called INTERSECT ... does the same ... but, ive given a the math behind the function ... But you will need some of the above math to determine in which direction to point the ray. ie, if you want a specific triangle, use the above ... if u want a tringle that is encountered by a ray ... use the command below. You can speed up the above by converting some of the functions to tables in an x/y/z matrix ... but it is pretty fast.
D3DX8.Intersect
Determines if a ray intersects with a mesh.
object.Intersect( _
MeshIn As D3DXMesh, _
RayPos As D3DVECTOR, _
RayDir As D3DVECTOR, _
retHit As Long, _
retFaceIndex As Long, _
retU As Single, _
retV As Single, _
retDist As Single)
Parts
object
Object expression that resolves to a D3DX8 object.
MeshIn
D3DXMesh object, representing the mesh to be tested.
RayPos
D3DVECTOR type, specifying the origin coordinate of the ray.
RayDir
D3DVECTOR type, specifying the direction of the ray.
retHit
If the ray intersects a triangular face on the mesh, this value is set to TRUE. Otherwise, this value is set to FALSE.
retFaceIndex
Index value of the face closest to the ray origin, if retHit is TRUE.
retU
Barycentric hit coordinate.
retV
Barycentric hit coordinate.
retDist
Ray intersection parameter distance.
Hope this helps, give a shout if u need more elaboration...