Digital Dawn Graphics Inc.

Contents of This Document

News
Release History
Todo List
Known Bugs

News

Jan 16, 2003 I have not continued development of my public terrain engine for the past 18 months and am unlikely to do so.
Mar 26, 2001 I am able to login in again and release the Feb 18 release properly.
Mar 5, 2001 DDG compiles under Linux again.
Mar 4, 2001 DDG site on SF gets 10,000th hit.
Dec 31, 2000 DDG site on SF gets 5,000th hit.
Dec 27, 2000 Release version 6, Another major source code overhaul.
Sep 17, 2000 Release version 5 Major source code update, see history file for details.
Jul 9, 2000 DDG website is now hosted on Source Forge
May 20,2000 DDG site gets 20,000th hit!
May 7, 2000 Release version 4
Mar 5, 2000 Release version 3
Mar 3, 2000 DDG site gets 10,000th hit!
Feb 18, 2000 DDG has been on the web for 1 year!
Jan 21, 2000 Web site gets a facelift.
Dec 4, 1999 Release version 2
Aug 6, 1999 Release version 1
May 19, 1999 DDG gets its own web site at oz.net.
Feb 18, 1999 DDG made available from the crystal space web site.

Release History

01/07/01	Rewrote the error value calculation to be much more accurate, smoothly sloping terrain now gets less detail, as it should be. The new error uses less memory, 1/4th of what I was storing previously. The improved error means we need fewer triangles to get a good image, I have reduced the default LOD to 10,000 triangles and this gives good results, frame rate is close to 150FPS with 120FPS moving forward and around 100FPS when making a 180degree turn.
25/06/01	Enabled inlining to work properly, should experiment with fast call next. Implemented support for the S3TC extention to handle compressed textures. Moving forward maintains 110FPS, turning head drops it to around 80FPS. Rendering is 133FPS. There is a bizarre compiler optimization bug in release mode that I have finally worked around.
18/04/01	Rewrote the rendering and especially the texturing for the terrain to use a texture cache. There is one cache for each texture LOD, nearby terrain is rendered with the highest res texture 1Kx1K, intermediate range is rendered with textures whose max size is 256x256 and distant terrain is with textures of max size 64x64. Implemented support for the S3TC extention to handle compressed textures. Rendering is now up to 2 1/4 million triangle per second for pure terrain, with a single texture pass (which looks ok with the high res textures.) This is from a debug build. Updated the screen shot page. There is a bug when rendering with the optimized build which I have not yet tracked down.
05/03/01	Optimizing rendering and moving all the extention stuff into the oglxt class.
05/03/01	I spent some time along with help from Stephan Heigl getting DDG to compile again under Linux. At least there are make files now and all the parts of DDG did compile. However I never had time to run it. If someone wants to complete the port let me know and I can try to put more effort into it.
28/02/01	Fixed starfield rendering.
18/02/01	Fixed bug in setHeight(). Fixed bug in loading terragen files, terrain was showing up as rice paddies because of a float/int issue. Fixed bug where I was not rendering the terrain at full resolution. Fixed a really nasty clipping bug. Collision detection is perfect now and trees no longer float in the air!
11/02/01	Fixed fullrender version of terrain. Can show wireframe overlay onto terrain. Fixed tree rendering.
04/02/01	Fixed some packaging errors w.r.t. missing files, bad project settings. Demo would not work on non GeForce cards, fixed the Extention detection code. Also made toolkit more lenient w.r.t. opengl errors, some cards do not support the blending mode that ddgSky uses, instead of exiting in this case, I report the error to the console and continue. Upgraded to run with GLuT 3.7.3.
03/02/01	Converted over to using the DDGDIR environment variable everywhere, this variable should be set in your autoexec.bat to the ddg directory. This will make compiling easier from now on. Created a project that automatically creates the zip files for me to allow me to make uploads more easily. I also added the missing .h files and .lib files to make it easier to compile DDG without having to search the internet for these files. I saw a problem on a TNT2 machine where the terrain did not show. If this is happening, try recompiling with ddgNVFence disabled in ddgterrainrender.cpp.
01/02/01	Optimized vertex data generation, we now send less vertices than triangles. Fixed cam.pth to work with the new scaled terrains. Now I can run perf tests again. Need a new path for testing a larger terrain than 256x256 though. NVidia fence extension is now dynamically enabled if the extension is supported. Note however if you enable the clip planeit slows down rendering a lot. Created a new release. This release includes source code to render the terrain. It also includes source code of the initial DirectX8 port (only viewport works). Ragnar Scheuermann has written an explanation on compiling DDG, that might help some other people. I will try to convert the VS project to use an environment variable soon. Note that the DDG data formats have changed, you will have to delete any existing files in the 'output' directory and regenerate them.
28/01/01	Pulled rendering of terrain out of the terrain lib. ddgTerrain view now accepts a memory block for a VertexBuffer and IndexBuffer, these blocks are then filled in with triangle data. This data can be rendered in one blow or block by block. Added code to generate lowres global texture. Implemented use of lowres texture for far away blocks, this means that much fewer high res textures need to be loaded at any given moment. Also makes rendering the far away data much more efficient since it can all render from the same global texture, it can all be merged into one render call instead of one per block. Cut per block memory consumption by 30%. Each block now takes only 10534 bytes.
20/01/01	Force terrain in immediate vicinity to highest detail resolution. This confirms that getHeight was correct. Can also use this to maintain a list of triangles onto which we want to render with additional detail.
12/01/01	Added support for dynamic terrain, ddgITerrain::setHeight() method on the terrain now almost works. ddgITerrain::getHeight() is working now. Fixed a bug in terrain variance calculation, terrain is more stable now, the areas which need more resolution, like cliffs get it now. Base geometry is no longer based on a right angle triangle but on a square. So blocks are really blocks now, this eliminated a bunch of unneeded memory/computation and especially code complexity from the terrain. It also saves on disk access time since there are no longer twice as many block files as texture files.
01/01/01	Texture generation can now write out a 24 bit color map as well as an eco map, this color map can be edited with a paint program to modify the generated ecosystems, then you can rerun the texture generation and it will can generate texture based on the colormap, this allows you to generate the general terrain and then add in textures for roads, lakes, rivers etc.
28/12/00	Release V6. Eliminated DDGSTREAM symbol, I am assuming streams are available, maintaining the ability to compile without streams was a mess. Blank viewport for DX8 shows up. Fixed some bugs w.r.t. text rendering and a memory corruption problem for non square terrains. Fixed location of sky/clouds etc. Fixed some data propagation errors w.r.t. invalid heightmap values which could cause an entire block to have an error value of zero when it should have been more. Discovered and fixed an error in which block zero remains at the lowest level of detail.

