Heya :)
This snippet may or may not interest you  :P
The following (working, tested !!) code returns TRUE or FALSE for whether a given 3D Point is within the Bounds of (and on the Plane of) the given 3D Triangle.
It ONLY works if the test point is on the triangle plane, but if that point was the result of an initial "plane intersection" test, then we can be sure this secondary "geometry bounds" test will work correctly.



;Test for whether intersection point (on Plane) is within actual triangle boundary
;This is achieved by using acos to measure the angles formed between pairs of
;triangle edges and the testpoint, and totalling the resulting angles.
;Points inside the triangle result in an angle very close to 2pi radians (360 degrees).
;It should be exactly so, but floating point error must be considered.
;We allow a small epsilon (fudging margin).
;If it's "very close to 2pi" we return TRUE, otherwise we return FALSE.
;Sadly, this method ONLY works for points on the Plane of the subject Triangle :(
;Happily, our Plane Intersection Point is always guaranteed to be on the Plane :)

IsPointInTriangle proc uses esi edi pPoint, pV0, pV1, pV2
local vec0:Vec3
local vec1:Vec3
local vec2:Vec3
local ftemp:REAL4
local ftemp0:REAL4
local ftemp1:REAL4
local ftemp2:REAL4

;    vec0 = Normalize( vtxPoint - vtx0 );
mov esi, pPoint
mov edi, pV0
fld .Vec3.X
fsub .Vec3.X
fstp vec0.X
fld .Vec3.Y
fsub .Vec3.Y
fstp vec0.Y
fld .Vec3.Z
fsub .Vec3.Z
fstp vec0.Z
invoke Vec3Normalize, addr vec0

;    vec1 = Normalize( vtxPoint - vtx1 );
mov edi, pV1
fld .Vec3.X
fsub .Vec3.X
fstp vec1.X
fld .Vec3.Y
fsub .Vec3.Y
fstp vec1.Y
fld .Vec3.Z
fsub .Vec3.Z
fstp vec1.Z
invoke Vec3Normalize, addr vec1

;    vec2 = Normalize( vtxPoint - vtx2 );
mov edi, pV2
fld .Vec3.X
fsub .Vec3.X
fstp vec2.X
fld .Vec3.Y
fsub .Vec3.Y
fstp vec2.Y
fld .Vec3.Z
fsub .Vec3.Z
fstp vec2.Z
invoke Vec3Normalize, addr vec2

invoke Vec3Dot, addr vec0, addr vec1
fst ftemp      ;This fpu stall is because we need the DotProduct result
fld ftemp      ;to be in st(0) and also in st(1) in order for facos() to work correctly
facos
fstp ftemp0

invoke Vec3Dot, addr vec1, addr vec2
fst ftemp
fld ftemp
facos
fstp ftemp1

invoke Vec3Dot, addr vec2, addr vec0
fst ftemp
fld ftemp
facos
fstp ftemp2

fld ftemp0
fadd ftemp1
fadd ftemp2
fldpi
fmul fp2
fsub
fabs
fcomp fpepsilon ;small floating point value like 0.001f
__FJGE @F
return TRUE
@@:
return FALSE
IsPointInTriangle endp


Have a nice day :)
Posted on 2005-04-25 11:17:43 by Homer
Perhaps this will run a bit faster:

IsPointInTriangle proc uses ecx pPoint, pV0, pV1, pV2
local vec0:Vec3
local vec1:Vec3
local vec2:Vec3
local ftemp:REAL4

assume eax:ptr Vec3
assume ecx:ptr Vec3

;----[ cache vtxPoint ]----------\
mov ecx,pPoint
fld .Z
fld .Y
fld .X
;--------------------------------/

; Y Z pX pY pZ

;----[  vec0 = Normalize( vtxPoint - vtx0 ); ]------------\
mov eax,pV0
fld .Z
fsub ST,ST(3)
fld .Y
fsub ST,ST(3)
fld .X
fsub ST,ST(3)
fstp vec0.X
fstp vec0.Y
fstp vec0.Z
invoke Vec3Normalize,addr vec0
;---------------------------------------------------------/

