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?

[Pilchard123]

That looks funny. It should have told you P was above BC, if you are using the example picture above...

EDIT: ...on the previous page.

EDIT2: And it should be bwlow CA. Workin on't.

[Pilchard123]

You must have gone wrong somewhere. I've just done it on paper and got the following results:

P is above AB (correct from picture)
P is above BC (also correct from picture)
P is below CA (also correct from picture)

Did you do those on paper or in code? If you did them in code, I'll have a look if you post it or PM me just the code to check the point's position.

[annikk.exe]

Ah maybe I got it wrong, I just did it by eye.

The point is, you can know whether P is above or below all the lines...  but that does not intrinsically tell you whether P is inside or outside the triangle.  How to do that last step?

[Pilchard123]

I think this is finished, but would need checking.

If P is above any line coming from the uppermost point of the triangle, it is outside of the face. Likewise, if it is below a line from the lowest point, it is outside. If it is neither of these things, it MAY be in the face.
If P is either above or below BOTH lines coming from the leftmost point, it is outside. If P is above or below both lines from the rightmost point, it is outside. Otherwise, if MAY be in the face.

If both these say that the point MAY be in the face, it IS in the face. However, if there are horizontal or vertical lines in the triangle, the following checks must be performed. In the case where there is only either a horizontal or only a vertical line, the other check may be ommited.

If there is a horizontal line AB and point O, then if O is above AB, P is outside if P is below AB.
If O is below AB, then P is out when above AB. Otherwise, it MAY be in the face.

If there is a vertical line AB in the triangle, and the remaining point O is to the left of it, P will be outside the triangle if P is to the right of the line.
If O is to the right of AB, then P is ouside if it is left of AB. Otherwise, it MAY be in the face.

[annikk.exe]

What is point O?  What does that represent?


There is a problem with this approach if (Px - Qx) = 0.  Then we'd get a divide by zero problem.


Also, this approach will work for triangles only, I think?  Ultimately it needs to be extendable to n-sided 2D polygons.

[annikk.exe]

Sorry by the way, I'm only bringing more questions and problems to the table rather than solutions... :p  I very much appreciate having your input to the discussion, it helps a lot.

[Pilchard123]

Point O is the point NOT in either a horizontal or vertical line in a triangle. Im,agine a triangle with points at A(0,0)  B(0, 10) and C(5, 5). The line AB is vertical, and could cause problems with determining the leftmost point, as both A and B are at the same X coordinate. C is the same as O in my previous post. Am I making sense?

Also, I dealt with (Px - Qx) = 0 in this post. It's right at the end.

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.

As for n-sided polygons, I haven't done them because I thought you were going to just use triangles. To be honest, triangles would be easier to work with as they don't deform. Why do you think most graphics/modeling stuff uses them? To determine whether a point is in an n-sided polygon, divide the polygon into triangles and check if it is any of them. The smallest number of triangles an n-gon can be divided into is n-2, and this is acheived by joining points as follows.

V0 - V2
V0 - V3
V0 - V4
...
...
...
V0 - V(n-1)

I'm sorry for effectively saying "just do it my way", but I don't know any other way to do this.

[annikk.exe]

No, that's ok.  Splitting larger polygons into triangles might be the way to go.

So for polygons, consider this:





How do we split that into triangles?

Also, if we draw a triangle between E, F, and A, we could say that P lies inside that triangle.  However, it still doesn't lie inside the polygon.  What to do in this eventuality?  Moreover, how do we detect this situation has occurred?  Measure the angle between AF and EF?

[Pilchard123]

Thow a hissy fit because that's not a convex shape.

Not sure really.

You could check every time you create a polygon whether each point would be inside the shape formed by the other points, and if it does, join that point to one that is at a position (n +- 2) from it to form two separate polygons and continue from there. However, this could be very computationaly expensive, so making many, simple shapes would be cheaper. That's actually another reason triangles are used (I think). They MUST be convex.

[annikk.exe]

An engine based purely on triangles is a possibility.
Hmm, I will think about this for a while...

[annikk.exe]

Ok, possible breakthrough incoming.
Take a look at this!! http://alienryderflex.com/polygon/