27-12-00 V6 External Release

Eliminated DDGGlut library, all Glut references are now localized within the ddgViewport class.
Implemented a Viewport class for DirectX8.
Added interfaces for Scene, Camera and a few others.
Simplified/rewrote the event handling system. Event objects are now passed through, this means you no longer need to implement 4 methods to handle events, just one will do. Chaining is also simpler now, just call insert on an event handler and the inserted handler will be processed 1st.

12-12-00 Internal Release

Separated terrain data from the view of the terrain data, this allows multiple independent views of the same terrain. Also implemented persisting the processed terrain data. Processed terrain blocks can now be saved to and loaded from disk.
Implemented reference counting for the ddgNode class to cleanup the destruction mess. When a ddgNode is added to a ddgGroup, it is now addrefed, if the group tried to destruct, it will decrease the refcount on each ddgNode, if one of these now has a refcount of 0, it will automatically delete itself. To keep a node alive outside of a ddgGroup container, you can addref and release it manually.

22-11-00 Website update

Searched the internet for any terrain engines and added a webpage indexing them. See this page.

22-10-00 Internal Release

Fixed orientation problems with heightmap and image files.
Note both height maps and images are now indexed using (col,row) instead of the (row,col) notation. This maps more closely to using (x,y).
Also note that an image map's (0,0) coordinate is the top left where as a height map's(0,0) refers to the bottom/left or south west corner.
Heightmap objects now calculate or determine their world space bounding box, this information is then available to other components. It also keeps track of sphere radius to possibly support curved earth in the future.
X/Y is now the ground plane and Z is height.
The keyboard control now works more like that of a plane. Heading,Pitch and Roll are relative the the viewers current orientation.

15-10-00 Internal Release

Multi-textureing works now, The ddgTexture now supports a UNIT property to indicate which texture unit to load into. Also added some support functions to set up texture arrays.
Started implementing some classes using interfaces. ddgIContext, ddgIHeigtmap, ddgITerrainMesh, ddgITerrainBinTree are implemented. The functionality in these interfaces is still not correct as there are some methods in the interfaces which should probably be removed.
Re-did much of the error/return code infrastructure. Instead of returning a boolean ddgFailure/ddgSuccess most methods now return a return code (ddgRC) which can be set to any of the error codes. The error codes have been changed a bit as well. ddgE_Success == 0, all other codes are some kind of error and are not == 0. Use the macros ddgFailed(functionWhichReturnsRC()) to test for failure. Use ddgSucceeded(functionWhichReturnsRC()) to test for success. See error.h.

25-09-00 Internal Release

Assign triangle caches only as needed. This reduces memory consumption by another 1 bytes per hexel (height element). We now use 3.5 bytes per hexel. 2 for heightmap and 1.5 for overhead. If I drop the hulls this would become 2.5, only 0.5 overhead. Hulls are not currently used. I can also decide not to keep hulls lower than some level N, say N = 4, this would effectively reduce overhead to about 0.6 bytes.
Fixed fog.

17-09-00 V5 External Release

Added support for streaming output to log files with ddgLogFile object.
Switched to blocks of size 65, produces fewer textures for large terrains.
Fixed ground rendering.
Fog is messed up for large terrains.
For the demo binary you have to move a bit before the terrain shows up correctly.

17-08-00 Internal Release

Implemented support to scale and offset the mesh.
Fixed tree rendering.

13-08-00 Internal Release

Implemented clipper and reflection classes, these additions allow you to implement water reflections see the screenshots page. To use this simply add the same scene node to the reflection node and it will be rendered in the relflection plane. There is no need for data duplication.

05-08-00 Internal Release

Increased triangle count to 8000 to avoid popping. Scene is very stable now. Memory usage reduced to 4 bytes, 2 for heightmap, 2 for overhead.

25-07-00 Internal Release

Working on generating the clipping planes from the forward, up, right vectors plus fov, near and far clipping planes and aspect ratio. This method will eliminate the need to use the OpenGL matrices directly.
Added Torus class from Ben Adams.

15-07-00 V4.8 Internal Release

Removed row/col data and went to calculating this on the fly, but hand optimized inline code instead of relying on the generic code. Had 100FPS at one point, but after completing the modifications, dropped back to 89FPS. Pure mode is down to 153 when doing this.
Pass texture coords as integers from 0-32 instead of 0-1 fixes texture seams. Also allows me to use SHORTs instead of FLOATs = > 50% memory savings. I could even use unsigned chars and reduce by 50% once more, but I dont know packing format for glTexCoordPointer(). Frame rate drops from 89FPS to 79FPS by doing this.
Rough Memory usage with -texture off = 2059616.

15-07-00 V4.7 Internal Release

Implemented histogram and histograph object, histogram is generic and histograph is a class which uses histogram to render a histograph of samples in a 2D box anywhere on the viewport. this class has given me the ability to view the distribution of computed priorities in real time, it showed that only the 1st 1/4 of buckets were being used and the rest was almost empty.
The dome object is no longer GL dependent, the cloud, sky and ground objects have been rewritten to deal with VBuffer directly and use that to render as well. Dome is only used to initialize the geometric structure.
Fixed a lot of the rendering artifacts of the sky/clouds. My choice of colours probably leave something to be desired.
Uploaded new set of data and binary. Source update will follow later.

