3D Concepts

[annikk.exe]

See this discussion for more detail on this method.

























To be continued.

[Aino]

Starting on this again are we?

[Pilchard123]

Apparently so.

[Aino]

Are you going to remake this, or?

[annikk.exe]

I want to, but my understanding of what is required isn't comprehensive enough.  So first I will make heaps of diagrams to help me visualise what needs to be calculated. :>  The maths behind it all is pretty scary.

[annikk.exe]

Drawing in perspective is hard!

[Aino]

I want to, but my understanding of what is required isn't comprehensive enough.  So first I will make heaps of diagrams to help me visualise what needs to be calculated. :>  The maths behind it all is pretty scary.

Yeah... The maths are very complicated

But I've begun, if you want to continue it. You sorta just kicked me off. The file has a nice clean array system, making the verticles objects instead of just a ton of variables.
Feel free to use it and expand it

I have added 4 faces, triangle, quad(rectangle), pentagon and hexagons. They make a face that includes the verticles of the face(which is logical) and you can call the verticles from each individual face or call each individual verticle.
I haven't fully completed the parralax effect(it works, but fails at calculating properly), I don't think you will need it for further stuff either though

If you have any question regarding the stuff inside, ask

[Aino]

Posted it, but I guess you've started already

Drawing in first person perspective wouldn't be that hard I guess, if you have the center located at your rotation(yaw and pitch) and then drawing everything according to it. Simpler said than done though...

[annikk.exe]

Parallax and 3D are different, I know what you mean though. :>

The tricky parts to calculate are coming in diagrams soon.  The next few diagrams will consider the problem of "how do we know if a vertex is "inside" a face?" -done
Then we'll consider the problem of "how do we tell if a vertex that was found to be inside a face, is in front of the face (and should be shown) or behind the face (and hidden)? -done
Then we'll introduce the concept of pseudo-vertices. -done
Then we'll consider the problem of calculating where pseudo-vertices should be created, and how to draw or not draw edges depending on the number and type of pseudo-vertices they contain.
Then we'll look at what we can do in the case where a face covers an edge, but doesn't cover either of the edge's connecting vertices.

Finally I'll make some diagrams with test configurations, EG a pyramid in front of a cube, and plot out the default behaviour, the expected behaviour, and how the systems we put in place in previous steps will produce the expected behaviour.

Then I'll make some function templates.
I'll work out which variables need to be sent and returned from the function templates.
Then I'll begin filling in the function templates with code.
I'll be testing as I go... if I have any problems whatsoever understanding what needs to be calculated I will stop and produce more diagrams to make it clearer to myself.
Then finally I hope to end up with a 3D engine. :>

Once that's done I can start with other cool projects such as formalising the way objects are expressed in the engine, implenting support for changing object sizes, face alpha (transparency), reflections, and of course actually building some objects!


An object editor is basically going to be required if we want to make anything more complex than primitives such as squares, triangles, cubes and pyramids.
Aino, I've no idea what the final requirements of an object template will be, but I'm strongly hoping that once I've fleshed it out a bit more, you would be the one to build the 3D object editor for it.  :>  It would need to allow the user to create and adjust vertex positions in 3D, rotate the object round so that you can look at it, the ability to declare edges and faces, etc.  It would need to output a text or lua file which would contain the object function.  It would also ideally need to be able to load an object from an existing template file, so that existing objects can be edited.  And it also needs to be easy to use!

The editor would run using the same 3D engine that the objects would be displayed in, so I need to finish my engine before you'll be able to get properly involved in that project.  Hopefully all this conceptual discussion is sufficiently stimulating to get you thinking about the problem, at least. :>

[annikk.exe]

Are you guys understanding the diagrams so far by the way? :>

As per previous post, Aino, do you have any thoughts on eventually building a 3D object editor? :>

[Aino]

I understand the diagrams perfectly clear, because I was aware of the stuff posted, but that's just me...
I can make a 3D object editor, but first I need a 3D engine to do it on.

Also, are you making this for a future map in Eufloria or just for the sake of learning how to do it?

[annikk.exe]

I definitely want to release something playable eventually.  Very little idea what form it will take yet.

I need to make, at minimum, another 6 or so diagrams before the basic part of the engine is fully explained.  I'll get those done soon..

