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.

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

' 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

'-------------------------

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$

'-------------------------

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

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

How i used to do it (when I was desparate) was to make a whole new class for each polygon (SLOW!!!). so, thanks again.

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.

All Courses

From novice to tech pro — start learning today.

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.