General DoomSharp() Discussion

Quote:

---

Originally Posted by kedaman

Not upset me anyway, its just my nature to be critical about these sort of things ;) I checked out the checked texture, and it seems that although its not isometric, its not perspective rendering either, you seem to be stretching the image over a 2d polygon. The attached picture shows that the stripes are not getting thinner to the right.

---

Can you show me a screeny of your function rendering a checkers board? So I can see what it is supposed to look like?


- ØØ -

Quote:

---

Originally Posted by NoteMe

I am optimizing it later on tonight..I just have to get the stuff around it working first..:(...I just made it work before I went on my vecation so Wossy could use it. And when I got back everything was caos....:D...But the way it is right now is more or less like this:


- First call the first function here to update the WorldToViewMatrix.
- Then multiply a point with that matrix.
- Then send the point into the second function here, so you can get the screen coordinates out.

Code:

---

        private void UpdateProjMatrix(){
                Vector cam_forward = m_lookAt.Normalise();
                Vector cam_right = cam_forward.CrossProd(m_up).Normalise();
                m_up = cam_right.CrossProd(cam_forward);

                m_worldView[0,0] = cam_right.X;
                m_worldView[1,0] = cam_right.Y;
                m_worldView[2,0] = cam_right.Z;

                m_worldView[0,1] = m_up.X;
                m_worldView[1,1] = m_up.Y;
                m_worldView[2,1] = m_up.Z;

                m_worldView[0,2] = cam_forward.X;
                m_worldView[1,2] = cam_forward.Y;
                m_worldView[2,2] = cam_forward.Z;

                m_worldView[0,3] = 0;
                m_worldView[1,3] = 0;
                m_worldView[2,3] = 0;
                m_worldView[3,3] = 1;

                Vector revPosition = -m_position;
                m_worldView[3,0] = cam_right.DotProd(revPosition);
                m_worldView[3,1] = m_up.DotProd(revPosition);
                m_worldView[3,2] = cam_forward.DotProd(revPosition);
        }


    public bool ViewScreen(Vector[] objectView, ref PointF[] thisPoint) {
        thisPoint[0].X = m_centerWidth - objectView[0].X / objectView[0].Z / m_effectiveFOV * m_centerWidth;
        thisPoint[0].Y = m_centerHeight - objectView[0].Y / objectView[0].Z / m_effectiveFOV * m_centerWidth;

        thisPoint[1].X = m_centerWidth - objectView[1].X / objectView[0].Z / m_effectiveFOV * m_centerWidth;
        thisPoint[1].Y = m_centerHeight - objectView[1].Y / objectView[0].Z / m_effectiveFOV * m_centerWidth;

        thisPoint[2].X = m_centerWidth - objectView[2].X / objectView[2].Z / m_effectiveFOV * m_centerWidth;
        thisPoint[2].Y = m_centerHeight - objectView[2].Y / objectView[2].Z / m_effectiveFOV * m_centerWidth;

        thisPoint[3].X = m_centerWidth - objectView[3].X / objectView[3].Z / m_effectiveFOV * m_centerWidth;
        thisPoint[3].Y = m_centerHeight - objectView[3].Y / objectView[3].Z / m_effectiveFOV * m_centerWidth;

        return true;
    }

---

- ØØ -

---

SLOOOOOOOOW ;)

http://www.vbforums.com/attachment.p...id=39549&stc=1
This isn't really a checkers board but its good enough to see that the texels are shrinking to the right.

Quote:

---

Originally Posted by kedaman

SLOOOOOOOOW ;)

---

No way it is..:D...so how would you have used it...and don't pull that I'll stretch your textures 10 time as wide as they should be on me again...;)

- ØØ -

Quote:

---

Originally Posted by kedaman

This isn't really a checkers board but its good enough to see that the texels are shrinking to the right.

---

OK, I can see your point....look like some nasty math behind that **** though...

- ØØ -

Quote:

---

Originally Posted by NoteMe

No way it is..:D...so how would you have used it...and don't pull that I'll stretch your textures 10 time as wide as they should be on me again...;)

- ØØ -

---

Basically depending on what size you have the screen height compared to the width, you can adjust the x and y scale transformations on the camera, it should be proportional, and it should save you all that stuff except the division by z ;)

Quote:

---

Originally Posted by NoteMe

OK, I can see your point....look like some nasty math behind that **** though...

- ØØ -

---

