pouët.net

Go to bottom

Interpolation in adaptive sub-sampling?

category: general [glöplog]
Decipher: it can hardly be a more waste of time than having to deal with the temporary obstacles presented to you by today's gpu-apis. Right now, to make a realtime demo, sure you should use hardware rendering. But there are certainly other arenas now and in the future where cpu-like thinking is valuable.

Besides, it must be fun doing some cpu-rendering, no?
added on the 2009-09-23 16:56:54 by Hyde Hyde
The basic principle is: if you subdivide on one side of the edge, you should also subdivide on the other side.

Let's say you have 32x32 square and want to go down a level. You trace extra 5 points (center and points on the edges) and subdivide to 4 squares sized 16x16. In the process, you have added 4 points on the edges, which affect neighboring 32x32 squares (unless they were already subdivided, but let's assume they were not). In this case, neighboring 32x32 squares also have to be subdivided, but you don't add extra 4 "black" points for them (center + 3 remaining edges), but instead subdivide them with "green" points. The "green" points don't cause further subdividions of their neighbors (but green points can be later replaced with "black" ones).

Of course there is a lot of room for optimization, but it's probably most simplified version of the algorithm.
added on the 2009-09-23 16:59:31 by KK KK
I was replying to rydis quest for the Trezebees II article.
added on the 2009-09-23 17:03:48 by datsua datsua
KK: yes, i will try something like that i think.

datsua: thanks, ill take a look at it.
added on the 2009-09-23 17:12:39 by rudi rudi
Isn't the level 0 squares simply too large on the previous page pictures ?
added on the 2009-09-23 17:14:37 by krabob krabob
krabob: with an overlay filter it doesnt seem so. if i understand what you mean.
added on the 2009-09-23 17:22:47 by rudi rudi
Well, Decipher has a point ;) But I also like sw rendering even if it does not make sense;) Whatever technique you use, the problem with the highlights is the one in my drawing. Texture/highlight/whatever properties won't match up on the two sides of an edge. This is not related to software or hardware rendering - nor can you solve this with trilinear or any higher order interpolation. In h7 this was nicely concealed by brilliant texture art. This works for 8x8 to 1x1, but not for 32x32 to 1x1. However, you can actually avoid the problem by interpolating properly on the non-subdivided side, too. I drew triangles to describe this, but you don't need hardware rendering nor triangles. To do this in sw with axis-aligned rects: in my pic, you subdivide the right tall rect into two squares, but you pick the right middle pixel by interpolation and not by sampling. This will make the squares match with the next rect on the right side. (hope it's possible to get what i say without another drawing.)

One more point, with 32x32 it's easy to miss objects if they are too small. So you need to force subdivision around object centres if the object has 0 hits on the 32x32 grid but it is inside the view frustum...
added on the 2009-09-23 17:37:33 by Ger Ger
Ger:
yes, i understand what you mean. maybe i need to find a way to go around the recursive-function i use, because its restricted. it recurses linearly on screensize which means some edges are not traced if i want to interpolate bigger with smaller blocks. may be an indexing issue aswell.
I have an own variable called blockSize which i can change from smaller to higher pow2 numbers. if i dont hit an object it does not matter that much right now. i have to take care of that later.
added on the 2009-09-23 18:02:58 by rudi rudi
Also, I think I'm saying something similar to KK, but you don't want to sample but just interpolate at KK's "green" points to get things right. If you do sample, then you avoid one edge mismatch by creating three edge mismatches around the neighboring square...
added on the 2009-09-23 18:04:28 by Ger Ger
Quote:
the problem with the highlights is the one in my drawing

but if there's such a blatant difference in lighting, how come the other square isn't subdivided? it should be way over the threshold.
added on the 2009-09-23 18:09:07 by Gargaj Gargaj
Gargaj: I think he doesn't consider lighting for subdivision decisions, and he probably won't need to if he gets the tesselation right... 16x16 to 1x1 may look nice that way if I remember well. (maybe not 32x32...)

Btw. there may be no the blatant difference if you only look at the corners. See the right edge on this pic...

BB Image

However, using the vertices in the middle of the left/right edge could make even this square look much better (it would get the highlight).
added on the 2009-09-23 18:38:17 by Ger Ger
Yes. In that case he should detect that there's a large difference at the right vertical edge between the interpolated result of the middle square and the raytraced result from the right square. Since the rightmost square has to be subdivided (as it overlaps the horizon of the sphere), you need to either subdivide the square next to it as well, OR discard the raytraced colour on that centre vertex and use the interpolated result instead. The latter would be preferable since, if subdivision is based on colour difference along the edges (the way I suggested), then T-sections like that would only appear where there isn't much need for subdivision anyway, i.e. the raytraced colour for that point and the interpolated result from the neighbouring square are going to be close anyway.
added on the 2009-09-23 19:25:47 by doomdoom doomdoom
Ger: about the picture - not if you look at the colors, but the sign of at least one component of the specular normal flips around, which should be considered...
added on the 2009-09-23 19:28:44 by Gargaj Gargaj
i've implemented a threshold now, but it doesnt seem to be correct. its the power of the dot-products

Code: float threshold = 0.000001; if ((dc[0] * dc[1] * dc[2] * dc[3]) > threshold)


i got some interesting results though:

BB Image

if you look closely you can actually see the highlights. im not sure whats causing it to be white though. it may be because i sample on each point or something.
added on the 2009-09-23 19:42:10 by rudi rudi
I would hereby like to welcome Pouet to the last 10 years of #scene.no on EFNet. :)
added on the 2009-09-23 19:51:44 by gloom gloom
rydi: are you making this?

Code: float length(vec3 a) { return sqrt(a.r + a.b + a.z); } //... float threshold = 0.000001; if (abs(length(left)-length(right)) > threshold)


If not, you should. You should also not use the sqrt function, the squared length should also make the trick and be faster.
added on the 2009-09-23 19:56:19 by xTr1m xTr1m
wtf? I meant this:

Code: float length(vec3 a) { return sqrt(a.r + a.g + a.b); }
added on the 2009-09-23 19:56:54 by xTr1m xTr1m
gloom \o/
added on the 2009-09-23 20:00:36 by rudi rudi
xTr1m:
i was not actually trying that. i was using the dot-products from the four corners. i may have it wrong. im just trying out different things. that code may come in handy though.
added on the 2009-09-23 20:04:36 by rudi rudi
subdivision finally works! some artifacts but those are just a minor bug!

BB Image

looks like threshold is the only thing to work on before getting everything perfect. :)
added on the 2009-09-23 20:20:58 by rudi rudi
Ger: Interpolating "green" points was exactly what I had in mind.

