Triangulation

[Charles Pegge]

There is always something to be learned from a triangle

This shows how the height of any triangle can be calculated, given the lengths of its 3 sides, but no angles.

Code Select Expand


#COMPILE EXE
#DIM ALL

FUNCTION triangulate _
(BYVAL a AS DOUBLE, BYVAL b AS DOUBLE, BYVAL c AS DOUBLE, BYREF d AS DOUBLE) AS DOUBLE
' given the sides a b c
' returns height h (and also half-base in d)
'
'          ^
'         /|\
'        / | \
'      a/  |h \b
'      /   |   \
'     /    |    \
'     --d--.-----
'      <---c--->
'
'  EQUATIONS:
'
'  1: d=a^2-b$2-c^2/(2*c)
'  2: h=sqr(a^2-d^2)
'
'
! fld qword ptr c
! fld st(0)
! fmul st(0),st(0)
! fld qword ptr b
! fmul st(0),st(0)
! fsubp st(1),st(0)
! fld qword ptr a
! fmul st(0),st(0)
! faddp st(1),st(0)
! fxch
! fdivp st(1),st(0)
! fld1
! fadd st(0),st(0)
! fdivp st(1),st(0)
! mov eax,d
! fst qword ptr [eax]
! fmul st(0),st(0)
! fld qword ptr a
! fmul st(0),st(0)
! fxch
! fsubp st(1),st(0)
! fsqrt
! fstp qword ptr function
'
END FUNCTION

FUNCTION PBMAIN () AS LONG
  DIM d AS DOUBLE
  MSGBOX STR$(triangulate(1,1,1,d))+$CR+STR$(d)
  MSGBOX STR$(triangulate(3,5,4,d))+$CR+STR$(d)
END FUNCTION



[Kent Sarikaya]

Charles on the second output I got 3 and 0, is this correct? Shouldn't it be 2, half of C which is 4.

[Charles Pegge]

Kent, the second example is a 3 4 5 right angle triangle, 3 being the height, 4 being the base and 5 the hypoteneuse. So its a useful test of the algorithm.

The left part of the base, d becomes zero as the left corner of the triangle becomes a right angle. If you were to use.

It you use 5,3,4 instead of  3,5,4 the right-angle will shift to the right corner of the triangle and d will then become 4 ie. equal to the length of the base.

This algorithm will cope with triangles of any shape whatsoever, but breaks down if the triangle is impossible, that is, if the base c is greater than the sum of a and b. in which case the height becomes a negative square root.

I have not investigated what the FPU does with negative square roots. It is a very clever device that can handle positive and negative zeros and even positive and negative infinities without flinching, so you might like to see what happens with impossible triangles like 1,2,6

[Charles Pegge]

In case you thought moving from 2d to 3d was trivial, this shows how to calculate the height of a tetrahedron given its sides. The biggest hurdle is being able to see the problem clearly. You might see a tetrahedron as a neat symmetrical structure, but it may egually be a narrow spike leaning over at 45 degrees.

The algorithm below, which will cope with all possible tetrahedra, involves a four stage calculation.
The first 3 steps derive the sides for a normalised triangle (perpendicular to the base). Then all you need to do is get the height of this notional triangle.

TRIANG is a formulated as a sub rather than a function. It returns the 2 values d and h in its last 2 parameters.
I have also done the same for the PYTHAG sub. This format I hope, brings some clarity to the procedure.

Code Select Expand


#COMPILE EXE
#DIM ALL

SUB triang ( _
BYVAL a AS DOUBLE,_
BYVAL b AS DOUBLE,_
BYVAL c AS DOUBLE,_
BYREF d AS DOUBLE,_
BYREF h AS DOUBLE _
)
' given the sides a b c
' returns height h (and also half-base in d)
'
'          ^
'         /|\
'        / | \
'      a/  |h \b
'      /   |   \
'     /    |    \
'     --d-.------
'      <---c--->
'
'  EQUATIONS:
'
'  1: d=a^2-b$2-c^2/(2*c)
'  2: h=sqr(a^2-d^2)
'
'
! fld qword ptr c
! fld st(0)
! fmul st(0),st(0)
! fld qword ptr b
! fmul st(0),st(0)
! fsubp st(1),st(0)
! fld qword ptr a
! fmul st(0),st(0)
! faddp st(1),st(0)
! fxch
! fdivp st(1),st(0)
! fld1
! fadd st(0),st(0)
! fdivp st(1),st(0)
! mov eax,d
! fst qword ptr [eax]
! fmul st(0),st(0)
! fld qword ptr a
! fmul st(0),st(0)
! fxch
! fsubp st(1),st(0)
! fsqrt
! mov eax,h
! fstp qword ptr [eax]
'
END SUB


