Topic awaiting preservation: Why hasn't anyone done this yet...?

http://www.rpi.edu/~laporj2/quadtree.html
http://www.rpi.edu/~laporj2/quadtree_border.html (shows borders of each section, to give an idea of how it renders)

Quadtree shape rendering. It works especially well for Javascript because the basic rendering primitive is a rectangle. Note that the version here is not optimally efficient... many of the same calculations are repeated. That problem is solved simply by buffering all the calculation points and only calculate places that havn't yet been calculated.

Note that the border version looks like crap in MSIE due to the way MSIE does divs and borders... thought the standard version looks good in both Mozilla and MSIE (havn't tested Opera, Konqueror, Safari, yet...)

I am going to combine it with raytracing pretty soon, when I have time apart from classes and work (which is uh... never, heh). As some of you have seen, my raytracer is reasonably fast already, so I expect to have very good results when the two are combined. (Real-time raytracing in JS? I can dream, can't I? )

"Any sufficiently advanced technology is indistinguishable from magic." -- Arthur C. Clarke
"Any sufficiently arcane magic is indistinguishable from technology." -- P. David Lebling

(Edited by Iron Wallaby on 09-03-2004 19:16)

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

Why have I not found any of this in my searches?

Must see...

(Edit: are you referring to the really low-res 20liner bouncey ball thing? If so, I was impressed by it, but I am referring to high-res realtime raytracing... )

(Edited by Iron Wallaby on 09-03-2004 19:32)

As I've never implemented an adaptative sub sampling in JS, I think InI refers to the low-res bouncing ball.

Indeed, it could really speed up the rendering, but I doubt we could achieve high-res realtime raytracing in JS. By high-res and realtime I think of a viewport of ~160x120 with pixel-wise precision and a framerate of ~15fps on an average computer.

Whatever, the idea is clever, and the implementation is nice. To optimize the rendering you could take advantage of the recursiveness of the function and return the HTML markup to be added and document.write( ) it only at the end. To make it short, the last statement would be :

document.write( recurse(0, 0, 512) );

Thanks for your input, I incorperated that into the design... it's faster and more sensible algorithmically now as well...

Basically, instead of recursing all the time (as it did before), it only recurses if there is something of note within the sample-square.

http://www.rpi.edu/~laporj2/quadtree2.html

"Any sufficiently advanced technology is indistinguishable from magic." -- Arthur C. Clarke
"Any sufficiently arcane magic is indistinguishable from technology." -- P. David Lebling

Actually you can also remove the if(r > 0) and replace the else by else if( r>1 ) to avoid the recursion in squares of 1pixels. That way the number of calls to function recuse() drops from 14,101 to 7,013.

In IE, you can improve the appearance by adding overflow:hidden; to the styles (if it matters to you).

By the way:

http://www.slimeland.com/misc/ironwallabyheart.htm

(hope you don't mind) =)

[edit:

by the way, is the speedup by saving the document.write call to the end really worth all of the string concatenation?

Also, try this style:

style="position:absolute;left:'+x+'px;top:'+y+'px;width:'+(r-1)+'px;height:'+(r-1)+'px;border:1px solid #000;background:#f00;overflow:hidden;"

looks way cool.]


 

(Edited by Slime on 09-03-2004 23:53)

Slime: Wow, really nice antialiasing.

Another thing, but that's certainly a detail, there's a lot of redundancy in the inline style of your DIVs that you could put in a stylesheet once for all, and a shorter tag like a <P style="..."/> could shorten the final string.

Ooh, that's very nice, Slime. I can only run it in MSIE, the calculation time crashes Mozilla, heheheh.

"Any sufficiently advanced technology is indistinguishable from magic." -- Arthur C. Clarke
"Any sufficiently arcane magic is indistinguishable from technology." -- P. David Lebling

Yeah, my friend said Mozilla took a while with it. I don't understand why; I didn't actually change anything from your version, with the exception that the AA'ing uses a 5x5 sampling of each pixel on the edge. Oh, and of course I changed the shape, so that may mean more computation.

I wish Mozilla ran JavaScript faster. =(


 

Iron Wallaby,

Is it faster to use your own "gethex" routine than it is to use "parseInt(n, 16)"?

I've not run any tests, but would be interested to know if that was why you wrote your own hex conversion routines (with array lookup).

Dan

good work slime, your heart is really stylish =)

gethex was my function. It would probably be much better to use parseInt(n, 16). However, although I remembered that there was some function that would do that, I was too lazy to look it up so I just wrote it myself.


 

You could also do n.toString(16) too, I think.

"Any sufficiently advanced technology is indistinguishable from magic." -- Arthur C. Clarke
"Any sufficiently arcane magic is indistinguishable from technology." -- P. David Lebling

yep, but don't forget to add a leading 0 if n is lower than 16 unless the final hex code of the color will be completely f***ed up.

Holy "&"%!
That thing runs even faster than my fill algorithm, and it has anti-aliasing!
Btw, I think that heart is a Trademarked logo for an Ice cream company...

/TwoD

And all this time I thought I invented x^2 - |x|y + y^2 = r^2 for Valentine's Day...

"Any sufficiently advanced technology is indistinguishable from magic." -- Arthur C. Clarke
"Any sufficiently arcane magic is indistinguishable from technology." -- P. David Lebling

(Edited by Iron Wallaby on 09-05-2004 18:31)

Umm, I'm trying to figure this out so I've played around with the script and managed tweak it so I can see the rendering in slow-mo.
But that just made me more confused... could someone please explain the math this code is based on?

/TwoD

TwoD: The script simply evaluate the heart function at the 4 corners of a square. If the values returned says all the corners are "inside" the heart, a square is displayed, otherwise the function is called recursively in the 4 sub-square ( of half the width of current square ). Finally the recursion stops if the size of the squares being tested reach 1 pixel, or if all the corners of a square are "outside" of the heart.

That sort of method is often used to speed up fractal rendering, and there's some similarities with the mid-point algorithm used to generate fractal lanscapes.

document.write(recurse(0, 0, 512)); // This initially calls the function on a large square, ranging from 0,0 to 512,512



		function recurse(x, y, r) {

			// Mask is a simple function that returns true if the point it's called for is within the heart, and false otherwise.

			// Find the corners of the current sample.

			var a = mask(x    , y    );

			var b = mask(x + r, y    );

			var c = mask(x    , y + r);

			var d = mask(x + r, y + r);



			// If any of the corners are within the heart...

			// (Note that this is for making sure that we don't recurse on empty space...)

			if(a || b || c || d || r > 256) {



				// If all of the corners are within the heart, render a square.

				if(a && b && c && d)

					return '<div style="left:'+x+';top:'+y+';width:'+r+';height:'+r+';"></div>';



				// Otherwise, then part of the square is filled and the rest is not.

				// Therefore, we recurse on it, using 4 half-sized squares (one for top left, top right, bottom left, bottom right...)

				// The (r > 1) is to make sure that we only recurse until we reach a pixel size of 1. It is pointless to recurse further without using a subpixel rendering scheme (anti-aliasing).

				else if(r > 1) {

					var hr = r >> 1;

					return recurse(x, y, hr) + recurse(x + hr, y, hr) + recurse(x, y + hr, hr) + recurse(x + hr, y + hr, hr);

				}

			}



			// If we didn't return something else already, we return an empty string. This prevents there from being lots of "NaN" and "Undefined" in the background, heh...

			return "";

		}

"Any sufficiently advanced technology is indistinguishable from magic." -- Arthur C. Clarke
"Any sufficiently arcane magic is indistinguishable from technology." -- P. David Lebling

http://www.rpi.edu/~laporj2/quadtree4.html

More tweaking. This time, it uses CSS to position the heart, and not having to do it manually by subtracting 256 from the x and y values in the mask. In addition, it is more "technically" correct... if the sample size is 1, and it is partially filled, it will consider it a part of the heart (as opposed to the previous version, which did not render unless the sample was completely filled).

The reason for this is because now, instead of using a binary mask, I *should* be able to use an n-ary mask of any amount of colors (works... http://www.rpi.edu/~laporj2/quadtree5.html ). Or so I hope, heh. It also more easily facilitates the use of anti-aliasing... I think I can even do anti-aliasing with minimal code addition now (4 more lines, perhaps?), allowing for very fast anti-aliasing (no offense Slime, I love your version, but it *is* awfully slow ). So, a little more work and it will be quite nifty.

"Any sufficiently advanced technology is indistinguishable from magic." -- Arthur C. Clarke
"Any sufficiently arcane magic is indistinguishable from technology." -- P. David Lebling

(Edited by Iron Wallaby on 09-05-2004 21:37)

Thank you for the details Iron Wallaby and thank you Poi for the summary. It all became crystal clear now
I've done quite some research on rendering algorithms but I've never come across this one before.
Must have been looking in the wrong places...

/TwoD

quote:

---

Slime said:
Yeah, my friend said Mozilla took a while with it. I don't
understand why; <snip/>
I wish Mozilla ran JavaScript faster. =(

---

With the exception of looping done wrong (see my post in the Better for loops and Java/Javascript optimisation thread...), moz is actually quite a deal faster than iew at JavaScripting. What moz is not as fast at is dynamically (re-)rendering, especially with many elements on the page. One of the tricks for optimising DHTML performance in moz is to reduce the number of communications between the rendering engine and the scripting engine. Instead of incrementally rendering something, build the entirety in memory and first when that is done do the rendering.

- Do a single document.write instead of many
- Do a single elm.innerHTML=string instead of many elm.innerHTML+=partialstring
- Build the entire tree in memory and finally append it to the parent instead of appending each element to it's place in the tree as you create it

If you are changing things that are already rendered, don't do it too often, where "too often" means any frequency below once per 55 ms on Win9x/me and below once per 10 ms on any other system, if you're using timeouts or intervals. This goes for all browsers, by the way, but especially for moz because of the poor performance of incremental rendering.

Moz is extra slow at opacity/alpha channel rendering, so avoid those for fast rendering.

--
var Liorean = {
prototype: XMLGuru.prototype,
abode: "http://web-graphics.com/",
profile: "http://codingforums.com/member.php?u=5798"};

(Edited by liorean on 09-05-2004 23:10)

liorean: As you seem quite aware of the internal behavior of Mozilla, do you know if there any chance to see a boost in the performance of its rendering engine for incremental changes ?

When coding an heavy JavaScript toy, it's always annoying to have to decide between a fast browser ( aka IE ) and a fully standard compliant one ( aka Mozilla ). For a script I wrote, there's up to 2,000 element update per frame, IE handles it fairly easily at ~15fps but Mozilla crawls and is 8 to 20 times slower.

ps: sorry to fork a bit this thread.

Well, I know quite a bit about SpiderMonkey but not as much about Gecko (though "not as much" may be a lot compared to what most know about it). I belive the problems in the rendering engine are structural, though, and will not be easily improved. They are currently reworking a lot of things in the process of getting SVG working, but you are not likely to see any real changes before the work that will finally result in moz2.0 has commenced. (I belive we can expect that to be slightly before ff1.0 is released, depending on the work progress in a number of other projects that are not in mozilla.org control). I believe the cairo toolkit that will eventually replace gfx in Gecko will provide cross platform high performance vector graphics rendering, and probably speed up a lot of the incremental rendering. The rest of the problems are related to mostly the use of SpiderMonkey, but also the communications between SpiderMonkey and other languages.

--
var Liorean = {
prototype: XHTMLGuru.prototype,
abode: "http://web-graphics.com/",
profile: "http://codingforums.com/member.php?u=5798"};