rydi: For me it looks like you still have some subdivision issues - there should be no visible hard subdivision edge near specular reflection (this 32x32 square 1/2 radius above sphere center). Also it will be good idea to always subdivide if the shadowed/unshadowed status of corners don't match (this way you'll get non-blocky shadow edge).

Still, it's starting to look like proper raytraced sphere, so keep up the good work. :)
added on the 2009-09-24 16:37:27 by KK KK
ridy: maybe this also (in pseudo pseudo-code):

Code:if( abs(delta_R) > threshold ) return has_edge; if( abs(delta_G) > threshold ) return has_edge; if( abs(delta_b) > threshold ) return has_edge; return has_not_edge;


but maybe the sum of the delta's squares compared against the squared threshold is a more performing choice (less conditional statements...).

check also here: http://mrl.nyu.edu/~perlin/ghost/
added on the 2009-09-24 17:59:32 by bdk bdk

i removed the middle points because it didnt work or i didnt manage to do it properly. however i used the same recursive function to recurse where uv coords didnt have flags and highlights. i am a little fed up with coding or i use time on the wrong things rather than the right ones. however i learn alot in the process. so it might take some time until i get the most optimal way. the code is so messy that changing a little thing might ruin it all or might take some time to update the rest.

BB Image

as you can see in the picture theres something wrong because the subdivision doesnt do it at the edges of the shadows but outside.

in the picture the white dots are where there are no texture (no uv-flags that is true). the green dots are where all the corner edges have an uv-flag that is true. and the red ones should be where there are atleast more than one that is true or none of them are all true (but i think i have done something wrong in the algo that dont do this properly. i will check that later).

Code: float w = dc[0] + dc[1] + dc[2] + dc[3]; if (w > powf(threshold, 0.009*keyFactor))


i dont know why i do it like this. i will change it later. but now there are so many things to work on. and the trace-code is 155 lines long :( so i have to do some cleanup.
added on the 2009-09-24 19:58:35 by rudi rudi
Just release it like this and call it art!
added on the 2009-09-24 20:10:55 by Rob Rob

login

Go to top