Faces

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