🔒 Locked

D3DXIntersect(), barycentric coords

Started by brekehan May 26, 2003 at 4:02 AM 2 replies 1.5k views

Original Post

May 26, 2003 at 4:02 AM

I am trying to figure a way to pick vertices instead of faces so that i can raise or lower a vertex of a terrain in an editor when the user clicks it with a given radius affecting nearby vertices as well. I am looking at D3DXIntersect in the SDK and it talks about "barycentric" coordinates: Barycentric coordinates are a form of general coordinates. In this context, using barycentric coordinates represents a change in coordinate systems... Ok that doesn''t tell me much at all. What is this barycentric coordinate system? Are they related to the texture coordinates, and if I define texture coordinates will it affect the barycentric coordinates this function returns? The documentation also says: "this function returns the resulting point by using the following equation v1+u(v2-v1)+v(v3-v1)" Yet the return value is an HRESULT and it seems to return an array of faces using a pointer to an array of DWORDS. So I don''t see a point being returned anywhere. Am I right? How do I figure the closest point (vertex) from the information returned. Of course, it doesn''t explain how the DWORD value corresponds to a face either. How do I know which face? As far as the term barycentric google turned up some info from which I assume this conclusion: there are three vertices of a tri ABC using barycentric coords u,v,w u increases as point P moves closer to A v increases as point P moves closer to B w increases as point P moves closer to C replace increase with the word decrease, and closer with the word farther in any of the above statements ,and they still hold true. but now let''s try to make sense of D3DXIntersect: 1 the function only gives u and v instead of 3 coords 2 nowhere are the ranges of the coords explained 3 and no where is explained how we can tell whether u corresponds to A,B, or C and the same for v (I am assuming some elaborate system of indexing, but I wouldnt be surprised if some unknown factor would screw it up since this function is documented like crap, i.e if u and v change depending on matrixes, or are always consistant in some manner) so here are more specific questions: how do you use a barycentric coord system with only two coords instead of three to find if you are closer to A, B, or C? what are the ranges of these coords? how can you keep track of whether u and v correspond to A,B, or C since these labels are abstract? Is it consistant? Do Matrixes affect this? Do I need an elaborate indexing system? There are probably enough questions in this post to write a book, but useful information at all would help a great deal. Thanx, Christopher

tibo

May 26, 2003 at 8:03 AM