Nah, that was quite a cheap trick I pulled there, which might become a problem unless you do some mip mapping at distance. I'm having it fixed in the new algo anyway, which uses the 9 so called magic numbers, which I've still not completely understood. The nasty part was getting the clipping right though, I didn't imagine you could clip a triangle in so many ways.

So what is the proper way to draw a texture without any gaps? I can fix the problem with more iterations but it takes much longer.

Quote:

---

Originally Posted by kedaman

Basically depending on what size you have the screen height compared to the width, you can adjust the x and y scale transformations on the camera, it should be proportional, and it should save you all that stuff except the division by z ;)

---

It sounds interesting, but I don't get it....but I suddenly got a problem with Merge sort here. I was looking at an example..and suddenly I didn't remember how it is done...hmmm..If you look at this example.


http://www.publicjoe.f9.co.uk/csharp/sort04.html

is the array split before you start into A and B? Or should it all be in A before you start or? Should it all be in a third array before you start? I am a bit confused now...


- ØØ -

Quote:

---

Originally Posted by wossname

So what is the proper way to draw a texture without any gaps? I can fix the problem with more iterations but it takes much longer.

---

Just draw one pixel after the other in horizontal spans, or alternatively vertical spans for walls ;)

And what about when none of the quad's sides are either horizontal or vertical (like the checkerboard above)?

Quote:

---

Originally Posted by NoteMe

It sounds interesting, but I don't get it....but I suddenly got a problem with Merge sort here. I was looking at an example..and suddenly I didn't remember how it is done...hmmm..If you look at this example.


http://www.publicjoe.f9.co.uk/csharp/sort04.html

is the array split before you start into A and B? Or should it all be in A before you start or? Should it all be in a third array before you start? I am a bit confused now...


- ØØ -

---

I only read the two first lines and saw it was bloated. It should be in one array from the start, its possible to do it inline but its probably cheaper (depends on the cost of memory) to do it with two arrays, the other should be half the size of the original. Merge sort is a divide and conquer (I was almost going to type command and conquer :D) which splits recursively the array to sort into two, until a certain point where you do insertion sort (better than splitting to smallest bits) this would be about when their size are about 10-20 each. Then (after the recursion call, unlike in quicksort) you merge the two sorted bits by picking the smallest of the two and put it back in the original array.

Quote:

---

Originally Posted by wossname

And what about when none of the quad's sides are either horizontal or vertical (like the checkerboard above)?

---

Then you will need increments for each row (or column), for the starting and ending points. Also you need to split the quad so that the top and bottom (or left and right) parts are level.

Quote:

---

Originally Posted by kedaman

I only read the two first lines and saw it was bloated. It should be in one array from the start, its possible to do it inline but its probably cheaper (depends on the cost of memory) to do it with two arrays, the other should be half the size of the original. Merge sort is a divide and conquer (I was almost going to type command and conquer :D) which splits recursively the array to sort into two, until a certain point where you do insertion sort (better than splitting to smallest bits) this would be about when their size are about 10-20 each. Then (after the recursion call, unlike in quicksort) you merge the two sorted bits by picking the smallest of the two and put it back in the original array.

---

But doing it with one list is not going to improve speed. And it is not much memory we are talking about anyway. Not even a Kb...so doing it in two lists should not be a problem. But in their example both a and b is of length 100.... :confused:

Quote:

---

Originally Posted by NoteMe

But doing it with one list is not going to improve speed. And it is not much memory we are talking about anyway. Not even a Kb...so doing it in two lists should not be a problem. But in their example both a and b is of length 100.... :confused:

---

yeah, that's why I concluded it bloated ;)

Quote:

---

Originally Posted by kedaman

Then you will need increments for each row (or column), for the starting and ending points. Also you need to split the quad so that the top and bottom (or left and right) parts are level.

---

Can you draw a quick picture of that? Not sure what you mean.

Sure, I love drawing pics ;) This time i just copied yours though to get it quickly over with. This is basically what I'm doing in my new algo: I'm splitting a triangle (it should work with other polygons as well, but it might best to split them into triangles to simplify the code) into trapetzoids that are parallell to the screen (vertical or horizontal depends on whether you render walls or floor/ceilings). Then use an increment for each starting and enpoint of each vertical or horizontal span. If you use floats, then converting to integers may be a bottleneck, so I'm using integers, but to be able to increment more precisely than 1 pixel per span I'm shifting the next starting and ending points by 16 bits. The spans should be fast to render, if you assume a constant depth accross it, which you can do for walls and ceilings.

