3D Concepts

[annikk.exe]

At what point did you get lost, by the way? :>
EG, did you understand all the diagrams in the beginning of this thread?

[annikk.exe]

Code: [Select]

pseudovertexX[edge][pseudovertexnumber] = intersectX
pseudovertexY[edge][pseudovertexnumber] = intersectY
These HAVE to be matrices.
They can't be arrays.  Because we need to refer to all the different edges.. and then each of those edges can have multiple pseudovertices.

So we need 2 counters.  One for the edge, the other for the pseudos on that edge.

[annikk.exe]

Here's my pseudo-vertex generating code thus far:

Code: [Select]

function GeneratePseudoVertices()

-- this function populates the arrays or matrices with pseuso vertex data based on the existing vertices and edges.

-- ie edgefrom[i] and edgeto[i]

for reset = 0, numberofedges do

-- do a full reset of all pseudovertex counters
pseudovertexcount[reset] = -1

end

for edge = 0, numberofedges do
-- for each edge

-- create temporary shorthand variables for edge
efe = edgefrom[edge]
ete = edgeto[edge]


--for each other edge
for otheredge = edge + 1, numberofedges do

-- create temporary shorthand variables for otheredge
efoe = edgefrom[otheredge]
etoe = edgeto[otheredge]

-- calculate if edge intersects other edge
if LinesIntersect(vertex2dX[efe],vertex2dY[efe],vertex2dX[ete],vertex2dY[ete],vertex2dX[efoe],vertex2dY[efoe],vertex2dX[etoe],vertex2dY[etoe]) == true then
-- LinesIntersect() returned true, so there is an intersection
-- the intersection coordinates have been assigned to "intersectX" and "intersectY"
-- by the LinesIntersect() function


-- we must now determine the equivalent 3D point of intersection on both edges
-- using interectX and intersectY
edgepointX =
edgepointY =
edgepointZ =
otheredgepointX =
otheredgepointY =
otheredgepointZ =

-- now we must calculate which of these 3D points is furthest from the camera
if DistanceFromCamera(edgepointX,edgepointY,edgepointZ) > DistanceFromCamera(otheredgepointX,otheredgepointY,otheredgepointZ) then

-- increment the edge's pseudovertex counter
pseudovertexcount[edge] = pseudovertexcount[edge] + 1
local currentpseudos = pseudovertexcount[edge]

-- add the pseudovertex to edge
pseudovertexX[edge][currentpseudos] = intersectX
pseudovertexY[edge][currentpseudos] = intersectY

-- how do we know how many pseudovertices are on this edge so far?
-- maybe pseudovertexcount is an array... so that it can have a different value for all the different edges.
-- the value would indicate how many pseudovertices are on that particular [edge] so far.

else

-- increment the otheredge's pseudovertex counter
pseudovertexcount[otheredge] = pseudovertexcount[otheredge] + 1
local currentpseudos = pseudovertexcount[otheredge]

-- add pseudovertex to otheredge
pseudovertexX[otheredge][currentpseudos] = intersectX
pseudovertexY[otheredge][currentpseudos] = intersectY

end

else

-- LinesIntersect returned false, so there is no intersection here.  Do nothing.

end

-- finished checking [otheredge], onto the next one

end

-- finished checking [edge], onto the next one
end

-- finished generating pseudovertices

end

Functionally, she's sound... but incomplete, and two of the function calls have yet to be written.


Currently I'm puzzling over this bit:

Code: [Select]

-- LinesIntersect() returned true, so there is an intersection
-- the intersection coordinates have been assigned to "intersectX" and "intersectY"
-- by the LinesIntersect() function


-- we must now determine the equivalent 3D point of intersection on both edges
-- using interectX and intersectY
edgepointX =
edgepointY =
edgepointZ =
otheredgepointX =
otheredgepointY =
otheredgepointZ =
I'm stuck on how to calculate those variables.

[annikk.exe]

Here's the problem.

In a 2D field, two lines intersect.

I can see what proportion of Line A is to the left of Line B, and I can measure this amount.

I'll express this amount as a number like 0.45
If the amount was 1, it would be the entire length of the line.

So 0.45 means the intersection happens 45% of the way along line A.


Now here's the crazy bit.  Those 2D lines, are actually 3D lines; but they look 2D because they're on a flat monitor screen.

The 3D lines exist in 3D space, and their 2D coordinates are being calculated independently in the background.


