Hit test (ray trace?)

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.
Who is Participating?

Commented:
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) .

ixdif = tarx - eyex
iydif = tary - eyez
getcord
horizofsetangle = itnang
ixdif = itargetrange
iydif = tarz - eyey
getcord
vertoffsetangle = itnang
targetrange = itargetrange

getcord:

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

intsctx = eyeX + Sin(hma / rad) * Sin(vma / rad)* range
intscty = eyeY + Cos(vma / rad) * range
intsctz = eyez + Cos(hma / rad) * Sin(vma / rad)* range

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

Commented:
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 ...

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...
0

Commented:
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"

leng1 = SQR((x1 - x2) ^ 2 + (y1 - y2) ^ 2)
leng2 = SQR((xx - x2) ^ 2 + (yy - y2) ^ 2)
leng3 = SQR((xx - x1) ^ 2 + (yy - y1) ^ 2)
ratio1 = ((leng2 + leng3) - leng2) / (leng2 + leng3)
ratio2 = ((leng2 + leng3) - leng3) / (leng2 + leng3)
px1 = (x2 * ratio1 + x1 * ratio2)
py1 = (y2 * ratio1 + y1 * ratio2)
dx1 = SQR((px1 - x3) ^ 2 + (py1 - y3) ^ 2)
dx2 = SQR((xx - x3) ^ 2 + (yy - y3) ^ 2)
CIRCLE (px1, py1), 7, 7
IF dx1 < dx2 THEN txt\$ = "OUTSIDE"

leng1 = SQR((x3 - x2) ^ 2 + (y3 - y2) ^ 2)
leng2 = SQR((xx - x2) ^ 2 + (yy - y2) ^ 2)
leng3 = SQR((xx - x3) ^ 2 + (yy - y3) ^ 2)
ratio1 = ((leng2 + leng3) - leng2) / (leng2 + leng3)
ratio2 = ((leng2 + leng3) - leng3) / (leng2 + leng3)
px1 = (x2 * ratio1 + x3 * ratio2)
py1 = (y2 * ratio1 + y3 * ratio2)
dx1 = SQR((px1 - x1) ^ 2 + (py1 - y1) ^ 2)
dx2 = SQR((xx - x1) ^ 2 + (yy - y1) ^ 2)
CIRCLE (px1, py1), 7, 14
IF dx1 < dx2 THEN txt\$ = "OUTSIDE"

leng1 = SQR((x1 - x3) ^ 2 + (y1 - y3) ^ 2)
leng2 = SQR((xx - x3) ^ 2 + (yy - y3) ^ 2)
leng3 = SQR((xx - x1) ^ 2 + (yy - y1) ^ 2)
ratio1 = ((leng2 + leng3) - leng2) / (leng2 + leng3)
ratio2 = ((leng2 + leng3) - leng3) / (leng2 + leng3)
px1 = (x3 * ratio1 + x1 * ratio2)
py1 = (y3 * ratio1 + y1 * ratio2)
dx1 = SQR((px1 - x2) ^ 2 + (py1 - y2) ^ 2)
dx2 = SQR((xx - x2) ^ 2 + (yy - y2) ^ 2)
CIRCLE (px1, py1), 7, 13
IF dx1 < dx2 THEN txt\$ = "OUTSIDE"

PRINT txt\$

'---------------------------------------------------end of calculatons

g\$ = ""
WHILE g\$ = ""
g\$ = INKEY\$

WEND
g\$ = RIGHT\$(g\$, 1)
IF g\$ = "K" THEN xx = xx - 1
IF g\$ = "M" THEN xx = xx + 1
IF g\$ = "H" THEN yy = yy - 1
IF g\$ = "P" THEN yy = yy + 1

CLS
LOCATE 1, 1

IF g\$ = "r" OR g\$ = "R" THEN GOSUB makenewtriangle

WEND
END

makenewtriangle:

x1 = RND(1) * 400
y1 = RND(1) * 300

x2 = RND(1) * 400
y2 = RND(1) * 300

x3 = RND(1) * 400
y3 = RND(1) * 300

RETURN

0

Author Commented:
I actually wanted to do a hit test for arbritrary triangles (that's what 3-vertex polygons are). And the line must be able to go in any direction.

Also, doing a loop is MUCh too slow. Sorry.
0

Author 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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.