12-07-00 V4.6 Internal Release

Updated the tutorial code to work against the current implementation.

30-06-00 V4.5 Internal Release

Reorganized the files again to completely separate the GLUT and OpenGL dependent files from the other files. We now have the following libraries:
- DDGCore - platform independent code mostly algorithmic.
- DDGGL - renderable objects using OpenGL.
- DDGGLUT - viewport and some event handling stuff using GLuT.
- DDGSDLGL- viewport and some event handling stuff using SDL.[Not yet implemented]
- DDGDX - renderable objects using DirectX. [Not yet implemented]
- DDGSDLDX - viewport and events for DirextX. [Not yet implemented]
This change also required me to rewrite all the event handling architecture to eliminate the use of the ddgParam object. A viewport now contains an event handler for the following:
- Simple keyboard events.
- Special keys like CTRL/ALT
- Mouse Clicks.
- Mouse Movement.
Any other component can override the viewport's event handler with their own. In that case if they decide not to handle the even, the overriding handler should fall back to calling the original handler.
The removal of the use of ddgParam also caused me to rewrite the commandline argument handling. Instead of having a parameter like '-nostars', we now use '-stars [on/off]' this allows you to explicitly indicate whether rendering should be on or off. We only check for 'on' anything else is considered off. The default setting of the parameter may be on or off.
Invented a way to traverse the leaf nodes of a bintree to allow me to iterate through all leaf nodes sequentially, implicitly (ie without any data storage) and topologically. The per bintree chains of active nodes are no longer needed and have been removed. We should be able to render any given bintree as one strip (if entirely visible) or several strips (if partially visible).
Implemented a texture based font class to replace the GLuT dependency in the ddgText class. DDG text now relies on the presence of a "data/texture/font/default.TGA". This class can easily be extended to support multiple fonts.

10-06-00 V4.4 Internal Release

Put better version of Linux makefile on the web, not actually tested under linux.
Implemented convex hull class to serve as generic clipping class. A convex hull is any space defined by a set of planes. Clipping will be implemented for BBox3, Prism3 and Triangle3. There is also a 2D version CHull2 which can clip rectangles and triangles.
Added suffix [1,2,3] to geometry classes to clarify what dimension they are. Eg. Plane -> Plane3, BBox -> BBox3. Those geometry classes need a major cleanup most of the code there has never been tested.

03-06-00 V4.3

This release requires a subdirectory in the data directory into which it can generate the texture tiles. This is all done automatically the first time you run the program. On subsequent runs, this data is simply loaded from disk.
Fix frame coherance bug.
Running in split only mode works now. Also when the orientation changes more than 70 degrees between frames, the engine restarts with a split only frame to avoid massive merging of triangles which are totally out of the current view.
Performed a ton of optimization, compute only mode is now 167FPS for 4000 triangles.
Completed integration with Crystal Space. The code should a lot more portable now. Note, not all of DDG is in CS only the terrain engine.
Added cone based clipping as a temporary measure for CS.
Implemented a 'curved terrain' to simulate curvature of a planet. This currently only affects the terrain so the ground/ocean is not curved and it appears that the land rised up from the sea as you move towards it. This can easily be fixed, but I havent had time.
The next thing I plan to do is to get rid of GLuT and investigate SDL and perhaps D3D.

25-05-00 V4.2 Internal release

Fixed bug in priority calculation.
Implemented error handler function, this will allow you to perform some cleanup like shutting down GLut windows even when an error has occurred.
Implemented the ability to switch between split/merge and split only computation based on the amount of change in the view direction, if the view direction changes by more than 70degrees, we dont bother trying to merge but just perform a pure split calculation.
Also implemented some functionality to limit the bintrees that need to be processed each frame to those that are theoretically visible from the user, this means the engine does not even need to touch bintrees which not in view, this will make paged data possible.

17-05-00 V4.1

Performed all sorts of cleanup and compatability changes w.r.t. the integration with CS.
Fixed the -notexture option.

07-05-00 V4.0

The new architecture is finally working and it is pretty quick (120FPS) in no render mode. This version renders as fast as the old version but uses less memory and adds the lowest level of detail. The code is now in a state where performance measurements may be useful.
Fix memory overflow bug in stars.
Added more feed back for operations that can take a lot of time like heighmap generation, texture loading, texture splitting.
The engine now supports loading split textures straight from disk, if split textures do not exists the global texture is automatically split and a texture is saved to disk for each block. The name of this texture is the same as the global texture plus a block number.
Memory usage is also reported. This does not include memory allocated by OpenGL.
The block size has been reduced from 65x65 to 33x33. The default texture resolution has been increased to 8x the heighmap. For a 256x256 map this generates a 12MB texture. For a 512x512 map this would by 48MB. I have run a 2048x2048 terrain but that required a texture resolution of 2x.
The next step is to profile and tune the performance. Trees have not been tested recently.

01-05-00 V3.6 Internal Release

Rewrote the movement infrastructure. Previously collision detection was handled in the global update function, this caused some problems because of the order of operations. The core rendering loop is now as follows:
```
	ViewportSet::draw
	for each Viewport which needs redisplay
		{
		Camera::update
			Context::update
				if playing back from a script change position/orientation for the frame
				else
					Control::update
						move the player according to keyboard feed back.
						perform collision detection and adjust position.
		global::update
				optional general purpose function.
		Camera::draw
			set GL matrices
			update projection matrix, modelview matrix and frustrum planes for context object.
			Scene::draw
				...
		}
	
```
There is now a Control class which maintains the position and orientation of an object in the scene. This class should be used for moving objects. The Context class which maintains a number of viewing parameters like field of view, clipping etc. now requires a control object to give it a position and orientation. Control and Context are both independent of the rendering (ie. not dependent on OpenGL). The Camera object uses a Context object to know how to set the viewing matrices. A Viewport require a camera to determine what will be shown in the viewport.