[annikk.exe]

1.  Get vertex, edge and face data.
2.  Compare all edges to calculate all possible pseudo-vertices; create a pseudo-vertex if the lines intersect.  Check distance of the lines' 3D intersection points from the camera to calculate which edge a pseudo-vertex should be assigned to (always the further away of the two edges).
3.  Use face data to calculate which vertices and pseudo-vertices should be hidden.  All vertices begin visible; if a vertex is behind a face, it gets hidden.  If it's in front of the face, no change is made.  That way only the vertices that aren't behind any faces will remain visible.
4.  For each edge, sort the vertices and pseudo-vertices so that they go from one end of the edge to the other.
5.  Draw each edge by only drawing between two visible vertices/pseudovertices.  These should ALWAYS arise in pairs; if no twin can be found, do not draw.

[Pilchard123]

ANNIKK'S BACK!

YAY! Maybe we'll see something happening here again!

[Lost Seedling]

It's hard to tell how many people actually read things on this forum, or appreciate the efforts of the map-makers, since so few seem to actually post comments. For what it's worth, I, for one, find this thread fascinating and look forward to seeing these concepts developed further. Keep it coming!

[Mihhaelo]

I'm always lurking around reading posts. Should probably get around to actually finishing a map, instead of half-finishing maps and then starting from scratch.

[annikk.exe]

I have nice plan now. :>

Decided to drop support for hiding vertices and edges behind asteroids.  This way it will be less code, so easier to focus on.  It will run significantly faster too.


I shall deliver a working 3D engine eventually!!

[annikk.exe]

How to generate pseudo-vertices, then?

Well a pseudo-vertex is generated for each edge that crosses another edge.

So I guess that means I must compare all edges, with all other edges.

Then I work out if their lines intersect in between the two vertices that form the tested edge.
If they do, I now add one pseudo-vertex to the edge..


This is gonna involve a lot of nested For loops..

For each face(1)
calculate number of edges in this face
for each edge in the face

for each face(2)
assuming this face isn't the face selected in face 1
calculate number of edges in this face
for each edge in the face
assuming this isn't the same edge as we selected for face(1)
check if it intersects with the edge in face(1)
if it does intersect, create a pseudo-vertex for... uh... one of them two edges.  Not sure which one yet.
increment this edge's pseudo-vertex counter...  then repeat for the next edge of the face, then repeat for the next face(2), until all face(2) is exhausted... then move onto the next edge in face(1), calculate everything, then eventually more onto the next face(2)..


hmm..  Quite a lot of duplication here.
Definitely room for optimisation.

[annikk.exe]

It might be worth developing a seperate function to check if a line formed by two points intersects with a line formed by 2 other points.


Something like:

LinesIntersect(x1,y1,x2,y2)

which would return two coordinates... somehow...

Hmmm.  How can I have a function return two coordinates?  ie, an X, and a Y?

[annikk.exe]

I could have something like..

Code: [Select]

if LinesIntersect(x1, y1, x2, y2) == true then
-- LinesIntersect returned true, so there is an intersection
-- the intersection coordinates have been assigned to "intersectX" and "intersectY"
-- by the LinesIntersect() function

pseudovertexX[edge][pseudovertexnumber] = intersectX
pseudovertexY[edge][pseudovertexnumber] = intersectY

end

Would that be a good approach?

[annikk.exe]

And, while on that subject, how will pseudovertices be stored?

A pseudovertex would be stored in a pair of matrices.
One matrix for the X-coordinate, and one matrix for the Y-coordinate.

Each matrix would be defined like:

pseudovertexX[edgeID][pseudoID] = 0
pseudovertexY[edgeID][pseudoID] = 0

So each pseudovertex X and Y coordinate belongs to a pseudo vertex ID.  The ID numbers are there to uniquely identify each pseudovertex.

So when a pseudovertex is created, a pseudoID number is created for it.  If it's the first pseudovertex in the Edge, it would probably have pseudoID = 0.

Then, each pseudoID belongs to a given edge, also defined by its ID.


So in total the data structure is like:


Each object is built out of several faces.
A face is comprised of Edges
Each Edge is comprised of 2 vertices..
Each edge also has 0 or more pseudovertices..

