Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / 3D Theory & Graphics / Using barycentric results Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
shields

May 09, 2005, 09:02 AM

How to get a vertex index using the Barycentric results from a ray intersect!.

  1.  
  2. DWORD GetVertexIndexFromBarycentric(float fU, float fV)
  3. {
  4.     float fOther = 1.0f - fU - fV;
  5.     DWORD rFoundVertex;
  6.        
  7.     if (fU > fV) {
  8.         if (fU > fOther) {
  9.             rFoundVertex = 1;
  10.         }else {
  11.             rFoundVertex = 0;
  12.         }
  13.     }else {
  14.         if (fV > fOther) {
  15.             rFoundVertex = 2;
  16.         }else {
  17.             rFoundVertex = 0;
  18.         }
  19.     }
  20.  
  21.     return rFoundVertex;
  22. }
  23.  


I hope this helps somebody...

 
IronChefC++

May 09, 2005, 12:42 PM

What's the point of this code?

 
Erik Faye-Lund

May 09, 2005, 01:04 PM

I'm not sure what you're trying to do here. isn't barycentric coordinates just used to blend attributes between vertices?

 
goltrpoat

May 09, 2005, 01:44 PM

IronChef/Erik -

He's picking the nearest vertex given a barycentric coordinate. The method is actually quite clever.

Given a triangle A+u(B-A)+v(C-A), the values of u and v corresponding to A, B and C respectively are (0,0), (1,0) and (0,1). We can partition the triangle into three quadrilateral regions corresponding to each vertex, such that if u and v are in that region, then the point is closer to that vertex than to any other. The regions all share a common vertex in the barycenter (1/3,1/3), and adjacent regions share vertices along edge midpoints, which are (1/2,0), (0,1/2) and (1/2,1/2).

The regions corresponding to each vertex are defined by the following points:

A: (0,0) (1/2,0) (1/3,1/3), (0,1/2)
B: (1,0) (1/2,1/2) (1/3,1/3), (1/2,0)
C: (0,1) (0,1/2) (1/3,1/3), (1/2,1/2)

The naive implementation would pick the pair (u,v) and then perform the four checks necessary to place it in a given region. In contrast, shields' method does the following. First, you notice that the line u=v is the line through A and the midpoint of the edge BC. The line u=(1-u-v) ==> 2u=1-v ==> u = 1/2 - 1/2v is the line through C and the midpoint of the edge BA. Finally, the line v=(1-u-v) ==> 2v=1-u ==> v = 1/2 - 1/2v is the line through B and the midpoint of the edge AC. But those are the exactly the lines that bound the regions we just found earlier.

So the code does the following:

  1.  
  2. If (u,v) is on the left of the line through A and (B+C)/2, then
  3. {
  4.    If (u,v) is on the right of the line through C and (A+B)/2, then we're  
  5.   closest to B.  Otherwise, the point is closest to A.
  6. }
  7. else
  8. {
  9.   If (u,v) is on the right of the line through B and (A+C)/2, then we're  
  10.    closest to C.  Otherwise, the point is closest to A.
  11. }
  12.  


-goltrpoat


EDIT: "Left" and "right" are used assuming clockwise winding of the triangle, and the direction of splitter lines is taken to be going from a vertex to the midpoint of the opposite edge.

 
goltrpoat

May 09, 2005, 02:12 PM

Having said that, I'm just curious -- where would this actually be used? I can't think of an application other than vertex picking, but maybe I'm just not quite awake yet.

-goltrpoat

 
Christer Ericson

May 09, 2005, 03:47 PM

goltrpoat wrote: He's picking the nearest vertex given a barycentric coordinate. The method is actually quite clever.


First, note that the returned vertex index I does _not_ have anything to do with the shortest distance between the vertex V[I] and the point P determined by the barycentric coordinates. The non-correspondance is obvious if you e.g. consider that barycentric weights (1/3, 1/3, 1/3) do _not_ correspond to the incenter of the triangle.

Second, I don't want to be rude or anything but I wouldn't categorize it as "clever" because it's just using a very basic fact about barycentric coordinates to return a vertex index. Namely, the normalized barycentric weight associated with a vertex V with respect to a given point P corresponds to the normalized height of P from the edge E opposite of V (zero height at E, height of one at V).

I have no idea what you'd want to use the posted function for. It basically just tells you which of the three barycentric components is the largest!


Christer Ericson
http://realtimecollisiondetection.net/

 
goltrpoat

May 09, 2005, 04:18 PM

Christer-

First, note that the returned vertex index I does _not_ have anything to do with the shortest distance between the vertex V[I] and the point P determined by the barycentric coordinates. The non-correspondance is obvious if you e.g. consider that barycentric weights (1/3, 1/3, 1/3) do _not_ correspond to the incenter of the triangle.


You're right, I screwed that up. (1/3,1/3,1/3) is the centroid, not the incenter. Converting the whole thing to, eg., trilinear coordinates, would make the result more meaningful, but at that point you might as well just compare squared Euclidean distances instead.

Aside from the fact that the algorithm doesn't do what I think the poster is expecting it to do, I thought it was clever from the efficiency standpoint (or maybe it's just that I started out in the whole "detect which Voronoi region we're in" mode, which was probably an ass-backwards way of looking at it, and after going through that whole explanation, it seemed clever in comparison).

I have no idea what you'd want to use the posted function for. It basically just tells you which of the three barycentric components is the largest!


Heh, yeah, pretty much.


-goltrpoat

 
IronChefC++

May 09, 2005, 07:52 PM

I still don't see the cleverness. It seems rather obvious. The code is almost identical to code I've seen many times before, e.g. it's the axis removal selection part of the standard 3D-reduced-to-2D point-in-triangle test.

Beyond the cleverness issue, what's the usefulness? Barycentric coordinates are useful for interpolating values between sample points and determining point inclusion. What's useful in discretizing back to one of the sample points?

 
goltrpoat

May 10, 2005, 02:06 PM

No cleverness. My whole post was one major brainfart. The initial explanation was wrong -- it works fine with barycentrics, it's just that the centroid has nothing to do with the incenter, and the code essentially picks which barycentric coordinate is the largest, as Christer pointed out. Which, in turn, is obvious from reading the code. That'll teach me to post before coffee.

The usefulness issue. Like I said in the followup, I can't see much use even for what I assume the poster intended to do (i.e. picking the nearest vertex to a point). It seems like it would have come in handy if you wanted to loosely pick a vertex based on a raycast (eg for mouse picking), although the only way that would work with, say, a single acutely oriented triangle is if the function got projected triangles as input.

By the "axis removal selection part of the standard 3d-reduced-to-2d point-in-triangle test" I assume you mean the test that drops the coordinate corresponding to the largest component of the normal, then transforms the 2d point into barycentrics by solving the 2x2 system, and rangechecks the result? If so, I'm not sure what the similarity is.

-goltrpoat

 
This thread contains 9 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.