Topic awaiting preservation: Some more image generation and 3D rendering

Hey all!
I haven't been online much lately.
Work on this script (FireFox only) has taken up a lot of time lately, along with a migration to a new computer which completely screwed up my LAN...
Anyway, inspired by all the talk about image generation in JS I decided to try it myself.
I think I have most of it figured out by now but there are still a few things that bother me.

I tried making a simple 16x16px white BMP with a single black pixel in it in JS, and compared it to an identical image made in MS Paint.
After examining the files in a HEX editor I noticed a few things.

The Paint image had been rendered from bottom up, while I rendered it from top down.
I read somewhere that according to standards, a BMP should be rendered from bottom up, but you could also render it from top down as long as you remembered to change something.

The height had been specified as a negative value (-16) in hex instead of positive as in the Paint image. Is this what you needed to change to render the image from top down?

I admit I did not fully understanding the BMP header structure bit by bit even though I have a pretty detailed specification document about it.
So I borrowed some code from inmates here to fix that, hope you don't mind guys...

Some programs like Paint Shop Pro do not recognize the generated files as BMP files and fail to open them. Could this be because of the reversed rendering?

If I want to render say a 5x5px image instead, the filesize isn't calculated correctly, I think it was 20 bytes too small.
The black pixel also becomes two pixels with different colours, it seems as if there is a wrong offset in the image data.
Probably because my JS script doesn't do zero-padding...

Now to the 3D rendering.
I've got all the basic stuff worked out here.
I can easily project a 3D point to a 2D plane and rotate it around each axis.
Drawing lines, triangles and even fill them is no problem.
However, I get a weird effect which makes it look as if the cube I use as a test-object gets stretched during rotation.
To me it looks like the things at the back of the scene doesn't rotate fast enough or they are too far away or something like that.
This is my first realtime 3D engine and I've tried to keep things simple and structured, but I can't figure out where this problem has its roots...

All comments are welcome.

/TwoD

(Edited by TwoD on 10-30-2005 04:29)

Die geocities, die!!
There #@! scripts screw your global variable w. I got a hint of that because the vertical position of the polygons seemed ok. A simple :

javascript:alert( w );void( 0 );

confirmed that. Btw, h is also screwed by http://us.geocities.com/js_source/geovck07.js

Damn, Yahoo! hired some talented developers though. I thought that sort of problem were gone. Why don't they simply nest their messy code in some functions and use local variables


I think I gave the URL of Wotsit's Format Search : Graphic files in another thread, but just in case, you'll find the specs of the BMP format I used.

The line width in a BMP is a multiple of 4. So if you want to create an image of say 5x5, you'll actually work it as if it was 8x5 : the fileSize chunk must be computed as if the image were 8x5 but the last 3 pixels of each line are useless. Sorry the buildBmpXXHeader( w, h ) functions in Neja did not care of that.


Actually I'm surprised by the speed of your test. All the more that your drawTriangle() set of functions is far from optimized for speed.
As you certainly see, in Neja the 3D effects are raycasted. I did that because my scenes are dead simple and it simplify/nullify the computation ( no need to sort/rotate the polygons, take care of the clipping, interpolate the coordinates for the polygon drawing and mapping, ... ). Raycasting also allow much more than flat shading almost for free ( i.e. gouraud mapping with perspective correct mapping ).

Why did you split the RGB components in rawImage ? is there any practical reason ? Because if you don't, it will speed up the rendering.

What's the next step for your 3D engine ?

Grr. I really need a better host. Been using geocities for ages. Me and a friend created the account for a school project and I got stuck with it lol.


That site looks great! Will be really helpful

Thank you for the explanation, that makes the specs I had a bit more logical lol

The drawTriangle() function is a 5 minute job. First it simply called drawLine() three times to create a wireframe model but I wanted to see how much the speed went down if I flatshaded the model instead. I only noticed a very slight difference so I let it be that way.

The drawLine() function is copied from the 2D vector engine I made for Naltabyte, except for the edgeBuffer part of course.
After a series of test I made using different linedrawing algorithms, this one seemed to be the fastest.
Do you have any suggestions for improvements?

Don't remember why I split the RGB components... Seems pretty dumb now that you mention it...
I'll fix that and change my global vars, then I'll upload it again...

The next step would be perspective correct texturing and then lighting effects. I want to push it as far as possible.
I might also add interactivity so I can rotate the models with my mouse or keyboard, that would be handy when debugging texture problems.
And of course, add more models and render many at the same time.

But first I need to fix that weird "elastic model" effect. Or is this just my mind playing a trick on me?
It feels as if the cube's corner rotates before the edges

/TwoD

From what I've seen, the most time critical function is setPixel(...) and especially its use in drawTriangle(...)

Your code was running at 6fps. By merging the RGB components and getting rid of the setPixel(...) in drawTriangle(...) it runs at 15fps

I think what you describe as "elastic model" is simply due to your wide fov, in the computation of perspW and perspH, change the angle from 100 to 60 and the distortion will disappear.

Wow, thanks!

Btw, what's the difference if I set the pixels directly in drawTriangleversus using setPixel?
Dos the extra function call take that long?

