Maths problem (barycentric coordinates)

96 views
Skip to first unread message

pa...@bustykelp.com

unread,
Jul 17, 2013, 11:38:08 AM7/17/13
to soft...@listproc.autodesk.com
Hi, I have spent days on this and I cant work it out
 
I have a selection of points (not on a flat plane) and I have a test position.
It returns an array that represents the weighting, related to the proximity to the other points.
 
I want to have it so that when the test position is directly at a point, the value for that point in the array = 1
and the rest will be zero
as the test point moves around the area it interpolates these values, but they always add up to 1
 
It sounds really easy, but I’ve been literally* tearing my hair out over this for days.
 
Ive managed to get barycentric interpolation working for a flat plane, and only 3 points, but I need it to accept multiple points in 3d space.
 
Please help. I’m going bonkers over this
 
Paul
 
*(not really literally)

Ben Houston

unread,
Jul 17, 2013, 12:04:05 PM7/17/13
to soft...@listproc.autodesk.com
So barycoords for a triangle works well and I believe there are tons
of references on the web for this. Barycoordinates for polygons is a
bit more problematic because they are no longer linear but rather
polynomials and thus harder to calculate. I'd stick with triangles
and then all those web references should work well.

Is your problem calculating them from points?

Basically this is a great guide:

http://en.wikipedia.org/wiki/Barycentric_coordinate_system

-ben
--
Best regards,
Ben Houston
Voice: 613-762-4113 Skype: ben.exocortex Twitter: @exocortexcom
http://Exocortex.com - Passionate CG Software Professionals.

David Barosin

unread,
Jul 17, 2013, 12:07:47 PM7/17/13
to xsi
If you can chew through the greek notation this is helpful.  http://en.wikipedia.org/wiki/Inverse_distance_weighting




On Wed, Jul 17, 2013 at 11:38 AM, <pa...@bustykelp.com> wrote:

Paul

unread,
Jul 17, 2013, 12:51:46 PM7/17/13
to soft...@listproc.autodesk.com
I have been googling all I can find trying to understand the maths notation but its not my forte and I've not found anything that does exactly what I want. I was hoping someone cleverer than i might take pity on me and provide an idiot proof explanation.  

Ben Houston

unread,
Jul 17, 2013, 12:58:23 PM7/17/13
to soft...@listproc.autodesk.com
BTW here is our code for calculating barycoordinates from points and
creating points from barycoordinates:

template<class T>
class Triangle3 {
public:
Vec3<T> a;
Vec3<T> b;
Vec3<T> c;

Matrix44<T> getPointToBarycoordMatrix() const;
Matrix44<T> getBarycoordToPointMatrix() const;
};

template<class T>
inline Matrix44<T> Triangle3<T>::getPointToBarycoordMatrix() const {
M44x pointToBarycoordMatrix;
bool success = inverseSafe( pointToBarycoordMatrix,
getBarycoordToPointMatrix() );
if( ! success ) {
T oneThird = ((T)1.0)/((T)3.0);
//Vec3<T> center = ( a + b + c ) * oneThird;
return Matrix44<T>(
0, 0, 0, 0,
0, 0, 0, 0,
0, 0, 0, 0,
oneThird, oneThird, oneThird, 0);
}
return pointToBarycoordMatrix;
}

template<class T>
inline Matrix44<T> Triangle3<T>::getBarycoordToPointMatrix() const {
Vec3<T> n = normal();
return Matrix44<T>(
a[0], a[1], a[2], 1,
b[0], b[1], b[2], 1,
c[0], c[1], c[2], 1,
n[0], n[1], n[2], 0);
}

And this you just multiple your point by the "pointToBarycoordMatrix"
matrix to get barycoords. And if you have barycoordinates, multiply
it by "getBarycoordToPointMatrix()" to get your point.

We are using 4 coordinate barycoordinates where the fourth element is
the distance from the triangle plane in the normal direction. Just
set it to zero and you should be fine. The above can be converted to
Softimage Matrix types pretty easily. Probably could be added to the
Softimage SDK as well if it isn't already there.

Best regards,
-ben

Alok Gandhi

unread,
Jul 17, 2013, 1:47:07 PM7/17/13
to soft...@listproc.autodesk.com

Grahame Fuller

unread,
Jul 17, 2013, 1:54:28 PM7/17/13
to soft...@listproc.autodesk.com
Translated from the Greek:

1. Calculate the distance from the test position to each of your selected points.

2. If one of the distances is 0, stop. The corresponding coordinate is 1, the others are 0.

