3D - On The Fly!

[Scott_Bro]

Here is a raycasting version of the game and it look great except for...
How do I find the shortest distance from player to line segment faster!  right now it loops through all and records if touching and deduces the shortest distance.
but if we could find which on is the shortest right away we would greatly improve the game. we only need to concern ourselves with the line segments that the rays touch and find shortest distance and bypass the other lines completely??? while looking.

press f1 to load map f12 to see render.

if you add more and more line loops in map view you will see that it starts to bog. ouch! ouch!


any mods are welcome

Thanks
Scott_Bro

[stevmjon]

hey scott

this is an edit 2 of the "level editor" demo, where i added 2D clipping. it works, but not perfect yet. enough to look at anyway.

clipping routine is in it's own tab. also 'render scene' gosub was modified to seperate different stages, so i could add in 2D clipping.
it would probably be better to add 3D world and do 3D clipping.

anyway, i left it as 2D map clipping for now so you could check it out easier without too much code being changed.

 enjoy, stevmjon

p.s. i will check out the new advanced raycasting demo. sounds exciting.

[stevmjon]

with the advanced raycasting demo, i like how you came up with line collisions, against walls and rays.

i came up with 2 ideas that may help speed up the process. one method is in 2D, and the other method is 3D.
what i will do is code the 3D method first and see how it goes. i will post it when done.
i am interested to convert the map to 3D, and see how it looks. that way the player movement can be inside the 3D world. for now i will do line drawing, then try out gouraudquad polygons to give shading for distance.

is the player going to look forward only (not look up/down) ?

   it's good fun trying out new ideas, stevmjon

[stevmjon]

i was excited that the 3D conversion works, yay. thought i would share a pic of my progress.

it does not yet have nearz clipping, nor polygon sorting yet.
i was mainly focused on the scale comparison. i converted the 64 * 64 pixel 2D grid cell, into a 1m * 1m grid in the 3D world.
i used gouraud quads so i can later set this to be shaded by distance from the camera.

also the 3D version is running much faster. see pic.

i hope you like the progress scott. i will keep going to tidy it up.

   stevmjon

[Scott_Bro]

Wow!  I like your clipping demo it really clean the scene up.
I also like what you did with the raycaster but the reason I showed you that was it does not need clipping along with many other 3d commands but...

The problem was coming up with the shortest distance between player rays and only the walls (line-loops) they touch.
It bogs because it's looping through each ray and every line-loop trying to come up with the answer.

I love your 3d-work but the 2.5D raycaster bypasses alot of 3d-formulas for instances now the 3d-demo requires back-face removal. Though I still think it's kewl but how to solve the above answer to the raycaster.

Still can't wait to see what your working on.

Thanks a bunch for the help.
Scott_Bro

[stevmjon]

glad you like the clipping demo.

i added 3D to the raycaster just to test the speed. you do need to add back-face removal etc, but these are relatively fast to calc. i will keep going with this to see how it turns out.

in regards to the closest wall calc in the raycaster, i did come up with a 2D idea for this too.
instead of checking every ray against every wall (even though i liked this idea you came up with), i thought of still using this method but instead try this:
> still use the rays but only check from the player to the wall points. don't shoot out every camera ray.
> then you can interporlate between wall points when drawing.
> you only need to calculate wall point distance once each.
> calc the camera start ray & end ray as a vector each. use this as inside min/max values. only keep points that are inside by calc dot product (making vectors from player to wall point). unit vectors may work better for -1 to +1 values.
eg. camera rays may fit within +0.5 to 1 (guess).
> then sort left to right order for the within range wall points, then work out which is full wall and overlap wall, and interporlate between full walls that are closer. jump too further wall when finished full closer wall...

anyway, its a bit of sorting out, but it will still be much faster than the line-loops for every ray. i will code this and post. i know what i need but too much to explain, lol.
so i will do this 2D method before i finish the 3D one. i am interested to see if it works...

   stevmjon

[Scott_Bro]

Whoa! That's sounds hard.  Programming is sometimes but two minds are better than one.
I can't wait to see what you come up with. Sorry, I have not been much of a help here as to some of this. I'm kind of stumped myself sometimes.
Though I'd still love to work on a group or team project for real with someone or a few who would help such as yourself lately.  But I am also willing too put forth some effort myself. Not just watch others do the work but help when I can. So until next time Good Luck!

Stay Positive!
Scott_Bro

[kevin]

Scott,

    The wolf3d demo that comes with PlayBASIC is basically written that the world is a polygonal world and then rendered to a strip buffer and displayed as line segments.   It's kind of line a 2D z buffer,  which is how I did it on the Amiga back in 1995. 

[Scott_Bro]

Steve, I was wondering if you could explain the clipping algorithm to me better?
I don't know how to clip in 3D and I would like to learn how it is done. Meaning how can I do it?

Thanks,
Scott_Bro

