Solved

How to calculate BaryCentric?

Posted on 2001-08-28
3
2,523 Views
Last Modified: 2013-12-26
Is there some formula to calculate the BaryCentric a,b & c values of a 3-D triangle?

I want to calculate this for a point P on the plane of the 3-D triangle. Is it then possible to calculate a point P' from a "warped" 3-D triangle so that P' is proportianally in the same place inside the "warped" triangle as P inside the original triangle?

Basically I want P' must "look" to be in the correct place as the triangle gets "warped" and I thought Barycentric coordinates would be the best, but the stuff on the internet is quite hairy to read through!
0
Comment
Question by:Claude050897
3 Comments
 
LVL 2

Expert Comment

by:cybermike3d
ID: 6440013
Right, here goes ... In order to simplify the explanation I have written a little qbasic program that demonstrates the concept. Check it out and see if you have any questions. Basicaly what happens is your triangl has three points in space. Each, a 3D co ord consisting of an X,Y and Z offset  Then, you have a point on the plane of the triangle. This too has an X,Y and Z offset. Now, as you move your 'eye' along any of the viewing axis (Yaw, Pitch and Roll) so, the viweing angle to the triangle will change. So too, will the corresponding angle to the point on the face of the triangle. So, you simply translate the XYZ of the three points plus the XYZ of the reference point which you then project onto a 2d surface (Your computer screen) The little program that I wrote below, does this using floating point or integer math. The trade off is of course fast and coarse vs slow and accurate. ie, Hi speed games would use the integer based math and cad systems would use the floating point math.

This will do it for you either way. As the triangle is warped by a changing viewing angle, so too is the aspect of the reference point, but it still retains its position ratio wise to the other points of the triangle. Like I said, play with it a bit and feel free to ask me if you have any further questions.

regards

Cybermike3D

Cut and paste the following code onto your notepad then save as a .bas file. Check that is does in fact save properly. You may need to rename it on the disk. The use qbasic to load and run it. Have fun

'Triangle face orientation. www.cybermike3d.co.za

    CLS
    SCREEN 9, 1

      'set alf to 0 for hi resolution lo speed calculation mode
      'set alf to 1 to lo res hi speed integer calculation mode.

    alf = 0 '

    IF alf = 1 THEN
      'DEFINT B-Z
    END IF
      DIM sine(360)
      DIM cosine(360)
      DIM arctab(100, 100)
      DIM rootab(80, 80)
      PRINT "Building arctan table :"
       
      FOR yy = 0 TO 100
      FOR xx = 0 TO 100
      x = xx - 50: y = yy - 50
      IF y <> 0 THEN gan = ATN(x / y) * 57
      IF y = 0 AND x = 0 THEN gan = 0: gang = 0
      IF y = 0 AND x < 0 THEN gan = 270
      IF y = 0 AND x > 0 THEN gan = 90
      gang = gan
      IF y < 0 THEN gang = 180 + gan
      IF x < 0 AND y > 0 THEN gang = 360 + gan
      arctab(xx, yy) = gang
      NEXT
      NEXT
       
      PRINT "Building square root table"
       
      FOR yy = 0 TO 80
      FOR xx = 0 TO 80
      ra = SQR(xx ^ 2 + yy ^ 2)
      rootab(xx, yy) = ra
      NEXT
      NEXT

      PRINT "Building sine / cosine table"
      FOR l = 0 TO 360
      a = SIN(l / 57) * 100:
      sine(l) = INT(a)
      a = COS(l / 57) * 100:
      cosine(l) = INT(a)
      
      
      NEXT

      DIM rx(70), ry(70), rz(70), col(70), cmd(70)
      DIM nx(70), ny(70), nz(70)
      zf = 10
      GOSUB loadf
      GOSUB roll
      GOSUB roll
      WHILE g$ <> CHR$(27)
      g$ = ""
      g$ = INKEY$

      ' ---------------------------------- keyboard stuff
      IF g$ = "l" THEN CLS : GOSUB loadf
      IF g$ = "8" THEN ya = ya - 4
      IF g$ = "2" THEN ya = ya + 4
      IF g$ = "4" THEN xa = xa - 4
      IF g$ = "6" THEN xa = xa + 4
      IF g$ = "3" THEN za = za + 4
      IF g$ = "1" THEN za = za - 4
      IF g$ = "+" THEN zf = zf + 1
      IF g$ = "-" THEN zf = zf - 1
       
      IF g$ = "t" THEN tf = 1
      IF g$ = " " THEN tf = 0
      IF tf = 1 THEN ya = ya + ac: xa = xa + ac1: za = za + ac2
      IF g$ = "a" THEN ac = ac + 1
      IF g$ = "s" THEN ac = ac - 1
      IF g$ = "q" THEN ac1 = ac1 + 1
      IF g$ = "w" THEN ac1 = ac1 - 1
      IF g$ = "z" THEN ac2 = ac2 + 1
      IF g$ = "x" THEN ac2 = ac2 - 1

      IF g$ = "j" THEN nx(4) = nx(4) - 1
      IF g$ = "k" THEN nx(4) = nx(4) + 1
      IF g$ = "i" THEN ny(4) = ny(4) - 1
      IF g$ = "m" THEN ny(4) = ny(4) + 1

      IF g$ = "r" THEN GOSUB loadf

      IF ya > 360 THEN ya = ya - 360
      IF xa > 360 THEN xa = xa - 360
      IF za > 360 THEN za = za - 360
       
      IF ya < 0 THEN ya = ya + 360
      IF xa < 0 THEN xa = xa + 360
      IF za < 0 THEN za = za + 360
      'STOP
      IF g$ <> "" THEN GOSUB roll
      IF tf = 1 THEN GOSUB roll

      WEND
      END
