Link to home
Start Free TrialLog in
Avatar of madmanmarkau
madmanmarkau

asked on

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.
Avatar of cybermike3d
cybermike3d

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



Avatar of madmanmarkau

ASKER

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.
ASKER CERTIFIED SOLUTION
Avatar of cybermike3d
cybermike3d

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
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.