[annikk.exe]

Actually, this is wrong:

Code: [Select]

For each face(1)
calculate number of edges in this face
for each edge in the face

for each face(2)
assuming this face isn't the face selected in face 1
calculate number of edges in this face
for each edge in the face
assuming this isn't the same edge as we selected for face(1)
check if it intersects with the edge in face(1)
if it does intersect, create a pseudo-vertex for... uh... one of them two edges.  Not sure which one yet.
increment this edge's pseudo-vertex counter...  then repeat for the next edge of the face, then repeat for the next face(2), until all face(2) is exhausted... then move onto the next edge in face(1), calculate everything, then eventually more onto the next face(2)..
Some edges might be part of 2 different faces (imagine a cube for example).
So this code would erroneously create 2 lots of pseudovertices for each edge, because each edge of a cube forms part of 2 different faces.  The actual edge is the same both times so 2 identical sets of pseudovertices would be created.


What I actually need to do is to just check all of the edges, and check them only once.


So...

Code: [Select]

for each edge
for each other edge
if edge and other edge are not the same edge
calculate if edge intersects other edge
if it does, add a pseudo-vertex to edge
else
do nothing
end
end
end
That's way better for efficiency and simplicity too.  Still involves a nested for loop though.

[annikk.exe]

Code: [Select]

for edge = 0,numberofedges
for otheredge = edge, numberofedges
if edge and other edge are not the same edge
calculate if edge intersects other edge
if it does, we'll need to add a pseudo-vertex to edge
calculate the 3D coordinates of the intersection point for edge and otheredge
if edge is closer to the camera than otheredge
add a pseudovertex to edge
else
add a pseudovertex to otheredge
end
else
do nothing
end
end
end
This describes the steps to adding the pseudovertex.
It's also more efficient because this way each pair of edges is checked against each other only once, using a "triangular for loop" configuration.

[annikk.exe]

Triangular For Loop:

Code: [Select]

for edge = 0,numberofedges
for otheredge = edge, numberofedges
Suppose we have the following edge ID's:

0
1
2
3
4

Lets look at the first passthrough.
Now consider the first line:

Code: [Select]

for edge = 0,numberofedges
this will translate to:

Code: [Select]

for edge = 0,4

Then the second line is:

Code: [Select]

for otheredge = edge, numberofedges
which will translate to:

Code: [Select]

for otheredge = 0, 4
The result?  On this first pass through, edge 0 is checked against edges 0-4.




On the second passthrough, the value of "edge" is no longer 0, it is 1.  This is because the base for loop has repeated, and incremented the counter called "edge" by one.

Code: [Select]

for edge = 0,4
So edge = 1


Therefore line 2 now evaluates to this:

Code: [Select]

for otheredge = 1, 4
So on this second passthrough, edge 1 is checked against edges 1-4.  We don't want to check edge 1 against edge 0, because we already did that in the first passthrough; by doing it this way, we only cover the comparisons that have not been made yet.



Third passthrough

Code: [Select]

for edge = 0,4
So edge = 2 this time.

Therefore line 2 now evaluates to this:

Code: [Select]

for otheredge = 2, 4
edge 2 is checked against edges 2, 3 and 4, but not edges 1 or 0.


Fourth passthrough

Code: [Select]

for edge = 0,4
edge = 3

Therefore line 2 now evaluates to:

Code: [Select]

for otheredge = 3, 4
edge 3 is checked against edges 3 and 4, but not edges 2, 1 or 0.


Fifth passthrough

Code: [Select]

for edge = 0,4
edge = 4

Therefore line 2 now evaluates to:

Code: [Select]

for otheredge = 4, 4
edge 4 is checked against itself, but no other edges.
This is correct because edge 4 has already been checked against edge 0, 1, 2, and 3 in the previous four passthroughs.

[annikk.exe]

Aha, with a small change I can even stop edges being compared with themselves!
That should make it even more efficient.

It would be:

Code: [Select]

for edge = 0,numberofedges
for otheredge = edge + 1, numberofedges
If edge = 0, otheredge = 0 + 1, 4... = 1,4
So edge 0 wouldn't be checked against edge 0.


Then lets look at what happens at the end:
If edge = 4, otheredge = 4 + 1, 4 = 5,4

