Given that we can quickly extract the eight corner vertices  (and if desired, the Planes) of a 3D View Frustum, it should be possible to determine from those a 2D approximation of said 3D Frustum.
Attached is an image which describes the concept visually, you can see a 3D view frustum partly rotated in 3D space, and around it, a 2D Frustum which completely encloses it using just four 2D coords.
I would like to hear your ideas :)
How would you go about approximating this 2D Hull, given that rotation of the 3D Frustum is completely arbitrary?

What I have in mind: I intend to compare the approximated 2D Frustum against a large Terrain HeightMap in order to identify which pixels (Terrain Vertices) are actually visible, and to keep track of them using a list of ScanLines representing them as cheaply as possible. The goal is to write a new Terrain Engine which dynamically samples the visible landscape in the most efficient way possible (only generating newly-visible vertices at the frustum boundaries), eliminating the concept of (and problems related to) patch-based management systems for large environments.
It's not as cool as my 'sparse radial oversampling' concept I proposed a few years ago, however its far cooler than anything I've actually produced so far.

So if you're bored, get a pen and paper and try to devise an algo for degenerating the 3D frustum into a 2D hull that has only four edges :)
Attachments:
Posted on 2007-08-24 01:44:33 by Homer
Edit: Expensive algo scrapped.. read on..
Posted on 2007-08-24 03:24:26 by Homer
first I want to perform a simple estimation of what is clipped belowscreen, based on playersy vs terrainmaxheight and if player looksup/looksforward, checks against a thresholdangle and clipout belowscreen and clipout abovescreen

shouldnt we simple use y=k*x+c for clippinglines and simple have a precalculated LUT for angle->k constants
ok we have a point px,py and we simple put in px in our formula and fmul and compare against clippingline1 and fmul and compare again against clippingline2
I dont know if its possible to get performance outta the beast fpu is with issuing several fmuls in a row, but I code a SSE clip solution, as 4 lines to clip against make it perfect for that
Posted on 2007-08-25 03:42:21 by daydreamer
Edit : Expensive code for Expensive Algo scrapped - read on
Posted on 2007-08-25 04:03:24 by Homer
I got a new idea and thought what the heck why not OOP eventbased structure ala
proc render;
3dtransformanddraw(arrayoftrianglestrips);
endproc

proc onmousemoveleft;
angle--;
addstripstoleft(arrayoftrianglestrips); //adds new strips depending on terrainsquare side*sin(45) against how much viewfrustrum moves, because tilted 45 degree when a terrainsquare takes up maximum xspace and yspace
remstripstoright(arrayoftrianglestrips);
endproc
proc onmousemoveright;
angle++;
addstripstoright(arrayoftrianglestrips);
remstripstoleft(arrayoftrianglestrips);
endproc
proc onforwardmove;
xyz++;
addscanlineofstripsfront;
removescanlineofstripsback;
endproc
proc onbackwardmove;
xyz--;
addscanlineofstripsback;
removescanlineofstripsfront;
endproc
proc onangleminmax; //only work in same 2 quadrants the whole time with small angles and change coordinates to those 2 quadrants when its nesserary to rotate more
rotatewholequadrant(arrayoftrianglestrips);
endproc
Posted on 2007-08-25 07:08:03 by daydreamer
Having read that, I am inclined to throw away my expensive-looking code and algorithm.
I really only want to create "a simple 2D hull that tightly fits the view frustum's 2D projection', ie, I want a decent APPROXIMATION of the view frustum, and in 2 dimensions.

I have been staring at my old code for 'extracting the 3D view frustum from the current projection and view matrices', which works by 'deforming a unit cube' via the Inverse of the aforementioned Transform matrices.
It occurs to me that rather than deforming a 3D Cube, I could be deforming a much simpler 3D geometry to begin with...


The following code deforms a Unit Square into a 3D Frustum Trapezoid.
We still need to get rid of the Y component in the output vertices,
but nonetheless we've now got a relatively accurate and still tightly-fitting four-sided hull, and we've eliminated mountains of processing..

.data
FrustumSquare D3DXVECTOR3 <-0.5f,  0.0f,  0.0f>, ;left middle front
<-0.5f,  0.0f,  1.0f>,       ;left middle back
< 0.5f,  0.0f,  1.0f>,         ;right middle back
  < 0.5f,  0.0f,  0.0f> ;right middle front
