Faces

[annikk.exe]

Ok, some questions...

1.  What is a face?
2.  How do I tell if a face is obstructing the view of something else?
3.  If a face is partially obscuring some edge at an arbitrary point along the edge's length, how do I calculate coordinates where the obstruction ends and the line should begin?


Feel free to answer these.  I will answer them in my own time, this is all just to help me conceptualise what needs to be done.

[annikk.exe]

Ok so.. 1)... what is a face..


A face is a 2D plane in a 3D environment.  It blocks vision of any vertices, edges, or parts of edges, that would otherwise be visible to an observer.  If this 2D plane gets in the way of your view of any arbitrary point in the coordinate system, your view will be blocked by the face.

A face is 2 dimensional, and must therefore have at least 3 edges, meaning a minimum of 3 vertices per face.
A face could also have dozens of edges.  The edges would link vertex-to-vertex until it reaches back round in a closed loop.  That closed loop may then be declared to be a face (but not always).

In the context of Eufloria, a face will not be visible.  Its presence will be discernable by the fact that it obscures vertices and edges behind it.

Without faces, the engine is only capable of wireframe.  Wireframe is more useful than single point rendering, however at this point my inclination is "why stop there?".  The addition of faces will allow objects and scenes to be rendered.  You could construct a spacecraft made of vertices, edges, and faces - you could create some large pulsing stars for the engine flares...  The body of the craft would have faces, but the glass cockpit would not (allowing an observer to see straight through it to the edges/vertices other side).  You could rotate the spacecraft and look at it from different angles.  The spacecraft could be made to fly around in 3D space.  One might attempt to build an AI to guide the spacecraft on an automated path, or fight other spacecrafts.  Or it might be the case that the spacecraft makes malicious deliveries of enemy seedlings, and that could be the visual mechanic behind the level.  It's a bit cooler than seedlings just spawning randomly!

[Pilchard123]

Try looking for "back face culling" or "back face occlusion" on Google or som't. Also, frustrum culling and the like.

EDIT the first wikipedia article on back-face culling mentions the dot product of two lines. I told Aino how to do that somewhere around here.

[annikk.exe]

Here's a rough plan for the programming:

1.  First I need to develop a method of declaring faces.

2.  Next, check each vertex in turn to see if it is fully inside any faces.
3.  For each face the vertex is inside, check if it is closer than the vertex, or further away.
4.  If it's closer than the face, continue to draw the vertex.  If it is farther away than the face, do not draw the vertex.

5.  Check each edge to see if it overlaps with any other edge.
6.  If it does not overlap with any other edge, and both its connecting vertices are not being drawn, the edge is fully obscured behind (or is in front of) a face.  Detect this and do not draw if appropriate.
7.  If it DOES overlap with any other edge, and one or both its connecting vertices are not being drawn, create new "pseudo-vertices" along the edge at the points of overlap with the other edge.  If a pseudo vertex exists, it temporarily replaces its corresponding real vertex, and the edge is drawn between pseudo vertices with preference, otherwise falling back on drawing to the real vertices.
8.  Finally, if the edge overlaps with another edge, but both its vertices are being drawn, compare the distance from the camera of the two edges at the point indicated by the psuedo-vertex.  Whichever edge is farther away will have pseduo-vertices created and part of it will not be drawn.  If the edges "cross over" so that Vertex 1A is closer than 2A, but 1B is further away than 2B, calculate the point at which they cross over and create pseudo-vertices at that point.




Does that account for everything?  Hmm...

[annikk.exe]

Perhaps this helps to answer question #2

http://softsurfer.com/Archive/algorithm_0104/algorithm_0104B.htm

[annikk.exe]

And for #3, here is how I calculate the coordinates of pseudo-vertices:

http://www.mathopenref.com/coordintersection.html

[annikk.exe]

This is getting insanely complicated real fast...

Still struggling to figure out how to declare faces in a way that is useful..

[Pilchard123]

Could faces be defined as an (not really) infinite set of lines along the face and the face is the set of points that are on those lines?

I suppose you'd need a IsPointOnLine() function for that, but...

[annikk.exe]

It needs to test whether it is enclosed by the lines, not on them.  That is a big part of the problem at the moment.



Consider this diagram:





Now I will solve this problem using only the power of my mind:

No, it is not inside the triangle.


There, that was easy.  :>  Now it's a pretty interesting subject about how I was able to tell that just by looking at it.  I didn't have to do any maths or anything, my brain just worked it out intuitively.  There's one for the psychologists to discuss...

But the question that we really want to answer here is, how do we calculate a yes or no answer to the posed question programatically, so that it can be done by a computer?

[Pilchard123]

Would the point have to be ON the plane, or just between it and the camera (or hidden behind the plane)?

EDIT:

To draw a plane through three defining points...    i j and k are the unit vectors in the three directions X, Y and Z.
http://www.jtaylor1142001.net/calcjat/Solutions/VPlanes/VP3Pts.htm

If you were to put the coordinates of the point P into the equation of the plane, and it still satisfies the equation, the the point is on the infinite plane for that equation. AS to whether it is inside a given region on the plane, that is doable, but I would have to do a bit of scribbling to sort my thoughts out first.

[annikk.exe]

Would the point have to be ON the plane, or just between it and the camera (or hidden behind the plane)?

For now, lets just consider the above problem strictly in 2D.  Chances are good that's how it will be calculated in the final engine anyway.

The main thing I am interested in for now is how to tell if it's inside the triangle or not.

[annikk.exe]

That's some good thinking RE the point in plane thing, though...

[Pilchard123]

2D is fairly easy to deal with. Notes coming soon.

[Pilchard123]

Right, to decide if a point is above or below a line, find the lines equation in the form Y - MX - C = 0. M and C are constants to be found. It is not necessary that they be integers. (Ay, I've done too many maths papers. That is almost exactly how they would have a question phrased.)

This is fairly long winded, so bear with me. Assume the line is between points P and Q. Also assume the coordinate system is such that moving UP the plane increases Y and moving RIGHT increases X. I can't remember what Eufloria uses, but it shouldn't be much of a problem to tweak it to work.

To find the gradient of the line, take (Py-Qy) and divide by (Px-Qx). Call this result M.

Then, take (Py-MPx). Call this C.

You now have the information for the equation in the form Y = MX + C, where X and Y are coordinates of any point on the line.

Now this, when rearranged is equal to Y - MX - C = 0  .  To check whether a point is above or below a line, insert the coordinates of the point into the above equation.

If it is satisfied, the point is ON the line.
If it is FALSE and Y - MX - C is a value LESS THAN 0, the point is below the line.
If it is FALSE and Y - MX - C is a value GREATER THAN 0, the point is above the line.


SPECIAL CASE: If (Px - Qx) is equal to zero, then the line is vertical, and calculating the gradient will result in (Py - Qy)/0. Not good. In this case, simply check what the X value of the point is in relation to the line and that will tell you which side of the line it is on. For horizontal lines (Py - Qy) = 0, there is not such error, and the long method can be used.

[annikk.exe]

Ok sweet.  So now I can test the following:


Is P above or below AB?
Is P above or below BC?
Is P above or below CA?


The answers are as follows:

Above
Below
Above


Now what? :>  Is P inside the triangle?