Apparently the thing I've drawn is called a "complex polygon" because it has concave components.
Turns out there IS a method of determining whether the point lies inside the polygon or not.  :>

[annikk.exe]

Right, what we do is we draw a horizontal line through P.

Then, we count how many times it crosses an edge.  We also count when we hit P.

[annikk.exe]

Consider these other diagrams for further evidence that this approach works:




The point has an Odd number, therefore it must be outside the n-sided polygon.



The point has an Even number, therefore it must be inside the n-sided polygon.



Can anyone think of a 2D shape composed only of straight lines for which this approach will not work?

[Pilchard123]

When it grases the corner of two intersecting lines. But then, I've read the page you linked and know that that's okay because of how it works in code. I think this one would be better than mine as it will allow for holes in the middle of the polygon, where mine wouldn't.

Also, 3 is odd.

[annikk.exe]

Thusly armed, I know that the only information required to declare a face should be the edges of which it is composed.

So a face is composed of at least 3 edges.
An edge is composed of exactly 2 vertices.
Vertices have coordinates.


With this structure clear, I will proceed to declare a face as a Matrix Column, with the row entries containing the ID's of the edges involved.

Code: [Select]

face = {}
for i = 0,numberoffaces do
face[i] = {}
end
Right, time to square this up with the rest of the plan..