.code
ApproxFrustumVerticesFromView proc uses esi edi ecx,pmatView,pmatProj,pOutputVertices
LOCAL matComb:D3DXMATRIX
LOCAL imatComb:D3DXMATRIX
invoke D3DXMatrixMultiply,addr matComb, pmatView, pmatProj
invoke D3DXMatrixInverse, addr imatComb,NULL, addr matComb
xor ecx,ecx
lea esi,FrustumSquare
mov edi,pOutputVertices
.while ecx<4
push ecx
invoke D3DXVec3TransformCoord, edi,esi, addr imatComb
add esi,sizeof Vec3
add edi,sizeof Vec3
pop ecx
inc ecx
.endw
ret
ApproxFrustumVerticesFromView endp


Happy Day :)
Posted on 2007-08-25 11:13:40 by Homer
The last pieces of the puzzle:



externdef g_dHalfMapSize:dword ;eg 512 if bitmap is 1024 x 1024 pixels
externdef g_fHalfWorldSize:real4 ;eg 5000.0f if World is 10,000 units across

;Functions to convert ('Map') coords from 2D 'HeightMapSpace' to 3D WorldSpace, and back again..
;Note that for 3D, the Y axis is NOT a valid 3D component and is essentially ignored.

;Convert 3D World Coordinate into 2D PixelMap Coordinate
WorldSpaceToHeightMappingSpace proc pvOut:ptr D3DXVECTOR2, pvIn:ptr D3DXVECTOR3
LOCAL multiplier
mov edx,pvIn
mov eax,pvOut
fld g_fHalfWorldSize
fidiv g_dHalfMapSize
fst multiplier
fmul .D3DXVECTOR3.x
fiadd g_dHalfMapSize
fstp .D3DXVECTOR2.x
fld .D3DXVECTOR3.z
fmul multiplier
fiadd g_dHalfMapSize
fstp .D3DXVECTOR2.y
ret
WorldSpaceToHeightMappingSpace endp

;Convert 2D PixelMap Coordinate into 3D WorldSpace Coordinate (with Y set to zero)
HeightMappingSpaceToWordSpace proc pvOut:ptr D3DXVECTOR3, pvIn:ptr D3DXVECTOR2
LOCAL multiplier
mov edx,pvIn
mov eax,pvOut
fld g_dHalfMapSize
fidiv g_fHalfWorldSize
fstp multiplier
;Convert 2D X to 3D X
fld .D3DXVECTOR2.x
fisub g_dHalfMapSize
fmul multiplier
fstp .D3DXVECTOR3.x
;Convert 2D Y to 3D Z
fld .D3DXVECTOR2.y
fisub g_dHalfMapSize
fmul multiplier
fstp .D3DXVECTOR3.z
;Clamp 3D Y = 0
fldz
fstp .D3DXVECTOR3.y
HeightMappingSpaceToWordSpace endp



and the driving method of the Camera class...


;This method returns an array of four 2D coords
;which represent an approximation of the View frustum
;mapped into HeighMap Space, that we will use to
;identify the currently visible HeighMap Pixels (Terrain Vertices)
;and which we will store as a Y-Sorted List of X-Spans
;The caller is responsible for MemFreeing the returned array..
Method Camera.Build2DFrustum,uses esi
LOCAL Out3D[4]:D3DXVECTOR3
SetObject esi
;Extract APPROXIMATE 3D version of Frustum Vertices
invoke ApproxFrustumVerticesFromView,addr .m_view,addr .m_projection,addr Out3D
;Map the 3D WorldSpace coords into 2D HeightmapSpace coords
push $MemAlloc (sizeof D3DXVECTOR2*4)
lea edx,Out3D
xor ecx,ecx
.while ecx<4
push eax
push edx
invoke WorldSpaceToHeightMappingSpace,eax, edx
pop edx
pop eax
add eax, sizeof D3DXVECTOR2
add edx, sizeof D3DXVECTOR3
inc ecx
.endw
;Return ptr to array of 2D output coords
pop eax
MethodEnd