Here's the thing though - those lines still intersect 45% of the way along in 3D space.

Or wait... maybe they don't...

No wait, THEY DO intersect when viewed from the angle of the camera.  That's the whole point.

So yes, when viewed from the angle of the camera, they do intersect at 45% and that's the value we're interested in.


So, given the following:

Line A, formed by:

Vertex1X
Vertex1Y
Vertex1Z

Vertex2X
Vertex2Y
Vertex2Z


Line B, formed by:

Vertex3X
Vertex3Y
Vertex3Z

Vertex4X
Vertex4Y
Vertex4Z

And in function form,

Code: [Select]

function Calculate3Dintersection(x1, y1, z1, x2, y2, z2, x3, y3, z3, x4, y4, z4)
-- code goes here
-- calculate intersectX, intersectY, and intersectZ
end
How do I calculate intersectX, intersectY, and intersectZ?

[annikk.exe]

I need to know whether edge or otheredge is farthest from the camera at the 3D point of their 2D intersection.

This is a really tough problem. :>

[annikk.exe]

I've got it.

I can draw an imaginary line between the camera and the 2D intersection point (where Z = 0).

So given this imaginary line, formed by:

GetCameraX()
GetCameraY()
CameraZ

intersectX
intersectY
z = 0

I can then work out where that line intersects the following two lines (and they DO intersect in 3D space):

Line 1, given by:

efe = edgefrom[edge]
ete = edgeto[edge]

vertex3dX[efe]
vertex3dY[efe]
vertex3dZ[efe]

vertex3dX[ete]
vertex3dY[ete]
vertex3dZ[ete]


Line 2, given by:

efoe = edgefrom[otheredge]
etoe = edgeto[otheredge]

vertex3dX[efoe]
vertex3dY[efoe]
vertex3dZ[efoe]

vertex3dX[etoe]
vertex3dY[etoe]
vertex3dZ[etoe]



I need the code that calculates line intersections in 3D space!

[Pilchard123]

I've just done this at college, I think. Want me to look it up? What information do you have on each line to calculate intersections of?

[annikk.exe]

Pilchard, if you could confirm if this is correct for me, that would be awesome :>

Line A, defined by two points:
[AX1, AY1, AZ1] [AX2, AY2, AZ2]

Line B, defined by two points:
[BX1, BY1, BZ1] [BX2, BY2, BZ2]


To find the intersection point between them:

Code: [Select]

t = (BX1 - AX1) / (AX2 + Bx1 - AX1 - BX2)


Xint = AX1 + ((AX2-AX1)*t)
Yint = AY1 + ((AY2-AY1)*t)
Zint = AZ1 + ((AZ2-AZ1)*t)
Note that this code assumes that the lines DO intersect.  Which they do in this case, always.

[Pilchard123]

My mistake, I'd just done intersection of line and plane, not line and line in 3D space. Sorry.

I'll have a look at that stuff you posted. It looks okay, but vectors are not my strong point...

[annikk.exe]

Think I will just go with it for now.  It seems like it should work..

[annikk.exe]

I've finished the pseudovertex generating code. :>

Debugging it now.

[annikk.exe]

Nearly there..

[annikk.exe]

Done!

In theory I now have a working pseudovertex generator. :>  Not quite sure how to test if it actually works as expected, but the level loads with it running now... so if all the maths is correct then hopefully it works. :>

Time for sleep.

[annikk.exe]

So, the parts that were outstanding to code were:

GeneratePseudovertices()
SortPseudovertices()
HideVertices()


And I needed to make some heavy modification to DrawEdges() to make it support pseudovertices.

The rest of the engine was completed already.


So basically the situation is that now I've finished coding one of those sections - GeneratePseudovertices().  I had to create a couple of other functions to support it, and I've completed all coding for those supporting functions too.

This is a huge step forward, one of the most complicated sections that I've been stuck with for a long time is now complete, and hopefully working.


I'm tempted to launch straight into sorting the pseudovertices, but I should really test what I've done so far.


To test it, I think I will create a new temporary function called by GeneratePsuedovertices() whenever it actually adds a pseudovertex to an edge (or an otheredge).  I'll convert to screendraw coordinates then render a red dot at the location of the intersection.
Then I can load up the level and check that the red dots appear in the right places, and behave they way they ought to. :>

Seeing pseudovertices for the first time is gonna be exciting!  Especially if it works correctly first time!

[Pilchard123]

Hate to be a downer, but don't forget the 90:90 rule...