Subdividing arbitrary Trapezoid on a 3D Surface

edited in Questions and Answers

I looked all over trying to find an easy (game programmer friendly) way to subdivide a trapezoid in 3D space.
(Convert a boundary of 4 Vector3s on the surfaces of a sphere into a mesh)
but Spock-like maths knowledge was limited, so I hit up the idea of using Vector3 functions.


Lerping the Y edges to find point Y1 and Y2, and then lerp between Y1 and Y2 to find X... result - a subdivided trapezoid in 3D space based on 4 arbitrary boundary points.


Used in conjunction with a new invention I call "Continuity Maps" it creates seamless patches on a surface.
Continuity maps are like terrain tiles (height and rgb), but with an extra edge of pixels to store the neighbour's tile edge. This means that Tiles are more OOP friendly, and thus more streamable, with no need for a stitching pass. (e.g. in old Unity Terrains you needed to set neighbors to do stitching of normals and edges, which meant an extra 'meta' terrain manager.)

Works great for creating continuous terrain patches on a 3D sphere without seams or the need for stitching.

Here's a video from the _MASSIVE engine, showing Cape Town constructed with +-16 patches on a real-size Earth sphere. The whole earth has 16,000,000 patches :D

Constructing a 256x256 BVHTriangle patch mesh takes about 3 seconds. Sadly Bullet steals all the cores to construct it, even when running on its own thread, so I need to investigate getting the patches loading and unloading without stuttering.

If anyone has tips on streaming terrain patches without using all cores I'd be keen to hear, or a more efficient way to generate a mesh from 4 corner points :)


  • I was actually experimenting with something like this in C# as I was playing with the idea of creating a ScriptablePatch mechanism. But why would it take 3 seconds to construct a patch? For a 256^2 patch this seems insane.
    Thanked by 1John
  • @MoruganKodi it does seem slow - the patch creation for rendering in OpenGL is only 12 ms, but to create the static collision mesh in Bullet takes 3 seconds (65000 double-precision vertices). It wouldn't be a problem if Bullet didn't use up all the cores to do its secret bullet things...
  • I had an idea to create a collider mechanism which doesn't use meshes, but instead use four sampled points on a height map for ground collisions. You would only need one quad below the player which moves with him.

    Not sure how well this will work, but it is something I want to try.
    Thanked by 1John
  • That's a good idea, especially for an MMO.
    The other avatars don't need physics because they're server-driven... Will give this a try, thanks
Sign In or Register to comment.