There, now we have all that we need to obtain our 2D frustum in HeightMapping Space :)
Now we need to Rasterize ... identify which Pixels of the HeightMap are inside the 2D approximated frustum, and create a Y-Sorted list of X-Spans identifying which HeightMap Pixels are visible.. then we have to contrast that with the List created in the PREVIOUS FRAME in order to identify which Pixels are new (need to generate Vertices for them), and which Pixels and Spans are now redundant (need to trash those Vertices).
Then, use the new and old SpanList and VB to build a new VB and IB.
Finally, switch the current and spare SpanList and VB for the Next frame.

The reason we drive all of this from the Camera class is because we don't need to do ANY of this until the Camera View changes (in position and/or orientation), and the chances of our Camera class containing methods with names such as 'onViewChanged" are very good indeed..

Have a nice day :)
Posted on 2007-08-25 13:32:42 by Homer
About the original problem, why not choose the 4 longest edges (2D) as lying on the lines of that quad. In the rare case of having a fifth edge being at least 50% of the shortest of these 4 edges, test whether to use it with permuting the subset-of-4-edges and calculating respective surface-area, to find the smallest area and the respective subset-of-4-edges.
Posted on 2007-08-25 17:59:40 by Ultrano

proc render;
3dtransformanddraw(arrayoftrianglestrips);
endproc

proc onforwardmove;
xyz++;
addscanlineofstripsfront;
removescanlineofstripsback;
endproc

in my already existing halfbaked terrainengine proc render already exist, except it doesnt support rotation yet
all those addscanlineofstripsfront is gonna be based on scanline conversion comparing old scanline and add or rem strips and directly read from heightmap
because I have interest of get my trianglestrips perform a little better than a single run across the screen on the cost of garbage right outside left and right of screen I intentionally want a SLOPPY 2dfrustrum calculation so garbage will not accidently get inside screenspace

by extending quads at one end of a trianglestrip by overwriting others we can have a performancegain because we not need to perform any removescanlinestrips
but need have a buffer on unused stripdata between the strips and unused data for whole strips
my data look like an array of trianglestrips ala scanlines on a bitmap
I want an opinion on how much bufferspace between scanlines should be enough to perform extension up in memory+when adding and vertexpointer++ when removing when rotation of camera gives me an uneven movement of this "scrolling" and also dont want to accidently get it to be so huge so it gets to be performancehit when GPU reads vertexbuffer
Posted on 2007-08-26 05:05:31 by daydreamer
homer: I think you should keep the expensive code + algorithm instead of editing it out, since it can be a useful learning experience to follow the evolution of an algorithm... although a "read on" "warning" and strike-through'ing the slower stuff is a good idea.
goes back to lurking.
Posted on 2007-08-27 05:05:23 by f0dder
My goal is to compare the 2D region (enclosed by the 2D Frustum Hull) against the 2D HeightMap to determine which Terrain Vertices (HeightMap Pixels) are Visible, and which are not.
My existing Rasterizing code is loosely based on Bresenham's Line Drawing algo.

The Frustum Hull is described as four 2D coordinates (A, B, C, D) arranged as two Interpolation Edges (AB, CD). When rasterizing, we will simultaneously walk along both EdgeAB and EdgeCD.
However, rather than scanning Pixels at some strange 2D angle, I will describe how to calculate Horizontal Spans of pixels (in X) at each ScanLine (in Y).

Let's look at the linear equation which describes a 2D Edge (X,Y)
1. Gradient = dY / dX (where d is 'delta').

We can transpose this Formula to solve to dX or dY as follow:
2. dX = dY / Gradient
3. dY = dX * Gradient

So, for a given HeightMap Y coordinate, we can now find a matching X coordinate on any Edge.
Or for a given X coord, we can find Y on any Edge.

Now we can quickly find the XY Maxima and Minima, and scan using a nested loop.
At each Y, we can calculate X on each Edge.
If both X values are legal (lay along their respective Edge), we've identified a Span.

Posted on 2007-08-30 00:37:53 by Homer
I decided to try a different way, so I went modelling a trianglestrip which I intend to import and modify at runtime to upperhalf will form a skydome and lowerhalf will keep crap outside of 2dfrustrum and add appropiate number of meshes on the floor, so you can just insert Y's there
Attachments:
Posted on 2007-08-30 00:51:12 by daydreamer
Apart from the skydome, you have almost exactly described my "sparse radial oversampling' concept.