My computer has a 2.4GHz AMD 64 processor and 2Gb RAM. The script runs pretty fast there (haven't checked the fps). But sometimes it uses up to 300Mb of memory and the CPU load is about 75-80%!
Usually it's somewhere around 30 to 50 Mb of memory usage so I think there's a memory leak somewhere...
No noticeable speed decrease when that happens though...

/TwoD

quote:

---

Btw, what's the difference if I set the pixels directly in drawTriangleversus using setPixel?
Dos the extra function call take that long?

---

I'm tempted to say : try by yourself but I'm too curious to not try. By calling setPixel( ) the framerate is 12fps



(Edited by poi on 11-01-2005 22:45)

I noticed a 2-4 fps difference when I put the "pixel setter" inside drawLine, strange that a simple function call has a delay that long...

I don't have exact figures since I used a pretty simple fps counter.
A simple setInterval runs each second and outputs the value of a variable, then it resets the variable. The variable is increased after each frame has been rendered. A bit unreliable but it's enough to notice a difference.

I added model grouping yesterday so now each rendered model belongs to a group.
That group can be rotated/moved/scaled as a single model while each individual models moves independantly.
Looks awsome so far but I need a fast way to determine if a pixel I'm about to set is behind or in front of the pixel which is already at that co-ordinate (if any).
I thought about interpolating z-values along the polygon borders and then between borders to get z-values for all drawn positions on a polygon face. But I fear that will be too much work for it to handle in realtime...

Anyway, I'll upload the version with grouping as soon as I can if anyone wants to take a look.

/TwoD

(Edited by TwoD on 11-05-2005 14:26)

The ~3fps difference is not that surprising. The setPixel() function is called a hell lot of time during the rendering.

Here comes the renderBmp() function as I changed it :

function renderBmp()
{
	var startTime=new Date().valueOf()
	rawImage = background.concat([])
	calcPoly()
	document.getElementById('render_area').src = header+rawImage.join("")

	top.status = Math.round( 100000/(new Date().valueOf()-startTime) )/100 +" fps"
	setTimeout( renderBmp,1)
}

To sort every pixel, a Z-buffer, though quite brutal, might be the best option in JavaScript. Or if you are not scared, you could try to code a S-buffer, that's the technique used in Quake 1.

I don't know for the others, but I'd like to see the enhancements of your code.

I think calculating complete Z-buffers might bee too CPU-unfirendly so I'm looking for other solutions.
If I assume no polygons intersect, I can make it a bit easier and use a simple version of "the painter's algorithm". (Painting layer by layer, and have them replace eachother until the closest one gets on top.)

I'll look into S-buffering, haven't heard about it before even though I've played a lot of Quake

Still haven't uploaded the new version, might not be until tomorrow, geting late here...

Btw, I've noticed that using the status-bar alot slows things down considerably, that's why I made my fps counter as light as possible and only made it update each second.

/TwoD

[uber_quick_post] Here comes Paul Nettle's famous tutorials about S-Buffer [/uber_quick_post]

Hehe, already found that page thanks to Google
I think S-Buffers might do the trick, just need to modify my edgeBuffer slightly and add the insert function.

Anyway, I've uploaded the "grouped-models" version now, it's not the fastest code arund but it works like I intended.

/TwoD

quote:

---

I think S-Buffers might do the trick, just need to modify my edgeBuffer slightly and add the insert function.

---

Meh, slightly might not have been the right word... Atleast I've got a working example of SBuffering now, with a few flaws.

I made a new drawTriangle function which renders each triangular face from top to bottom, drawing two lines at the same time until they intersect at the bottom (after one of them has formed the third corner of the triangle).
This allows me to easily interpolate the Z co-ordinates for both the start and end positions of each span.

My insertion routine first checks if the new span is entierly before or after the filled part of the buffer.
Then it loops through all entries in the buffer and performs these checks:

• Is the span "inside" this entry? If yes, is it completely behind or in front of the entry? (Intersection is not allowed) If in front of, check which parts of the entry to keep.
• Does the span start on this entry? If yes, is the first part of the span in front of the entry? If yes, insert whole span and cut off entry. Otherwise cut off the first part of the span and start over with the checks.
• Does the span start before this entry? If yes, do a similar check to the one above.
• Does the span start after this entry? If yes, add it to the buffer.

Anyway, I have some problems with this as you'll see when running the demo.
Here's the link to it again.
There is some info in the source about the problems I have, along with extensive comments.

/TwoD

(Edited by TwoD on 11-22-2005 22:26)

Muahahaha! Poi here called me insane (in a good way) on MSN a while ago. Now I see why...
Take a look at my script again. The SBuffering is finally acceptable
I could extend it a bit further by taking intersecting spans into consideration, I already have a working algorithm for that which was needed for Paul Nettle's insertion routine but I never got the rest of the routine to work...

I also tried using <div> tags instead of the bmp image. It works, in all browsers I might add, but it runs at 4 fps at 108*108px without background rendering....

On my machine the BMP version now runs at about 12-14 fps which is pretty acceptable considering I'm rendering quite a lot of faces.

Next, I need to study the art of applying texture to a 3D surface.

/TwoD

let me repeat it again : you are insane.

The art of texture mapping is not that hard. All you have to do is to interpolate the u, v ( that's name generally given to the x, y coords in texture space ) along the edges, and then along the spans.

If you only do this you'll actually completely process the texture mapping in 2D and will see some distortions since the polygons are in 3D. That's the problem with the texture mapping on PlayStation 1.

If you want a perspective correct texture mapping, you'll have to interpolate the Z and project the u, v. But damn, that's a lot more computation per pixel and I doubt one could achieve an acceptable framerate.