flipCode - Tech File - Alex Champandard [an error occurred while processing this directive]
Alex Champandard
Click the name for some bio info

E-Mail: alex@base-sixteen.com

   09/16/1999, More About Bezier Patches And Fractals

I realised my name dropped off the bottom of the recently updated techfile list, so it must be time for an update... I've been doing some work lately on adding random fractal coefficients to my rectangular bicubic bezier patches, and I was going to give you a full explanation about that technique, when Conor kindly pointed out that he already had. Saved me a bit of work :) Anyway, check out his tech file for the theoretical background.

The main advantage being the algorithm adds detail as you get closer, rather than removes detail in the distance. I'll just extrapolate on the practical issues, also known as nasty problems you can run into while implementing them into your landscape engine.

1) It is very unlikely that you will be able to store a series of random floats for each patch since the memory requirements will grow exponentially. But if you did, I'd recommend storing a prime number of random floats, so that the more you tessellate no repetitive artefacts appear.

2) If you don't store a series of random numbers for each patch, you may run into trouble when joining up two neighbouring patches together. By that i mean that the common vertices along the edges might not coincide, even at the same tessellation level. A simple, but quite expensive solution would be to collapse the edges of each patch once tessellated. Another solution is to let the vertices on the edges form a perfect curve, the two neighbouring curves then join up, but that looks out of place since all vertices around it have extra randomness. A third solution is to have a separate fractal for each of the 4 edges, and obviously in common with the neighbouring patches. You would tessellate the edges using those 4 fractals first, and then tessellate the rest of the patch with a 5th fractal.

3) The time required to tessellate will be much higher. I use a hybrid recursive binary patch subdivision algorithm, that performs worse than my iterative forward differencing algorithm, even with the "fractalness" put aside. I have another idea to combine the advantages of both methods, but it's still in it's early stages.

4) Clipping is a nightmare... Single player is obviously not a problem here, rather multiplayer. Say two people Peter and Paul are at either side of a mountain, and they are theoretically just out of each other's sight. If on Peter's machine, you tessellate at a lower level (slower PC), Paul might become visible, even though Paul can't see Peter for the mountain. Say Peter shoots at Paul, how do you perform clipping in that case? You could just clip against the data Paul has, which would be quicker, but Peter would die without knowing why. On the other hand, you could retessellate the mountain in that specific area (much slower), and clip against that. But then Paul would not be able to see what the bullet hit... An idea is to have the server doing all the clipping in multiplayer, with obviously a massive speed hit, and a lot of data transfer over the network.

I'd love to hear any comments on any of these topics.

  • 01/05/2002 - A.I., Websites and Voxels
  • 03/05/2001 - State Of The Art Character Animation
  • 01/24/2001 - Alternate Programming Languages
  • 01/11/2001 - The Sound Of Silence
  • 09/20/2000 - Engine prototypes, yet more landscape LOD and hard body physics
  • 07/13/2000 - Good Practice (TM)
  • 06/13/2000 - Revision Week Indeed
  • 04/11/2000 - Escape From Inactivity ;)
  • 01/05/2000 - Generic Shaders
  • 12/03/1999 - Start Of Term: Lots Of Good Intensions :)
  • 10/06/1999 - Dynamic LOD, Landscape Generation and much more...
  • 09/22/1999 - Water Contest Entry: Rendering Raytraced Refraction with 3D Hardware
  • 09/16/1999 - More About Bezier Patches And Fractals
  • 08/11/1999 - The Right Landscape Engine For You!
  • 07/12/1999 - Leftovers From The Contest: Fixing TP7's Runtime Error 200 bug
  • 07/01/1999 - Introduction

  • This document may not be reproduced in any way without explicit permission from the author and flipCode. All Rights Reserved. Best viewed at a high resolution. The views expressed in this document are the views of the author and NOT neccesarily of anyone else associated with flipCode.

    [an error occurred while processing this directive]