22-04-00 V3.5 Internal Release

Rewrote the engine, the new engine is a split only worldspace engine.
Reduced memory usage back to 8 bytes per point (includes height map), this includes a hull to allow occlusion culling other wise we could use 6 bytes. all other data is handled by a cache which is cleared each frame.
Memory usage for a 257x257 map is now 1053568 bytes.

11-04-00 V3.2

Fixed tree orientation bug. Note all textures by default expect to be mapped from 0 to 1 now. Added mapColorToAlpha() method to Image class, this method adds an alpha channel to the image and sets it to transparent every where the specified background colour is defined.

06-04-00 V3.1

Most significant changes in this version are the addition of the following:
Trees that can be planted by eco class. Optimized rendering for these.
All calculations are performed in world space, no more need to deal with camera space vertices. Great for T&L cards, for the other ones it should not make a difference.
Improved texture synthesis code.
Full release of source, data, windows binaries and documenation. Note this version does have more popping than the camera space version, this is a work item. Also version currently uses more memory, this is also temporary.

03-04-00

Height map data is now 100% local per bintree.
Improved the opengl extention detection code and it detects the GeForce features correctly.

Fixed bugs in world space priority calculations, visually it looks ok but we are doing way too many insert/remove and priority operations (factor 4)

type	tr	pri	ins	rem	mov	vis
split/merge May 7	2409835	2498141	690123	86202	993449	1328121
split only. Apr 22	3191234	5770438	4299961	2976451	0	1347056
world space Apr 14	3206238	4452597	266435	263077	205991	1132524
camera space	2936913	1065067	211750	209007	70546	1176083

02-04-00 Internal Release

Small bug fix in sky dome.

30-03-00 Internal Release

Fixed a long standing nasty bug in ddgColor4, it was being derived from ddgVector4 and was 20 bytes instead of 4... that screwed up the rendering.
Implemented texture splitter and adapted mesh renderer to render per bintree pair. I have tested a 50MB texture and it works (4096x4096x3).
Split src directory in to several subdirectories.
- util
- the most low level parts of DDG.
- math
- math/vector/matrix and geometry objects.
- struct
- various data structures, like bintrees, splaytree, octtree, hash table, cache.
- render
- all objects which depend on OpenGL.
- ext
- extensions to DDG like the eco, texture synthesis and spectral height field systems from Klaus Hartmann.
- dem
- digital elevation map loading files from Ben Discoe.
Implemented ddgFrameBuffer class to hold renderer specific functionality. ddgImage is now renderer independent and ddgFrameBuffer is a subclass which can copy Zbuffer, frame buffer or alpha buffer to the image data which can be persisted.
Removed file loading from ddgPath constructor.
Started on world space priority calculation.
Implemented ddgForest class, supports visibility culling and planting according to a property image. Property maps can be generated by the texture synthesis class or a normal 8bit image map. Rendering speed still leaves something to be desired. I have implemented display lists 5FPS.

23-03-00 Internal Release

Moved functionality from ddgCamera to ddgContext. ddgContext is not Renderer specific and contains all the generic information like bounding box, position, orientation which is used by several other renderer independent classes.
ddgVBuffer can now handle vertex arrays of points, lines, triangles or quads.
many fixes to optimize tree culling and rendering.

03-16-00 Internal Release

Upgraded Terragen file loader to support new V0.8 file format.
Added screen shot of trees to website, now getting 10-30FPS depending on how many trees are visible at once. Getting between 15 and 30FPS with 50,000 trees

02-03-00 V3.0

Integrated eco system code from Klaus Hartmann. Thanks to this, DDG now has a texture synthesis system to build very nice textures on the fly. To activate this feature run with the '-synthtexture' option on the command line, note this currently requires a graphics card capable of handling 1Kx1K textures or more.
Added ddgConsole class to provide system independent console output.
You can now specify a path for the data directory using the '-data path' option. The archives also have restructured data directories.
Added occlusion data generation. Started work on making use of this to provide more visibility determination. This will also be use for shadow/light calculation.

24-02-00 Internal release

Integrated PGM loading support from CS into DDG. Reads from memory only.
Fixed start field rendering again.
Fixed cloud/sky dome zbuffer artifacts, cloud dome is now smaller, this causes some horizon artifacts.
Fixed fullscreen mode rendering.
Added ability to perform world space culling. 10% speed degradation. Need a way to perform priority calculation in world space.
Avoid inserting/removing leaf nodes into split tree. 12% speed increase
Avoid recalculating total # of vis triangles, and merge reset/visibility call. 12% speed increase.
Use a faster triangle cache 2% speed increase, adds 2 bytes to every MTri.
Converting sun to render as bill board.[In progress]
Use 2 bits for visibility now instead of 8. Still have added overhead of tcacheId.(2byte)
Renamed all .hpp files to .h to allign more closely with Crystal Space, also renamed those files which are included in CS to match the shortened CS names.

07-02-00 Internal release

Eliminated recursion from setup/visibility and update priority methods. 2% slower.
Added initial support for multi texturing.
Enabled scissor. No speed impact.
Enabled ALPHA plane so RGBA really is RGBA not RGB. This has a 30% speed hit in SW mode.
Use '-nocolor' option to disable vertex color interpolation.
Add more rendering detail to performance log file.
Implemented absMaxDetail option, defines max possible on screen triangles and all memory for vertex buffers are based on that, should avoid memory overflow problems better. Default is 2 * Detail (-detail) = 6000.
Lighting can be turned on/off interactively.
Topview window is now off by default.
Made the extensions to DDG optional, the following features are off by default and can be enabled by defining them in ddg.hpp or in your project/makefile: DDGPNG, DDGDEM, DDGSPECTRAL.
Use ddgSuccess and ddgFailure instead of false and true as return values.
Updated source and binary archives. Hopefully the project files are a little better this time.

02-02-00 Internal release

