This is a very general textfile containing notes and stuff that
I should not forget. It is in general a mess and not designed as a good
and structured document. Consider it an expansion of my memory :-)


-----------------------
From: Jorrit
Subject: Dynamic Worlds
Date: 28-Sep-1998
-----------------------

Normally the portal approach lends itself very well for dynamic worlds.
However, the big problem is lighting. Static lightmaps are very static
(as you can imagine :-) and are difficult to scale/recompute. This severely
restricts what you can do dynamically in general. However, in many specific
cases you can do a lot. Here is a summary of these cases:

First a small definition. The 'sector-lights' is the list of lights that
affect some sector. Every sector will have a 'sector-lights' list containing
not only the lights in that sector but every light that shines through the
sector. It will contain dynamic, psuedo-dynamic and static lights.

Another small note about lighting. Crystal Space currently has static lights,
pseudo-dynamic lights and dynamic lights. The pseudo-dynamic lights are an
extension on the static lights which allow the static light to change color
or intensity but not move. The advantage of pseudo-dynamic lights compared to
real dynamic lights is that shadows are computed more correctly,
Pseudo-radiosity will also work correctly and there is no run-time
view-frustrum calculation as with dynamic lights. Their only disadvantage is
that they cannot move.

- CREATING A NEW THING. When you create a new thing it is easy to update the
  static lightmaps for that thing. This involves taking all lights in the
  sector-lights list and doing a view frustrum calculation for all the static
  lights and only for the new Thing. This only means that lighting on the
  Thing itself will be correct but it will not mean that the Thing will cast
  shadows for static lights. Calculating correct shadows is more complicated
  and time consuming. We cannot just update the lightmaps of the polygons
  that will become shadowed since there is no way to know how much light we
  should remove. The problem is that there is an upper light-level. If many
  lights affect the same lumel then it will be capped. When that happens
  you cannot just subtract a light because it will then not correspond with
  the real amount of light still reaching the lumel. The only way to correct
  this would be to redo all static lighting precalculation for those polygons.
  This is time-consuming.

- DESTROYING A THING. In this case it would be easier to remove the shadows.
  You can redo the needed static lighting precalculations. However you have
  to be careful here!! If you remove a Thing which was added without doing
  shadows (previous paragraph) then you should not remove shadows!
  So we have to remember if a Thing has casted shadows or not so that we can
  remove them.

- MOVING A THING. This basicly boils down to first destroying it and then
  recreating it at another position. There is an optimization possible.
  If we know that a Thing is ment to move from one position to another
  without interruption then we can calculate the lightmaps as they will
  become finally (at the last position) and just linearly interpolate the
  lightmaps in between.

- OPENING A PREDEFINED PORTAL. In future it will be possible to flag polygons
  as having a portal which is closed. When you open this portal you'll have
  to recalculate all lighting that goes through the new portal. If you know
  in advance that some polygon is going to be opened in the future you can
  already store a lot of helpful information together with this portal to
  make calculation easier. One possibility would be to store the light-patches
  combined with view-frustrum for every light that hits the polygon. We can
  then just continue the static lighting precalculation when the portal
  opens. This would be useful for doors that open and when opened let through
  the light: the door would be a Thing. When closed the portal is also closed
  and blocks the light. As soon as the door opens the portal opens and
  let's the light come through. A disadvantage is that this will be sudden
  and not gradual (as the door opens). But I think this is better than not
  relighting at all. But see the discussion in the next paragraph.

- CLOSING A PREDEFINED PORTAL. The problem with the previous approach is that
  you cannot in general use it for closing a portal again. The problem is
  that while it is easy to add light to a static lightmap you cannot easily
  remove light (since lightvalues are capped to a maximum). So the above
  solution would really only be useful for doors that once opened, remain
  open for the rest of the game. But maybe we have another solution. When
  the engine knows that a portal can open/close we can do the static lighting
  calculations as usual but store all lighting information that came through
  that portal in seperate static lightmaps. That would be surprisingly easy
  to do. What this means is that polygons may have several series of static
  lightmaps which are conditionally used depending on the state of nearby
  portals.
  Another big advantage of this approach is that you can then use linear
  interpolation to interpolate between the two static lightmaps when a door
  is opening. For example, when a door is 50% open you show 50% of the
  first static lightmap and 50% of the second.

- OPENING AN ARBITRARY PORTAL. In principle it is possible to open portals
  everywhere you want, to anywhere you want. In this case however it is
  more difficult to adjust the lighting. You can still do it but more slowly.
  Opening arbitrary portals is going to be useful when you create new sectors
  to simulate destroying a wall. For example, when you shoot a missile at
  a wall you could create a new portal on that wall which simulates a hole.
  You could also create a whole new sector behind the wall.
  Note that this is getting a little complicated. Calculating the lighting
  is relatively easy as the sector is brand new and you can just calculate
  the lighting. See also the 'BREAKING THROUGH' section.