Quote:

---

Originally Posted by kedaman

yeah, that's why I concluded it bloated ;)

---

Ok, hmm...I'll think I'll let it lie down for a while, and do an other that I actualy remember how works..:)

- ØØ -

Quote:

---

Originally Posted by NoteMe

Ok, hmm...I'll think I'll let it lie down for a while, and do an other that I actualy remember how works..:)

- ØØ -

---

I recommend you use insertion sort, since it will just run trough once, and do whatever small differences may occurr when you move around in a jiffy ;)

OK ok ok ..:D...but I kind of want to test Quick sort too.:)..but shell sort was REALLY REALLY fast, so it is not much time we can save no matter how we do this I guess...


- ØØ -

I see, but how do you map your texels to your original texture?

I'm doing it this way, with the 3 trajectories...the two red trajectories are synchronised and move down a small amount each time the green trajectory has drawn a scan line of the image. From the red trajectories I can work out the the Y coordinate of the source pixel and from the green trajectory i can calculate the x coord.

Quote:

---

Originally Posted by wossname

I see, but how do you map your texels to your texture pixels?

I'm doing it this way, with the 3 trajectories...the two red trajectories are synchronised and move down a small amount each time the green trajectory has drawn a scan line of the image. From the red trajectories I can work out the the Y coordinate of the source pixel and from the green trajectory i can calculate the x coord.

---

Yeah I figured you did something like that, I did the same once until i realized what the problem was ;) The mapping of coordinates is trickier. The trick, which I consider a bit cheating, is doing reverse mapping along iterating the pixels, which can be shown in the code I posted earlier. That's why I have 4, or was it 3 loops instead of 2. The proper way to do it is find the perspective correct texture coordinate from the current pixel, which you can find here for instance:
http://www.flipcode.com/articles/dem..._issue14.shtml

Quote:

---

Originally Posted by kedaman

Yeah I figured you did something like that, I did the same once until i realized what the problem was ;) The mapping of coordinates is trickier. The trick, which I consider a bit cheating, is doing reverse mapping along iterating the pixels, which can be shown in the code I posted earlier. That's why I have 4, or was it 3 loops instead of 2. The proper way to do it is find the perspective correct texture coordinate from the current pixel, which you can find here for instance:
http://www.flipcode.com/articles/dem..._issue14.shtml

---

Riiiight. OK well can you give any hint as to how I can get rid of the black dots in the output I already have? We don't need perspective correction on the textures.

With the current method I have I suppose I could have another increment on the texture X and Y coordinates so i don't keep calculating then every pixel. It should jsut be texture (height (or width) / trajectory length).

Just as a side post. Not sure if anyone is interested at all, but just in case. I found some great tutorials on gamedev. One for perspective corect texture mapping, and one for the magic numbers as Keda talked about.


http://www.gamedev.net/reference/art...article331.asp
http://www.gamedev.net/reference/art...article334.asp


- ØØ -

Quote:

---

Originally Posted by wossname

Riiiight. OK well can you give any hint as to how I can get rid of the black dots in the output I already have? We don't need perspective correction on the textures.

With the current method I have I suppose I could have another increment on the texture X and Y coordinates so i don't keep calculating then every pixel. It should jsut be texture (height (or width) / trajectory length).

---

No perspective correction? In that case the current isometric one would probably be fastest ;) Looking at the pictures posted so far, it doesn't seem too bad in fact :afrog: If you still want to hang on to the stretching method, then split up the polygon into trapezoids and do the spans.

I think the fact that all our wallparts are square will limit the lack of perspective texturing, we aren't ussing any really long textures that would look weird.

Do you have a link for a tutorial about trapezoid splitting?

nah, tha trapezoid splitting was my own invention. It's especially usefull with all the clipping (if you need to access the bitmap bits then this is necessary.) First you need to sort all the points in your polygon (which has to be convex) by the screen y coordinate, and then make a horizontal split for each corner, except the first and the last (for a triangle, you only need to split once, a quad twice). This means that you need to calculate the endpoint or starting point of the other end of the split, which will make up the fourth point in your trapezoid. A triangle should make two trapezoids and a quad three. The upper most trapezoid will be a triangle with the the two upper points of the trapezoid joined, and similarly the lower most trapezoid will have the lower points joined. If you apply clipping, then you will need to split up into further trapezoids. Once you have the trapezoids done, for each trapezoid, calculate the endpoint and startpoint increments, which is done by dividing the height between the points with the width between the point (or vice versa), and then loop with these increments in the outher loop, and loop between the start and end point in the inner loop.

