Faces

[annikk.exe]

Here's a rough plan for the programming:

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

Done.  I will declare a new matrix called Face, the columns will refer to each face, and the rows will contain the ID's of all the edges belonging to that face.
The length of the row will be variable.

2.  Next, check each vertex in turn to see if it is fully inside any faces.

Using the approach described here and some maths for the equation of a line, and the intersection of 2 lines, this should be possible.

3.  For each face the vertex is inside, check if it is closer than the vertex, or further away.

Using the approach detailed above in #2, check whether the vertex is in front of the face or behind it.  Some thought needed on how to do that, exactly...

[Pilchard123]

Are you assigning a z-value to the points? Which way is Z increasing?

[annikk.exe]

The points can have a Z-value if it's useful for them to have one.  Otherwise I just use the 2D representation that I am calculating anyway in order to render vertices at the correct location on the screen.
Sorry, that's a bit of a non-answer... but it really does depend on what is being calculated.  Further away from the camera is +Z, toward the camera is -Z.  The flat 2D plane upon which asteroids, seedlings, etc, exist, is Z = 0.


Lets talk a bit about what to do with an edge that is partially obscured by a face.


Consider these two objects.  Both of them contain 4 vertices, 4 edges, and 1 face.




Now lets move the Orange object so that it overlaps with the red object.  In this case, the orange object is closer to the camera than the red object.

As soon as they are overlapping, pseudo-vertices are created on the overlapped (red) object.




These pseudo vertices are dynamically created as needed.  The sequence above is "vertex, pseudo-vertex, pseudo-vertex, vertex".  I think I may be able to use the rule that vertex ID 0 to 1 = draw, 1-2 = don't draw, 2-3 = draw, etc.  I believe it will alternate in this way regardless of the arrangement of shapes.

[Pilchard123]

Well, if every point had a Z value, then you could do the above/below line test from before, with a little tweaking.

[annikk.exe]

Yep that's pretty much the maths right there which completes the rest of it, I think.  Technically it's intersection of a line with a plane, but the plane (ie the face) is ALWAYS flat, so any 3 vertices should give the equation of the plane.


Going back to pseudo-vertices for a moment...  does that system look workable to you Pilchard?  Can you think of any special cases that would break it?

[Pilchard123]

I typed this while you were also posting, so I'll leave it here for the future:

If you were to find any two points A(X, Y) and B(X, Y) where the line to check whether a point P is inside the polygon crosses the edges, you would then calculate the equation of the line between those two points in the plane through the line AB.

To do this you would calculate the equation of the line as I explained before, only using the Z values of the points A and B in place of the Y values.

Then, determine as before if the point is above (far side) or below (near side) of the line, and that will tell you if it is in front of or behind that face, regardless of the face's orientation. If the face is parallel to the asteroid plane (Z of A = Z of B), then compare the Z value of the point P with the Z of A.

Anyway, special cases...

What if there were holes in the faces, like a Menger sponge.

[annikk.exe]

If there were holes in the spaces, the holes would have vertices describing the edges of the hole, so it would be consistent still, I think...

I've thought of one problem though.  The solution thus far has no support for intersecting planes.
Look at the orange object above.  Imagine it in 3D space.  Now imagine that the left side of the orange object is in front of the red object, but the right side of the orange object is behind the red object.

This means at some point the two faces must intersect.  Therefore, pseudo-vertices would need to be created at the point of intersection.  In fact, every time pseudo-vertices are created, this possibility must be accounted for.

If the faces do not intersect, the pseudo-vertice on the right would always be at the intersection between the right edge of the orange object and the bottom edge of the red object.
If the faces DO intersect, the pseudo-vertice on the right would drift left into some place in the middle of the orange object.  A pseudo-vertice would be needed for the top edge of the orange object.  Another pseudo-vertice would be created at the point where the orange right edge and red bottom edge intersect - this time it would be for the orange edge.

Thinking about it, the alternating draw/dont draw rule would still work here.  But I will need to account for the face intersection problem.

[annikk.exe]

Should I bother with support for intersecting planes?
Thinking about it, an awful lot of complexity is created by adding support for it...

[annikk.exe]

Here's a complete conceptual plan for how the mechanics I will program ought to work.


Vertex Visibility

First, each vertex is checked against all faces except the face it belong to.

An imaginary horizontal line with Y value equal to that of the vertex being tested extends from the smallest X-value of any vertex in that face, until it reaches the X-value of the tested vertex.  All edges in the face being tested are checked to see if they overlap with this line.  If an overlap is detected, a counter called edgecounter is incremented.  edgecounter begins life with a value of 1, and is incremented by 1 every time an edge is encountered in this manner.

When all of the face's edges have been tested to see if they meet the imaginary horizontal line, we can then say whether this vertex appears inside the face, or outside it, in the following way:

Code: [Select]