[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...

[annikk.exe]

Maybe like this...


Face[Face ID][Numbered vertices that are part of this face] = Vertex ID


So...
Face[0][0] = firstvert + 0
Face[0][1] = firstvert + 1
Face[0][2] = firstvert + 3


That would indicate a face with ID 0 on part of the pyramid in the current test program.
This basically just means you are making a list of the vertices that will be part of that face.

So if I want, say, the X-coordinate of the first vertice in the list, I can access that like this:
temp = Face[0][0]
whatsthexcoord = vertex3dX[temp]

If I want to test edges, I access their coordinates in this way:

temp = Face[0][0]
tx = vertex2dX[temp]
ty = vertex2dY[temp]

temp2 = Face[0][1]
tx2 = vertex2dX[temp2]
ty2 = vertex2dY[temp2]

Now I can access coordinates for 3 different vertices on the face, allowing plane-checking to take place.  Furthermore, I can access the coordinates of each edge - due to the polygonal nature of Faces this can ALWAYS be inferred as vertex 0 to vertex 1, vertex 1 to vertex 2, 2 to 3, 3 to 4, and so on, until... 15 to 0.  That allows access to edge-checking of the face - this would be important in Vertex Visibility checking.

[annikk.exe]

I've implemented this data structure and halfway through coding it realised why it's not going to work.

I end up with something like this:

Code: [Select]

-- faces
i = numberoffaces

-- bottom face
face[i][0] = firstvert + 0
face[i][1] = firstvert + 1
face[i][2] = firstvert + 2
face[i][4] = firstvert + 3
...and this effectively just stores a list of all the vertices that are in the face.
But it doesn't tell me how they are connected up.  I don't know if 1 is joined to 3 by an edge, for example.  I need to be able to derive this information from the data structure because I need to know where the edges of the face are, so that I can check whether a point is inside them or not.

This data structure doesn't hold enough information.

[Pilchard123]

Could you not take the edges from the vertices themselves? If you know which vertices it includes, you know the edges. Just discard the ones that don't connect to other points in the face.

[annikk.exe]

....yea, I _just_ realised that and was about to post back !  you beat me to it, heh

[annikk.exe]

Ok so I guess I'll press ahead and try implementing the face data structure as planned.  Then there will have to be some crazyness later on to sort out where the edges are.  :p

[annikk.exe]

Made the data structure and declared the near-side face of the cube as an official Face.  The level still loads...  although it doesn't hide anything that's behind the face yet.

Going to have a try at the first section today, vertex visibility...

[Pilchard123]

You could make the faces have a semblance of visibility if, after they were all declared, all the vertices in a face were joined with lines that weren't edges. The crossing of the lines may be sufficient to look like a plane, particularly if they were thick enough. Don't know how hard that would be to do, though...

[annikk.exe]

I tried to make the vertex visibility code today.

It's too hard.  It's impossible trying to grab the face that is required, then the vertices.. work out which of them connects to which, and then finally to know what to test...

Too many for loops.  It would run slowly.

Something has to give.
Perhaps the data structure needs a radical re-think.

What's the best way to do this?  Vertices must be measured against faces, which are composed of a series of vertices... at least 3 to measure the interaction with the plane, but all of them must be known to test other vertices... and the edge information must be known..

What I want for the vertex visibility is something like this:

Code: [Select]

for faceID = 0,numberoffaces do
-- detect numberoffedges
passededges = 0
for edgeID = 0,numberofedges
v1 = edgefrom[edgeID]
v2 = edgeto[edgeID]
slope = (vertex2dX[v2] - vertex2dX[v1]) / (vertex2dY[v2] - vertex2dY[v1])
vertexXintercept = vertex2dY[v1] - (slope * vertex2dX[v1]) + vertex2dY[i]

-- intercept is equal to the X-value where the line crosses the P line

if vertex2dX[v2] <= vertex2dX[v1] then
vertex2dX[v2] = min
vertex2dX[v1] = max
else
vertex2dX[v1] = min
vertex2dX[v2] = max
end

if vertex2dX[i] > vertexXintercept and vertexXintercept > min and vertexXintercept < max then
passededges = passededges + 1
end
end

if math.floor(passededges) == math.ceil(passededges) then
-- the vertex is behind a face
draw = false
end

end
Maybe that's the way to structure edges.  EdgeFrom, and EdgeTo.  Two different arrays.

[annikk.exe]

So how to structure the faces..


I will need to refer to a face, like Face[ID of the face]
Then from that, I need to be able to derive the ID's of all edges involved.

Perhaps this is where a matrix would be useful.
I could have Face[ID of the face][numbered] = ID of the edge

So declaring the faces of the cube would be like:

Code: [Select]

-- nearside face
face[i][0] = firstedge + 0
face[i][1] = firstedge + 1
face[i][2] = firstedge + 2
face[i][3] = firstedge + 3
i = i + 1

-- farside face
face[i][0] = firstedge + 4
face[i][1] = firstedge + 5
face[i][2] = firstedge + 6
face[i][3] = firstedge + 7
i = i + 1

-- top face
face[i][0] = firstedge + 0
face[i][1] = firstedge + 4
face[i][2] = firstedge + 8
face[i][3] = firstedge + 9
i = i + 1

-- etc

[annikk.exe]

Anyone want to come up with an algorithm that auto-detects all the faces? :P

[Pilchard123]

EDIT2: You could just have people declare the faces themselves.  END EDIT2


Beware - badly-worded description of process below.

Could you use an adjacency matrix or list (although I think you may be already), then use a cycle detection algorithm to find cycles from/to a vertex P. Having taken note of all the cycles from P, compare all of them. Discard any cycle which contains a cycle within it. (e.g. {a,b,c,d,e,f,g,a} would be discarded if {a,b,c,a} exists, as there is a line between c and a) If there are more cycles from P than there are edges from it, discard all but the N shortest cycles, where N is the number of edges from P. This set of cycles will give you the vertex sets of each face including P.

Repeat this process for all vertices.

If a rotation of a cycle exists, (e.g. cycle{a,b,c,d,e,a} = cycle{c,d,e,a,b,c}), then discard ONE of them.

The resulting set of cycles gives you the vertex lists for ALL faces. I think.

EDIT:
You could force the algorithm to use each edge from P at least once.
Also, the cycle-within-cycle check may be unecessary if the algorithm you use always returns the shortest cycle...


http://www.cs.berkeley.edu/~kamil/teaching/sp03/041403.pdf       see at the bottom.

[Pilchard123]

Asked at college about my previous post: apparently something like that is possible, it'll just take a while for someone to code it. I won't go into the dtails as they are rather complex, but may it suffice that I say I know how to do what I want to do, just not quite how to code it.

[Pilchard123]

I've been thinking about my previous post. While my idea would be plausible, I'm not too sure how slow it would be, and there would be a few special cases where it wouldn't work, though I think they are rare enough to avoid with careful shape-building. Now if the engine worked in triangles...


How do you want the faces to be defined - as sets of edges or sets of vertices?

Also, to give each edge its own ID, could you not say lines go from P to Q, rather than point P being attached to Q. (make sense?)

[annikk.exe]

The new system is as follows:

Vertices are identified by a unique number known as a Vertex ID, and that number is used for the 3D X, Y and Z arrays, as well as the 2D X and Y arrays and various other arrays such as those pertaining to colour.
vertex3dX[3] = -500 means that vertex ID 3 has an x-coordinate of -500 in the 3D system.

Edges are also identified with a unique Edge ID.  The Edge data is stored in two arrays; EdgeFrom and EdgeTo.  The data contained inside each array slot is the Vertex ID of the Vertex that is participating in this edge.
If edgeFrom[0] == 4 and edgeTo[0] == 5 then Edge ID 0 is joining vertices 4 and 5.

Faces are stored in a matrix.  The matrix columns (ie in the left square brackets) correspond to the Face ID.  The matrix rows are of indeterminate length and each cell contains the Edge ID of a participating edge.  The edges can be listed in any order.
face[3][0] = 4 means that for Face ID 3, the first edge in the list is Edge ID 4.

[annikk.exe]

So here's where we are:

The problem of vertex visibility was always going to be a 2-stage process.
The first stage, which is now complete, is determining whether the vertex is inside a face from a 2D point of view... ie from the point of view of the camera.
That's done and working correctly.

Now the second part will perform an additional check, which decides whether the vertex is further away than the plane... and if so, it means the vertex should not be drawn because it is behind a face.

Here are the main tasks for the second part:


1.  Find the equation of the plane in the form Ax + By + Cz + D = 0
2.  Find the equation (in parametric form) of an imaginary line drawn between vertex and camera.
3.  Combine the two to find the X, Y and Z values of the point of intersection.
4.  Calculate the distance of this point from the camera.
5.  Compare the distance of the intersect point with the distance of the vertex.  If the distance to the vertex is greater than the distance to the intersection point, the vertex is behind a face and should be hidden.


Steps 4 and 5 I already know how to do.

[annikk.exe]

Here's what I have:

Code: [Select]

-- for a plane defined by coordinates (Px1, Py1, Pz1), (Px2, Py2, Pz2), and (Px3, Py3, Pz3)
-- and a line defined by coordinates (Lx1, Ly1, Lz1), (Lx2, Ly2, Lz2)
-- find the X, Y, and Z coordinates at which they intersect

-- first get 2 vectors along the plane
-- ("PV1x" stands for Plane Vector #1, X-coordinate)

PV1x = Px2 - Px1
PV1y = Py2 - Py1
PV1z = Pz2 - Pz1

PV2x = Px3 - Px1
PV2y = Py3 - Py1
PV2z = Pz3 - Pz1

-- now find the cross product
-- PV1 X PV2 = normal vector!

i = (PV1y * PV2z) - (PV1z * PV2y)
j = (PV1z * PV2x) - (PV1x * PV2z)
k = (PV1x * PV2y) - (PV1y * PV2x)


-- define d
planex = i
planey = j
planek = k
d = (i * PV1x) + (j * PV1y) + (k * PV1z)



-- for the line, calculate tx, ty, tz
tx = Lx2 - Lx1
ty = Ly2 - Ly1
tz = Lz2 - Lz1


-- calculate t

t = (i * (tx + PV1x)) + (j * (ty + PV1y)) + (k * (tz + PV1z))


-- calculate intersection coordinates
intersectX = t * tx
intersectY = t * ty
intersectZ = t * tz

It doesn't work perfectly.  There's something wrong.  But what..? :>

[Aino]

Sudden crash for me D:

Edit: If it is dependand of dividing with camerax or y then that mi9ght be it... I got no real idea, but not recreateable :/

[annikk.exe]

Fixed it, I think.  I was calculating "t" using the normal vector instead of the vertex coordinate.  :P  And I needed to subtract "d".

[annikk.exe]

Oh, wait.. no...  it's still broken. :<

[Aino]

Talking stuff that I don't have much idea of... By the way annikk; what is "t" for you?

Just asking, I have a sense that it might mean temporarily

And what is the problem, I don't see any... or is it that the lines ain't disapearing?

[annikk.exe]

It's "t" from the parametric equation of a line.  It's a maths convention that I just copied for the variable name.

[annikk.exe]

No further forward with this..

I'm having a lot of difficulty translating this from maths into code.
A lot of the programming examples out there use facilities available in the language in which they are written to represent things like vectors, and there are shortcut commands such as cross() for the cross product...  the rest all seem to be written in complex mathematical notation, or substitute in coordinates at some point in order to solve something.  Argh...

[Aino]

What?!

The great Annikk can't be in vain D:

Well, I'm no good at that, so I'm to no help yet again -.-'

[annikk.exe]

Hmm, for the "great Annikk" standing on the shoulders of giants is one thing, balancing is another...

[Bonobo]

Youze folks are a luvable bunch!

Just sayin’.

[annikk.exe]

With some help, I have identified a possible algebra problem.


I have this:

Code: [Select]

0 = (i * ((t * tx) + Lx1) - Px1)) + (j * ((t * ty) + Ly1) - Py1)) + (k * ((t * tz) + Lz1) - Pz1))
t is the unknown, and the value i need to calculate.  The equation has to be reshuffled to have t on the left side, and all the other terms on the right side.

