3D Concepts

[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