Point in triangle edge

[kaizer]

Hello,

with a set of values defining Triangles I need to know weather a point is in or out of the triangle. Also, for any point that is in the triangle, the code must check if it is in the edge or not.

The following strategy seams to make some sence for the Point in triangle edge situation, however it may not work properly due to float to int roundings.

* Get the two points that define the edge
* Use the y = m x + b and m = y2 - y1 / x2 - x1 to find 'b' and 'm'
* With the coordinates for the PointNew see if it's in the line and between the other two points. If so, PointNew is in the edge.

And this algorithm would be applied after the coordinates are transformed into perspective projection.

Do you think this will give good (or at least decent) results?



Any other proven techniques?

BTW: Working based only on software rendering, not using DX or Opengl.

Thanks for your comments. m .

[Reedbeta]

Google returns: http://www.blackpawn.com/texts/pointinpoly/default.html

I'm not sure what you mean by asking whether a point is "in the edge". Because of floating point roundoff error a point will almost never lie precisely on an edge unless it is equal to a vertex. However, you can employ some epsilons for determining if a point is close to being on an edge. Just replace the test of the dot product's sign with a test for it being greater than epsilon (in), less than -epsilon (out), or neither (edge).

[kaizer]

Hello,

The purpose of doing the "poin in edge" verification is to know if a given pixel is to appear in the wireframe with invisible line removal.

For Example

Using z-buffer algoritm,

For each triangle
For each point in the triangle
If point.z is the closest so far
z[point.x][point.y] = point.z
color[point,x][point.y] = white if point in edge, black otherwise


Then use color array to do pixel plotting.

The initial model didn't have triangles, just points and a topology matrix. To achive the invisible line removal The z-buffering algorithm requeries that pixels are compared so "faces" are necessary. However the points within the face are not to get painted if they are not the "edge" or "border" of the polygon.

Since the calculations are exact, it may look strange and end up with some weird wireframe.

Other ways to do this?

Note: no Dx or OpenGL.

Thanks.

[Reedbeta]

Well, the trouble is that if you use a test like this to determine if a pixel's on the edge, you're going to get popping and holes and other weird artifacts. In order to draw a line you should really just draw a line, not draw a triangle and try to identify edge pixels. What if, for each face, you just draw a black triangle and then draw the lines with a slight z-offset, to ensure that the lines come out in front of the triangle despite roundoff error?

[kaizer]

Hello,

What do you mean by "draw the lines with a slight z-offset"?

Thanks.

[Reedbeta]

Make the depth value generated for each pixel of the line slightly smaller than it ought to be. That will ensure the depth values generated for the line will be smaller than the depth values generated for the triangle. Otherwise you will have z-fighting, as some pixels of the line will be in front and some will be behind the triangle due to roundoff error.