- CLOSING AN ARBITRARY PORTAL. No problem but you'll not be able to remove
  the lighting easily without recomputing a LOT. Note that in the current
  version of Crystal Space portals also have correctly lighted lightmaps
  so closing a portal will yield a polygon which is correctly lighted.

- BREAKING THROUGH. When you fire a missile at a wall you may expect to be
  able to break through to the sector that is behind that wall. Aside from
  the portal and lighting problems there is an additional problem here.
  The portal world does not in itself have spatial information like this.
  It does NOT know that there is a sector behind that polygon. In fact there
  really is no concept of 'behind a polygon' unless the polygon happens to
  be a portal. This would of course be a solution. If you make breakable
  walls state-portals (portals which can be closed and opened on demand
  like explained earlier) then there is no problem. But if you want to
  support this in general then we'll need to find a way to calculate
  spatial information like this. Calculating this at run-time is probably
  too expensive (you have to traverse every sector in the world and see
  which one you're arriving in). One way to solve this would be with a
  sparse 3D matrix which contains all sectors that intersect with a given
  3D cube. This could be precalculated and would greatly improve the speed
  of testing in which sector a given 3D location falls. This of course only
  works with worlds which are 'standard' and contain no special space-
  warping features (like overlapping sectors). Mirrors and reflecting
  surfaces would be ok as they can be flagged as not defining extra
  geometry but only reflecting existing geometry.

- ADDING A STATIC LIGHT. In some cases it may be a good option to have the
  ability to add a static light. Static lights have the advantage that there
  is no run-time overhead as soon as they are merged with the other static
  lights. So if you want to be able to put a light at an arbitrary position
  which is never going to be removed again then you should be able to create
  new static lights. Note that you can (and should) use pseudo-dynamic
  lights when you know in advance where the light is going to be. A good
  option would probably be the ability to merge a pseudo-dynamic light with
  the static lights. When you know that a pseudo-dynamic light is never
  going to change then this would be a very good idea. So converting a
  pseudo-dynamic light to a static light should be possible.

- REMOVING A STATIC LIGHT. This is more complicated. In general you should
  use pseudo-dynamic lights for this. The pseudo-dynamic light can be on
  by default. When you want the light to be removed (for example because
  it is destroyed by a missile or something). You can set the intensity
  of the pseudo-dynamic light to black and then remove it from the world.


-----------------------
From: Dan Ogles
Subject: Micromapping and Macromapping
Date: 24-Sep-1998
-----------------------

While we're on the subject, I thought I'd bring up something. Unreal has a
feature that they call 'macromapping' and 'micromapping'. The feature is
only available on 3d accelerators that support transparency. What this is is
that they alpha-blend a much larger texture onto polygons if they are being
viewed from far away to reduce the tiling effect (macro-mapping), and they
blend a much smaller, more densly packed texture when viewing up close to
give the appearance of higher-res textures. Any one who has played Unreal on
a Voodoo would probably agree - the effect was amazing. Up until recently, I
thought that they were using large, super hi-res textures to do this. But
using the macro/micro mapping scheme is ultimately more efficient because it
is faster on 3D accelerators to blend two textures onto each other rather
than cache a really hi-res texture. 

This doesn't seem like it'd be too hard to implement, except in software
(Unreal does not support this feature in software). What does everyone
think?



-----------------------
From: Jorrit and Philipp Spöth
Subject: 16-bit Truecolor Texture Cache
Date: 28-Sep-1998
-----------------------

Philipp presented an improvement of the 16-bit texture cache
which will really be an improvement when I implement 24/32-bit internal
textures in Crystal Space. Not only will this make the texture cache
considerably faster (I think it will be a significant amount) but it will
also improve the visual quality since all textures will be 24-bit. The
only downside is that it makes textures four times bigger but since this is
only for the unlighted textures I don't think this is a big problem.
We will also be able to remove the 16-bit private colormap mode as this
will then be obsolete.



-----------------------
From: Jorrit
Subject: Lighting
Date: 28-Sep-1998
-----------------------

Here is a summary of all lighting features that are still missing in Crystal Space.

    1. Things are correctly lighted by the dynamic lights as long as the thing remains
       stationary. When the thing moves (and the dynamic light doesn't) then the lightmaps
       for the thing will not be updated.
    2. Things don't cast shadows for dynamic lights.
    3. Lighting on things is not updated for static lights when the thing moves.
    4. Static shadows that a thing casts are not updated when the thing moves.
    5. Static lighting which is reflected (by a mirror/reflecting surface or else by radiosity)
       does not correctly take things in acount.
    6. The triangles of 3D sprites must be lighted.
    7. 3D sprites don't cast shadows for any kind of light.

To solve many of the above problems I will use a list of lights for every sector. This list
will contain all static and dynamic lights which affect the sector. This is easy to compute
and will come automatically as a result of the frustrum calculation that happens
for every static and dynamic light. We call this list 'sector-lights'.

Here I go over every lighting feature (as numbered above) and possible implementation
issues:

1. Here we will need to recalculate all dynamic lights on the old position and the new
   position (when the thing moves). To find all those lights we can use the sector-lights.
   We'll have to recalculate the whole view frustrum of those dynamic lights.

2. There are a few possibilities here. First we could try to simulate correct shadows by
   finding a fast way to test for intersection of a light-beam with every thing that stands
   in the way. This needs to be very fast. Maybe we can just implement this and then
   disable this on slow computers?
   Another way to have some shadow is to only cast a shadow just below the thing. Maybe
   something like this can be done with a negative dynamic light (one that doesn't cast light
   but casts darkness instead :-) This would be more efficient (equivalent to dynamic lighting)
   but less accurate.

3. One way to solve this problem is to avoid it. When we tag things which can move with
   a special flag then we can switch to the sprite way of lighting/shadows (see below).
   In principle, recomputation of the static lightmaps is also possible but of course rather slow
   since they are shadow correct. What we can do to fix this is to consider static lights as
   dynamic lights for this thing. Since static lighting and dynamic lighting share a lot of code
   and are very compatible this is not difficult to do.

4. Same problem as 3. Also same solutions.

5. Well, this is a bug that I still need to fix :-)

6. We can use uniform lighting for the sprite triangles or else gouraud/phong or any other
   shading mechanism (depending on what the hardware/software can handle). In any case
   we are going to use the sector-lights list and for every triangle/vertex (depending on how
   we shade) we will calculate the amount of light that reaches it. We can hardly check if a
   light can reach every triangle/vertex but we can check if a light can reach some central
   point in the sprite. That way a sprite which is in a sector that is affected by many lights
   but which is currently standing in a dark part of that sector will not be lighted too much.

7.  Similar solutions to 2.


-----------------------
From: Jorrit
Subject: Fog-volumes
Date: 28-Sep-1998
-----------------------

It is very easy to create fog-volumes as a result from the view-frustrum
calculations that are used by lighting. These fog-volumes could then be
used to simulate particles that are lighted by the sun. Imagine a room
with windows through which the sun shines. The room is very dark otherwise
but you can see the dust which floats in the room being lighted by the
sun :-)  I think this would be very nice and not too difficult to do.
The generation of the fog-volumes would be easy (and could even be done
real-time for dynamic lights!!!) but how to render them?


