Perspective correction
category: general [glöplog]
I'm working in a little 3D project, in a system where I have texture mapping, but there is no perspective correction, the mapping is affine.
The characteristics of the system are:
- Somewhat fast texture rendering
- The size of the area where the textures are applied doesn't affect too much the rendering time.
- The number of triangles affects so much the rendering time.
- I'm limited to a very limited number of triangles because the system is very limited and I need interactivity or real-time.
So, well, to explain this a bit with an example:
If I render an squared area of 100x100 with 2 triangles of area 5000 pixels each, it is MUCH faster than if I do it with, let say, 8 triangles with an area of 1250 pixels each. So, just suppose I have "infinite" fillrate but I'm limited in number of triangles.
Well, I have to render rectangular faces with a rectangular texture applied to it. In order to have some perspective correction, I'm tesselating the rectangular faces. I'm doing it in the easier way: just to make a grid of squares dividing the rectangle, and then, each square divided into 2 triangles.
This is producing good enough results, but thinking if it would be possible to reduce the perspective distortion with the same - or less - number of triangles, I thought that the best triangle shape would not be the right triangles I'm using.
Oh, the objects are going to rotate freely in any axis and angle. So, my thought was that the longer edge from any of the triangles in the tesselation would define the maximum perspective distortion I would have.
So then, I deduce that the best triangle shape to minimize the maximum perspective distortion is the equilateral triangle.
Now I'm going to work in a new tesselation routine for the rectangles that instead of using a grid of squares, uses equilateral triangles. I suppose I'm going to get about the same number of triangles or a bit less, and the perspective distortion should be less visible than now. But I've to test if this is true or not.
My question: have any of you thought, read and/or tried things like this? I know the case I relate is not a very common one, but maybe you have had similar in any kind of little machines... maybe the DS or something.
I've also thought in tesselating in screen space by following the constant-z lines of the triangle, and it looks that would be even better when I can use a big amount of triangles, but since I can use a very low number of triangles, for the lower tesselation levels I believe it is not going to help, and it would add aditional costs to compute that.
Well, any thoughts?
The characteristics of the system are:
- Somewhat fast texture rendering
- The size of the area where the textures are applied doesn't affect too much the rendering time.
- The number of triangles affects so much the rendering time.
- I'm limited to a very limited number of triangles because the system is very limited and I need interactivity or real-time.
So, well, to explain this a bit with an example:
If I render an squared area of 100x100 with 2 triangles of area 5000 pixels each, it is MUCH faster than if I do it with, let say, 8 triangles with an area of 1250 pixels each. So, just suppose I have "infinite" fillrate but I'm limited in number of triangles.
Well, I have to render rectangular faces with a rectangular texture applied to it. In order to have some perspective correction, I'm tesselating the rectangular faces. I'm doing it in the easier way: just to make a grid of squares dividing the rectangle, and then, each square divided into 2 triangles.
This is producing good enough results, but thinking if it would be possible to reduce the perspective distortion with the same - or less - number of triangles, I thought that the best triangle shape would not be the right triangles I'm using.
Oh, the objects are going to rotate freely in any axis and angle. So, my thought was that the longer edge from any of the triangles in the tesselation would define the maximum perspective distortion I would have.
So then, I deduce that the best triangle shape to minimize the maximum perspective distortion is the equilateral triangle.
Now I'm going to work in a new tesselation routine for the rectangles that instead of using a grid of squares, uses equilateral triangles. I suppose I'm going to get about the same number of triangles or a bit less, and the perspective distortion should be less visible than now. But I've to test if this is true or not.
My question: have any of you thought, read and/or tried things like this? I know the case I relate is not a very common one, but maybe you have had similar in any kind of little machines... maybe the DS or something.
I've also thought in tesselating in screen space by following the constant-z lines of the triangle, and it looks that would be even better when I can use a big amount of triangles, but since I can use a very low number of triangles, for the lower tesselation levels I believe it is not going to help, and it would add aditional costs to compute that.
Well, any thoughts?
I have no thoughts -- I'm braindead in the 3D department. But I am curious about the hardware you're using.. Can you tell us more?
Perhaps you should consider pure software rendering if the hardware offers such poor 3D acceleration.
Perhaps you should consider pure software rendering if the hardware offers such poor 3D acceleration.
I'm guessing it runs on CSS ;)
Do you have to render rectangular faces in screen-space? If so, I can't see how you get any perspective at all. If not, what kind of the texture distortion happens when the primitive is distorted by projection?
constant-z causes actually pretty bad visible effect since even though absolute texel/pixel error isn't that bad, derivatives tend to go all wrong when splitting quadrangles into triangles.
that is, it works with constant-z lines/quadrangles. not pairs of triangles with near-constant-z.
No no, I've to render rectangular areas in 3D. A piece of paper in 3D, for example.
So, I do it with triangles. 2 Triangles are enough to render a piece of paper, but, I have to tesselate if I want to avoid perspective distortion
So, I do it with triangles. 2 Triangles are enough to render a piece of paper, but, I have to tesselate if I want to avoid perspective distortion
No, not CSS. I'm working in 3D/Javascript crossbrowser. So, I'm using a lot of shitty things from Javascript and different versions to make it work in old Internet Explorers and everything... so no webGL or whatever.
Oh, about the "do it software rendering", I'm tempted to try it too. Raycasting maybe fast enough for low resolutions... I don't know.
But my question is... have you ever tried to tesselate with equilateral triangles? Does it looks better?
But my question is... have you ever tried to tesselate with equilateral triangles? Does it looks better?
I don't really understand what's holding you back from doing perspective correction. Is is the jacascript "library" you're using?
If you go the software rendering way, why not use piecewise affine? Do the perspective divide only every 8/16 pixels.
If you go the software rendering way, why not use piecewise affine? Do the perspective divide only every 8/16 pixels.
Raycasting is silly. Do regular scanline rendering with perspective correction every n pixels if you're doing software rasterising. If it's good enough for AMIIIIGAAAAAA, it's good enough, period.
If the faces must be statically subdivided, then you're right, the best general-case solution is to aim for equilateral triangles. But that also guarantees you're always rendering more triangles than you should. If it's possible, consider adaptive recursive subdivision, something like this:
If the faces must be statically subdivided, then you're right, the best general-case solution is to aim for equilateral triangles. But that also guarantees you're always rendering more triangles than you should. If it's possible, consider adaptive recursive subdivision, something like this:
Code:
subdividedRender( triangle ABC ):
sort vertices by z so A.z < B.z < C.z
if C.z-A.z < threshold
use whatever API to render triangle ABC with affine mapping
else
create vertex D at (A+C) / 2
subdividedRender( ABD )
subdividedRender( BCD )
I was about to say more or less what doom said about adaptive subdivision. I've never done it myself, but doom told me about it before, and it was one of those things i intended to try "at some point" (although i've pretty much retired from any kind of scene programming these days).
Doom's approach is ace if you can do triangles. AFAICT, it shouldn't create any T-junctions either, which can some times be a problem with subdivision-approaches.
What I was after was that subdividing like this:
while theoretically pretty optimal, still looks often awful. Thus doom has a point in equilateralness.
Code:
________
/ __-´\
/__--´ \
/------------\
/ ___--´´\
/___---´´ \
/------------------\
while theoretically pretty optimal, still looks often awful. Thus doom has a point in equilateralness.
216: Depends how accurate the affine texture mapper is. If it's accurate enough, then long, narrow slices will look fine. The perspective correction is achieved by minimising the z difference between vertices - the x and y differences are really irrelevant to that.
Kusma: To completely avoid T-junctions you'd still have to do the subdivision per edge rather than per face, I think. But then maybe if the input shapes are always rectangles, then that might be a special case where it never happens anyway. Idunno.
Kusma: To completely avoid T-junctions you'd still have to do the subdivision per edge rather than per face, I think. But then maybe if the input shapes are always rectangles, then that might be a special case where it never happens anyway. Idunno.
doom: since it divides the edges with the longest z-span and then recurses into both sides, it should actually always split an edge the same number of times. And since it uses "(A+C) / 2" instead of something like "A + (C - A) * 0.5", it should always yield the same result no matter what way you're splitting. So actually, I think it's perfectly safe.
i once did some LOD type subdivision (only using parallel edges, otherwise fugly if you don't have high sub-texel accuracy) .. this works pretty nicely. you can stick to affine mapping and have all the complexity in the higher level parts.
the quake type perspective correction i read about. every 8 or 16 pixels i think.. there were two way:
- 'magic' vectors which sounds like a black art, and was explained crappily, so i didn't bother.
- interpolating 'w' = 1/z, and somehow multiplying by that
plane raycasting+linear interpolation is also an option. but you'd need full 3D vertex information in your rasterising stage...
the quake type perspective correction i read about. every 8 or 16 pixels i think.. there were two way:
- 'magic' vectors which sounds like a black art, and was explained crappily, so i didn't bother.
- interpolating 'w' = 1/z, and somehow multiplying by that
plane raycasting+linear interpolation is also an option. but you'd need full 3D vertex information in your rasterising stage...
earx: Unless you're using floating point coordinates, you really want to interpolate 1/w instead of 1/z, as it's range is only dependent on projection, and not the z-range of the scene. And w != 1/z, that's just wrong ;)
this is what is missing in modern demo programming.... maybe I should say good by to GL....
kusma: But it actually dividides faces according to the z-span of each face, not each edge. Which edge gets the extra vertex is determined by the z order of the original vertices, and there's no relationship between neighbouring faces in that respect.
But it could be modified so that each face is split on either one, two or three edges based on the z-span of each edge. That way I guess you would avoid T-junctions completely:
But it could be modified so that each face is split on either one, two or three edges based on the z-span of each edge. That way I guess you would avoid T-junctions completely:
Code:
subdividedRender( triangle ABC ):
aSplit = ( abs( B.z - C.z ) > threshold )
bSplit = ( abs( A.z - C.z ) > threshold )
cSplit = ( abs( A.z - B.z ) > threshold )
if not( aSplit or bSplit or cSplit )
use whatever API to render triangle ABC with affine mapping
else if aSplit and not( bSplit or cSplit )
split from A to (B+C)/2
recurse
else if... etc.
the other 6 cases are straightforwardDoom, if you try my example scene with a stripe pattern you'll see an interesting phenomenon. On every other triangle the lines follow the left edge, while on every another, the right one.
With such a texture (and polygon angle) the effect is annoying until you subdivide to pixel level. With more extreme angles you get noise even when going below pixel thin triangles.
But what happens when you subdivide along the "wrong" direction? Well, the result is distorted, but zigzag goes away.
With such a texture (and polygon angle) the effect is annoying until you subdivide to pixel level. With more extreme angles you get noise even when going below pixel thin triangles.
But what happens when you subdivide along the "wrong" direction? Well, the result is distorted, but zigzag goes away.
doom: It seems you didn't get my point. All edges above the threshold should be subdivided until they are below the edge, because it divides the "longest" (by z-span) edge and then traverses into the two halves until none of the edges are above. So it should still be robust, each edge gets split in two until each piece is below the threshold. The order they will be subdivided won't be the same for all triangles, but that shouldn't matter.
Basically, if you already sorted your vertices by z, and the C->A edge is below the threshold, then A->B and B->C CANNOT be above.
Basically, if you already sorted your vertices by z, and the C->A edge is below the threshold, then A->B and B->C CANNOT be above.
[sorry to interrupt the trifiller gurus for a moment... ]
Texel, if you are not fillrate limited and sicne you do have the division instruction in the hw, why don't you simply go for perspective correct texture interplation? Perhaps it's just faster than all that triangle subdivision and setup.
If you are like me - not exactly the king of homogeneous coordinates and projective spaces and shit - instead of trying to figure out all that 1/w trickery you can simply raycast the triangle as you rasterize. Because you know in which triangle you are you only raycast _this_ triangle, which is fast (one interection per pixel!), and there you will get your correct per pixel division (1/dot(raydirection,planenormal)). No change for mistakes. Once you have the ray-tri routine perhaps you can do inverse engineering, start extracting commong factors and stuff and get to something that looks (exactly) as the perspective correct interpolation. Or just leave the ray/tri routine as is, should be fast (no tests needed for the u,v baricentric coordinates and ray parameter t, as you know you are IN the triangle, so the code get's really serial and stuff).
[end of interruption]
now please go on
Texel, if you are not fillrate limited and sicne you do have the division instruction in the hw, why don't you simply go for perspective correct texture interplation? Perhaps it's just faster than all that triangle subdivision and setup.
If you are like me - not exactly the king of homogeneous coordinates and projective spaces and shit - instead of trying to figure out all that 1/w trickery you can simply raycast the triangle as you rasterize. Because you know in which triangle you are you only raycast _this_ triangle, which is fast (one interection per pixel!), and there you will get your correct per pixel division (1/dot(raydirection,planenormal)). No change for mistakes. Once you have the ray-tri routine perhaps you can do inverse engineering, start extracting commong factors and stuff and get to something that looks (exactly) as the perspective correct interpolation. Or just leave the ray/tri routine as is, should be fast (no tests needed for the u,v baricentric coordinates and ray parameter t, as you know you are IN the triangle, so the code get's really serial and stuff).
[end of interruption]
now please go on
kusma: Oh, you're right of course, I didn't get it. Of course it splits edges, just only the longest edge in every face. So yes, if an edge gets split in one face, it must be split in the neighbouring face, too.
So I was being thick, yet somehow smarter than I thought.
So I was being thick, yet somehow smarter than I thought.
I wouldn't call one intersection calculation per pixel cheap.
You might want to try this. I find it quite elegant. Has been posted gazillions of times though...
You might want to try this. I find it quite elegant. Has been posted gazillions of times though...