flipCode - Tech File - Conor Stokes [an error occurred while processing this directive]
Conor Stokes
(aka DirtyPunk)
Click the name for some bio info

E-Mail: cstokes@crytek.com
http://www.claustrophobe.8m.com



   04/25/1999, Fractal Curves, Emulation Of Nature


Yet another update so soon? Well I think this one is important. It involves the creation of a regeneratable fractal set for game geometry.

I have been, as some people who I have been idea swapping with know, been contemplating putting a few different styles of curves into CI. Some people say "So what? Q3:A and others will have them. CS already has them." I say to them, yes but they are just an extension on polygons, they may be more natural, but a true polynomial curve in nature is rare.

Nature doesn't follow normal equations, it is based on fractals, which is to say, that nature is in fact random, but the thresh-hold of randomness actually gets smaller between each other random iteration.

To explain it better than I ever could, go to: http://www.gameprogrammer.com/fractal/fractal.html which explains fractals rather well, and puts them in the context of the old diamond square landscape routine.

Now, once you have an understanding of fractals you can read on...

Okay, now comes the fractal curve bit. Imagine you have a triangle. You take each line segment used to make the triangle, generate your random value and off set in the direction of the triangle normal. Now connect these 3 points up and guess what? You have split your triangle into 4 triangles. And you can repeat this over, but be aware, after the first loop, triangles share line segments, and each midpoint you generate for a line must be used on both triangles. Also, if you use multiple interlinked fractal curves, you must make sure the edges share values. I assume also,that you know to use the roughness to reduce each pass? If you don't go read the listed above doc.

This will get you a simle fractal curve. Importantly, you may wish to "seed" iterations of the fractal, by predefining values. You may want to do this if you want your fractal curve to link up with non fractal polygons, or you may want something that resembles a polynomial or sinus curve. Seeding can be done rather easily. For polynomials or sinus curves, you would have to seed probably 3 iterations.

LOD comes in two variaties. You can precalculate the whole fractal, up to a certain number of iterations and then remove later iterations from drawing as you need more detail, or such. This takes a lot of memory, especially for large fractals, and it doesn't offer infinate LOD.

I use a different method. It solves the problems of BOTH the a forementioned problems. What I do is make a re-creatable fractal. I do this by using a look up table array of arround 64 random numbers per curve. Then, when doing your fractal iterations, always make sure you do them in the same order. That way you can just loop through the 64 random numbers, and multiply them by the iterations roughness. That way, no matter what the random numbers will be the same.

If 64 random numbers per curve is too much for you, as you inteand to have many curves, You can use say 4 look up tables for the entire engine, of say 255 in size, and then for each curve save two variables. One is the randomly selected table number, the other is the offset to start on in the table. That way, you pretty much get a random result ;-).

Seeding in most circumstances is saved, unless of course you predefine the iterations algorithmically for pass.

One thing I can not emphasise enough though is... CACHE THE FRACTAL!. When you deterimine one is visibile, and you process it, store it in a structure like the texture cache. It means simply that you can store it and keep it until it is overwritten by the next LOD. This saves you valuable time and memory.

Conor Stokes

PS Congrats To Henry Robinson, and welcome to ranks!





  • 12/29/2000 - Techfile From Somewhere Different
  • 10/10/2000 - Some Fun, And A Cameo Appearance
  • 08/10/2000 - Déjà vu - And I've Done It Before
  • 07/08/2000 - Various Loose Ends To Hang
  • 05/15/2000 - The Way To Hit A Ball With A Bat. Or Not
  • 03/28/2000 - The Fine Art Of
  • 02/13/2000 - A Life Time of Learning, Teaching and Eating M&Ms
  • 12/09/1999 - Strangeness And Wondering If You Are Taking Innovation A Tad Too Far
  • 11/12/1999 - How to Break Exam Tension? Update Your Techfile
  • 09/14/1999 - Lots of Ramblings, personal things and comments on why SNFU
  • 08/23/1999 - Trials and Tribulations of Being Cerebrally Defunct
  • 07/29/1999 - Quick Update about Stuff and Things
  • 07/25/1999 - I'm Back Baby
  • 07/01/1999 - Is it so? Or am I just a Psycho Babbling Mental Hobo, who's Brain has No Home?
  • 06/25/1999 - Another Couple of Things
  • 06/17/1999 - I Am A Naughty Little Boy ;( But I Have A Way To Make Up
  • 06/16/1999 - What the hell? A new data structure for visibility? I don't know, I haven't heard of it.
  • 06/05/1999 - A Little Right Brained
  • 05/12/1999 - A Couple O Things
  • 05/08/1999 - Pre Computable Nice Visibility Sets
  • 05/04/1999 - More on Volumetrics
  • 04/30/1999 - Generic Update
  • 04/27/1999 - Spherical Volumetric Rendering (Mapping)
  • 04/25/1999 - Fractal Curves, Emulation Of Nature
  • 04/25/1999 - Claustrophobic Irony Level Loading and Manufacture
  • 04/24/1999 - Visibility Ramblings
  • 04/21/1999 - Why Software Rendering Is Not Dead
  • 04/17/1999 - Optimizing For Specific 3D Hardware

  • 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]