-----------------------
From: Jorrit
Subject: Shared plane optimization
Date: 16-Oct-1998
-----------------------

Just something that should not be forgotten. For the software version and 
I think also for the hardware accelerated versions there are a lot of calculations 
that are done for every polygon (the DrawPolygon function). That function 
only prepares the actual rendering and then does the triangulation but it does 
not actually render. Nevertheless it still comes up pretty high in the profiling 
results. 

But most of the calculations done there are independent of the polygon and only 
depend on the plane of the polygon. Since many polygons share planes in Crystal 
Space (for example, the floor of large.zip is actually a number of polygons sharing 
a common plane) a lot of those calculations could be shared for those polygons. 

I think this might give a considerable speed increase and would make it less costly 
to split polygons. Splitting polygons has the advantage that it increases the 
efficiency of the texture cache and also allows to represent concave surfaces. 
Currently splitting polygons gives a rather large overhead because this multiplies 
the number of calls to DrawPolygon. 


-----------------------
From: Jorrit
Subject: Overlay-textures in Cache
Date: 19-Oct-1998
-----------------------

I have an idea which would be easy to implement and which would
allow for more dynamic textures. The idea is somewhat inspired by the
game Duke Nukem 3D where your footsteps and bullet imprints remain
visible on the polygon that is hit. Something like this would be very easy
to do in CS. We can have small textures which can be overlayed on a
polygon. This overlaying could happen in the texture cache just before
lighting occurs (this would make texture cache handling of such a texture
a bit slower but only if there is actually something to draw).

These overlay-textures can just be copied (with a transparent color) onto
the large texture or even alpha blended.

Using such techniques you could really paint on polygons.

Some possible uses are:
    - blood stains
    - footprints
    - bullet holes
    - explosion burns (part of the texture is blackened because of
      a nearby explosion)
    - graffiti
    - leaving messages on the wall for other players (that would be nice!)


-----------------------
From: Jorrit
Subject: REAL lighting
Date: 6-Nov-1998
-----------------------

Use the formula intensity = source / distance^2 for
lighting.