3. Otherwise for each of the distances, calculate 1/distance, or 1/distance^2, or 1/distance^3, or ... .

4. Normalize the values above. In other words, get their sum and for each value calculate value/sum.

Ta da!

gray

From: softimag...@listproc.autodesk.com [mailto:softimag...@listproc.autodesk.com] On Behalf Of Paul
Sent: Wednesday, July 17, 2013 12:52 PM
To: soft...@listproc.autodesk.com
Subject: Re: Maths problem (barycentric coordinates)

I have been googling all I can find trying to understand the maths notation but its not my forte and I've not found anything that does exactly what I want. I was hoping someone cleverer than i might take pity on me and provide an idiot proof explanation.

On 17 Jul 2013, at 17:07, David Barosin <dbar...@gmail.com<mailto:dbar...@gmail.com>> wrote:
If you can chew through the greek notation this is helpful. http://en.wikipedia.org/wiki/Inverse_distance_weighting


winmail.dat

Vincent Ullmann

unread,
Jul 17, 2013, 2:05:59 PM7/17/13
to soft...@listproc.autodesk.com
Quote Paul:
��� {
��� Ive managed to get barycentric interpolation working for a flat plane, and only 3 points, but I need it to accept multiple points in 3d space.
��� }

Not sure if this helps, but some time ago i made a ICE-Compound for calulating barycentric-Coordinates, based on 3 3D-Vectors.
Dont know if my formula was correct.... ;-)


Am 17.07.2013 19:47, schrieb Alok Gandhi:


On Wed, Jul 17, 2013 at 12:58 PM, Ben Houston <b...@exocortex.com> wrote:
BTW here is our code for calculating barycoordinates from points and
creating points from barycoordinates:

template<class T>
class Triangle3 {
public:
� � � � Vec3<T> a;
� � � � Vec3<T> b;
� � � � Vec3<T> c;

� � � � Matrix44<T> getPointToBarycoordMatrix() const;
� � � � Matrix44<T> getBarycoordToPointMatrix() const;

};

template<class T>
inline Matrix44<T> Triangle3<T>::getPointToBarycoordMatrix() const {
� � � � M44x pointToBarycoordMatrix;
� � � � bool success = inverseSafe( pointToBarycoordMatrix,
getBarycoordToPointMatrix() );
� � � � if( ! success ) {
� � � � � � � � T oneThird = ((T)1.0)/((T)3.0);
� � � � � � � � //Vec3<T> center = ( a + b + c ) * oneThird;
� � � � � � � � return Matrix44<T>(
� � � � � � � � � � � � 0, 0, 0, 0,
� � � � � � � � � � � � 0, 0, 0, 0,
� � � � � � � � � � � � 0, 0, 0, 0,
� � � � � � � � � � � � oneThird, oneThird, oneThird, 0);
� � � � }
� � � � return pointToBarycoordMatrix;

}

template<class T>
inline Matrix44<T> Triangle3<T>::getBarycoordToPointMatrix() const {
� � � � Vec3<T> n = normal();
� � � � return Matrix44<T>(
� � � � � � � � a[0], a[1], a[2], 1,
� � � � � � � � b[0], b[1], b[2], 1,
� � � � � � � � c[0], c[1], c[2], 1,
� � � � � � � � n[0], n[1], n[2], 0);

}

And this you just multiple your point by the "pointToBarycoordMatrix"
matrix to get barycoords. �And if you have barycoordinates, multiply

it by "getBarycoordToPointMatrix()" to get your point.

We are using 4 coordinate barycoordinates where the fourth element is
the distance from the triangle plane in the normal direction. �Just
set it to zero and you should be fine. �The above can be converted to
Softimage Matrix types pretty easily. �Probably could be added to the

Softimage SDK as well if it isn't already there.

Best regards,
-ben


On Wed, Jul 17, 2013 at 12:04 PM, Ben Houston <b...@exocortex.com> wrote:
> So barycoords for a triangle works well and I believe there are tons
> of references on the web for this. �Barycoordinates for polygons is a

> bit more problematic because they are no longer linear but rather
> polynomials and thus harder to calculate. �I'd stick with triangles

