### Author Topic: 3D Concepts  (Read 4112 times)

0 Members and 1 Guest are viewing this topic.

#### annikk.exe

• Achiever
• Ent
• Thank You
• -Given: 0
• Posts: 1,794
##### Re: 3D Concepts
« Reply #30 on: May 17, 2012, 03:17:40 PM »
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

• Achiever
• Ent
• Thank You
• -Given: 0
• Posts: 1,794
##### Re: 3D Concepts
« Reply #31 on: May 17, 2012, 05:45:46 PM »
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

• Achiever
• Ent
• Thank You
• -Given: 0
• Posts: 1,794
##### Re: 3D Concepts
« Reply #32 on: May 17, 2012, 06:37:19 PM »
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

• Achiever
• Ent
• Thank You
• -Given: 0
• Posts: 1,794
##### Re: 3D Concepts
« Reply #33 on: May 17, 2012, 06:46:33 PM »
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 intersectZend`
How do I calculate intersectX, intersectY, and intersectZ?
« Last Edit: May 17, 2012, 06:53:53 PM by annikk.exe »

#### annikk.exe

• Achiever
• Ent
• Thank You
• -Given: 0
• Posts: 1,794
##### Re: 3D Concepts
« Reply #34 on: May 17, 2012, 07:30:37 PM »
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

• Achiever
• Ent
• Thank You
• -Given: 0
• Posts: 1,794
##### Re: 3D Concepts
« Reply #35 on: May 17, 2012, 08:05:30 PM »
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

• Tester
• Old Oak
• Thank You
• -Given: 0
• Posts: 899
• Eufloria: Yes
##### Re: 3D Concepts
« Reply #36 on: May 17, 2012, 09:51:22 PM »
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

• Achiever
• Ent
• Thank You
• -Given: 0
• Posts: 1,794
##### Re: 3D Concepts
« Reply #37 on: May 17, 2012, 10:27:38 PM »
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

• Tester
• Old Oak
• Thank You
• -Given: 0
• Posts: 899
• Eufloria: Yes
##### Re: 3D Concepts
« Reply #38 on: May 17, 2012, 10:37:47 PM »
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

• Achiever
• Ent
• Thank You
• -Given: 0
• Posts: 1,794
##### Re: 3D Concepts
« Reply #39 on: May 17, 2012, 10:47:12 PM »
Think I will just go with it for now.  It seems like it should work..

#### annikk.exe

• Achiever
• Ent
• Thank You
• -Given: 0
• Posts: 1,794
##### Re: 3D Concepts
« Reply #40 on: May 18, 2012, 12:06:19 AM »
I've finished the pseudovertex generating code. :>

Debugging it now.

#### annikk.exe

• Achiever
• Ent
• Thank You
• -Given: 0
• Posts: 1,794
##### Re: 3D Concepts
« Reply #41 on: May 18, 2012, 12:53:49 AM »
Nearly there..

#### annikk.exe

• Achiever
• Ent
• Thank You
• -Given: 0
• Posts: 1,794
##### Re: 3D Concepts
« Reply #42 on: May 18, 2012, 01:11:13 AM »
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

• Achiever
• Ent
• Thank You
• -Given: 0
• Posts: 1,794
##### Re: 3D Concepts
« Reply #43 on: May 18, 2012, 09:14:01 AM »
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!

• Tester
• Old Oak
• Thank You
• -Given: 0