hi
Barycentric coordinates are not monsters, they are just another way of describing the same thing than cartsian coordinates.
Every triangle is defined by 3 vertices, say A, B and C; and each of these vertices has 3 coordinates x, y and z. We can also use vectors do describe our triangle, 2 are needed, we call them v1 and v2 and they equal:
v1 = (B-A) = (Bx-Ax, By-Ay, Bz-Az)
v2 = (C-A) = ...
Now, when you want to know wether a ray (with a position and direction) intersects your triangle, you want to know 2 things:
- does the ray actually cuts the plane in which the triangle lies ? If they are parallel, the answer is no,
- is the intersection of the ray and the plane inside the triangle ABC ?
If the first answer is no, there is no intersection. If it yes, then the intersection can be defined by I, with 3 cartesian coordinates Ix, Iy and Iz. We can also use another coordinate system; all we need is to get sure we have the same amount of data. Since we know that the intersection is in our plane, we can use a 2d-coordinate system in which the origin is A, the x-axis is v1, and the y-axis is v2. We call u the v1-axis coordinate, and v the v2-axis coordinate. With such a coordinate system, you compute the cartesian coordinates of I with the equation:
(Ix,Iy,Iz) = u*(v1x,v1y,v1z) + v*(v2x,v2y,v2z)
See we dont loose information: we have one set of 2-d coordinates (u and v) plus 2 vectors defining the plane (v1 and v2).
When both u and v are between 0 and 1, the point is inside the triangle, when one or both are in ]-oo,0]U[0,+oo[, the intersection is outside the triangle.
Hope this helps

tibo

May 26, 2003 at 9:11 AM

re-hi
I made a mistake in the previous post:
the point is inside the triangle if
- both u and v are in [0,1]
- u+v=1
I forgot that u+v=1 was another condition

Cuculain

May 26, 2003 at 10:20 AM

The following code from my engine seems to work well for dynamic terrain modification. I don''t think it is usable as is but maybe it can be an inspiration.

  

// Given a ray origin (orig) and direction (dir), and three 

// vertices of of a triangle, return TRUE if the triangle is 

// intersected

bool CTerrain::IntersectTriangle(const D3DXVECTOR3& orig, 
  const D3DXVECTOR3& dir, D3DXVECTOR3& v0, D3DXVECTOR3& v1,   
  D3DXVECTOR3& v2)
{
    // Find vectors for two edges sharing vert0

    D3DXVECTOR3 edge1 = v1 - v0;
    D3DXVECTOR3 edge2 = v2 - v0;

    // Begin calculating determinant - also used to 

    //calculate U parameter

    D3DXVECTOR3 pvec;
    D3DXVec3Cross(&pvec, &dir, &edge2);

    // If determinant is near zero, ray lies in plane of 

    //triangle

    FLOAT det = D3DXVec3Dot(&edge1, &pvec);

    D3DXVECTOR3 tvec;
    if(det > 0)
    {
        tvec = orig - v0;
    }
    else
    {
        tvec = v0 - orig;
        det = -det;
    }

    if(det < 0.0001f)
        return false;

    // Calculate U parameter and test bounds

    FLOAT u = 0.0f;
	u = D3DXVec3Dot(&tvec, &pvec);

    if(u < 0.0f || u > det)
        return false;

    // Prepare to test V parameter

    D3DXVECTOR3 qvec;
    D3DXVec3Cross(&qvec, &tvec, &edge1);

    // Calculate V parameter and test bounds

    FLOAT v = 0.0f; 
	v = D3DXVec3Dot(&dir, &qvec);

    if(v < 0.0f || u + v > det)
        return false;

	float dist = 0.0f;

	// Acquire and store the barycentric hit coordinates

	D3DXIntersectTri(&v0, &v1, &v2, &orig, &dir, &m_fU, 
          &m_fV, &dist);

    return true;
}

// This function finds the nearest corner in a tile consisting

// of four vertices using barycentric coordinates previously

// acquired with IntersectTriangle

HRESULT CTerrain::GetNearestCorner() 
{
   if(m_iPickedFace < 0)
      return S_OK;

   int iTile = m_iPickedFace / 2;

   m_iTargetVertex = -1;

   // Determine the nearest vertex within the selected face. 

   // m_fU and m_fV already contains the barycentric hit    

   // coordinates from IntersectTriangle

   if(m_iPickedFace % 2 == 0) // Even face

   {
      if(m_fU >= 0.5f) // Lower Right

      {
	 m_iTargetVertex = iTile * 4 + 1;
	 m_eTileRegion = LowerRight;
      }
      else if(m_fV >= 0.5f) // Lower left

      {
	 m_iTargetVertex = iTile * 4 + 2;
	 m_eTileRegion = LowerLeft;
      }
      else // Upper left

      {
	 m_iTargetVertex = iTile * 4;
	 m_eTileRegion = UpperLeft;
      }
    }
    else // Odd face

    {
	if(m_fV >= 0.5f) // Lower Left

	{
	   m_iTargetVertex = iTile * 4 + 2;
	   m_eTileRegion = LowerLeft;
	}
	else if(m_fU + m_fV >= 0.5f) // Lower right

	{
	   m_iTargetVertex = iTile * 4 + 3;
	   m_eTileRegion = LowerRight;
	}
	else // Upper right

	{
	   m_iTargetVertex = iTile * 4 + 1;
	   m_eTileRegion = UpperRight;
	}
    }

    return S_OK;
}

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.