> and then all those web references should work well.
>
> Is your problem calculating them from points?
>
> Basically this is a great guide:
>
> http://en.wikipedia.org/wiki/Barycentric_coordinate_system
>
> -ben
>
>
> On Wed, Jul 17, 2013 at 11:38 AM, �<pa...@bustykelp.com> wrote:
>> Hi, I have spent days on this and I cant work it out
>>
>> I have a selection of points (not on a flat plane) and I have a test
>> position.
>> It returns an array that represents the weighting, related to the proximity
>> to the other points.
>>
>> I want to have it so that when the test position is directly at a point, the
>> value for that point in the array = 1
>> and the rest will be zero
>> as the test point moves around the area it interpolates these values, but
>> they always add up to 1
>>
>> It sounds really easy, but I�ve been literally* tearing my hair out over

>> this for days.
>>
>> Ive managed to get barycentric interpolation working for a flat plane, and
>> only 3 points, but I need it to accept multiple points in 3d space.
>>
>> Please help. I�m going bonkers over this

>>
>> Paul
>>
>> *(not really literally)
>
>
>
> --
> Best regards,
> Ben Houston
> Voice: 613-762-4113 Skype: ben.exocortex Twitter: @exocortexcom
> http://Exocortex.com - Passionate CG Software Professionals.



--
Best regards,
Ben Houston
Voice: 613-762-4113 Skype: ben.exocortex Twitter: @exocortexcom
http://Exocortex.com - Passionate CG Software Professionals.




--

barycentric_coordinates_Compound.JPG
barycentric_coordinates_Result.JPG

Vladimir Jankijevic

unread,
Jul 17, 2013, 2:26:11 PM7/17/13
to soft...@listproc.autodesk.com
something we recorded last year while I was in NY: https://vimeo.com/44951318
maybe this helps :)

Cheers
Vladimir


On Wed, Jul 17, 2013 at 2:05 PM, Vincent Ullmann <vincent...@googlemail.com> wrote:
Quote Paul:

    {

    Ive managed to get barycentric interpolation working for a flat plane, and only 3 points, but I need it to accept multiple points in 3d space.
    }

Not sure if this helps, but some time ago i made a ICE-Compound for calulating barycentric-Coordinates, based on 3 3D-Vectors.
Dont know if my formula was correct.... ;-)


Am 17.07.2013 19:47, schrieb Alok Gandhi:
You can have a look at my blog post: 
On Wed, Jul 17, 2013 at 12:58 PM, Ben Houston <b...@exocortex.com> wrote:
BTW here is our code for calculating barycoordinates from points and
creating points from barycoordinates:

template<class T>
class Triangle3 {
public:
        Vec3<T> a;
        Vec3<T> b;
        Vec3<T> c;

        Matrix44<T> getPointToBarycoordMatrix() const;
        Matrix44<T> getBarycoordToPointMatrix() const;
};

template<class T>
inline Matrix44<T> Triangle3<T>::getPointToBarycoordMatrix() const {
        M44x pointToBarycoordMatrix;

        bool success = inverseSafe( pointToBarycoordMatrix,
getBarycoordToPointMatrix() );
        if( ! success ) {
                T oneThird = ((T)1.0)/((T)3.0);
                //Vec3<T> center = ( a + b + c ) * oneThird;
                return Matrix44<T>(
                        0, 0, 0, 0,
                        0, 0, 0, 0,
                        0, 0, 0, 0,
                        oneThird, oneThird, oneThird, 0);
        }
        return pointToBarycoordMatrix;
}

template<class T>
inline Matrix44<T> Triangle3<T>::getBarycoordToPointMatrix() const {
        Vec3<T> n = normal();
        return Matrix44<T>(

                a[0], a[1], a[2], 1,
                b[0], b[1], b[2], 1,
                c[0], c[1], c[2], 1,
                n[0], n[1], n[2], 0);
}

And this you just multiple your point by the "pointToBarycoordMatrix"
matrix to get barycoords.  And if you have barycoordinates, multiply

it by "getBarycoordToPointMatrix()" to get your point.

We are using 4 coordinate barycoordinates where the fourth element is
the distance from the triangle plane in the normal direction.  Just
set it to zero and you should be fine.  The above can be converted to
Softimage Matrix types pretty easily.  Probably could be added to the

Softimage SDK as well if it isn't already there.

Best regards,
-ben


On Wed, Jul 17, 2013 at 12:04 PM, Ben Houston <b...@exocortex.com> wrote:
> So barycoords for a triangle works well and I believe there are tons
> of references on the web for this.  Barycoordinates for polygons is a

> bit more problematic because they are no longer linear but rather
> polynomials and thus harder to calculate.  I'd stick with triangles