Added support for Spectral Fractal height maps, these are symmetric and look very interesting. Uses code from Klaus Hartman.
Improved error checking in height map code.
VBuffer supports sorting triangles by z-depth.
Added support for stereo rendering (untested).
Integrated code with Crystal Space again.

21-01-00 V2.7

Thanks to Ben Discoe's ElevationGrid loader, I have added support for loading DEM,BT,DTED and GTOPO30 terrain files.
Added support to specify sealevel, default it 0.0
Small bug fix to cleanup triangles that become non visible.
Andre Sodermans and I have also made progress on using the Pentium III SSE instructions.
Uploaded: Sources, Binaries, Documentation, Screenshots and new Webpages.

11-01-00 V2.6

Added functionality to the ddgVector and ddgMatrix classes.
Implemented billboard option on ddgTransform.

07-01-00 V2.5

Fixed height map generation to extend area instead of scaling it, also support saving heightmap as an 8 bit TGA file.
Fixed saving of heightmaps to file.
Tested terrain with size 1024x1024
Verify all signification memory allocations to ensure memory could be allocated.
Size of 2048x2048 also works, had to increase splay iterator stack size though. Frame rate is not significantly affected by having larger terrains.

07-01-00 V2.4

Binary and source release.
Removed some debug code that was causing program to look in wrong dir for data.
Program is also fixed not to crash if a file cannot be found.
Automatically turn topview off for fullscreen mode, thanks to Shawn Gonzales for mentioning this to me.
Even when no files are found, you will still get a nice fractal landscape which you can run around in.
Did some profiling, I am spending a 70% of the CPU time rendering, that seems too much. Also I think the CPU is blocked waiting on the Card quite a bit, we will try locked vertex buffers next.

07-01-00 no code release

Posted a couple of new screen shots.

06-01-00 V2.3

Some more cleanup and fixes to the balance operation.

The problem is that with the new merge queue, we check the parent triangle's priority and this causes a lot more(3x) priority calculations but less queue operations overall (25%).

version	tri	pri	ins	rem	mov	vis	FPS
nov 29	2369432	1548039	378888	375029	501816		51.6
jan 5	2521161	4792487	288344	284508	534083
jan 5 fix1	2521161	4120086	288344	284508	534083
jan 5 fix2	2521161	4082911	288344	284508	534083
jan 5 prog50	2521161	3589152	286181	282352	512182		5.4
jan 5 prog10	2671729	1106775	259768	255912	273348		5.4
jan 5 noDL	2671729	1106775	259768	255912	273348		58.4
feb 19noLeaf	2481047	1102582	223521	220108	172676		65.3
feb 23noreset	2315104	1005583	184852	181819	163495	1073896	72.2

Progressive priority calculation works again and even with fewer operations for pri/ins/rem/mov it is still a factor 10 slower! discovered this massive slow down is caused by the display lists added on dec 11!
I get 97.2 FPS when rendering is off and prog dist = 10 and 65 with prog dist = 0.

04-01-00 source code release V2.2

Andre Sodermans has joined the project and is already adding stuff to DDG. We now support reading PNG files for textures, we will get saveing images as PNG files soon.
assert is now renamed to ddgAssert to avoid system conflicts.
Fixed the merge Queue bug I think! the merge queue is re-enabled now. Something is slowing stuff down though worse than some time ago, so I must have introduced some slowdown somewhere.

01-01-00 no release

Fixed priority calculations to enforce child priority < parent.

12-31-99 no release

Fixed saving of heightmaps as terragen files. Also supports sizes other than the 256x256 which terragen itself supports.
Implemented bucketsort/hash table, much slower than splay tree though, not sure why. Can now compile to use either one.
Upgraded to ASUS GeForce. What a beauty. I can't wait to implement the bumpmapping features into DDG.
Added ability to render in wire frame mode only by turning off solid mode with 'o'.
Turn text statistics on/off with 'E/e'.
Added support for 12 fullscreen modes.
Commandline support for specifying initial window width/height.
Increased default size to 800x600 and run in 32bit mode.

12-11-99

Uploaded new documentation and updated the perf page a bit.
Implemented display lists.

12-11-99 V2.1

Performed a lot of cleanup and fixed some bugs.
Progressive recalc delay is now a single bit instead of an unsigned char. This shaves another 2 bytes of the mesh data.
Fixed rendering bug if camera stood still, vbuffer was getting appended to. Rendering has now been changed to leave vbuffer intact when not moving. This is also a performance win.
Remapped a bunch of the keys to more logical character. Prog dist can now be adjusted with 'p'.
In an effort to debug the Balance Queue operation, we can now provide loggin of all queue operations as well as dumping snapshots of the queues every frame.
Added ability to run balance operation as a split only engine with dynamic switching to activate/deactivate merge queue. In split only mode the engine is 100% stable and requires about n/2 operations to produce n triangles. With the merge queue active we are still unable to reach a stable state and rely on the bail out method to quit after n/3 operations. Basically it is a mess with merging active. Default is to use split only method for now.

12-04-99 V2.0

Added high resolution timing capabilities to clock and fixed FPS display (Win32).
Added 'farclip' and 'progdist' commandline options to control the farclipping distance and the distance at which progressive calculation takes effect.
Implemented memory allocation tracker.
Added new command line option
memlogfile to indicate log file for memory usage.
Reduced memory requirements in MTri from 24 bytes to 8 bytes.

Replaced precalculated normal grid with a normal map and indices, cut memory usage from 12bytes down to 2.

Mode	256x256	512x512	1024x1024	Date
Orig	2 349 764	9 042 804	37 391 060	Nov 99
New MTri	2 026 964	6 752 004	26 441 060	Dec 99
New Normals	2 505 236	4 916 996	16 741 732	Dec 99
Reuse bufidx	2 084 236	4 515 196	14 896 732	Dec 99
DelayBit	2 010 436	4 113 396	13 051 732	Dec 99