roll:
      ws = ws - 1: ws = ABS(ws): os = ws - 1: os = ABS(os)
      SCREEN 9, 1, ws, os
      VIEW (0, 0)-(639, 349), 0
      LOCATE 1, 1
      PRINT "Press [I,J,K,M] to move point within triangle, [L] to load new traingle"
      PRINT "      [1,2,3,4,6,8] to rotate on x,y,z axis,  +- to zoom in/ out"
      PRINT
      PRINT "X-angle ="; xa
      PRINT "Y-angle ="; ya
      PRINT "Z-angle ="; za
      FOR l = 0 TO f
      rx(l) = nx(l)
      ry(l) = ny(l)
      rz(l) = nz(l)
      '----------------- translate in the three axis
rolx:   x = rx(l):
      y = ry(l):
      na = xa:
      GOSUB getcord
      rx(l) = xn:
      ry(l) = yn:
roly:   x = rz(l):
      y = ry(l):
      na = ya:
      GOSUB getcord
      rz(l) = xn:
      ry(l) = yn:
rolz:   x = rx(l):
      y = rz(l):
      na = za:
      GOSUB getcord
      rx(l) = xn:
      rz(l) = yn:
      '-------------------------- place polygon on screen
      xx = rx(l) * zf / 10 + 320:
      yy = ry(l) * zf / 10 + 268:
      '-------------------------- and correct aspect ratio
      yy = yy * 6 / 8
        '------------------------- draw thingys on screen
      IF cmd(l) = 4 THEN CIRCLE (xx, yy), 4, 8: PAINT (xx, yy), 8
      IF cmd(l) = 4 THEN CIRCLE (xx, yy), 4, col(l): PAINT (xx, yy), col(l): PSET (xx - 1, yy - 2), 15:   PSET (xx - 2, yy - 1), 15
      IF cmd(l) = 2 THEN CIRCLE (xx, yy), 3, 8: PAINT (xx, yy), 8
      IF cmd(l) = 2 THEN CIRCLE (xx, yy), 3, col(l): PAINT (xx, yy), col(l): PSET (xx - 1, yy - 2), 15:   PSET (xx - 2, yy - 1), 15
      IF cmd(l) = 2 THEN LINE (ox, oy)-(xx, yy), col(l)
      
      x4 = x3: x3 = x2: x2 = x1: x1 = x0: x0 = xx
      y4 = y3: y3 = y2: y2 = y1: y1 = y0: y0 = yy
      ox = xx: oy = yy

      PSET (320, 200)

      NEXT
      RETURN

getcord:

   IF alf = 0 THEN
   '---------- floating point calculation routine
       ixdif = x
       iydif = y
     itargetrange = SQR(ixdif ^ 2 + iydif ^ 2)
     ra = itargetrange
     IF iydif <> 0 THEN itgan = ATN(ixdif / iydif) * 57.2958
     IF iydif = 0 AND ixdif = 0 THEN itgan = 0: itgang = 0
     IF iydif = 0 AND ixdif < 0 THEN itgan = 270
     IF iydif = 0 AND ixdif > 0 THEN itgan = 90
     itgang = itgan
     IF iydif < 0 THEN itgang = 180 + itgan
     IF ixdif < 0 AND iydif > 0 THEN itgang = 360 + itgan
     itnang = na + itgang
     IF itnang > 180 THEN itnang = itnang - 360
     IF itnang < -180 THEN itnang = itnang + 360
     xn = SIN(itnang / 57.2958) * ra
     yn = COS(itnang / 57.2958) * ra
     RETURN
    END IF
   
    IF alf = 1 THEN
     
   ' ----------- integer based lookup table routine
      xx = ABS(x): yy = ABS(y)
      xx = xx / 2: yy = yy / 2
      ra = rootab(xx, yy)
      ra = ra * 2
      x = x / 3 + 50: y = y / 3 + 50
      nang = arctab(x, y) + na
      IF nang > 360 THEN nang = nang - 360
      IF nang < 0 THEN nang = nang + 360
      xn = sine(nang) * ra
      xn = xn / 100
      yn = cosine(nang) * ra
      yn = yn / 100
      RETURN
    END IF
      

