Another Triangle thing :-/

Hi all,



Ok, Given the (XYZ) vertex positions of a, b and c, how do I find the (XYZ) position of O.

I've tried a few ways, but can't seem to quite get it right.

I'm sure it's a fairly simple calculation to do (thinking vaguely of DOT or CROSS products), but can't quite get it. Ideas?

Is the orginal trianle a right angled one? Do you know any of the angles a b or c?

Pretty much as the image above really. I am trying to bisect an arbitrary triangle along the longest edge, producing two right angle triangles in the process.

I believe you can cross (c -> b) and (c -> a) to produce the vector from c -> o but then the length escapes me.

Just trying to get a formula to work out position o. :)

Label the three vertices a,b,c ( just like the angles ).

The vector bo is just the projection of vector bc onto ba.

You get this be taking the dot product of bc with a unit vector in the direction of ba. Multiply the unit vector by this dot product ( a number ).
This is the vector bo. Add that to b to get o.

NOTE: I've edited this as I had some confusion with letters a,b. Unfortunately I can't see the picture and what I'm writing at the same time. The frequent scrolling mixed me up. I probably should have opened another window.

Hi Floyd,

I'll give that a go. Let you know how it goes...

Thanks. Appears to work, here's a runnable proof:-

Global RX#, RY#, RZ#

Local AX#, AY#, AZ#
Local BX#, BY#, BZ#
Local CX#, CY#, CZ#

Local UX#,UY#,UZ#
Local VX#,VY#,VZ#

AX = 100 : AY = 100 : AZ = 0
BX = 250 : BY = 10 : BZ = 0
CX = 300 : CY = 100 : CZ = 0

Graphics 800,600,32,2
SetBuffer BackBuffer()

While Not KeyDown(1)
Cls
If tog = 0 Then bx = bx + 1
If Tog = 1 Then bx = bx - 1

If bx > 290 Or bx < 110 Then tog = tog Xor 1

Line AX,AY,BX,BY
Line BX,BY,CX,CY
Line CX,CY,AX,AY

Vector(AX,AY,AZ , BX,BY,BZ)

VX = RX
VY = RY
VZ = RZ

UnitVector(AX,AY,AZ, CX,CY,CZ)

UX = AX+(RX * VX)
UY = AY+(RY * VY)
UZ = AZ+(RZ * VZ)

Line BX,BY, UX,UY

Rect ux -4, uy-9, 9,10,False


Flip

Wend 

Function Dot#(X1#,Y1#,Z1#, X2#,Y2#,Z2#)
	Return D# = (x1*x2 + y1*y2 + Z1*Z2)
End Function
Function UnitVector(X1#, Y1#, Z1#, X2#, Y2#, Z2#)
		Local L#
		RX# = X1#-X2#
		RY# = Y1#-Y2#
		RZ# = Z1#=Z2#
		
		L# = Sqr((RX# * RX#) + (RY# * RY#) + (RZ# * RZ#))
		
		RX# = RX# / L#
		RY# = RY# / L#
		RZ# = RZ# / L#
End Function
Function Vector(X1#, Y1#, Z1#, X2#, Y2#, Z2#)
		Local L#
		RX# = X1#-X2#
		RY# = Y1#-Y2#
		RZ# = Z1#=Z2#
End Function

Thanks again 8D

I've updated the code above so that it animates the topmost vertex to show that the bisection occurs at the correct point.

It works well, now I'll do it on a 3D one :)

Wow! That has problems. And yet, by a miracle, it works for the example. Try changing CY a little, say to 110.

I've tweaked it to match the method I outlined. And I let b move over a larger range, to emphasize that the projection is really onto the infinite line through a and c, i.e. the point o may be outside the triangle.

I left in the Z's, which are irrelevant for 2D. So this already works for 3D. You just have to find nice way to draw everything. In fact, this method works for any number of dimensions, although you would need more letters.

Global RX#, RY#, RZ#

Local AX#, AY#, AZ#
Local BX#, BY#, BZ#
Local CX#, CY#, CZ#

Local UX#,UY#,UZ#
Local VX#,VY#,VZ#

AX = 100 : AY = 200 : AZ = 0
BX = 250 : BY = 100 : BZ = 0
CX = 300 : CY = 250 : CZ = 0

Graphics 800,600,32,2
SetBuffer BackBuffer()

While Not KeyDown(1)

	Cls
	If tog = 0 Then bx = bx + 1
	If Tog = 1 Then bx = bx - 1
	
	If bx > 400 Or bx < 70 Then tog = tog Xor 1
	
	Line AX,AY,BX,BY
	Line BX,BY,CX,CY
	Line CX,CY,AX,AY
	
	Vector(AX,AY,AZ , BX,BY,BZ)     ; R is vector ab
	
	VX = RX
	VY = RY
	VZ = RZ
	
	UnitVector(AX,AY,AZ, CX,CY,CZ)  ; R is unit vector in direction of ac
	
	d# = Dot( VX,VY,VZ, RX,RY,RZ )
	
	RX = RX * d
	RY = RY * d
	RZ = RZ * d   ;  now vector R is ao, the projection of ab onto ac.
	
	Line BX, BY,  AX + RX, AY + RY   ; point o is point a  plus vector R.	
	
	Flip

Wend 

Function Dot#(X1#,Y1#,Z1#, X2#,Y2#,Z2#)
	Return x1*x2 + y1*y2 + Z1*Z2
End Function

Function UnitVector(X1#, Y1#, Z1#, X2#, Y2#, Z2#)   ; from 1 to 2
		Local L#
		RX# = X2#-X1#
		RY# = Y2#-Y1#
		RZ# = Z2#=Z1#
		
		L# = Sqr((RX# * RX#) + (RY# * RY#) + (RZ# * RZ#))
		
		RX# = RX# / L#
		RY# = RY# / L#
		RZ# = RZ# / L#
End Function

Function Vector(X1#, Y1#, Z1#, X2#, Y2#, Z2#)
		Local L#
		RX# = X2#-X1#
		RY# = Y2#-Y1#
		RZ# = Z2#=Z1#
End Function

This could be made a little more efficient. If you look closely you will see that the normalizing factor 1/Length( vector ac) has, in effect, been applied twice. Thus you are really dividing by length^2, so you could eliminate a square root and some divisions.

I can implement this if a little extra speed is of any significance.

Ha! I knew it was too good to be true for me to have got it to work first time! 8D

Thanks for the adjustment. At the moment, speed is not such a big issue.

Why am I looking at this in the first place? Here's the idea..

I am working on an environmental (not terrain) megatexture UV texture mapping idea which uses Right-Angle Triangles as a base for mapping textures (i.e. they simply exhibit a width and height (the shorter edges), so triangles which are significantly off of a right angle are to be bisected along the longest edge to avoid texture stretching. (The tiles are exacly right angle come what may!)

If you sort the triangles by size and rotate them 180 deg every other triangle, you are left with near rectangles which can be packed into a texture only a pixel or two apart using most of the texture space.

It's something I have planned for Decorator-Max so as to allow unique texturing for an entire level (kind of a cross between Decorator and Tattoo). I was hoping to implement CSG too, to allow you to build, texture and populate a level from the first person perspective. Really early days yet, just getting the bits working separately atm.

Anyway the long and short of it is, I'll use this to decompose any mesh into one composed entirely of right angle triangles. It's just at an experimental stage at the moment. :)

That sounds great man. I did like tattoo and always thought it would be cool to apply this to terrains and scenes :o)