Besides the fixed overhead for rendering buffers, the following memory is required depending on terrain size:
- MTri data 8 bytes * rows * cols (was 24 bytes)
- Height samples 2 bytes * rows * cols
- Normal map indices 2 bytes * rows * cols (was 12 bytes)
- TBintrees 52 bytes * (rows-1) * (cols-1) / ( blocksize * blocksize ) * 2
Total memory usage per data point is 12bytes.
Overal memory consumption cut by 66%.
Increased default detail to 3000 triangles.
Uploaded new sources and binaries to web site, updated web site.

11-29-99 V1.9

Bug fix in priority calculation as mentioned in algorithms news group, this fix solves the problem which was causing the triangles along the frustrum intersection to go to max detail at the expense of the the rest of the image. The terrain is now really stable even at 1000 triangles. Performance is the same 43FPS on the test data set.
Released new source code, binaries and perf data to web site.

11-11-99 V1.8

Cleanup. Eliminated ddgQueue, ddgTBinMesh now uses ddgSplayTree directly.

11-11-99 V1.7

Uploaded some performance stats from a TNT2 and a GeForce board.
Terrain in CS is now functional. Code will be developed separately from DDG. But important improvements will be ported as needed.
Modified performance testing to collect total elapsed time since samples are too inaccurate.
Bug fix in perf log files, months was off by one.

10-31-99 V1.7

Fixed jerky movement.
Cleaned up camera class a bit.
Fixed noise functions and added project to generate sample noise.
New noise function to generate terrain like surfaces used if no terrain is specified.
Ported some CS compatibility items into toolkit. Eg. CS does not support the use of cerr. Functionality which is only supported by DDG has a #ifdef DDG surrounding it now.
Also added support for different endian computers to ddgHeightMap.
Releasing smaller star database, cuts 150K off the binary archive.
Releasing source and binaries for Win32.

10-14-99 V1.6

Fixed collision detection/x,y height calculation.

10-10-99 V1.5

Removed all references to rendering/cameras from the Mesh and TBinTree classes
Renamed ImageH to HeightMap because that is what it is, it wasn't sharing any code with Image anyway. Separated HeightMap into own file.
Changed initialization of Node classes to also have the Context available during initialization. Initialization is more structured now. Super class init should always be called as 1st thing in init() methods. Return value of true means class is already initialized.
Elminated the TriSet and RTriSet classes. They were not really useful anymore.
Separate Str and Error classes into their own files.
Renamed some files.
Now the terrain engine is fully seperate from the rest of the toolkit.
Cleaned up the VC++ projects and compile time warnings/errors.
Added fullscreen mode. (Has problems on shutdown).
Added blend mode to textures. This fixes cloud not being transparent in no accel GL problem and probably Mesa as well.
Implemented basic tree.
Accel mode no longer looks good because PermediaII doesn't support blend mode.
Iinitial integration of files with CS has occurred.
Released binaries for Linux and Windows.
Released new screen shots.
Released documentation.

09-19-99 V1.4

Implemented proper reuse of vertices in vertex array for terrain mesh. This change leads to about 10% performance increase in 32bit mode, 10% decrease in 16bit mode.
Modified buffers to pass Vector3 instead of Vector4 for vertices and normals. Also reduced buffer size from 10,000 to 5,000 entries. This change has no measureable speed difference.

09-16-99 V1.3

Reimplemented normal calculation to use floats instead of unsigned chars. simplifies code a bit.
Implemented function to get mesh height at given x,z location. Usefull for collision detection.
Implemented progressive priority recalculation. Increased rendering speed from 39FPS to 41FPS in 16bit mode (~5%). This feature allows you to specify the triangles which are further away do not get their priority recalculated each frame, but rather every 2nd or 3rd frame. This cuts down on the calls to priority and queue updates by about 30%. These are the most expensive functions. This is by setting the progressive limits to 1/3rd and 2/3rd of viewing distance. These numbers can be adjusted at runtime.
I think I am reaching the limit in optimization of the algorithm because even when not going anywhere (ie mesh is not being modified) the upper limit on rendering is about not much more than that.
Renamed all files/classes/globals with ddg prefix to avoid name collisions when integrating with CS.
Releasing optimized Linux and Windows binaries.
Releasing source, note the source has been tested and compiles under windows and linux RedHat6.
Releasing updated documentation.
Updated perf info.

09-09-99 V1.2