we're saying loop from 5 to 4.  That means don't run the loop. :>  So no comparisons would be made.

This triangular system is nice and efficient. :>

[annikk.exe]

Suppose 0?3 means edge 0 is checked against edge 3.

This is how the block for loop would operate:

0?0 0?1 0?2 0?3 0?4
1?0 1?1 1?2 1?3 1?4
2?0 2?1 2?2 2?3 2?4
3?0 3?1 3?2 3?3 3?4
4?0 4?1 4?2 4?3 4?4

It results in (numberofedges + 1)^2 number of comparisons; in this case, that would be (4 + 1)^2 = (5)^2 = 25 comparisons

The triangular version would look this this:


0?1 0?2 0?3 0?4
1?2 1?3 1?4
2?3 2?4
3?4

That contains 10 comparisons.
So it's 2.4 times more efficient than the block method in this case.


If we had a proper level, with say, 0-100 edges, the block method would work out at:

(numberofedges + 1)^2
(100 + 1)^2
(101)^2 = 10201 comparisons!

For the triangle method, I'll try and calculate that...

For the first row, it would be 99 comparisons, second row 98, third row 97, etc.
So to find the answer I would need to add up every number from 0 - 99.

Lets work it out double first.
0 + 99 = 99
1 + 98 = 99
2 + 97 = 99

...
we're going to end up with 100 iterations of 99, so we can save ourselves some time with 100 * 99 = 9900.
Divide by two and we arrive at 4950 comparisons.

So it's 10201 comparisons versus 4950 comparisons.
Which is 2.06 times more efficient than the block method.

[annikk.exe]

I think algorithmicly speaking the triangle method would be exactly twice as efficient as the block method for an infinite number of edges... but the triangle method gets exponentially more efficient the smaller the number of edges is.  For 1 edge, the triangle method would perform 0 comparisons and the block method would perform two, or at least one depending on the implementation.  So the triangle method is infinitely more efficient than the block method for only 1 edge.  :>

[Tomfloria]

At this point, I'm not understanding your code much, but I really enjoy reading people's work, and idea, keep going man

[annikk.exe]

Yeah it's mainly for my own notes at this point.

The 3D Engine relies on lots of other complicated work that I've done previously, such as the 3D Starfield engine.  A thorough understanding of that is probably necessary to fully understand this thing. :>

[Tomfloria]

And maybe A few months of actually doing this stuff haha, as I've only just started learning, three weeks I'm guessing

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

[annikk.exe]

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

What's that? :>

[annikk.exe]

Nm, googled it. :>

Yes you're right, it's going to take a long time to finish it, and then an even longer time to troubleshoot all the bugs. :>
However hopefully I will minimise the amount of time troubleshooting takes, because this time around I have followed some good programming practices:

1) All my stuff is commented like crazy, so it's reasonably easy to see what everything does
2) Things are split up into different functions, so I think the longest single function is only about 100 lines.
3) My tabs and spacing are well thought out and make it clear to see where loops and conditionals start and end.
4) Most importantly, I've spent nearly a year working on diagrams, plans and conceptual understanding of how it ought to work.

If I test each major section (such as pseudovertex generation) carefully before moving on, hopefully the troubleshooting needed at the very end will be kept to a minimum. :>

[annikk.exe]

It's crazy how much time has gone into this.

I started working on the 3D engine in January 2011! 

[Tomfloria]

You did leave for a while though

[annikk.exe]

That's true.  The conceptual stuff has always been on my mind though.

There are heaps of threads on this forum related to the 3D stuff.  The original parallax thread, the "problems with parallax" thread, the Faces thread, and now this thread... no doubt there are more too.

[annikk.exe]

Excited to try out the drawing of pseudovertices tonight.. :D

[annikk.exe]

The pseudovertices go flying all over the place and don't display correct behaviour at all. :<

Hmm..

[annikk.exe]

I've set the name of the single asteroid in my test level to be equal to to X-coordinate of pseudovertex ID 0 on edge 9.

One thing I notice is that it seems to change very infrequently.  Expected behaviour is that it should be shifting around a lot, especially when the camera moves or zooms.


Hmm...

[annikk.exe]