loadf:
      ' --------------- load a random triangle
      f = 4
      FOR l = 0 TO 4
      nx(l) = RND(1) * 200 - 100: rx(l) = nx(l)
      ny(l) = RND(1) * 200 - 100: ry(l) = ny(l)
      nz(l) = 0: rz(l) = 0
      cmd(l) = 2
      col(l) = 7
      cmd(0) = 0

      NEXT

      nx(3) = nx(0): rx(3) = nx(3)
      ny(3) = ny(0): ry(3) = ny(3)
      cmd(4) = 4

      nx(4) = (nx(1) + nx(2) + nx(3)) / 3
      ny(4) = (ny(1) + ny(2) + ny(3)) / 3


      nx(5) = -100
      nx(6) = 100
      cmd(6) = 2
      col(6) = 2

      ny(7) = -100
      ny(8) = 100
      cmd(8) = 2
      col(8) = 1

      nz(9) = -100
      nz(10) = 100
      cmd(10) = 2
      col(10) = 4
      f = 10
      RETURN



0
 

Accepted Solution

by:
ChristerEricson earned 200 total points
ID: 6535349
Claude,

Barycentric coordinates will indeed let you map points from one triangle to another.

The barycentric coordinate of a point P with respect to the vertices A, B and C of a
triangle ABC is a triplet of values, (a, b, c), such that P = a*A+b*B+c*C, with a+b+c=1.
With appropriate values for a, b and c, P can assume the position of any point in the
plane of ABC.

Given a different triangle DEF with vertices D, E and F, you can now map P into the plane of DEF to some point Q by computing Q=a*D+b*E+c*F.
For instance, the barycentric coordinates (1,0,0), (0,1,0) and (0,0,1) would map
A into D, B into E and C into F, respectively.

There are many ways of actually computing the barycentric coordinates (a, b, c)
for P with respect to the triangle ABC. The perhaps simplest method uses the fact
that a, b and c are proportional to ratios of specific (signed) triangle areas.
If |ABC| denotes the area of the triangle with vertices A, B and C (given counter-clockwise
in that specific order) then specifically you have that:

a = |PBC| / |ABC|,
b = |PCA| / |ABC|,
c = |PAB| / |ABC| = 1 - a - b

It's important that these areas are "signed", which simply means that when looking at
the triangles from a fixed position, if their vertices are arranged counter-clockwise,
the area is positive, and if clockwise, it's negative.

What remains is to actually compute |ABC| for some given points. This too can be done
in many ways. A conceptually straightforward way (but somewhat expensive computation-
wise) is to use the fact that a cross product of two vectors gives you a vector
whose magnitude is twice the area of the triangle with those two vectors as its sides.

So, to compute (a, b, c) you would do something like this (assuming a reasonable C++
vector class):

// Compute the normal of the triangle
Vector N = Normalize(Cross(B-A,C-A));

// Compute twice area of triangle ABC
float AreaABC = Dot(N,Cross(B-A,C-A));

// Compute a
float AreaPBC = Dot(N,Cross(B-P,C-P));
float a = AreaPBC / AreaABC;

// Compute b
float AreaPCA = Dot(N,Cross(C-P,A-P));
float b = AreaPCA / AreaABC;

// Compute c
float c = 1.0f - a - b;

This computation can be made less computationally expensive by projecting
the triangle and the point into one of the XY, XZ or YZ planes and performing
the calculations there (which automatically reduces the computation by 1/3 as
there is one less coordinate to perform calculations on).

You can test your code, making sure it's working, by computing:

Point PP = a*A + b*B + c*C;
Point Zero = PP - P;

and making sure that the components of Zero are indeed (near) zero.


Christer Ericson
Sony Computer Entertainment, Santa Monica
0
 
LVL 1

Expert Comment

by:Moondancer
ID: 6759878
No response to Proposed Answer, assume it served the need and finalizing today.  In the event Asker returns with additional needs here, please response.

Moondancer
Community Support Moderator @ Experts Exchange
0

Featured Post

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

What is RenderMan: RenderMan is a not any particular piece of software. RenderMan is an industry standard, defining set of rules that any rendering software should use, to be RenderMan-compliant. Pixar's RenderMan is a flagship implementation of …
Artificial Intelligence comes in many forms, and for game developers, Path-Finding is an important ability for making an NPC (Non-Playable Character) maneuver through terrain.  A* is a particularly easy way to approach it.  I’ll start with the algor…
Here's a very brief overview of the methods PRTG Network Monitor (https://www.paessler.com/prtg) offers for monitoring bandwidth, to help you decide which methods you´d like to investigate in more detail.  The methods are covered in more detail in o…
This video shows how to remove a single email address from the Outlook 2010 Auto Suggestion memory. NOTE: For Outlook 2016 and 2013 perform the exact same steps. Open a new email: Click the New email button in Outlook. Start typing the address: …

747 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now