"Hard" maths: angle between 2 triangles ??

Blitz3D Forums/Blitz3D Programming/"Hard" maths: angle between 2 triangles ??

Braincell

(Posted 2006) [#1]

Hi

working on my stencil shadow system its getting late and im a bit tired so if there are math people out there that could help would be nice. If not i'll probably solve it myself tomorrow.

I need an angle between two triangles that share one edge. So they have 4 verts that can move anywhere in XYZ space, and they share 2 of those verts. Both facing same direction. Each triangle has its plane and its normal defined by the 3 verts that make it up. I need to know the angle (0 to 360) between each of the planes or normals (whichever you want). I was looking into cross product but dont have time tonight so maybe someone can give a hint?

This is for a predefined list of triangles and edges that is made for each shadow caster so that when two triangles form a cavity (angle smaller than 180) the edge between them is ignored and in this way less calculation and volume updating has to be done each loop because a cavity never casts a shadow, its always "inside". Most systems dont have this optimisation but since blitz is slow enough as it is, i think we really need it. BTW any helpful soul will be included in credits :P

thanks

Braincell

(Posted 2006) [#2]

No actually this optimisation isnt crucial so i might leave it for later. Better finish the primary stuff and optimise it after. So this question stays open.

I figured out the theory of it but putting down the equations, im not so keen on doing.

N	(Posted 2006) [#3]

I believe the dot product of the two normals of the planes is what you want.

Braincell

(Posted 2006) [#4]

Hmm i was heading in that direction as well but i will try it later. I think this wont be in the first release, but it is a crucial feature that could speed the system up by 140%.

If someone can just gimmedacodez that would be sweet :) i have enough theoretic ideas as it is.

Stevie G

(Posted 2006) [#5]

I think this is right .... assuming p & q are vectors

MagP = sqr( px * px + py * py + pz * pz )
MagQ = sqr( qx * qx + qy * qy + qz * qz )

cos( theta ) = ( px*qx + py*qy + pz*qz ) / ( MagP * MagQ )

=> Theta = Acos( ( px*qx + py*qy + pz*qz ) / ( MagP * MagQ ) )

Stevie

Braincell

(Posted 2006) [#6]

:o

Looks good to me. But i suppose P and Q are vectors of normals (or probably crossproduct)? I'll test.

Braincell

(Posted 2006) [#7]

Hmm it works but the problem is it is always giving a positive angle because of Squareing and Squarerooting. I worked out a similar problem before so i will work this one out. It's just a matter of comparing signs of the vectors. Thanks Stevie!

Here's the code i have now(mess left over from previous tests):
Use WASDFC to move camera, and insert,home,pgup,pgdn,delete,end to move the 4th vertex.

Graphics3D 800,600,0,2



Global vectorx#
Global vectory#
Global vectorz#
Global vectorw#

Const UPS=60

cam=CreateCamera()
PositionEntity cam, 0,5,-15

l=CreateLight()

period=1000/UPS
time=MilliSecs()-period

v1=CreateSphere()
ScaleEntity v1,0.5,0.5,0.5
v2=CreateSphere()
ScaleEntity v2,0.5,0.5,0.5
v3=CreateSphere()
ScaleEntity v3,0.5,0.5,0.5
v4=CreateSphere()
ScaleEntity v4,0.5,0.5,0.5

cp1=CreateSphere();cross product marker
ScaleEntity cp1,0.5,0.5,0.5
EntityColor cp1, 0,0,250
cp2=CreateSphere()
ScaleEntity cp2,0.5,0.5,0.5
EntityColor cp2, 0,0,250


smesh = CreateMesh()
ssurf = CreateSurface(smesh)

v1x#=-6;left
v1y#=4
v1z#=2
v2x#=0;middle front
v2y#=1
v2z#=4
v3x#=0;middle back
v3y#=1
v3z#=0
v4x#=6;right
v4y#=1
v4z#=2

v1v = AddVertex (ssurf, v1x,v1y,v1z)
v2v = AddVertex (ssurf, v2x,v2y,v2z)
v3v = AddVertex (ssurf, v3x,v3y,v3z)
v4v = AddVertex (ssurf, v4x,v4y,v4z)

AddTriangle (ssurf, v1v,v2v,v3v)
AddTriangle (ssurf, v2v,v4v,v3v)

PositionEntity v1, v1x,v1y,v1z
PositionEntity v2, v2x,v2y,v2z
PositionEntity v3, v3x,v3y,v3z
PositionEntity v4, v4x,v4y,v4z

Repeat
	Repeat
		elapsed=MilliSecs()-time
	Until elapsed
	ticks=elapsed/period
	tween#=Float(elapsed Mod period)/Float(period)

msp# = 0.2

If KeyDown(17) Then MoveEntity cam, 0,0,msp
If KeyDown(31) Then MoveEntity cam, 0,0,-msp
If KeyDown(33) Then MoveEntity cam, 0,msp,0
If KeyDown(46) Then MoveEntity cam, 0,-msp,0
If KeyDown(32) Then MoveEntity cam, msp,0,0
If KeyDown(30) Then MoveEntity cam, -msp,0,0
If KeyDown (203) Then TurnEntity cam, 0,msp*5,0
If KeyDown (205) Then TurnEntity cam, 0,-msp*5,0
If KeyDown (200) Then TurnEntity cam, msp*5,0,0
If KeyDown (208) Then TurnEntity cam, -msp*5,0,0

If KeyDown (199) Then v4y = v4y + msp
If KeyDown (207) Then v4y = v4y - msp
If KeyDown (210) Then v4z = v4z + msp
If KeyDown (201) Then v4z = v4z - msp
If KeyDown (209) Then v4x = v4x + msp
If KeyDown (211) Then v4x = v4x - msp


;update verts
VertexCoords ssurf, v4v,v4x,v4y,v4z


;update spheres representing verts
PositionEntity v1, v1x,v1y,v1z
PositionEntity v2, v2x,v2y,v2z
PositionEntity v3, v3x,v3y,v3z
PositionEntity v4, v4x,v4y,v4z


ax#=v1x-v2x
ay#=v1y-v2y
az#=v1z-v2z
bx#=v1x-v3x
by#=v1y-v3y
bz#=v1z-v3z
CrossProduct(ax,ay,az,bx,by,bz)
t1vx#=vectorx
t1vy#=vectory
t1vz#=vectorz

ax#=v4x-v3x
ay#=v4y-v3y
az#=v4z-v3z
bx#=v4x-v2x
by#=v4y-v2y
bz#=v4z-v2z
CrossProduct(ax,ay,az,bx,by,bz)
t2vx#=vectorx
t2vy#=vectory
t2vz#=vectorz

px# = t1vx
py# = t1vy
pz# = t1vz
qx# = t2vx
qy# = t2vy
qz# = t2vz

MagP# = Sqr( px * px + py * py + pz * pz )
MagQ# = Sqr( qx * qx + qy * qy + qz * qz )

Theta# = ACos( ( px*qx + py*qy + pz*qz ) / ( MagP * MagQ ) )

wtf=False
If t1vx <= 0 And t2vx > 0 Then
wtf=True
ElseIf t1vx >= 0 And t2vx < 0 Then
wtf=True
ElseIf t1vy <= 0 And t2vy > 0 Then
wtf=True
ElseIf t1vy >= 0 And t2vy < 0 Then
wtf=True
ElseIf t1vz <= 0 And t2vz > 0 Then
wtf=True
ElseIf t1vz >= 0 And t2vz < 0 Then
wtf=True
EndIf

If Theta = NaN Then
	djhfsdf$="No Edge"
Else
	djhfsdf$="Edge"
End If

;update the cross product results
PositionEntity cp1, v1x+t1vx,v1y+t1vy,v1z+t1vz
PositionEntity cp2, v4x+t2vx,v4y+t2vy,v4z+t2vz

;show projected lines of cross product
CameraProject (cam, v1x,v1y,v1z)
p1x=ProjectedX()
p1y=ProjectedY()
CameraProject (cam, v1x+t1vx,v1y+t1vy,v1z+t1vz)
pt1x=ProjectedX()
pt1y=ProjectedY()
CameraProject (cam, v4x,v4y,v4z)
p2x=ProjectedX()
p2y=ProjectedY()
CameraProject (cam, v4x+t2vx,v4y+t2vy,v4z+t2vz)
pt2x=ProjectedX()
pt2y=ProjectedY()


	For k=1 To ticks
		time=time+period	
		If KeyHit(1) End
		UpdateWorld	
	Next
	
	RenderWorld tween
	
	Color 255,255,255
Text 10,10,	t1vx + ", " + t1vy + ", " + t1vz
Text 10,20,	t2vx + ", " + t2vy + ", " + t2vz
Text 10,30, Theta
Text 10,40, djhfsdf
Text 10,50, "wtf:" + wtf
	Color 255,00,0
;Line p1x,p1y,pt1x,pt1y
;Line p2x,p2y,pt2x,pt2ya
	Flip

Forever





Function TriangleNormal#(Ax#,Ay#,Az#,Bx#,By#,Bz#,Cx#,Cy#,Cz#)
SubVector Bx#,By#,Bz#,Ax#,Ay#,Az#
ux#=VectorX()
uy#=VectorY()
uz#=VectorZ()
SubVector Cx#,Cy#,Cz#,Bx#,By#,Bz#
vx#=VectorX()
vy#=VectorY()
vz#=VectorZ()
CrossProduct vx#,vy#,vz#,ux#,uy#,uz#
;Normalize vectorx,vectory,vectorz
Return Ax#*vectorx+Ay#*vectory+Az#*vectorz
End Function

Function VectorX#()
Return vectorx
End Function

Function VectorY#()
Return vectory
End Function

Function VectorZ#()
Return vectorz
End Function

Function VectorW#()
Return vectorw
End Function

Function SubVector(Ax#,Ay#,Az#,Bx#,By#,Bz#)
vectorx#=ax#-bx#
vectory#=ay#-by#
vectorz#=az#-bz#
End Function

Function Normalize(nx#,ny#,nz#)
If nx=0 And ny=0 And nz=0 Return
m#=Magnitude(nx#,ny#,nz#)
vectorx#=nx#/m#
vectory#=ny#/m#
vectorz#=nz#/m#
End Function

Function CrossProduct(Ax#,Ay#,Az#,Bx#,By#,Bz#)
vectorx#=Ay#*Bz#-Az#*By#
vectory#=Az#*Bx#-Ax#*Bz#
vectorz#=Ax#*By#-Ay#*Bx#
End Function


Function Magnitude(nx#,ny#,nz#) 
m#= Sqr( (nx*nx) + (ny*ny) + (nz*nz) ) 
Return m# 
End Function

Braincell

(Posted 2006) [#8]

Ok i solved it. If anyone needs a function to check the angle between triangles, or rather the angle between the normals of two triangles, it is contained in there.

I would have spent much more time if it wasn't for you Stevie G, so thanks again.

I'm not sure this is useful enough to post it in the code archives :)

;Checks the angle between (normals of) two triangles.
;By Braincell, February 2006 
;
;Note: If you dont want them to share 2 vertices you can modify the function
;to take 6 verts and calculate the cross prodcut accordingly, ie instead of
;v123 and v432 that is there now, have v123, v456 cross products.
;
;This function was made to be part of the stencil shadow system

Graphics3D 800,600,0,2

;3.bb >> final version with function



Global vectorx#
Global vectory#
Global vectorz#
Global vectorw#

Const UPS=60

cam=CreateCamera()
PositionEntity cam, 0,5,-15

l=CreateLight()

period=1000/UPS
time=MilliSecs()-period

v1=CreateSphere()
ScaleEntity v1,0.5,0.5,0.5
v2=CreateSphere()
ScaleEntity v2,0.5,0.5,0.5
v3=CreateSphere()
ScaleEntity v3,0.5,0.5,0.5
v4=CreateSphere()
ScaleEntity v4,0.5,0.5,0.5

;cp1=CreateSphere();cross product marker
;ScaleEntity cp1,0.5,0.5,0.5
;EntityColor cp1, 0,0,250
;cp2=CreateSphere()
;ScaleEntity cp2,0.5,0.5,0.5
;EntityColor cp2, 0,0,250


smesh = CreateMesh()
ssurf = CreateSurface(smesh)

v1x#=-6;left
v1y#=4
v1z#=2
v2x#=0;middle front
v2y#=1
v2z#=4
v3x#=0;middle back
v3y#=1
v3z#=0
v4x#=6;right
v4y#=1
v4z#=2

v1v = AddVertex (ssurf, v1x,v1y,v1z)
v2v = AddVertex (ssurf, v2x,v2y,v2z)
v3v = AddVertex (ssurf, v3x,v3y,v3z)
v4v = AddVertex (ssurf, v4x,v4y,v4z)

AddTriangle (ssurf, v1v,v2v,v3v)
AddTriangle (ssurf, v2v,v4v,v3v)

PositionEntity v1, v1x,v1y,v1z
PositionEntity v2, v2x,v2y,v2z
PositionEntity v3, v3x,v3y,v3z
PositionEntity v4, v4x,v4y,v4z




.mainloop
Repeat
	Repeat
		elapsed=MilliSecs()-time
	Until elapsed
	ticks=elapsed/period
	tween#=Float(elapsed Mod period)/Float(period)

msp# = 0.2

;WASDFC moves the camera
If KeyDown(17) Then MoveEntity cam, 0,0,msp
If KeyDown(31) Then MoveEntity cam, 0,0,-msp
If KeyDown(33) Then MoveEntity cam, 0,msp,0
If KeyDown(46) Then MoveEntity cam, 0,-msp,0
If KeyDown(32) Then MoveEntity cam, msp,0,0
If KeyDown(30) Then MoveEntity cam, -msp,0,0
If KeyDown (203) Then TurnEntity cam, 0,msp*5,0
If KeyDown (205) Then TurnEntity cam, 0,-msp*5,0
If KeyDown (200) Then TurnEntity cam, msp*5,0,0
If KeyDown (208) Then TurnEntity cam, -msp*5,0,0

;Insert, Delete, Home, End, PgUP, PgDN moves the vertex
If KeyDown (199) Then v4y = v4y + msp
If KeyDown (207) Then v4y = v4y - msp
If KeyDown (210) Then v4z = v4z + msp
If KeyDown (201) Then v4z = v4z - msp
If KeyDown (209) Then v4x = v4x + msp
If KeyDown (211) Then v4x = v4x - msp


;update verts
VertexCoords ssurf, v4v,v4x,v4y,v4z


;update spheres representing verts
PositionEntity v1, v1x,v1y,v1z
PositionEntity v2, v2x,v2y,v2z
PositionEntity v3, v3x,v3y,v3z
PositionEntity v4, v4x,v4y,v4z

af# = AngleBetweenTriangles#(v1x#,v1y#,v1z#,v2x#,v2y#,v2z#,v3x#,v3y#,v3z#,v4x#,v4y#,v4z#)

If af# < 180.0 Then
	txt$ = "No edge."
Else
	txt$ = "Edge."
End If

;update the cross product results (places blue spheres at CP result)
;PositionEntity cp1, v1x+t1vx,v1y+t1vy,v1z+t1vz ;values moved to function
;PositionEntity cp2, v4x+t2vx,v4y+t2vy,v4z+t2vz

	For k=1 To ticks
		time=time+period	
		If KeyHit(1) End
		UpdateWorld	
	Next
	
	RenderWorld tween
	
	Color 255,255,255
Text 10,10, txt
Text 10,25, "Angle: " + af

	Flip

Forever





Function TriangleNormal#(Ax#,Ay#,Az#,Bx#,By#,Bz#,Cx#,Cy#,Cz#)
SubVector Bx#,By#,Bz#,Ax#,Ay#,Az#
ux#=VectorX()
uy#=VectorY()
uz#=VectorZ()
SubVector Cx#,Cy#,Cz#,Bx#,By#,Bz#
vx#=VectorX()
vy#=VectorY()
vz#=VectorZ()
CrossProduct vx#,vy#,vz#,ux#,uy#,uz#
;Normalize vectorx,vectory,vectorz
Return Ax#*vectorx+Ay#*vectory+Az#*vectorz
End Function

Function VectorX#()
Return vectorx
End Function

Function VectorY#()
Return vectory
End Function

Function VectorZ#()
Return vectorz
End Function

Function VectorW#()
Return vectorw
End Function

Function SubVector(Ax#,Ay#,Az#,Bx#,By#,Bz#)
vectorx#=ax#-bx#
vectory#=ay#-by#
vectorz#=az#-bz#
End Function

Function Normalize(nx#,ny#,nz#)
If nx=0 And ny=0 And nz=0 Return
m#=Magnitude(nx#,ny#,nz#)
vectorx#=nx#/m#
vectory#=ny#/m#
vectorz#=nz#/m#
End Function

Function CrossProduct(Ax#,Ay#,Az#,Bx#,By#,Bz#)
vectorx#=Ay#*Bz#-Az#*By#
vectory#=Az#*Bx#-Ax#*Bz#
vectorz#=Ax#*By#-Ay#*Bx#
End Function


Function Magnitude(nx#,ny#,nz#) 
m#= Sqr( (nx*nx) + (ny*ny) + (nz*nz) ) 
Return m# 
End Function



Function AngleBetweenTriangles#(v1x#,v1y#,v1z#,v2x#,v2y#,v2z#,v3x#,v3y#,v3z#,v4x#,v4y#,v4z#)

ax#=v1x-v2x
ay#=v1y-v2y
az#=v1z-v2z
bx#=v1x-v3x
by#=v1y-v3y
bz#=v1z-v3z
CrossProduct(ax,ay,az,bx,by,bz)
t1vx#=vectorx/3
t1vy#=vectory/3
t1vz#=vectorz/3

ax#=v4x-v3x
ay#=v4y-v3y
az#=v4z-v3z
bx#=v4x-v2x
by#=v4y-v2y
bz#=v4z-v2z
CrossProduct(ax,ay,az,bx,by,bz)
t2vx#=vectorx/3
t2vy#=vectory/3
t2vz#=vectorz/3



px# = t1vx
py# = t1vy
pz# = t1vz
qx# = t2vx
qy# = t2vy
qz# = t2vz

MagP# = Sqr( px * px + py * py + pz * pz )
MagQ# = Sqr( qx * qx + qy * qy + qz * qz )


Theta1# =ACos ( ( px*qx + py*qy + pz*qz ) / ( MagP * MagQ ) )


;move refference point by 1000th of cross product and check the change ---- <<< solution
t2mx# = t2vx / 1000.0
t2my# = t2vy / 1000.0
t2mz# = t2vz / 1000.0
v4bx# = v4x + t2mx
v4by# = v4y + t2my
v4bz# = v4z + t2mz
ax#=v4bx-v3x
ay#=v4by-v3y
az#=v4bz-v3z
bx#=v4bx-v2x
by#=v4by-v2y
bz#=v4bz-v2z
CrossProduct(ax,ay,az,bx,by,bz)
t2bvx#=vectorx/3
t2bvy#=vectory/3
t2bvz#=vectorz/3

qx# = t2bvx
qy# = t2bvy
qz# = t2bvz

MagP# = Sqr( px * px + py * py + pz * pz )
MagQ# = Sqr( qx * qx + qy * qy + qz * qz )


Theta2# = ACos ( ( px*qx + py*qy + pz*qz ) / ( MagP * MagQ ) )

If Theta2 < Theta1 Then
	actualangle# = Theta1 + 180
Else
	actualangle# = 180 - Theta1
End If

Return actualangle#


End Function

big10p

(Posted 2006) [#9]

I'm not sure this is useful enough to post it in the code archives

If it's not already in there, it's certainly worth adding. ;)

Stevie G

(Posted 2006) [#10]

I would have spent much more time if it wasn't for you Stevie G, so thanks again.

No problem, anything to speed up a demo of your shadow thing :)

p.s. If you're only using normals then no reason to calculate the vector magnitude ... will always be 1?