Please help :)

I want to classify a point (3d vertex) against a triangle's plane.
In order to do this, first I must calculate the Surface Normal of the triangle.
This is achieved by obtaining the Cross Product of any two Edges of the triangle.
To calculate two Edges U,V from vertices A,B and C, we simply perform some vertex subtractions, U=B-A , V=C-A
We then obtain the Cross Product of U and V vectors, which is the Surface Normal of the Triangle - but before we use it, we Normalize it to ensure it has Unit Length.

Having calculated the triangle's SurfaceNormal, we can now obtain "d" (distance from Origin to nearest point on Plane).

d is calculated by obtaining the Dot Product of the Normal Vector and a Point Vector which must lay on the Plane (just use any of the Vertices).

I'm confused as to how to use d to calculate the distance of arbitrary points from the plane - and thus determine which side they are on... any help here?
Posted on 2004-07-05 10:56:15 by Homer
That sound so much like the vectors that I have to study for my maths exams ;) . The method of obtaining the normal of a plane is the same as what I learnt. I do not think you need to find d. To find point on the plane, just use the express the plane equation in dot product form.

maybe this is irrelevant because I am not very sure what are you asking. :grin:
Posted on 2004-07-05 11:59:29 by roticv
What I want is the shortest distance from any point to the plane, signed, showing which side it lays on.
Posted on 2004-07-05 12:06:40 by Homer
I see I see.... First find the normal, lets call it n.
Let A be a point on the plane and U be the point from the plane that you want to find.
Find the direction vector UA.
Shortest distance = UA dot unit vector of n

I am not sure about the showing which side it lies on.
Posted on 2004-07-05 12:15:18 by roticv
The sign of the result :) Thanks :)
Posted on 2004-07-05 12:22:50 by Homer
Here's some not-working code to look at - see if you can spot the issue.
(Polygons are Triangles, Triangles are just 3x3d vectors for vertices)




;Nx=UyVz - UzVy
;Ny=UzVx - UxVz
;Nz=UxVy - YyVx
D3DXVec3Cross proc uses ebx ecx pOut, pv1, pv2
mov eax,pv1
mov ebx,pv2
mov ecx,pOut
assume eax:ptr D3DXVECTOR3
assume ebx:ptr D3DXVECTOR3
assume ecx:ptr D3DXVECTOR3
fld [eax].y
fmul [ebx].z
fld [eax].z
fmul [ebx].y
fsub
fstp [ecx].x

fld [eax].z
fmul [ebx].x
fld [eax].x
fmul [ebx].z
fsub
fstp [ecx].y

fld [eax].x
fmul [ebx].y
fld [eax].y
fmul [ebx].x
fsub
fstp [ecx].z

assume eax:nothing
assume ebx:nothing
assume ecx:nothing
ret
D3DXVec3Cross endp

;DotProduct = (x1*x2 + y1*y2 + z1*z2)
D3DXVec3Dot proc pv1,pv2
mov ebx,pv1
mov ecx,pv2
fld [ebx].D3DXVECTOR3.x
fmul [ecx].D3DXVECTOR3.x
fld [ebx].D3DXVECTOR3.y
fmul [ecx].D3DXVECTOR3.y
fld [ebx].D3DXVECTOR3.z
fmul [ecx].D3DXVECTOR3.z
fadd
fadd
ret
D3DXVec3Dot endp


;Calculate the "Surface Normal" of a Polygon surface (ours are all triangles)
;(Think of it as an arrow pointing in the direction the surface is facing)
;pNormalOut: pointer to a 3DVector to receive the returned Normal vector
;pPolygon: pointer to a Triangle
SurfaceNormal proc pNormalOut:DWORD, pPolygon:DWORD
local v1:D3DXVECTOR3
local v2:D3DXVECTOR3
local fLen:FLOAT

;We need to calculate two EDGE VECTORS from the triangle vertices
mov ebx,pPolygon
lea ecx,v1
fld [ebx].Triangle.Point1.x
fsub [ebx].Triangle.Point2.x
fstp [ecx].D3DXVECTOR3.x
fld [ebx].Triangle.Point2.y
fsub [ebx].Triangle.Point1.y
fstp [ecx].D3DXVECTOR3.y
fld [ebx].Triangle.Point1.z
fsub [ebx].Triangle.Point2.z
fstp [ecx].D3DXVECTOR3.z

;$Message "Side1.x=%lX",v1.x
;$Message "Side1.y=%lX",v1.y
;$Message "Side1.z=%lX",v1.z