> and then all those web references should work well.
>
> Is your problem calculating them from points?
>
> Basically this is a great guide:
>
> http://en.wikipedia.org/wiki/Barycentric_coordinate_system
>
> -ben
>
>
> On Wed, Jul 17, 2013 at 11:38 AM,  <pa...@bustykelp.com> wrote:
>> Hi, I have spent days on this and I cant work it out
>>
>> I have a selection of points (not on a flat plane) and I have a test
>> position.
>> It returns an array that represents the weighting, related to the proximity
>> to the other points.
>>
>> I want to have it so that when the test position is directly at a point, the
>> value for that point in the array = 1
>> and the rest will be zero
>> as the test point moves around the area it interpolates these values, but
>> they always add up to 1
>>
>> It sounds really easy, but I’ve been literally* tearing my hair out over

>> this for days.
>>
>> Ive managed to get barycentric interpolation working for a flat plane, and
>> only 3 points, but I need it to accept multiple points in 3d space.
>>
>> Please help. I’m going bonkers over this

>>
>> Paul
>>
>> *(not really literally)
>
>
>
> --
> Best regards,
> Ben Houston
> Voice: 613-762-4113 Skype: ben.exocortex Twitter: @exocortexcom
> http://Exocortex.com - Passionate CG Software Professionals.



--
Best regards,
Ben Houston
Voice: 613-762-4113 Skype: ben.exocortex Twitter: @exocortexcom
http://Exocortex.com - Passionate CG Software Professionals.




--


Bk

unread,
Jul 17, 2013, 4:49:04 PM7/17/13
to soft...@listproc.autodesk.com
Thanks for all the replies. It's much appreciated. I'll grind through them tomorrow at work.

David Barosin

unread,
Jul 20, 2013, 11:03:06 PM7/20/13
to xsi
Hey Paul.  Here's a scene that shows how to get a normalized weighted value.  It also shows how to use this weighted array on scale, rotation & color.  It uses a null group to influence particles.
weighted.zip

Andy Moorer

unread,
Jul 21, 2013, 2:47:53 PM7/21/13
to soft...@listproc.autodesk.com
Alok since you bring it up I am reminded to belatedly thank you for this article - it's a fantastic read, and your blog is a personal favorite. 

Sent from iGadget

Alok Gandhi

unread,
Jul 21, 2013, 3:18:54 PM7/21/13
to soft...@listproc.autodesk.com
Thanks for your kind words Andy. I am planning a few more. This gives me opportunity to ask people here which concepts, areas of 3D mathematics are most difficult to master so that I can try to cover them up at my blog.

The ones that I have in mind are :

1. Rotations - What the hell are quaternions, eulers etc.

2. Transforms and Matrix - why do we need them.

3. Half float precisions numbers and how exr uses them.

4. The math behind the stereoscopy.

Bk

unread,
Jul 21, 2013, 4:28:20 PM7/21/13
to soft...@listproc.autodesk.com
Thanks very much for doing this. I look forward to testing it when I get back from holiday in a week.

I did get something that works, by stripping back the 'calculate envelope weights' compound to the core maths, but I'm keen to see anything else.

Paul 


<weighted.zip>

Leonard Koch

unread,
Jul 21, 2013, 6:10:23 PM7/21/13
to soft...@listproc.autodesk.com

I recently had to properly understand rotations on a low level and an article written by you would have been awesome.

Raffaele Fragapane

unread,
Jul 21, 2013, 8:33:01 PM7/21/13
to soft...@listproc.autodesk.com
Isner's page on quaternions is still up, and it's still more than OK if you haven't bumped into it:
http://www.isner.com/tutorials/quatSpells/quaternion_spells_14.htm

Personally I've never quite understood the struggle with quaternions and rotations, I think most of it comes from the fact people are too used to numbers that have a Newtonian intuitiveness on a linear scale to them, and therefore are puzzled by the fact that the numbers in quaternions are not to be intuitively read and translated in your head the way Euler angles in a gimbal system or scalars in vector maths are.

The basic concept of direction + roll and interpolation being "warped" in spherical space is not that un-intuitive to understand though.

The rest is all down to simple matrix maths, which again tend to be overly mystified and puzzling to many, but if explained well and if segwayed from their 3D application (rather than from the abstracts of linear systems and general matrix composition) tend to be very intuitive.
--
Our users will know fear and cower before our software! Ship it! Ship it and let them flee like the dogs they are!

David Barosin

unread,
Jul 22, 2013, 8:25:43 AM7/22/13
to xsi
Hope it helps.  I realize there is a division by zero problem that should be fixed by adding this 'if' node. 

weighted.jpg
Reply all
Reply to author
Forward
0 new messages