SUB pythag(_
BYVAL x AS DOUBLE,_
BYVAL y AS DOUBLE,_
BYREF h AS DOUBLE _
)
! fld qword ptr x
! fmul st(0),st(0)
! fld qword ptr y
! fmul st(0),st(0)
! faddp st(1),st(0)
! fsqrt
! mov eax,h
! fstp qword ptr [eax]
END SUB


FUNCTION PBMAIN () AS LONG
   
  DIM a1  AS DOUBLE: a1=1
  DIM a2  AS DOUBLE: a2=1
  DIM a3  AS DOUBLE: a3=1
  DIM c1  AS DOUBLE: c1=1
  DIM c2  AS DOUBLE: c2=1
  DIM c3  AS DOUBLE: c3=1
  '------------------
  ' derived data
  '------------------
  DIM d1  AS DOUBLE ' front face left halfbase result
  DIM d2  AS DOUBLE ' base face  left halfbase result
  DIM d3  AS DOUBLE ' notional normal triangle unused result
  DIM h1  AS DOUBLE ' height of front face
  DIM h2  AS DOUBLE ' height of base face
  DIM h3  AS DOUBLE ' bottom edge of notional triangle
  DIM h4  AS DOUBLE ' height of notional normal triangle = height of tetrahedron

'          ^                   ^
'         /|\ FRONT           /|\ RIGHT SIDE
'        / | \               / | \
'     a1/  |  \ a2        a2/  |  \a3
'      /   |h1 \           /   |   \
'     /    |    \         /    |    \
'     --d1-.-----         -----.-----
'     <----c1---->        <----c2--->
'
'
'
'          ^  BASE
'         /|\
'        / | \
'     c3/  |  \c2
'      /   |h2 \
'     /    |    \
'     --d--.-----
'     <----c1--->
'
'
'          ^  NORMALISED TRIANGLE
'         /|\
'        / | \
'     h1/  |  \a3
'      /   |h4 \
'     /    |    \
'     --d--.-----
'     <----h3--->
'
'


'------------A----B-------C----D----H-------------------
       triang a1 , a2    , c1 , d1 , h1  ' FRONT
       triang c3 , c2    , c1 , d2 , h2  ' BASE
       pythag h2 , d1-d2 ,           h3  ' BASE h2 adjust to get h3
       triang h1 , a3    , h3 , 0  , h4  ' normalised triangle
'------------A----B-------C----D----H-------------------

MSGBOX STR$(h4)

' a*sqr(6)/3 for equilateral tet
' = 0.81649

END FUNCTION


[Kent Sarikaya]

Charles not to change the subject, but have you looked into file formats to save mesh data in openGL.  Petr of course developed M15 format to be used in thinBasic and Mike wrote a very nice exporter for Blender for it. But I have been looking into using standard full fledged formats and wonder if you have looked at any.

I got my 2 choices narrowed down to FBX and Collada. I am going to do more research on both, but these are full fledged scene describing formats, but since they are widely supported in many apps I think they would be good to develop for powerBasic or bring into powerBasic. Any thoughts?

[Charles Pegge]

Well I'm aquainted with a few. There is  DXF and 3DS. POVRay for ray traced scenes, which Theo will also be familiar with.. VRML and X3D are aimed at animated WEB 3d and have good multimedia support including
directional sound.

At the top end there is Maya ascii format:
http://caad.arch.ethz.ch/info/maya/manual/FileFormats/FileFormats.fm.html

A link for  FBX
http://usa.autodesk.com/adsk/servlet/index?id=6837478&siteID=123112

Collada looks very similar to X3D

http://www.collada.org/
http://www.web3d.org/

They are all formidible! I try  not to worry about them too much. As long as the documentation is good, it is no great burden to to translate, and who knows which will be the predominant standard in ten year's time?