[stevmjon]

hey scott

here is a pic of the explanation of how clipping routine works, with example calculation.

in this example i am calculating the nearz border (so it is z axis border). the same calc is used for each border, focusing on that border axis. it is best to make sure the border is perpendicular to an axis, then clip. the reason for this is you don't need to calc 'dot product' when clipping.
this is what i do in my 3D engine.

the 3D engine requires 4 matrix stages, add clipping in between these stages:
> translate martix
> rotate matrix
* clip nearz here *
> perspective projection matrix
* clip left, right, top, bottom, farz here *
> screenspace matrix

i choose to clip when the camera frustum borders are perpendicular to an axis. less calcs this way.
in the game engine i usually use object vector data to begin with (less data to calc this way), then when the object itself needs to be clipped, then that object is then converted to polygons data, then do the clip calc. easy to clip polygons.

i hope this example pic helps get you familiar with what is needed.

  stevmjon

[Scott_Bro]

Wow! It seems like you know alot about 3D-formulas.  I also sounds like your good at matrixs maths. I don't know much about them execpt they house trig ops.
On an easier track how about?

Can you explain backface removal with what you were saying about dot-product or is that cross-product. I could use some help getting reaquainted with 3d maths#%@!!!! Sorry!

From what I know you check if they normal of the quads/tris are greater than 90 degrees and if so it can't be seen so don't render it.

I would like to learn more about that if I could bother you in trying to explain it to me as you did great with last question.

Thnaks for now,
Scott_Bro

p.s. I would love to see your 3d-engine sometime if you would like to share code back and forth I am all for it if you are!

Thanks Again!

[kevin]

  Scott_Bro,

   

p.s. I would love to see your 3d-engine sometime if you would like to share code back and forth I am all for it if you are!

 
      Steve's already been gracious enough to blog about his forays into  building a 3d engine over here in the 3D section of the forums..    Building a basic 3D Engine

     You'll find a number of examples by various people there as well in the source code forums..

[stevmjon]

thanks for the links kev.

the early code is a step by step process of building the 3D engine.
if you want to see the most updated version, it is page 5  :  reply #62  :  v0.9(2)
with this latest version i have removed all the test code and it should be easier to follow.

when it comes to polygon backface culling, you need cross product to get the polygon normal (as a vector), then just look at the sign of it's z value (no need for dot product if this is checked after all the clipping is finished).
i will write up another image to follow.

[stevmjon]

hey scott

i hope these pics helps explain the cross product (left hand rule) & (right hand rule).

cross product takes more explanation, because there is 2 methods , left hand rule & right hand rule, and there are a few ways to visualise the order of the actual calculation too.
i will try to explain this calculation.  see the vector values (text on right side) in the pic. vector 1 is on the top row, and vector 2 is on the bottom row. visualise covering with your hand the 'column' you want to calc, and then calc the remaining visible values written in yellow, in a criss - cross pattern. the left hand rule and the right hand rule criss - cross in a different order.
you sorta need to see this explained... maybe youtube?

anyway, i hope this helps

 stevmjon

p.s. you usually use left hand rule if your 3D engine is looking down the +z axis after the translate matrix > rotate matrix. also the order in which you draw the polygon points can effect the result too. so... either use left hand rule calc, or right hand rule calc.

EDIT:  i added a pic showing a method to visualise cross product

[Scott_Bro]

Whoa! I guess that clarifies cross-product well. As to the dot-product that does what? I imagine the angle difference between two vectors? Care to elaborate? Man, There is so many calculations done in computer science it's enough to scare a big wig? he he he I realize this is not a job for the weak, week ! he he he I get confused about this sometimes.  Anyways, I'm wondering before ever stepping into matrixes ouch! ouch! How do I calculate? Reflectance angle? I know I have an incident angle and a surface normal and a reflectance angle and the angle difference between the incident and the normal then the reflectance is + or - that angle. but...
How do I code that up or even understand the real formula behind it better to where I can understand it better?  I am sort of a veteran but these math keep adding up. It makes it hard to get sometimes. I don't claim I could program anything. ha ha ha ha I would like to know more though and am willing to learn more though.  Thanks for giving me all the help lately steve. really!  Here's something to think over. I would love a program that took video footage like say star wars tie figher scene and did motion tracking and created bounding boxes around objects of interest and allowed us to re-cord and playback the footage where we could now, shoot those tie fighters or what ever else as they went by. interactive movies per-say. I've done a bit of tinkering and I was able to use blender 3d to spit out x and y positions into text file of a moving dinosaur in a video as it walked by I tracked motion tracking his eye and had a text file output and re-played the video back in app game kit and the box was shootable just no death scene after, explosion ect... but it worked at least. I just did not know how to do it in a convenient way. Would you be interested in this kind of game? Interactive film/movies/videos? Just asking because I though it was a great idea.

Thanks,
Scott_Bro