if math.floor(edgenumber/2) == math.ceil(edgenumber/2) then
-- The vertex is inside the face.
else
-- The vertex is outside the face.
end
If a vertex is detected as being inside a face, the distance of that vertex from the camera is then compared to the distance from the plane at the line-of-sight point of overlap.  If the plane is found to be closer to the camera than the vertex, the vertex is marked as "hidden".  Hidden vertices will not be drawn, and edges will not be drawn to or from hidden vertices.


If a vertex is found to not be blocked by any faces in the way described above, the vertex is marked as visible.  It will be drawn, and edges will be drawn to/from the opposing vertex or the first-in-line pseudo vertex.


Edge Visibility




This diagram shows two intersecting planes.
A plane that enters another plane from above, and goes beneath it (thus being obscured), requires pseudo-vertices to be created at each edge which goes below the surface of the plane.

Top Two Pseudo-Vertices - Edge to Face Check
During edge checking, each 3D edge must be checked against each 3D face to determine if it passes through.
If it does, a pseudo-vertex must be created at the point where the line meets the plane.
The pseudo-vertex is assigned to the edge's list of pseudo-vertices.

Bottom Two Pseudo-Vertices - Edge to Edge Check
During edge checking, each 2D edge must be checked to see if it passes through another 2D edge.
If they meet, a pseudo-vertex must be created at the 2D position of their meeting.
The pseudo-vertex will be assigned to whichever edge is furthest from the camera at the point of overlap.



Drawing the edges
Once the above checks are complete, edges can be drawn.  For each edge, a list is created.  The first item in the list is the ID of the origin vertex of the edge, if visible.  The next items are the ID's of the pseudo-vertices belonging to that edge, if there are any.  The final item in the list is the ID of the desitnation vertex of the edge, if visible.  The vertices are added to the list in that specific order.

The edge is then drawn according to the following rule:

Between the first and second vertices, draw.
Between the second and third vertices, don't draw.
Between the third and fourth vertices, draw.
Between the fourth and fifth vertices, don't draw.
Etc.

If both vertices are hidden, and there are no pseudo-vertices, the edge is not drawn.

[annikk.exe]

I've figured out a special case that will cause my idea to not work.

The problem occurs when 3 planes are overlapping.  Consider this diagram.




This shows 3 planes overlapping.  The largest plane is in the foreground, the medium-sized plane immedietely behind it, and the small plane in the far background.
Note the 3rd horizontal line from the bottom.
From left to right, it contains: Vertex, Pseudo-Vertex, Pseudo-Vertex, Pseudo-Vertex, Vertex.

That would result in a completely incorrect series of lines behind drawn.


To fix it, it will be necessary to run a final check before drawing.
The check will determine if any of the pseudo-vertices created during that pass are being blocked (ie are inside) any faces.  If it finds a vertex that is within the bounds of a face - and it must be properly within the bounds of the face, sitting on the border is not sufficient - it then does an additional check to determine whether the plane or the Pseudo-Vertex is closer to the camera.  If the face is closer to the camera, the Pseudo-Vertex is considered null and will not be used as a draw destination.
Applying that rule would "discount" several of the Pseudo-Vertices from the edge, leaving this:



Red vertices have been "deactivated".
Now the 3rd horizontal line from the bottom would be drawn in one of the following two ways, depending on which vertex was selected as the origin vertex:

From left to right: First vertex is hidden, so do not draw it or draw from it.  Next vertex is a deactivated pseudo-vertex, so do not draw from it.  Next vertex is also a deactivated pseudo-vertex, so do not draw from it.  Next vertex is a pseudo-vertex - start drawing from here!  Final vertex is the last vertex in the list - so it is the destination vertex.  Draw the line to here.

From right to left: First vertex is the origin, draw from here to the next vertex, which is an active Pseudo-Vertex.  Don't draw to the next vertex, which is... ah... lets see, there's a deactivated pseudo-vertex, and another... and then a vertex which is hidden.  So don't draw any more lines.


Both result in an identical line being drawn, and both are correct.


With the relevant pseudo-vertices deactivated, the engine can proceed to the drawing stage.

[annikk.exe]

To help with visualising the above, consider this fully populated diagram.

[annikk.exe]

One final thing to be added - Edge to Asteroid check.
Pseudo vertices would need to be created for this.

This would require maths for the intersection of a circle and a line.  It would produce two different results.  Both results are checked and if they are within the bounds of the edge's two vertices, a pseudo-vertice is added.  That means if the edge enters the asteroid and reappears on the other side, both pseudo-vertices will correctly be created.  If it enters but does not exit, only one pseudo-vertice will be created, which is also the correct behaviour.

[Pilchard123]

General formula of a circle:

(X - A)^2 + (Y - B)^2 = R^2

A is the X coordinate of the circle's center (Asteroid.position.x?)
B is the Y coordinate of the center.
R is the radius of the circle.

[annikk.exe]

Realised I need to rethink how Faces will be stored...

[annikk.exe]

Face[Face ID][Origin Vertex ID][Edge ID] = Destination Vertex ID

Messy.. :/

I've realised Edges don't have unique ID numbers.  Instead they are more like properties of the origin vertices...
See, it's a good thing I figure all this stuff out BEFORE I actually start the really difficult coding...