lea ecx,v2
fld [ebx].Triangle.Point2.x
fsub [ebx].Triangle.Point3.x
fstp [ecx].D3DXVECTOR3.x
fld [ebx].Triangle.Point2.y
fsub [ebx].Triangle.Point3.y
fstp [ecx].D3DXVECTOR3.y
fld [ebx].Triangle.Point2.z
fsub [ebx].Triangle.Point3.z
fstp [ecx].D3DXVECTOR3.z
;$Message "Side2.x=%lX",v2.x
;$Message "Side2.y=%lX",v2.y
;$Message "Side2.z=%lX",v2.z

;Calculate vector normal of polygon = crossproduct of any 2 _SIDES_ of the triangle
invoke D3DXVec3Cross, pNormalOut, addr v2, addr v1


;Now Normalize the Normal so it has Unit Length (3d Length=1.0)
mov ebx,pNormalOut ;First calculate the Length of the un-normalized Vector
fld [ebx].D3DXVECTOR3.x
fmul [ebx].D3DXVECTOR3.x
fld [ebx].D3DXVECTOR3.y
fmul [ebx].D3DXVECTOR3.y
fld [ebx].D3DXVECTOR3.z
fmul [ebx].D3DXVECTOR3.z
fadd
fadd
fsqrt
fstp fLen ;fLen= sqrt (x^2 + Y^2 + z^2)
fld [ebx].D3DXVECTOR3.z ;Then, Divide Vector Components by fLen to Unitize them (without altering the Vector)
fdiv fLen
fstp [ebx].D3DXVECTOR3.z
fld [ebx].D3DXVECTOR3.y
fdiv fLen
fstp [ebx].D3DXVECTOR3.y
fld [ebx].D3DXVECTOR3.x
fdiv fLen
fstp [ebx].D3DXVECTOR3.x

ret
SurfaceNormal endp
;================================================================

.data
fp0 FLOAT 0.0f
.code
ClassifyPoint proc pPolygon:DWORD, pPoint:DWORD
local vNormal:D3DXVECTOR3
local fDistance:FLOAT

fld fp0
fst vNormal.x
fst vNormal.y
fstp vNormal.z

invoke SurfaceNormal, addr vNormal, pPolygon ;Calculate the Normal of the polygon surface

mov ebx,pPolygon ;Offset the Point Being Tested by - the "Origin" used in the Normal calculation
mov ecx,pPoint ;This has the effect of offsetting the Plane to the Point, less the Normal.
fld [ebx].D3DXVECTOR3.x
fsub [ecx].D3DXVECTOR3.x
fstp [ebx].D3DXVECTOR3.x
fld [ebx].D3DXVECTOR3.y
fsub [ecx].D3DXVECTOR3.y
fstp [ebx].D3DXVECTOR3.y
fld [ebx].D3DXVECTOR3.z
fsub [ecx].D3DXVECTOR3.z
fstp [ebx].D3DXVECTOR3.z

invoke D3DXVec3Dot, addr vNormal, pPoint ; Get which side of surface is point
fstp fDistance

fld fDistance
fabs ;absolute (unsigned) value of distancefromplane
fcomp fEpsilon ;if returnvalue < floating tolerance (small float value like 0.001)
__FJG @F
return COINCIDING ;then we say it's close enough to being smack on the Plane
@@: ;but if the (unsigned) distancefromplane isnt really small

mov eax,fDistance ;then we check the sign of the distancefromplane
and eax,80000000h ;by checking the sign bit (31)
.if eax!=0 ;and if its set, the distance is negative
return BEHIND ;meaning the point is BEHIND the plane
.endif ;otherwise, if the distance is positive,
return INFRONT ;then the point is INFRONT of the plane.
ClassifyPoint endp
;================================================================
.data
testtri D3DXVECTOR3 <10.0f,10.0f,20.0f>,<10.0f,20.0f,20.0f>,<15.0,15.0f,5.0f>
testvec D3DXVECTOR3 <0.0f,0.0f, 6.0f>

Posted on 2004-07-05 12:28:18 by Homer
Nevermind, I got it working :)

Ignore the filename, the attached example binary+src merely classifies a 3d point against a 3d triangle and tells you whether the point lays on the plane of the triangle, or on either side of it. The plane is discovered from the triangle geometry. An Epsilon value is used to give the plane some "thickness" to negate fpu inaccuracy.
The example also employs the use of a CVector array manager which I intend to employ in a fast-sorting algorithm for a bspgen.
Posted on 2004-07-06 01:07:56 by Homer
Somehow it seems that the vectors crap that I learnt in college came in handy here ;). At least it works here..
Posted on 2004-07-06 06:53:47 by roticv
Yes you helped in a small way, and I appreciated it.
I guess a lot of my interests are not broad interests, however I was disqualified from college in year 11 (long story) and missed this part of math... I've had a long hard slog teaching myself over the past few years, and I daresay I wouldn't have cared if I'd listened the first time !!
Posted on 2004-07-06 08:47:45 by Homer