[Bonobo]

I can’t do such things, but I know that something’s wrong with your parentheses here. Two or three closing ones too many.

[Sniped50]

My advice would be (don't know if this would work) splitting the equation into three equal parts (so they contain 1 t each), then working out t = ? for each of them. Once you've done that, I think you can just add them together so you get 3t = ? + ? + ?, and then just divide by 3, t = (? + ? + ?)/3.

Would that work, Annikk?

PS: Bonobo is right. You do actually have too many closing parentheses. By my count, 9 opening ones and 12 closing ones.

[annikk.exe]

Ah, well-spotted.  It should be like this, I think:

Code: [Select]

0 = (i * (((t * tx) + Lx1) - Px1)) + (j * (((t * ty) + Ly1) - Py1)) + (k * (((t * tz) + Lz1) - Pz1))

[annikk.exe]

Code: [Select]

t = ((i * (Px1 - Lx1)) + (j * (Py1 - Ly1)) + (k * (Pz1 - Lz1))) / ((i * (Lx2 - Lx1)) + (j * (Ly2 - Ly1)) + (k * (Lz2 - Lz1)))

Perhaps this?

[dragoonreas]

Code: [Select]

t = ((i * (Px1 - Lx1)) + (j * (Py1 - Ly1)) + (k * (Pz1 - Lz1))) / ((i * (Lx2 - Lx1)) + (j * (Ly2 - Ly1)) + (k * (Lz2 - Lz1)))

Perhaps this?

Where did tx, ty and tz go?

Code: [Select]

t = ((i * (Px1 - Lx1)) + (j * (Py1 - Ly1)) + (k * (Pz1 - Lz1))) / ((i * tx) + (j * ty) + (k * tz))That's the answer I got using this site.

(click to show/hide)

Code: [Select]

0 = (i * (((t * tx) + Lx1) - Px1)) + (j * (((t * ty) + Ly1) - Py1)) + (k * (((t * tz) + Lz1) - Pz1))
u=tx
v=ty
w=tz
m=Lx1
n=Ly1
o=Lz1
q=Px1
r=Py1
s=Pz1
0 = (i * (((t * u) + m) - q)) + (j * (((t * v) + n) - r)) + (k * (((t * w) + o) - s))                    <-- Input for the website
t = (-j * n + j * r - k * o + k * s - i * m + i * q) / (j * v + k * w + i * u)                           <-- Output from the website
t = (-j * Ly1 + j * Py1 - k * Lz1 + k * Pz1 - i * Lx1 + i * Px1) / (j * ty + k * tz + i * tx)
t = ((i * (Px1 - Lx1)) + (j * (Py1 - Ly1)) + (k * (Pz1 - Lz1))) / ((i * tx) + (j * ty) + (k * tz))

[annikk.exe]

tx = Lx2 - Lx1

So our answers are actually the same.

It seems like we are dividing one dot product by another.  That's how a lot of people seem to be doing it..

[annikk.exe]

Lets have a look at ALL the code that governs this:

Code: [Select]

-- get plane coordinates
Px1 = vertex3dXtransformed[firstvertex]
Py1 = vertex3dYtransformed[firstvertex]
Pz1 = vertex3dZtransformed[firstvertex]

Px2 = vertex3dXtransformed[secondvertex]
Py2 = vertex3dYtransformed[secondvertex]
Pz2 = vertex3dZtransformed[secondvertex]

Px3 = vertex3dXtransformed[thirdvertex]
Py3 = vertex3dYtransformed[thirdvertex]
Pz3 = vertex3dZtransformed[thirdvertex]


-- get line coordinates
Lx1 = GetCameraX()
Ly1 = GetCameraY()
Lz1 = CameraZ

Lx2 = vertex3dXtransformed[vertexID]
Ly2 = vertex3dYtransformed[vertexID]
Lz2 = vertex3dZtransformed[vertexID]


-- get 2 vectors along the plane
-- PV1x stands for Plane Vector #1, X-coordinate

PV1x = Px2 - Px1
PV1y = Py2 - Py1
PV1z = Pz2 - Pz1

PV2x = Px3 - Px1
PV2y = Py3 - Py1
PV2z = Pz3 - Pz1

-- now find the cross product, which is a line perpendicular to the plane
-- PV1 X PV2 = normal vector!
i = (PV1y * PV2z) - (PV1z * PV2y)
j = (PV1z * PV2x) - (PV1x * PV2z)
k = (PV1x * PV2y) - (PV1y * PV2x)

-- for the line, calculate tx, ty, tz
tx = Lx2 - Lx1
ty = Ly2 - Ly1
tz = Lz2 - Lz1

t = ((i * (Lx1 - Px1)) + (j * (Ly1 - Py1)) + (k * (Lz1 - Pz1))) / ((i * (Lx2 - Lx1)) + (j * (Ly2 - Ly1)) + (k * (Lz2 - Lz1)))

intersectX = (t * tx) + Lx1
intersectY = (t * ty) + Ly1
intersectZ = (t * tz) + Lz1


-- calculate distance from intersection
intersectdistance2d = (GetCameraX() - intersectX)^2 + (GetCameraY() - intersectY)^2
intersectdistance3d = math.sqrt((CameraZ - intersectZ)^2 + (intersectdistance2d))


if intersectdistance3d > distance3d then
-- return false if the vertex is in front of the face
return false
else
-- return true if the plane is closer than the vertex
return true
end

[annikk.exe]

I've tried 2 different versions of t.
One like this:

Code: [Select]

t = ((i * (Lx1 - Px1)) + (j * (Ly1 - Py1)) + (k * (Lz1 - Pz1))) / ((i * (Lx2 - Lx1)) + (j * (Ly2 - Ly1)) + (k * (Lz2 - Lz1)))

And one like this:

Code: [Select]

t = ((i * (Px1 - Lx1)) + (j * (Py1 - Ly1)) + (k * (Pz1 - Lz1))) / ((i * (Lx2 - Lx1)) + (j * (Ly2 - Ly1)) + (k * (Lz2 - Lz1)))
Neither is working :<  But we're getting close now, I think...

[Bonobo]

Ouf … http://www.myalgebra.com/algebra_solver.aspx shows two different solutions w/ mighty big square roots




<edit>

Dang. I missed a whole page of posts …

</edit>

[Pilchard123]

Are tx, ty and tz their own thing, or t*x, t*y, t*z? It has a _*massive*_ effect on the outcome.

To me, the t*tx is the same as (t^2)x, and that is what most other people would say as well.

What are you even trying to do?

[annikk.exe]

"tx" is NOT "t * x".
"tx" is a unique variable.  It represents the x-component of the vector of the line from L1 to L2.  I gave it a short name instead of something more descriptive to keep the calculations reasonably short.


I've had a breakthrough, though not where I was expecting.
I found a problem with my plane-overlapping-in-2D code.  It doesn't work well with horizontal or vertical edges.  Testing and writing code to trap for it now...  Seems like the only reason I thought it was working correctly before is because I had my test cube rotating constantly.

[annikk.exe]

I've almost cracked it.  Trapping for horizontal and vertical seems to work fine, and the vertices of static objects behave correctly now.

There's still a really bizarre problem, though.  The vertices on the right hand side of each static cube flicker.  I have no idea why.  Moving or zooming the camera seems to "excite" them to flicker more.

[Aino]

Good to hear

I hope to make some mor emodels, it's very fun, maybe I'll even make an editor for it when you're done, who knows...

[annikk.exe]

A girl from another forum I post on has taken a look at the maths for the line-through-plane check and confirmed this is what the calculation for t should be:

Code: [Select]

t = ((i * (Px1 - Lx1)) + (j * (Py1 - Ly1)) + (k * (Pz1 - Lz1))) / ((i * (Lx2 - Lx1)) + (j * (Ly2 - Ly1)) + (k * (Lz2 - Lz1)))
She studies physics and this stuff is apparently quite simple for her so hopefully it's gonna work this time.  :>

So once I get this flickering issue sorted out, I'll have another crack at that and see if I can get it to work with expected behaviour.  :>

Now, what is up with this flickering, hmm?  It's bizarro.

[Aino]

Ohh, wow

How many more cracks are there?

[annikk.exe]

If by cracks you mean attempts, that number is undefined.. :p

[Aino]

Sounds scary...

Gonna do a little more relaxing things for now: creating a risk map, a proper risk, not the eufloria map I released

[annikk.exe]

This bug is really annoying.  I can't figure out why it produces this behaviour.  Very strange....

[Aino]

I know that feeling :/

Adventure Map is so annoying with that one bug... If I kept the Maps internaly in the file, it would get alot simplier, but harder to create maps...

[Pilchard123]

The flickering may be the loops not completing before the next fram is drawn, or something. Or it may be that they so long that it's below the 'framerate' for the human eye.

[Aino]

Or it may be that a part of the algorythm is failing and the parts are flickering?

Or the calculations take so long time to do(doubting this one though)...

Better check if the last ones usually flickers, the last IDs

[annikk.exe]

I don't think it's a case of too much stuff per loop.  Bizarrely, if I turn on my (currently not working correctly) code to check plane depth, the flickering disappears!  There is no reason why it should do that.  Very strange...


I guess I should post the code that is producing the erroneous behaviour.

Code: [Select]

for faceID = 0,numberoffaces do

-- detect numberoffedges
numberofedgesinthisface = -1
for i = 0,100 do
if face[faceID][i] ~= nil then
numberofedgesinthisface = numberofedgesinthisface + 1
else
break
end
end


passededges = 0
-- this counter is used to check how many edges are passed through to the left of this point

for faceEdgeNumber = 0,numberofedgesinthisface do
-- for each edge in this face

edgeID = face[faceID][faceEdgeNumber]
-- use the ID of the selected edge

v1 = edgefrom[edgeID]
v2 = edgeto[edgeID]
-- set v1 and v2 equal to the ID's of the vertices that join this edge

partoftheface = false

if v1 ~= vertexID and v2 ~= vertexID then
-- make sure the point passed to us in this function is not the same point mentioned in v1 or v2...

if math.floor((vertex2dX[v2] - vertex2dX[v1])) == 0 or math.ceil((vertex2dX[v2] - vertex2dX[v1])) == 0 then
-- vertical edge detected

if vertex2dY[v2] <= vertex2dY[v1] then
minv = vertex2dY[v2]
maxv = vertex2dY[v1]
else
minv = vertex2dY[v1]
maxv = vertex2dY[v2]
end

if vertex2dX[vertexID] > vertex2dX[v2] and vertex2dY[vertexID] > minv and vertex2dY[vertexID] < maxv then
passededges = passededges + 1
end

elseif (vertex2dY[v2] - vertex2dY[v1]) == 0 then
-- horizontal edge detected.  It is therefore parallel to the P line and as such will never intersect.
-- so no chance to add a passed edge here.

else
slope = (vertex2dY[v2] - vertex2dY[v1]) / (vertex2dX[v2] - vertex2dX[v1])
-- first calculate the slope of the line formed by the two coordinates

-- we need to find the X-value where the line drawn between v1 and v2 crosses the axis of vertexID

Yintercept = (-slope * vertex2dX[v1]) + vertex2dY[v1]
-- this is the Y-intercept

vertexXintercept = (vertex2dY[vertexID] - Yintercept) / slope
-- vertexXintercept is equal to the X-value where the line crosses the P line
-- ie vertexXintercept is equal to the value of X when this edge reaches Y = vertex2dY[vertexID]

if vertex2dX[v2] <= vertex2dX[v1] then
minv = vertex2dX[v2]
maxv = vertex2dX[v1]
else
minv = vertex2dX[v1]
maxv = vertex2dX[v2]
end

if vertex2dX[vertexID] > vertexXintercept and vertexXintercept > minv and vertexXintercept < maxv then
passededges = passededges + 1
end
end

else
partoftheface = true
break
end
end

if math.floor(passededges / 2) ~= math.ceil(passededges / 2) and partoftheface == false then
-- the vertex is inside a face
draw = false
end
end

This part of the code is the part which checks if a vertex is "inside" a face, based on the 2D coordinates.
These pictures from earlier in the thread show the basic technique for doing this:

[Aino]

Sh*t...

I really have to say: It's to much for my brain to catch up with, stupid boat trip I was on, making me skip all the posts you and Pilchard did before :/

[annikk.exe]

Breakthrough! :D

From wikipedia:

Most implementations of the ray casting algorithm consecutively check intersections of a ray with all sides of the polygon in turn. In this case the following problem must be addressed. If the ray passes exactly through a vertex of a polygon, then it will intersect 2 segments at their endpoints. While it is OK for the case of the topmost vertex in the example or the vertex between crossing 4 and 5, the case of the rightmost vertex (in the example) requires that we count one intersection for the algorithm to work correctly. A similar problem arises with horizontal segments that happen to fall on the ray. The issue is solved as follows: If the intersection point is a vertex of a tested polygon side, then the intersection counts only if the second vertex of the side lies below the ray. This is effectively equivalent to considering vertices on the ray as lying slightly above the ray.

This is my problem.  I have thought about it, and I am 100% sure this is what the problem is.

[Aino]

Hmmm, by the way annikk, what is your ultimate purpose of this 3d thing?

It would be awesome with some sort of sun in the background of the map

[annikk.exe]

FIXED.  YEAH BABY!!!!"!  fejwpqw JPJWF PJWFPFWFW!"!"

[annikk.exe]

Witness my perfectly vertical/horizontal cube, and it's gleaming east vertices, in their steadfast unflickering glory !


Now to give vertices their depth perception...

[Aino]

Hmm, it has gone from smooth to a little laggy though... And when removing vertexes, try to check the z depth, I see vertexes infront of another face being removed :/

GOOD JOB THOUGH

[annikk.exe]

I will do an optimisation run soon to get it running a bit faster.  I want to get vertices to recognise when they are inside a polygon, but are closer than the face to the camera.

My current problem is that my cross product always returns (0,0,0).


Let P1, P2 and P3 be vertices that belong to the face being checked.
This code is supposed to calculate the plane's normal based on the three sets of coordinates.

Code: [Select]

PV1x = Px2 - Px1
PV1y = Py2 - Py1
PV1z = Pz2 - Pz1

PV2x = Px3 - Px1
PV2y = Py3 - Py1
PV2z = Pz3 - Pz1

-- now find the cross product, which is a line perpendicular to the plane
-- PV1 X PV2 = normal vector!

i = (PV1y * PV2z) - (PV1z * PV2y)
j = (PV1z * PV2x) - (PV1x * PV2z)
k = (PV1x * PV2y) - (PV1y * PV2x)
The values of i, j and k are always 0.