Archived

This topic is now archived and is closed to further replies.

Caesar

-infinite (-#INF) with 2d dot product? what do i do wrong?

Recommended Posts

Hi, there''s something wrong with my point in face detection routine. The deal is I work in carthesian space, -1.0 to 1.0 both horizonatally and vertically. Now if my triangle is about 0.05-0.1 each side on the bottom middle of the space and my point is somewhere up in the middle, I get a -infinite result. The method I''m using is to make a vector form the point to each vertex of the face and then add together the angles between the vectors. Now I get the - infinite... why? I guess the problem is that as all the 3 vectors point from one point to three points that are (relatively to the proportions of my space) quite close, the floats I''m using don''t get enough precision somehow... I''m not sure though and haven''t found much more than what #INF means... here''s the source I should also fine that the routine worked fine (I haven''t tested it much though, but worked fine with larger triangles)
        //construct the 3 vectors
	D3DXVECTOR2 a(face[0].x - x, face[0].y - y),
	            b(face[1].x - x, face[1].y - y),
		    c(face[2].x - x, face[2].y - y);

//	D3DXVec2Normalize(&a, &a);
//	D3DXVec2Normalize(&b, &b);
//	D3DXVec2Normalize(&c, &c);

	float angle;

        //add the angles together
	angle = acos(D3DXVec2Dot(&a, &b));
	angle += acos(D3DXVec2Dot(&b, &c));
	angle += acos(D3DXVec2Dot(&c, &a));

        //-2PI to get how close to 2pi it is
        angle -= 2 * D3DX_PI;

        //if it''s close enough, we''ll take it for being inside
	if(fabs(angle) < 0.01)
		return TRUE;

	return FALSE;	
 

Share this post


Link to post
Share on other sites
The dot product gives the product of magnitudes of the vectors times the cosine of the angle - so you need to uncomment those normalizations.

Otherwise yeah, I''d suspect some kind of numerical unstability problem. Can you afford to use doubles?

Share this post


Link to post
Share on other sites
try this instead:

D3DXVECTOR2 a(face[1].x-[face[0].x,face[1].y-face[0].y);
D3DXVECTOR2 b(face[2].x-[face[0].x,face[2].y-face[0].y);
D3DXVECTOR2 v(x-face[0].x,y-face[0].y);
float w,d,p,q;

d=a.x*b.y-a.y*b.x;
if(d!=0)
{
w=1/d;

p=(b.y*v.x-b.x*v.y)*w;
q=(a.x*v.y-a.y*v.x)*w;
return p>=0 && q>=0 && p+q<=1;
}
else
{
// are there going to be triangles without area?

// ask me if you need this part too

return false;
}


I hope i got my linear algebra right.

Never use acos(,asin,atan) if your not planning to use the angle, it's slow.

[edited by - Ghwerig on January 23, 2004 2:30:12 PM]

Share this post


Link to post
Share on other sites
Another word of warning...

before you run the acos function you may want to check that your dotproduct lies between -1 and 1... this will be the case if your vectors are normalised MOST OF THE TIME... but once in while you may get some numerical errors that cause the dot product to be 1.00000001 or -1.00000001... in which case the acos function will return #INF

so something like this is in order:

if (DotProd > 1)
DotProd = 1;
else if (DotProd < -1)
DotProd = -1;

Share this post


Link to post
Share on other sites
ad Ghwerig - oh, what method is that? could you just explain it a little bit? I rather code the stuff myself to know how it work and understand it better... yeah, I''ll use a table for this acos (well, now that doesn''t sound that convincig, considering it''s -1.0 to 1.0, well I''ll have to take a look how allegro or some amth lib does it if I''d stick with this version... so explain, I''ll try to revamp it if I know how

ad spacedude - ah, now that might be the problem! I''ll take a closer look, thanks a lot

Share this post


Link to post
Share on other sites
Mathematical description:

1. Translate all points so that the image of face[0] is the origin.

face[0] |-> (0,0)
face[1] |-> w[1]=face[1]-face[0]
face[2] |-> w[2]=face[2]-face[0]
(x,y) |-> v

a=w[1]-(0,0)=w[1]
b=w[2]-(0,0)=w[2]


2. If a,b are linear independent, they form a vector space basis {a,b}. To calculate the coordinates (p,q) of v relative to the basis {a,b} we need the inverse of the matrix M=[a|b]


[a.x b.x]
M=[ ]
[a.y b.y]


d=det(M)


1 [b.y -b.x]
M^(-1)=-*[ ]
d [-a.y a.x]


(p,q)=M^(-1)*v

"v is in the triangle ((0,0),a,b)" is equivalent to "p>0, q>0, p+q>1"

EDIT: if you don't like matrices solve
(x,y)=v[0]+p(V[1]-V[0])+q*(V[2]-V[3]) for p and q

[edited by - Ghwerig on January 23, 2004 5:20:23 PM]

Share this post


Link to post
Share on other sites