I have written (efficient) code to rasterize the 2D frustum hull edges into a contiguous series of Spans, as you would find in a more lowlevel software renderer / polygon filler.
Each Span represents a horizontal run of pixels that we would normally use to Fill the 2d hull, and each Span owns a small list of Terrain Vertices...
The SpanBuffer is dynamic.. when I have rasterized the hull, I take the output Spans, and I Clip the Spans ALREADY in the SpanBuffer (from previous Frame) against the new Spans, expanding and shrinking the SpanList both in X and Y as required to accomodate the New set. During this process, any redundant Spans (and their Vertices) are trashed, and any new Spans and their Vertices are generated.
We touch as few Vertices as possible, we edit the SpanList as little as possible.
Now we have updated the SpanList, we can use its contents to feed a TriangleStrip Generator.
We can generate one TriangleStrip between the Vertices contained in each two Spans.
We will have several relatively short TriStrips, which is slightly less efficient than generating one single TriStrip.. but there are no 'mutant' vertices joining the TriStrips in this scheme.. and it will work where subsequent spans are displaced in X and/or are of different lengths (do not align at their ends).

How would you create a single tri-strip for pixels arranged in arbitrary linear runs?

    ---
  ----------
  -------------------
  ---------------------------
      --------------------------
        ----------------------
            ------------------
              -------------
                    -----


It is time now to write my Tesselator, I am inclined to:
A) expand the 2d hull slightly beyond the actual view frustum
B) while creating a tristrip between two spans A and B, ignore any vertices in row A which have no Y-neighbour in span B. This means that the edges of our tesselation will look as jagged as my ascii art - which is fine, because that is happening just beyond the actual view ;)

I could add a few triangular Filler polygons at the problem locations to solve this issue completely .. but I am attracted to the workaround on several levels.. a somewhat expanded view would allow the activation of nearby entities without requiring us to continually measure their proximity.. what do you think?

Posted on 2007-09-03 00:29:04 by Homer
I have almost finished writing the pixel-to-span rasterizer and span-to-trianglestrip tesselator stuff.
Everything builds fine, but I'm yet to test it properly, and theres a couple of functions unwritten, especially a function to generate a newly visible Vertex's UV values.

That was deliberate, because this terrain engine will be using single pass multi-texturing.
I have not decided exactly what I plan to do, but likely it will be similar to my previous 'terrain texture generator' code, which was based on my guesses about the internals of a free utility called T2, which would be excellent if it only used bilinear or some other kind of filter versus the staircase effect..

There will be a Base texture painted using texture stage 0.
Its very coarse looking in the real world, but when blended with some other textures, can help add a different feel to different regions of the world.
There will be several layers of terrain texture, with weighting applied by per vertex alpha blending... so perhaps four more texture stages used up
On top of that will be a spare layer or two for 'Splatting' temporary textures on the Terrain.
We have EIGHT stages available for single pass blending (on a non prehistoric video card), and we can apply different kinds of blends at each Stage.
Early testing will be just two stages.

I've shoved all the spanlist and rasterizing and tesselating code into an object called SpanList, and changed my Camera class to create one of these support objects during its Init method.
Each Camera will own a SpanList.. I don't like this, I'll change it again later, I just wanted to make clear the association between Camera and SpanList.

So, I'm ready to test (and probably, debug) what I have done, but I am inclined to now make a firm decision about how the UV Blending Weights will be calculated, and write a Vertex generator, before I even begin testing the existing code (did I mention it compiled ok? lol)

I'm thinking that the terrain detail textures,although requiring separate Teture stages, can share common UV coordinates, so my Vertex Format might look something like this:

TerrainVertex struct
vPosition  D3DXVECTOR3 <>  ;Position of Vertex in 3D WorldSpace
vNormal    D3DXVECTOR3 <>    ;We need per vertex normals for nice Lighting
TexUVBase D3DXVECTOR2 <>    ;Texture Coords for BaseTexture
TexUVDetail D3DXVECTOR <>    ;Texture Coords for all Detail Textures
TerrainVertex ends


One extra 2D vector per vertex - nothin to worry about :)
Posted on 2007-09-04 08:29:31 by Homer