Implemented z-ordering for all visible triangles, sorting 1000 triangles 20 times per second cost me about 10% of rendering speed.
Optimized SplayTree. Eliminated TKey class and inlined all methods. Tried useing less memory by using 16 indices instead of 32bit pointers but this had about a 10/15% negative performance impact. Moral of the story is to stick to 32bit values whenever you can. End result of all this is only a marginal speed improvement.
Modified Mesh to use vertex arrays, this causes only a 10% increase in performance. To do this I created a DVBuffer class which all objects which can render as vertex arrays can use (mesh, cloud, sky, ground) it handles memory allocation as well as pushing triangles into the buffer and rendering the buffer as desired with optional normals/colors/textures.
Fixed bug with Alpha on software mode (wasn't getting the right display type). Clouds should now look the way they were designed. Note on my machine I need to be in 16bit mode (as opposed to 32bit mode) for this to work, only in 16bit mode can I get an RGBA buffer in software. My software 16bit mode is 5FPS and the software 32bit mode is 1FPS.
Added
notopview and
notext options to commandline.
Uploaded new demo.

08-14-99 V1.1

Fixed fog, fog is now white and looks pretty good.
Fixed reading depth buffer for sun eclipsing detection.
Modified scene graph to use a Context object when rendering. Previously there were two parameters passed around to indicate the rendering mode and some object were storing clocks and cameras because they needed them. This information is now stored in the context object which is passed down to everyone. This also saves a little stack space.
Image class can now capture the frame, alpha or z buffer. Since an image can already save this info, I can now dump it to view it for debugging.
Implemented far and near clipping for terrain (independent of camera clipping). This means terrain won't go on forever now but gets clipped behind the camera and beyond a certain distance. This speeds up visibility testing as well. In combination with fog this efficiently removes the parts of the mesh which cannot be seen.
Removed MUI dependency.
Fixing Noise functions. Incorporated Geoff Wyvill's 4D Noise from Siggraph99.

08-06-99 V1.0

Bug fix for stars in optimized version.
Using large draped texture for default now.
Removed some debug code which printed text to console while clouds were rendered.

08-05-99

New screenshot using large texture.

08-04-99 V0.9.9

Generalized FacetSet and derived ClippedFacetSet and GeoDesic from that class.
Fixed star field clipping.
Added moon using GeoDesic, moves with time, doesn't look good though.
Clip triangles beyond certain distance. Not working to my satisfaction
Added fog support, doesn't look very good though (fog is black).
Cloud cover varies over time, cloud brightness varies according to sun position.
Various rendering fixes and code cleanup.

07-26-99 V0.9.8

Created Dome class, Separated sky functionality from Cloud. Sky, Cloud and Ground all derive from the Dome class. Next step is to implement view frustrum clipping for the Dome class.

07-26-99 V0.9.7B

Bug fix. I still had a piece of code commented out from the conversion to Splay trees.
Performance log now writes out time/date detail, terrain size and block size into the log.
Got some more statistics from the machine at work with the 3D accelerator card, I am getting frame rates of 32FPS in rendering mode and 64FPS in algorithm mode, since the demo is driven by redraw calls I think I am seeing an artificial limit, I will try an 85Hz refresh setting to see if it makes any difference.

07-25-99 V0.9.7

Major speed improvement. Replaced the horrible queue implementation which was sucking up about 80% of CPU time leaving 20% for the rest. I replaced it with a Splay Tree. This variant of the Binary tree is much more efficient for inserting and removing items and still keeps things sorted. Queue overhead is now down to about 24% of CPU with 76% left for the rest. My perf2 statistics went from 9.7FPS to 63.1FPS (this test cuts out rendering to test algorithm performance), that is a 600% increase. Performance Table

07-15-99 V0.9.4B

Bug fixes, wouldn't run w/out
array option.
Releasing Linux binaries.
New screenshots.

07-15-99 V0.9.4

Releasing new src, and binaries for win32.
Fixed vertex arrays for ground rendering, problem was that the color array of the cloud pass pass still active. Ground shows up but doesn't look right yet, colour array must be wrongly specified. Fixed
Terrain eats about 1MB per frame of memory. Fixed memory leak.
Converted all Color3 objects to use unsigned chars instead of floats. This should reduce memory requirements a bit.
Fixed performance script (new coordinate system made the old path invalid. Converted it to new coordsystem). Also fixed a bug which was introduced in camera path following. Camera can now be directly associated with a path and the camera will follow it automatically.
Fixing lighting which broke after conversion of colors to unsigned bytes. Fixed.
Fixed cloud array rendering, UNSIGNED_BYTE is not an implemented type for the glColorPointer array even though OpenGL does support it. Have to mix colors anyway so I have secondary float color array.
Fixed and tested the various interpolation functions. Color mixing can now use any of the 4 interpolation methods.
Terrain map size is now completely independent from BinTree size, this allows the BinTree size to be tuned easily and also allows for non square terrains. Terrain maps are rounded off to the nearest whole BinTree size eg. if bintree size is 65 and the terrain is 1000x200 the terrain would be broken down into 15x3x2 bintrees covering 961x193 samples.
Reenabled color mixing on the terrain, looks good but need a white base color in the texture.
Performance analysis done for pure terrain calculation (perf2) at 1000 visible triangle on a PIII-500Mhz 256Mb is 10.6 FPS up from 9.8 FPS on Jul7. This is as constant movement. On Permedia II accelerated 450Mhz machine current frame rate fully rendered is 6.7FPS.

07-01-99 V0.9.3

Releasing new src, and binaries for win32 and linux (RH6) Note for Linux be sure to run your X server in 16 bit or better mode or the graphics will look awful.
Fixed runtime errors under Linux. The problems are related to GLUT, I had to disable the TopDown view viewport and everything worked. However keyboard character i/o isn't working. Could be due to fact that I am using the Mesa3.1beta.
For windows, I implemented the cloud rendering using vertex arrays, tried to do the same for ground rendering which is practically the same but I cannot get it to work, as soon as I render it with vertex arrays, it doesn't show up. I used the same variation of vertex arrays as John Carmack described in his recent Optimizing OpenGL paper.
Fixed terrain rendering so that the triangle count the algorithm is the visible triangles and not the total triangles in the mesh at that point.
Optimized the recalculation/rendering a bit by avoiding extra calculation of visibility and priority info if triangles are queried multiple times during a frame.
Set the default number of triangles down to 500 from 1000.
Fixed normal calculations, the mesh is no longer transformed by OpenGL but deals with real world coordinates all the time. This will make porting it into crystal space a lot easier. This also fixed the awful lighting
Moved all BinTree functionality out of mesh.cpp and into a new file, bintree.cpp.
Moved all bintree logic out of main and into mesh class. The mesh will create as many connected bintrees as needed to cover the given image. This is not automated yet and is the next step. This will allow arbitrary height maps to be imported. These will then be automatically converted to a number of BinTrees, the size of these bintrees will be 129 or 65 points on each side. This would allow each bintree to keep its own set of coordinates in a vertex array. BinTrees which a far away from the camera or entirely out of view wont need to be processed and because the bintrees are smaller we should get better cache coherence and less overhead.
For some reason ground rendering is now sporadic even without vertex arrays. This is not happening with Mesa only under Windows.
Tried to change the cloud color (it is a 24bit texture so it should be easy) but for some reason my colour interpolation doesn't work yet...
Made colour/material blending an option (now off by default). Textures shouldn't be so gray anymore.
Top view colour codes triangles according to priority, brighter for higher priority triangles.

06-22-99 V0.9.2

Fixed compilation for Linux RedHat 6. But generates Mesa errors when running.
Started experimenting with Vertex arrays in ground rendering.

06-13-99 V0.9.1

Implemented performance measurement infrastructure. The command line option -record filename records camera movements. The option -play filename plays a recording back. The option -perf filename records the elapsed time between each frame, it also disables rendering everything but the mesh. The option -perf2 filename runs perfomance testing without rendering at all testing only the algorithm.
Started implementing vertext arrays and triangle strips.
Added -help option to explain command line options.

06-01-99 V0.9.0

Added support for 16 bit height maps.
Added support to read and write Terragen height files. DEM files can be loaded by converting them to Terragen files with the 3DDEM program.
Fixed Clouds, Sun and Stars to work in demo.
Added global ground/ocean object.
Added Geodesic object (used it to test the lighting).
Fixed lighting somewhat, still isn't what I want.
Fixed initial support for textures.
Fixed loading of .RGB files.
Some performance modifications w.r.t. memory usage.
Increased static Queue sizes to 20000, should not crash at the 2000 polygon limit.
All texture files can be specified from the command line.
All parts can be enabled/disabled (stars, clouds, sun, ground terrain).
Some other performance improvements
Don't render polygons which are below "sea level"
Don't perform unneeded processing for the top down window.
Added new screenshots.
Generated new documentation.
Almost got Linux to compile again.
Updated web site.

05-19-99 V0.8.4

DDG gets its own web site.
Cloud and demo integrated, partially working.

05-16-99 V0.8.3

Fixed update to only recalculate anything if the camera actually moves.

05-13-99 V0.8.2

Changed rendering to use coloured vertices to give some sense of scale.
Added startup parameters for various things.

05-06-99 V0.8

Clipping is now performed on Wedgie volumes instead of the triangles.
Visibility information is now calculated correctly and used. It is not a 100% accurate test, but a conservative test which works pretty good when there are at least 200 triangles in the mesh.
Several rendering problems w.r.t line drawing are fixed.
FPS calculation was wrong because elapsed time was queried twice per frame. I am getting about 16FPS in 300x300x24mode with OpenGL rendering ~500 triangles This is under W32 no HW accel. The base mesh contains 513x513 points about a half million triangles.
Many optimizations, vertices are ony transformed to camera space as needed now. Frustrum clipping also takes advantage of fact that if parent was wholly in frustrum, child will be as well.
Merge Diamonds which are outside of the viewing frustrum are now cleaned up and recycled to allow more splits in the visible part of the mesh.

04-27-99 V0.7

Screen space error calculation finally works.
Still needs to be optimized though.
Restructure TBinTree to derive from TriMesh, all rendering code is now outside of TBinTree, TBinTree only answers questions about triangles.
Split TBinTree in to unique and shared pieces. The class TBinMesh maintains the data which is constant for all TBinTrees, and TBinTree only stores instance specific data.
Upgraded TBinMesh to support many TBinTrees. Triangle splits and merges now work across TBinTrees.
Many fixes to update priority. Still not in a final state.
Optimized initialization of Brother data.
Added some more features to control canyonism/glaciation in landscape generation.
Improved colour handling.
Tested maps of 513x513. (250K tri).

03-04-99 V0.6.4 Internal release

Debug and use screen space priority function.
Triangle priority is now adjusted according to the z distance in camera space coordinates.

28-03-99 V0.6.3 Internal release

Reorganized all error handling.
Add UI components for color control by using MUI.
Fixed texturing on the terrain.

16-03-99 V0.6.2 Internal release

Coded the screen space priority function.
Improved the vector classes by adding operators for various functions.

14-03-99 V0.6.1 Internal release

Tested larger maps of 33x33 and 65x65 (10K tri)

13-03-99 V0.6

Fixed LOD merging bug, bintree grid now increases and decreases LOD as required, from full res down to minimal and back again.

11-03-99 V0.5.2 Internal release

Integrated the Linux and Windows projects to live in the same directory structures.
Fixed normal calculations (normals were upside down).
Overhauled lighting classes.
Implemented visible light object for debugging.

02-03-99 V0.5.1 Minor upgrade

Fixed windows project not to rely on hard coded paths. Note Windows project relies on a directory called ddg_opt and ddg_dbg to exist at the same level as ddg. This is its install directory from which the applications can be run and so they can find DDGCore.ddl.
Fixed paths to use '/' which works on W32 and Linux.
Updated the Cloud application.
- Fixed cloud noise generation.
- Fixed bug in saving TGA files.
- Minor changes to Camera object.
- Added moving sun object with effect similar to HALOs.
Added this file.
Added DDGdata.zip to the archives.

18-02-99 V0.5 Initial Public Release of DDG Toolkit

This is the initial public release of the DDG Toolkit.

Current TODO List

Cleanup/Test geometry functionality.
Detail textures for nearby terrain.
Support for shadow maps.
Trees and other foliage with LOD branches.
Grass.
Fix deletion/destructors/memory leaks. Maybe add reference counting to objects.
Implement own mainloop instead of GLUT main loop to allow proper shutdown. Will take a look at SDL, http://www.devolution.com/~slouken/SDL/ [In progress]
Implement assembler version of distance formula. PIII SIMD version. Also convert world to camera transformation as SIMD function. [Visual C++ SP4 is now available]
Optimize rendering w.r.t. multipass texturing etc.
Star field rotation.
Particle System for rain/snow/waterfalls/rivers.[Idzard is working on this]
Cache neighbour LUT to a file to possibly speed up startup.
Import 3D Studio objects
JPEG support read/write
PGN support write (read is done).
Integrate EiC script engine http://www.kd-dev.com/~eic/

Known Bugs

Plenty of stuff but nothing serious.
Reportedly there is a crash on TNT or TNT2 cards which is preceded by a scrambling of vertices, this can be avoided by not rendering the star field, simply add '-nostars' to the command line. It appears the TNT2 drivers cannot handle the number of points I pass in the vertex array.
Navigation is not working correctly.
Fog does not work correctly on TNT2 cards, it seems some terrain blocks fog is not enabled.