### Author Topic: Faces  (Read 7019 times)

0 Members and 1 Guest are viewing this topic.

#### annikk.exe

• Achiever
• Ent
• Thank You
• -Given: 0
• Posts: 1,794
##### Re: Faces
« Reply #120 on: July 01, 2011, 10:37:34 AM »
So, what sort of data structure is require for pseudo-vertices?

Pseudo-vertices are properties of an edge.  When an edge is drawn, the number and coordinates of pseudo-vertices along its length must be known.
There are two ways I could store the coordinates.  I could either specify the X and Y coordinates individually in two seperate matrices (first box is the edge ID, second box is the ID of the pseudo-vertex, value is the coordinate).  Or, I could store a single value between 0 and 1 which represents the proportion of the length along the edge where the pseudo-vertex lies.

The latter approach results in one less matrix, but involves a lot more calculations as the proportion would need to be calculated once initially to establish the proportion, then again when it is rendering time to bounce out some actual coordinates.  I think an additional data structure is probably preferable here.

Now, when we're storing coordinates...what do we store?  Should it be 2D or 3D coordinates?
2D would be a cheaper calculation... but we want to calculate depth anyway to tell whether the pseudo-vertex should be disabled or not.  2D doesn't let us do that.... but still, I think 2D is the best approach.  We can follow it up with a line intersecting plane calculation to determine whether a face or a pseudo-vertex is closer, that allows us to calculate the enabled/disabled state.

So, that means we'd have the following:

Code: [Select]
`pseudovertex2dX[edgeID][pseudovertexID] = X-coordinatepseudovertex2dY[edgeID][pseudovertexID] = Y-coordinatepseudovertexenabled[edgeID][pseudovertexID] = booleanvertexenabled[vertexID] = boolean`

A key property of this data structure is that it has to expand or contract in size dynamically from frame to frame.  In frame 200, there may be no overlapping edges at all, and thus no pseudo-vertices.  In frame 250, maybe there are a bunch of overlapping edges and edge ID's 3 and 4 have 4 pseudo-vertices each.  The engine must be able to handle this automatically.

How to do that?

Code: [Select]
`for edgeID = 0,numberofedges do -- check if any edges are overlapping any other edges -- if found to overlap another edge, check that this edge is further away at the 2D point of overlap -- assuming it IS further away, create a pseudo-vertex at the point where the overlap takes place -- if it's not further away, don't create the pseudo-vertex for this edge (it will be created for the other edge instead when it is checked) -- check if any edges are intersecting with a plane -- if intersecting a plane, create a pseudo-vertex at the point of overlapendfor pseudovertexID = 0,numberofpseudovertices do -- check if this pseudo-vertex is inside a face -- if not inside a face, set state to enabled. -- if it IS inside a face, check if this pseudo-vertex is behind the face.  if behind, set state to disabled -- if in front, set state to enabledendfor i = 0,numberofedges do if i == 0 then -- DrawFrom = EdgeFrom end for j = 0,NumberOfPseudoVerticesInThisEdge do if `
Hmm, that last part is going to be tricky.  Not quite sure how to represent that in pseudo-code right now..

#### annikk.exe

• Achiever
• Ent
• Thank You
• -Given: 0
• Posts: 1,794
##### Re: Faces
« Reply #121 on: July 02, 2011, 01:13:07 AM »
Why bother storing disabled pseudo-vertices?  Why not just do the depth check whenever a potential pseudo-vertex is detected inside a face, and if it turns out it would be disabled anyway, just don't create it..

#### annikk.exe

• Achiever
• Ent
• Thank You
• -Given: 0
• Posts: 1,794
##### Re: Faces
« Reply #122 on: July 04, 2011, 10:18:21 AM »
Lets have another try...

Code: [Select]
`for edgeID = 0,numberofedges do -- check if any edges are overlapping any other edges -- if found to overlap another edge, check that this edge is further away at the 2D point of overlap -- assuming it IS further away, check that the point of intersection is not behind any other face -- if it is not behind any other face, create a pseudo-vertex at the point where the overlap takes place -- if it's not further away, don't create the pseudo-vertex for this edge (it will be created for the other edge instead when it is checked) -- check if any edges are intersecting with a plane -- if intersecting a plane, check if the point of intersection is behind any other faces -- if the point of intersection is NOT behind any other face, create a pseudo-vertex at the point of overlapendfinisheddrawing = truefor i = 0,numberofedges do if i == 0 then -- DrawFromX = EdgeFrom X -- DrawFromY = EdgeFrom Y end if pseudovertex2dX[i][0] ~= nil then DrawToX = pseudovertex2dX[i][0] DrawToY = pseudovertex2dY[i][0] -- Draw line from DrawFrom to DrawTo finisheddrawing = false else DrawToX = EdgeTo X DrawToY = EdgeTo Y -- Draw line from DrawFrom to DrawTo end if finisheddrawing == false then for j = 1, numberofpseudovertices do if math.ceiling(j) ~= math.floor(j) then DrawFromX = pseudovertex2dX[i][j] DrawFromY = pseudovertex2dY[i][j] if pseudovertex2dX[i][j] ~= nil then DrawToX = pseudovertex2dX[i][j + 1] DrawToY = pseudovertex2dX[i][j + 1] else DrawToX = EdgeToX DrawToY = EdgeToY end end end endend`

That should do it!

#### annikk.exe

• Achiever
• Ent
• Thank You
• -Given: 0
• Posts: 1,794
##### Re: Faces
« Reply #123 on: August 01, 2011, 12:15:56 PM »
I started thinking about this again today and realised there is another problem with the pseudovertices implementation.

The problem is that when I generate the pseudovertices, I am checking edges according to their ID numbers.  So for example I pick Edge ID 0 first, and check it against Edge 1, then Edge 2, then Edge 3, and so on.

If pseudovertices are created as a result of this, they may not necessary appear in the correct order.  So as well as creating a list of pseudovertices, I will have to find a way to pick from them selectively according to whichever one is next closest as you proceed along the Checked Edge.

A method to do this is to check all the pseudovertices that belong to the edge each time the next pseudovertex is being selected, and choose the one that is next biggest according to its X value (or Y value if it's a perfectly vertical edge).  The next pseudovertex would be selected by looking for the nearest value of X that is still greater than the current value of X.

• Ent
• Thank You
• -Given: 1