Here's a pic to illustrate what I mean with the splits and the startpoints and endpoints, and clipping if you want to squeeze in more frames. The algo is simplified and shows how you work with the start and end point increments.

btw, the horizontal clipping may not need any additional splits, depends on what sort of trapezoid and where the clipping applies.

OK, I have fixed rendering in the right order no matter where you are on the map (Screeny), but when I was taking this screenie I found 2 more bugs to fix...:(

ONE: I moved really close to a wall or two, and then triangles appeard from the top down about half the screen
TWO: On this screenie the cube in the middle is moving for EACH frame. Like shaking a tiny bit back and forth.


http://www.noteme.com/doomsharp/img/img047.jpg


hmmm...

ONE: what do you mean top down half the screen?
TWO: are you sure you aren't shaking the table? ;)

Quote:

---

Originally Posted by kedaman

ONE: what do you mean top down half the screen?

---

Hmmm...I can't recreate it now...when I manage to get the problem to show up again, then I will post a pic.

Quote:

---

Originally Posted by kedaman

TWO: are you sure you aren't shaking the table? ;)

---

Yeah, the rest of the picture was not shaking..:)


- ØØ -

Quote:

---

Originally Posted by NoteMe

Hmmm...I can't recreate it now...when I manage to get the problem to show up again, then I will post a pic.





Yeah, the rest of the picture was not shaking..:)


- ØØ -

---

No use posting that pic then, its neither shaking or showing the top down thingie ;)

I know....I am a bit torn now...should I implement the camera class first or the culling...hmmm....I think I will try the camera....ok Wossy..stay tuned...


- ØØ -

W0o00ot! Just implemented a scrollable grid area! we can now have unlimited map sizes (in theory)

I have some problems finding the center of a bounding circle around the FOV...I can't belive that I can't do that simple math anymore..:(

- ØØ -

Ok, here is the problem.

The red dot is the position of the camera. The black lines out of it is the left side of the screen, and the right side is the right side of the screen. The black line they meet on the top is the far plane.

The imaginary blue line that goes straigt forward is 11 units long. You can find this direction by taking the "LookAT" position minus the "position of the camera".

The green half circle is the angle "a". It is right now PI/4. But it can be anything really. But since this calculation will be different if the angle is PI/2 or bigger we will just look at smaller then PI/2 right now.

The yellow big thing in the middle is the point we want to find. The point is just as far away from the camera position as it is from one of the two corners near the far plane. This point AND the radius of the circle it creates around it's centre has to be found. Now how do you do that.


PS: Tell me if I forgot to add some info. And if you do find a solution, then please draw with letters and so on what angles and lengths you are talking about..:)


http://www.noteme.com/doomsharp/img/img048.jpg

bounding circle radius= left side *right side / 2blueline, but since leftside=right side we have
leftside^2/2blueline, where blueline/leftside=cos pi/8 i.e leftline=blueline/(cospi/8) so
bounding circle radius=blueline (cospi/8)^2/2
probably wrong, but thats what you get when yo're tired :p

I soon have a result...so then we can test against each other..:)


- ØØ -

I got:

Radius: 6.443651


now lets see what you got...

- ØØ -

Ehh..are you deviding EVERYTHING on 2 or? And the ^2 is that with the blue line or not?


- ØØ -

I'm getting 4.69454
^2 is just on the cos thing, and yeah everything is divided by two

Grrr...hmmm.....so now we don't know witch one that is right..:D


- ØØ -

Quote:

---

Originally Posted by NoteMe

Grrr...hmmm.....so now we don't know witch one that is right..:D


- ØØ -

---

no we don't, but we know at least that you are still typing which wrong ;)

OK, lets start from the start. Can you agree to this:

One of the black lines (now called B) from the camera position is:

cos (a/2) = BlueLine / B

that becomes:

B = BlueLine / cos(a/2)



???

Quote:

---

Originally Posted by kedaman

no we don't, but we know at least that you are still typing which wrong ;)

---

Hehehe..lay off that..:D:..grrrrrrrrrrrr....:)

- ØØ -