Saw a -900 value.. and a 16817.

That's beyond the range of the objects.
So maybe some of the maths is wrong.

[annikk.exe]

Working!!!

w000000ttt :>

[annikk.exe]

Here it is working:





The big colourful dots are the vertices that form 3 cubes, two of which are rotating.

The little red dots are the pseudovertices. :>

[annikk.exe]

So now I'm thinking about function HideVertices().

I've realised that at the moment, the 3D intersection point of a vertex is known only briefly during the generation of the pseudovertices.  After that this information is discarded, and all that is left is the 2D equivalent.

I can't check if a 2D point is "behind" anything.  The whole concept of "behind" implies 3 dimensions.


So maybe I need to do the hiding of vertices in-loop during the generation of pseudo vertices.  I could pass the 2D coordinates to a function that checks if the pseudo-vertex is inside or outside any 2D face polygons, then for any faces that the pseudovertex is inside I could calculate the coordinates at which a line drawn between the camera and the tested pseudovertex intercepts with the face.  If the interception point is closer to the camera than the pseudovertex itself, the pseudovertex should be hidden.. and in fact, doesn't even need to be added in the first place.

So rather than generating all the vertices then deactivating some of them, I can try to generate them all but selectively not generate any ones that would be behind faces.

That system makes more sense.


So basically function HideVertices() will be called from deep within the Pseudovertex generator's loops.

[Tomfloria]

Annikk, you know when you say 3D, do you mean, able to scroll around the Eufloria game world, so an Asteroid would look like a ball, or are you doing it so it's like Fl0w?

[annikk.exe]

It's a 3D engine comprised of lines and sprites.  It won't transform things like flowers and seedlings into 3D.

Asteroids appear like flat discs that sit on the plane z=0.

[Tomfloria]

So like fl0w? I think it would still be good though, could bring some great storyline ideas to mind, I have a few already.

[annikk.exe]

No, absolutely nothing at all like fl0w :p

It will be able to display 3D objects made up of points and straight lines, and move/rotate them.  There won't be any textures or lighting effects or anything like that.

[Tomfloria]

I'm a bit confused now, But, get on with it

[Aino]

You could make it like fl0w, but it would take a lot of time and CPU power...

[annikk.exe]

No, I really couldn't...  that would require textures and all sorts of things that aren't supported and never will be, due to constraints of Eufloria itself.

I could make gameplay like fl0w perhaps, but it will never look the same way.

[Tomfloria]

Could you control the seedling? As in like a car? :p

[Aino]

No, I really couldn't...  that would require textures and all sorts of things that aren't supported and never will be, due to constraints of Eufloria itself.

I could make gameplay like fl0w perhaps, but it will never look the same way.

Textures consist of? Pixels... you can make that happen, but as I said it'd require a lot of time and CPU power...

[Tomfloria]

I didn't mean the looks of it, I mean an asteroid that has layers

So say that

Code: [Select]

depth = 0
which if we was looking at a house, would be the ground floor.

Code: [Select]