;----[  vec1 = Normalize( vtxPoint - vtx1 ); ]------------\
mov eax,pV1
fld .Z
fsub ST,ST(3)
fld .Y
fsub ST,ST(3)
fld .X
fsub ST,ST(3)
fstp vec1.X
fstp vec1.Y
fstp vec1.Z
invoke Vec3Normalize,addr vec1
;---------------------------------------------------------/

;----[  vec2 = Normalize( vtxPoint - vtx2 ); ]------------\
mov eax,pV2
fld .Z
fsub ST,ST(3)
fld .Y
fsub ST,ST(3)
fld .X
fsub ST,ST(3)
fstp vec2.X
fstp vec2.Y
fstp vec2.Z
invoke Vec3Normalize,addr vec2
;---------------------------------------------------------/

;-----[ free the vtxPoint cache ]---\
assume eax:nothing
assume ecx:nothing

fdecstp ; pop vtxPoint.X to nothing
fdecstp ; pop vtxPoint.Y to nothing
fdecstp ; pop vtxPoint.Z to nothing
;-----------------------------------/

;-----------[ Do dot-products ]----------------\
invoke Vec3Dot,addr vec0,addr vec1
fld ST
facos ; a macro that needs ST(0) = ST(1)
; note: ST(0) now contains the angle1 value

invoke Vec3Dot,addr vec0,addr vec1
fld ST
facos  ; ST(0) contains the angle2 value
fadd  ; angle1+= angle2, discard angle2

invoke Vec3Dot,addr vec0,addr vec1
fld ST
facos  ; ST(0) contains the angle3 value
fadd  ; angle1+= angle3, discard angle3
;----------------------------------------------/

;-------[ introduce fp2 and finalize ]--------------\
fldpi
fmul fp2  ; <------ what is this ?!
fsub ;  angle1 = angle1 - (fp2 * 3.1415)
fabs
fstp ftemp
xor eax,eax
cmp ftemp,3A83126Fh ; 0.001f
setl al
;---------------------------------------------------/
ret
IsPointInTriangle endp


But I need to know the definitions of facos, and what fp2 is.
We can also optimize this further, by replacing the calls to Vec3Normalize and Vec3Dot with macros - though, we may run out of FPU registers ^^" - but still. at least 6 extra cycles will be saved this way :)
Posted on 2005-05-07 14:01:04 by Ultrano
facos is a macro I describe elsewhere on this board.
It's "acos", also known as "arc cosine".
The source is here, and on my old hdd which is still covered in melted plastic (hope its ok!)

fp2 is simply 2.0f
I needed the value 2*pi (this is 360 degrees, in Radians)
and I was too lazy to define it since I already had fp2 defined, and since fldpi is a valid opcode.

The above test requires that the point being tested is on the plane of the test triangle.
The above test is really measuring the three angles formed between a theoretical edge (based on the testpoint and the surfacenormal of the triangle) and another theoretical edge (based on the testpoint and each triangle vertex).
If the point is inside the triangle, these should total to 360 degrees, aka 2pi radians.
Due to fpu error the actual result may vary slightly and so we employ an Epsilon (fudge value).

You can visualize this test by drawing a 2D triangle on paper, and placing deliberately a point inside it.
Now draw lines from the point to each triangle vertex.
The angles inbetween the lines you drew total 360 degrees.

That's how the test works.
It saves us from performing three separate 3D point / edge tests and then checking the three results, it produces accurate results but only if we can ensure the test point is already on the plane of the triangle.
That's why I stress that the test point should be the result of a ray/plane test, ie, an intersection point on the plane of the triangle.

Posted on 2005-05-08 03:47:07 by Homer
I sourced most of my Vec3 math code from a set of fpu macros released by Caleb with his masm DX8 includes. I chose to wrap a couple that I use heavily as procs to keep my binary size down.
No worries about overflowing the fpu either way mate :)

Posted on 2005-05-12 22:07:09 by Homer