Wait a second, mine has to be wrong because the diameter is smaller than the blue line :(

Quote:

---

Originally Posted by NoteMe

OK, lets start from the start. Can you agree to this:

One of the black lines (now called B) from the camera position is:

cos (a/2) = BlueLine / B

that becomes:

B = BlueLine / cos(a/2)



???

---

yeah thats basically what I was saying here:

Quote:

---

leftline=blueline/(cospi/8) so

---

I get that B= 10.1627

Ok...so can you agree that if you take the NORMAL on the MIDDLE of line B down to the blue line. Then you will hit the blue line a place that is JUST as far from the camera position as the two upper corners near the far plane?


- ØØ -

Quote:

---

Originally Posted by kedaman

I get that B= 10.1627

---

???

Ehh...am I tired now..I get:

B: 11.90631


- ØØ -

I think mine is more correct..even if I think mine is short...but it HAS to be longer then the blue line, and the blue line is 11units...


- ØØ -

Its proven now, I'm more tired than you :D I get the same thing now though

OK, I really need to draw some more to be able to fix this frustum culling once and for all...:D Getting closer though.


BTW wØØsy, so you remember the other C# app that was posted in a thread on an other page. The one with the checkers board and the glass? Check out that thread now.

- ØØ -

Have you thought of putting this onto Sourceforge??

And have we got a first release yet?!?

Why would we put it on source forge...:)


And no...first release is still a tiny bit of 100miles away..:D..but the map editor is close though...at least it seems like it..:)


- ØØ -

Quote:

---

Originally Posted by NoteMe

Why would we put it on source forge...:)

---

sourceforge would give you free hosting and bug tracking services.

Merge Sort algorithm done in haskell:

Code:

---

mergesort :: (Ord a) => [a] -> [a]
mergesort []  = []
mergesort [x]  = [x]
mergesort list = merge left right
  where
      left      = mergesort leftList
      right    = mergesort rightList
      leftList  = take n list
      rightList = drop n list
      n        = (length list) `div` 2

merge :: (Ord a) => [a] -> [a] -> [a]
merge [] x  = x
merge x []  = x
merge (firstA:restA) (firstB:restB)
  | firstA < firstB = firstA : (merge restA (firstB:restB))
  | otherwise      = firstB : (merge (firstA:restA) restB)

---

my god, it's like a storm in here...

2 new pages worth of arguing :eek:

I don't know about the speed thing.. but the texture algo not being perspective is true.

you should all keep in mind that when drawing the texture in perspective pixels to the left may need to be drawn as a 4 pixel square, middle as normal 1 pixel and far end as 0.5 (skipping every second pixel) as the size of the image is changing in different locations.

Jaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa................I have been updating D#, and made a shell so mine and wØØsys code is seperated again so it is easier to work on. And I have implemented depth sorting, and now my ladies and gentlemen, I have made a dynamic frustum culling. And it looks like it is working pretty fast and nice and all that....I am soooooooooooooo proud....I have been sitting with this code for 21 hours. I managed to finish it 7 hours before schedual...:) Wooohoooo...:)...

I still have an hour or two before the first buss goes home. So I will try to clean up this mess a bit...you have NOOOOOO idea how messy it is right now. And there is still quit a few optimization things I can do still. So I will see what I can get done. But at least things are working as they should, and in the right order they should..:)

PS: I consider from now on the following files "mine":
- Culling
- Vector
- Matrix
- GameTimer
- Sorting
- Camera
- Collision


The rest of the files I consider yours. If you are going to do any changes in my files. Then I would like to know about it.

Looking forward to see if you can improve the drawing speed. It is about 21FPS right now. And because of my frustum culling, it will more or less keep that speed no matter how big the map is. So it is up to you to improve it more. Next thing to implement (next week after sync up) is moving camera. That will be a nice joy..:)


- ØØ -

Quote:

---

Originally Posted by tr333

Merge Sort algorithm done in haskell:

Code:

---

mergesort :: (Ord a) => [a] -> [a]
mergesort []  = []
mergesort [x]  = [x]
mergesort list = merge left right
  where
      left      = mergesort leftList
      right    = mergesort rightList
      leftList  = take n list
      rightList = drop n list
      n        = (length list) `div` 2

merge :: (Ord a) => [a] -> [a] -> [a]
merge [] x  = x
merge x []  = x
merge (firstA:restA) (firstB:restB)
  | firstA < firstB = firstA : (merge restA (firstB:restB))
  | otherwise      = firstB : (merge (firstA:restA) restB)

---

---

Ehhh...ok...