depth = -1[/code

which if we was looking at a house, would be the basement.

[code]depth = 1
which if we was looking at a house, would be the second level above ground floor.

Something like that could be done with Asteroids? but only some type of asteroids allow you to switch between depths? But I know you can't hide asteroids can you, as in fullly. So really, the Asteroids would have to be very small, and depending on the depth layer, some asteroids would come back to normal size

Code: [Select]

if depth = 0

GetAsteroid(0):SetRadius(3000)
GetAsteroid(1):SetRadius(1)
GetAsteroid(2):SetRadius(1)
etc...[/code]

[annikk.exe]

You can temporarily shrink the size of an asteroid to a radius of 0, causing it to effectively disappear, however trees and seeds will then struggle to interact with it properly.

Another option is to use MoveTo to temporarily move the asteroid off the screen.. :>

I would probably tackle a problem like that from a different angle, other than the 3D engine.

[annikk.exe]

Now, I have pseudovertices being generated and stored in arrays like this:

pseudovertexX[edgeID][pseudovertexID]
pseudovertexY[edgeID][pseudovertexID]

Lets take an example edge, edge 5.

pseudovertexX[5][pseudovertexID]
pseudovertexY[5][pseudovertexID]

This will contain a number of different points that occur along the edge.
Suppose the edge has the equation y = 2x + 3
So some sample points would be:
0, 3
-1.5, 0
2, 7
4, 11
-3, -3

Prior to sorting, they might appear like this:

pseudovertexX[5][pseudovertexID] = { 0, -1.5, 2, 4, -3 }
pseudovertexY[5][pseudovertexID] = { 3, 0, 7, 11, -3 }

Each contains 5 elements.

When I use table.sort or similar to sort these elements into the right order, they would be sorted independently.  However because we are dealing with a straight line, this should not matter; they should naturally stay in sync with each other

pseudovertexX[5][pseudovertexID] = { -3, -1.5, 0, 2, 4 }
pseudovertexY[5][pseudovertexID] = { -3, 0, 3, 7, 11 }

So the elements then line up like this:

-3, -3
-1.5, 0
0, 3
2, 7
4, 11

So even though they were sorted independently, they didn't get mixed up.
This is always true for all possible lines in the engine.

It's even true of a horizontal or vertical.

Consider the line y = 4, which is horizontal.

A possible set:

pseudovertexX[5][pseudovertexID] = { 0, -1.5, 2, 4, -3 }
pseudovertexY[5][pseudovertexID] = { 4, 4, 4, 4, 4}

Sorted, becomes:
pseudovertexX[5][pseudovertexID] = { -3, -1.5, 0, 2, 4 }
pseudovertexY[5][pseudovertexID] = { 4, 4, 4, 4, 4}

In such a case, all the Y values are identical... so it doesn't matter that this situation mixes their indexes up.



Now, the question arises... can I sort pseudovertexY[edgeID][pseudovertexID] and only sort the pseudovertex ID's?  Hmm, I suspect I will have to copy it to a seperate array first...


So that would be done in this way:

Code: [Select]

function SortVertices()

for edgeID = 0, numberofedges do
-- calculate number of pseudovertices in this edge

numverts = -1
sortedX = {}
sortedY = {}
for pvID = 0,100 do -- maybe change 100 to maxpseudovertices or whatever that variable is called... i set it in StarfieldInit()

if pseudovertexX[edgeID][pvID] ~= nil then

sortedX[pvID] = pseudovertexX[edgeID][pvID]
sortedY[pvID] = pseudovertexY[edgeID][pvID]
numverts = numverts + 1

else

break

end

end
-- numverts is now equal to the number of pseudovertices
-- ie if numverts = 0, there is one pseudovertex
-- if numverts = 1, there are two pseudovertices, etc

-- first check that there is at least two pseudovertices - if there are 1 or 0, there's nothing to sort.
if numverts > 0 then

table.sort(sortedX)
table.sort(sortedY)

for pvID = 0, numverts do

pseudovertexX[edgeID][pvID] = sortedX[pvID]
pseudovertexY[edgeID][pvID] = sortedY[pvID]

end

end

end

end
And that should sort the pseudovertices... hopefully..? :>

[annikk.exe]

In terms of advanced graphics for this engine, it would be possible to implement face alpha (transparency), and also face reflections.  However I will focus on the basic engine first.

[annikk.exe]

Pseudovertex generator isn't quite perfect yet, it's displaying some erroneous pseudovertices.  It displays the correct ones too though.

Erroneous vertices appear on a single rotating cube.  I'm not sure why yet.  It has taken a fair bit of studying and trying to understand what I'm seeing to realise they are erroneous in the first place.  I'll study them a bit more and maybe figure out what part of the code I ought to be checking again..

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

Here's the solution.
We use linear interpolation to travel a portion of the way along the 3d edge. To do this, we need the proportional multiplier. It's called t and has a value between 0 and 1. We calculate t from the 2d lines. Then we travel t proportion of the distance across the edge and arrive at the 3d intersection.. We can calculate each component (x, y, z) separately.

[annikk.exe]

I got this bro!

[annikk.exe]

seed guys, I think this might be it. Not seeing any other obstacles.. After all these months, I think I am on the verge of completing the engine.

Tasks left to do:
1. Code up the linear interpolation depth check (should be easy)
2. Test it.. Pseudovertices should all be correct at this point.
3. Code a function to draw edges with respect to pseudovertices.
4. Test it..
5. Victory dance!

[annikk.exe]

Problems with step 1. :P
Oh well.

Take a look at this!

[annikk.exe]

I can see the pseudovertices...  whenever the lines cross, a pseudovertex is created.  So next step is we take the 2D X and Y coordinates, and add Z = 0 to create a 3D coordinate.  Next we take the camera position as another 3D coordinate.  Now we draw a line along those two points... I shall call it the CamSect line, because it's formed from the camera and the 2D intersection point.  This 3D CamSect line will intersect with both of the edges that are crossing to create the pseudovertex.

1.  Find sect1, the 3D coordinates of the intersection point between CamSect and Line 1.
2.  Find sect2, the 3D coordinates of the intersection point between CamSect and Line 2.

3.  Calculate the distance from the camera to sect1, call this dist1.
4.  Calculate the distance from the camera to sect2, call this dist2.
5.  Which distance is furthest?  Call that distance 3Ddist. Whichever is furthest away is the edge that will receive the pseudovertex, for which we have just calculated 3D coordinates.  Call the 3D pseudovertex Pseu, with coordinates PseuX, PseuY, and PseuZ.

6.  Next we must check the coordinates PseuX, PseuY, PseuZ against all faces, to see if there are any faces in front of them:
7.  Does this vertex appear inside any faces in 2D?
8.  If it appears inside in 2D, check that face in 3D.  Calculate the coordinates where the plane formed by the face is intersected by the CamSect line.  Call that point CamPlaneSect.

9.  Calculate the distance between CamPlaneSect and the camera.  Call this distance CamPlaneSectDist.
10. Compare CamPlaneSectDist with 3DDist from step 5.  If 3DDist is greater than CamPlaneSectDist, this pseudovertex is behind a face.  If it is, hide it.  If it isn't, don't hide it (yet) and return to step 6 and check the rest of the faces.

[annikk.exe]

Here's the solution.
We use linear interpolation to travel a portion of the way along the 3d edge. To do this, we need the proportional multiplier. It's called t and has a value between 0 and 1. We calculate t from the 2d lines. Then we travel t proportion of the distance across the edge and arrive at the 3d intersection.. We can calculate each component (x, y, z) separately.

This solution won't work!

To see why, consider this image of a 3D scene:



Look at the line that forms the edge of the sidewalk.
Note how it extends into the distance.  How long is this line in 3D, perhaps a mile?

Now consider that same line, but as 2D.  Find a point halfway along it.  How far away is that in 3D?  Perhaps 15 metres.  No way is it half a mile!

This approach WILL NOT WORK.


So instead I need to find a different way to calculate the intersection point of two 3D lines.


The new method is currently this:

Code: [Select]

function Calculate3DIntersectionPoint(Ax1, Ay1, Az1, Ax2, Ay2, Az2, Bx1, By1, Bz1, Bx2, By2, Bz2)

t = (Ax1 - Bx1) / (Ax1 - Ax2 - Bx1 + Bx2) )

intersectX3d =  Ax1 + ((Ax2 - Ax1) * t)
intersectY3d =  Ay1 + ((Ay2 - Ay1) * t)
intersectZ3d =  Az1 + ((Az2 - Az1) * t)

end

[annikk.exe]

Updated the code with this new method of calculating line intersections.  As expected, it still works correctly, but some vertices still flicker.

Damn flickering!  Currently the to-do list is: Fix the flickering, spend an hour throwing together some draw code, and finish.


EDIT.  Actually, wait...  this doesn't work after all.  It's giving some crazy values for the intersection point...
Sigh..

[Pilchard123]

I'll get that explanation finished at some point tomorrow hopefully.

[SweetCandyGrimm]

It's hard to tell how many people actually read things on this forum, or appreciate the efforts of the map-makers, since so few seem to actually post comments. For what it's worth, I, for one, find this thread fascinating and look forward to seeing these concepts developed further. Keep it coming!

IM READING IM READING!!!!! and learning.. i think this is giving me the drive to let math stick.. ty for this wicked game... and a way for us to stick our hands in too

oh yea was playing around with window's attempt at iOS's selective screenshots.. then threw it in an editor.. thought it would be cool for bgs and facebook timelines ect ect
my lil gift to all