Author Topic: Custom VoxelTypes  (Read 17621 times)

d3x0r

  • Jr. Member
  • **
  • Posts: 75
    • View Profile
Custom VoxelTypes
« on: November 09, 2014, 01:26:37 am »
Success!
I have a block called 'fertile ground' that in a second or 2 from creation grows 'low foliage' aka food.
food will eventually age and become medium and tall; which will be unusable by the first animals... a block called rabbit and a block called fox....
------------
I implemented a type called ZVoxelRef
Code: [Select]
#ifndef ZVOXEL_REF_DEFINED
#define ZVOXEL_REF_DEFINED

#include "ZVoxelSector.h"
#include "../ZVoxelExtension.h"
class ZVoxelWorld;
class ZVoxelRef
{
public:
ZVoxelSector * Sector;
int Offset;
int x, y, z;
UShort VoxelType;
ZVoxelWorld *World;
ZVoxelTypeManager *VoxelTypeManager;
ZVoxelExtension *VoxelExtension;
ZVoxelRef( ZVoxelWorld *world, ZVoxelTypeManager *vtm, long x = 0, long y = 0, long z = 0, ZVoxelSector *Sector=NULL, UShort VoxelType = 0, int offset = 0 )
{
this->x = x;
this->y = y;
this->z = z;
this->Sector = Sector;
this->Offset = offset;
this->World = world;
this->VoxelType = VoxelType;
VoxelTypeManager = vtm;
}
static int ForEachVoxel( ZVoxelWorld * World, ZVoxelRef *v1, ZVoxelRef *v2, int (*f)(ZVoxelRef *v) );

};

#endif

that I for implemented for the result of raycast at maxiter... before I changed method to render selection cube in space in front of player...


// modified GetVoxel which just returned the UShort from a world coordinate
//  to return the World, Sector, relative x,y,z within the sector, and the UShort type
// the sector has it's x,y,z scaled world coordinate... so the absolute coord is knowable from the reference.
... reviewing this a little... the ref could be used for all the temp variables themselves... this actually returns a copy of the world coordinate, React uses it as x,y,z within the sector...
Code: [Select]
inline ZVoxelRef *ZVoxelWorld::GetVoxelRef(Long x, Long y, Long z)
{
  ZVoxelSector * Sector;
  Long Offset;

  Sector = FindSector( x>>ZVOXELBLOCSHIFT_X , y>>ZVOXELBLOCSHIFT_Y , z>>ZVOXELBLOCSHIFT_Z );

  if (!Sector) return NULL;

  Offset =  (y & ZVOXELBLOCMASK_Y)
         + ((x & ZVOXELBLOCMASK_X) <<  ZVOXELBLOCSHIFT_Y )
         + ((z & ZVOXELBLOCMASK_Z) << (ZVOXELBLOCSHIFT_Y + ZVOXELBLOCSHIFT_X));

  return new ZVoxelRef( this, VoxelTypeManager, x, y, z, Sector, Sector->Data[Offset], Offset );
}


inline UShort ZVoxelWorld::GetVoxel(Long x, Long y, Long z)
{
  ZVoxelSector * Sector;
  Long Offset;

  Sector = FindSector( x>>ZVOXELBLOCSHIFT_X , y>>ZVOXELBLOCSHIFT_Y , z>>ZVOXELBLOCSHIFT_Z );

  if (!Sector) return(-1);

  Offset =  (y & ZVOXELBLOCMASK_Y)
         + ((x & ZVOXELBLOCMASK_X) <<  ZVOXELBLOCSHIFT_Y )
         + ((z & ZVOXELBLOCMASK_Z) << (ZVOXELBLOCSHIFT_Y + ZVOXELBLOCSHIFT_X));

  return(Sector->Data[Offset]);
}

-------------
Used this in VoxelReactor to call React virtual method in voxel table...
Code: [Select]
      Long RSx = Sector->Pos_x << ZVOXELBLOCSHIFT_X;
      Long RSy = Sector->Pos_y << ZVOXELBLOCSHIFT_Y;
      Long RSz = Sector->Pos_z << ZVOXELBLOCSHIFT_Z;
  ZVoxelRef ref(World,VoxelTypeManager, 0,0,0,Sector );
    // z, x, y should just be ref.x, ref.y, ref.z, ... redundant copy
      for (z = 0; z < ZVOXELBLOCSIZE_Z; z++)
        for (x = 0; x < ZVOXELBLOCSIZE_X; x++)
          for (y = 0; y < ZVOXELBLOCSIZE_Y; y++)
          {
VoxelType = *(VoxelP);
            if (ActiveTable->Get(VoxelType))
            {
              if (!Sector->ModifTracker.Get( MainOffset ) ) // If voxel is already processed, don't process it once more in the same cycle.
              {
                switch(VoxelType)
                {
default:
  ref.x = x; ref.y = y; ref.z = z;
  ref.Offset = VoxelP - DisplayData;
  ref.VoxelType = VoxelType;

IsActiveVoxels = true;
ref.VoxelExtension = (ZVoxelExtension*)Sector->OtherInfos[MainOffset];
// not sure what St is ...
//St[i]->ModifTracker.Set(SecondaryOffset[i]);
VoxelTypeManager->VoxelTable[VoxelType]->React( ref, LastLoopTime);
break;

« Last Edit: November 09, 2014, 01:33:04 am by d3x0r »

olive

  • Administrator
  • Full Member
  • *****
  • Posts: 149
    • View Profile
Re: Custom VoxelTypes
« Reply #1 on: November 09, 2014, 11:19:41 pm »
Success!
I have a block called 'fertile ground' that in a second or 2 from creation grows 'low foliage' aka food.
food will eventually age and become medium and tall; which will be unusable by the first animals... a block called rabbit and a block called fox....

Interesting ideas. We dreamed to make some agriculture and food in blackvoxel since a long time.  But, be careful of animals that could be present in some other voxel games.
Maybe you could make it as some extra terrestrial animals. If you keep reference to some known animals, they could be very different of what we know. In blackvoxel, the idea is that one should be surprised from what he is expecting (when possible, of course).

Quote
------------
I implemented a type called ZVoxelRef
Code: [Select]
#ifndef ZVOXEL_REF_DEFINED
#define ZVOXEL_REF_DEFINED

#include "ZVoxelSector.h"
#include "../ZVoxelExtension.h"
class ZVoxelWorld;
class ZVoxelRef
{
public:
    ZVoxelSector * Sector;
    int Offset;
    int x, y, z;
    UShort VoxelType;
    ZVoxelWorld *World;
    ZVoxelTypeManager *VoxelTypeManager;
    ZVoxelExtension *VoxelExtension;
    ZVoxelRef( ZVoxelWorld *world, ZVoxelTypeManager *vtm, long x = 0, long y = 0, long z = 0, ZVoxelSector *Sector=NULL, UShort VoxelType = 0, int offset = 0 )
    {
        this->x = x;
        this->y = y;
        this->z = z;
        this->Sector = Sector;
        this->Offset = offset;
        this->World = world;
        this->VoxelType = VoxelType;
        VoxelTypeManager = vtm;
    }
    static int ForEachVoxel( ZVoxelWorld * World, ZVoxelRef *v1, ZVoxelRef *v2, int (*f)(ZVoxelRef *v) );

};

#endif

that I for implemented for the result of raycast at maxiter... before I changed method to render selection cube in space in front of player...


// modified GetVoxel which just returned the UShort from a world coordinate
//  to return the World, Sector, relative x,y,z within the sector, and the UShort type
// the sector has it's x,y,z scaled world coordinate... so the absolute coord is knowable from the reference.
... reviewing this a little... the ref could be used for all the temp variables themselves... this actually returns a copy of the world coordinate, React uses it as x,y,z within the sector...
Code: [Select]
inline ZVoxelRef *ZVoxelWorld::GetVoxelRef(Long x, Long y, Long z)
{
  ZVoxelSector * Sector;
  Long Offset;

  Sector = FindSector( x>>ZVOXELBLOCSHIFT_X , y>>ZVOXELBLOCSHIFT_Y , z>>ZVOXELBLOCSHIFT_Z );

  if (!Sector) return NULL;

  Offset =  (y & ZVOXELBLOCMASK_Y)
         + ((x & ZVOXELBLOCMASK_X) <<  ZVOXELBLOCSHIFT_Y )
         + ((z & ZVOXELBLOCMASK_Z) << (ZVOXELBLOCSHIFT_Y + ZVOXELBLOCSHIFT_X));

  return new ZVoxelRef( this, VoxelTypeManager, x, y, z, Sector, Sector->Data[Offset], Offset );
}

inline UShort ZVoxelWorld::GetVoxel(Long x, Long y, Long z)
{
  ZVoxelSector * Sector;
  Long Offset;

  Sector = FindSector( x>>ZVOXELBLOCSHIFT_X , y>>ZVOXELBLOCSHIFT_Y , z>>ZVOXELBLOCSHIFT_Z );

  if (!Sector) return(-1);

  Offset =  (y & ZVOXELBLOCMASK_Y)
         + ((x & ZVOXELBLOCMASK_X) <<  ZVOXELBLOCSHIFT_Y )
         + ((z & ZVOXELBLOCMASK_Z) << (ZVOXELBLOCSHIFT_Y + ZVOXELBLOCSHIFT_X));

  return(Sector->Data[Offset]);
}


There is a function like this in ZVoxelWorld::GetVoxelLocation() and the VoxelLocation structure returned provide most of the informations about a Voxel. I'll explain how to use it.

There is a particularity in C++ games : the  operator "new" should be avoided in "game loops" whenever possible because use of the system heap memory manager is always slow (and could lead to massive use causing memory fragmentation problems).
There is no garbage collector like in C# or Java, so that's very different in programming style.

We used some ways to avoid problem:

In Blackvoxel, we use a custom "recycling" memory manager for some classes which absolutely needed "on the fly" memory allocation.

But the simpler and best way in most case is to declare a "stack variable" structure in the caller and pass it to the a function that will fill it. That's what GetVoxelLocation() is doing.

Quote
-------------
Used this in VoxelReactor to call React virtual method in voxel table...
Code: [Select]
      Long RSx = Sector->Pos_x << ZVOXELBLOCSHIFT_X;
      Long RSy = Sector->Pos_y << ZVOXELBLOCSHIFT_Y;
      Long RSz = Sector->Pos_z << ZVOXELBLOCSHIFT_Z;
      ZVoxelRef ref(World,VoxelTypeManager, 0,0,0,Sector );
    // z, x, y should just be ref.x, ref.y, ref.z, ... redundant copy
      for (z = 0; z < ZVOXELBLOCSIZE_Z; z++)
        for (x = 0; x < ZVOXELBLOCSIZE_X; x++)
          for (y = 0; y < ZVOXELBLOCSIZE_Y; y++)
          {
            VoxelType = *(VoxelP);
            if (ActiveTable->Get(VoxelType))
            {
              if (!Sector->ModifTracker.Get( MainOffset ) ) // If voxel is already processed, don't process it once more in the same cycle.
              {
                switch(VoxelType)
                {
                default:
                      ref.x = x; ref.y = y; ref.z = z;
                      ref.Offset = VoxelP - DisplayData;
                      ref.VoxelType = VoxelType;

                    IsActiveVoxels = true;
                    ref.VoxelExtension = (ZVoxelExtension*)Sector->OtherInfos[MainOffset];
                    // not sure what St is ...
 //St[i]->ModifTracker.Set(SecondaryOffset[i]);
 VoxelTypeManager->VoxelTable[VoxelType]->React( ref, LastLoopTime);
                    break;

As we said, an extension will be added to support this kind of stuff. Be patient as we'll finish it in the next few days (we understand you need it).

We need to think it well and not precipitate because there is some important considerations to make it useable easily.

Quote
// not sure what St is ...

St is a table holding sector pointers for the neighbor points. The problem with MVI is accessing quickly neighbor voxels that could be in another sectors than the one where the voxel is located.
The modif tracker is a system recalling "processed" voxels in order to avoid moving these again in the same MVI cycle.

The Blackvoxel Team

d3x0r

  • Jr. Member
  • **
  • Posts: 75
    • View Profile
Re: Custom VoxelTypes
« Reply #2 on: November 10, 2014, 10:17:25 am »

Interesting ideas. We dreamed to make some agriculture and food in blackvoxel since a long time.  But, be careful of animals that could be present in some other voxel games.
Maybe you could make it as some extra terrestrial animals. If you keep reference to some known animals, they could be very different of what we know. In blackvoxel, the idea is that one should be surprised from what he is expecting (when possible, of course).
I agree; was going to make some cyber-space names for them.. but fell back to my idea of foxes and rabbits .... predator/prey and make the foliage be like data nodes... but the concept of growth didn't apply so much... am open to ideas ... maybe 'bit scav'/'virus' and 'antivirus'... so a virus consumes data and anti-virus consumes viruses...

general properties of an 'animal'
health/data size
damage/data consumption
level/entities consumed  (improve damage application effectiveness)
propagation_threshold - if health > threshold spawn new X
age maybe - builtin obsolescence
scent?

----------
Something I've been considering; making transparent voxels have a base voxel extension that can store other voxels... fish in water; animals in plants, animals sharing spots... 1) animals could attack horizontally and just require nearness... 2) animals could be 'on top of' plants... 3) could be a meta voxel type 'fish in water' that behaves like water... but...
Something I'd like to implement is 'smell' that is empty (air) voxels will be like a textureless voxel that's not zero; and contain information about aromas in the air...

normally the player isn't a voxel; so voxels that are player-like should also respect 'can player pass through' ... but then they would be in the voxel.... and since there's only a current reprensentation of a single voxel type in any voxel, it could be an interface implemented on transparent voxels that allow being 'in' the voxel.  Can do a multi-layered render of the voxel at some point to represent the contained voxels... thoughts?  I will assert that from previous experience, I think you'd prefer to keep to a purist approach, and animals will just hop from ground to the top of foliage, and animals can attack animals nearby disregarding height differences.. and then I can't really populate air ... because eventually aroma voxels will exist above fertile land and prevent growth....

Quote

There is a particularity in C++ games : the  operator "new" should be avoided in "game loops" whenever possible because use of the system heap memory manager is always slow (and could lead to massive use causing memory fragmentation problems).
There is no garbage collector like in C# or Java, so that's very different in programming style.
depends on your allocer; most malloc will return the same block as was last freed... so allocating short term storage doesn't fragment.. yes returning into a caller-owned struct solves it.... was more concerned with keeping the function signature the same for quickness; and when not deleted was what was causing my memory error :)  ended up removing that.

well... memory deallocated is defragmented and allowed for reuse; so the things you throw away are collected, so there is garbage collection; just not automagic object reference increment/decrements... and garbage on the stack is collected...

And even so; you still have to intentionally throw away things like Datatables because of the circular references they won't auto implode.... so you should never count on things just going away.

free works kinda like ZMonoSizeMemoryPool::Free such that when released, it's immediately reused for new mallocs...
I find it's better to do a slight more work, and do 2 comparisons in the free list to order free blocks from least memory address to most; further reducing fragmentation... also if the allocer has a minimum memory block size there's less chance of having blocks that are not big enough laying around; my MUD terminal (dekware) improved greatly by setting minimum alloc at 60 bytes... at not that much increase in memory usage.
Also block types that are tiny like binary tree nodes come from a pool of structs so there's only a few allocs from physical memory.

so ya; I saw the techniques and recognized their purpose :) 
----------------------------

And back on aromatics; could do seed dropping too... for vegetation... maybe fertile gruond is just ground until fertilized... I kind of see an evolution of foliage more.. so it's not just that it's A plant that grows, but really the plant type changes... so when it propagates, a 'tall/thick foliage' would cause more thick folliage to grow... that itself being an enemy to the vegetation consumer... I guess the diffusion function would be different for that...



d3x0r

  • Jr. Member
  • **
  • Posts: 75
    • View Profile
Re: Custom VoxelTypes
« Reply #3 on: November 10, 2014, 12:52:38 pm »
Hmm... does the mem pool really help?  Is new and delete not really based on malloc/free?  Glibc usually collects garbage pretty well... I had my own memory allocator that was in the core of my library; still do, just hard to initialize a dynamic program without having initialized memory; and sometimes core debugging becomes impossible....

In my library I made a set allocator which is a linked list of nodes that have a bitmap mask of used mono-sized nodes... also keep a counter of used nodes so can just check if all used, otherwise scan the bits 32 at a time until it's not ~0 ... otherwise allocates a new block of nodes... so all nodes are continuous in memory ...

even if you're recycling previously allocated things, they're still jumbled all over memory....

d3x0r

  • Jr. Member
  • **
  • Posts: 75
    • View Profile
Re: Custom VoxelTypes
« Reply #4 on: November 12, 2014, 10:00:54 am »
Managed to add Aroma Generator and Aroma types.
Aroma diffuses itself such that if it is near itself, it moves away from itself, otherwise if it is not in free space it moves.  I dunno basically it works pretty well... gave me something to think about regarding inter-mingling voxels, and various things... like 'wind' .... and what it actually is useful for... and what meaning it would have...

the particles also age-out so after 12 seconds they evaporate... but worked good for a long time without despawning... also had a really cool overflow that resulted in a solid growing bubble form... not sure if the inside was just solid transparent of it if was just the outside sheet somehow... but it's fixed now and that was a memory fault anyway...

https://github.com/d3x0r/Blackvoxel/blob/group_voxel_datas/src/ZVoxelType_AromaGenerator.cpp
https://github.com/d3x0r/Blackvoxel/blob/group_voxel_datas/src/ZVoxelType_Aroma.cpp

also; in consideration of making a container for voxels, needed to know what a voxel was, so I reimplemented Sector->Data,OtherInfos,TempInfos as VoxelData *Data;

https://github.com/d3x0r/Blackvoxel/blob/group_voxel_datas/src/ZVoxelSector.h#L203

------------
just messing around... it is rather stable backend for dynamic updates to voxels ...

noting that there should be some more standard routines... like to get the array of voxels around a single voxel...

----------
Oh; a sector reactor... to do computations between sectors... could use a point per sector as a air pressure, and create a gradient between sectors for 'wind'... wind as a velocity could represent a propability of motion in time rather than a linear motion....

1.0 = 1 voxel in (100ms?) a 1 tick... how long is a 'tick' target?
0.5 = 50% chance to move 1 voxel in 1 tick.. something... for partial motions... I guess use the fraction as a proabilty to move one more (if available )... might work


olive

  • Administrator
  • Full Member
  • *****
  • Posts: 149
    • View Profile
Re: Custom VoxelTypes
« Reply #5 on: November 12, 2014, 11:50:14 pm »

Interesting ideas. We dreamed to make some agriculture and food in blackvoxel since a long time.  But, be careful of animals that could be present in some other voxel games.
Maybe you could make it as some extra terrestrial animals. If you keep reference to some known animals, they could be very different of what we know. In blackvoxel, the idea is that one should be surprised from what he is expecting (when possible, of course).
I agree; was going to make some cyber-space names for them.. but fell back to my idea of foxes and rabbits .... predator/prey and make the foliage be like data nodes... but the concept of growth didn't apply so much... am open to ideas ... maybe 'bit scav'/'virus' and 'antivirus'... so a virus consumes data and anti-virus consumes viruses...

general properties of an 'animal'
health/data size
damage/data consumption
level/entities consumed  (improve damage application effectiveness)
propagation_threshold - if health > threshold spawn new X
age maybe - builtin obsolescence
scent?

----------
Something I've been considering; making transparent voxels have a base voxel extension that can store other voxels... fish in water; animals in plants, animals sharing spots... 1) animals could attack horizontally and just require nearness... 2) animals could be 'on top of' plants... 3) could be a meta voxel type 'fish in water' that behaves like water... but...
Something I'd like to implement is 'smell' that is empty (air) voxels will be like a textureless voxel that's not zero; and contain information about aromas in the air...

We encourage you in your searching.  :)

Quote
normally the player isn't a voxel; so voxels that are player-like should also respect 'can player pass through' ... but then they would be in the voxel.... and since there's only a current reprensentation of a single voxel type in any voxel, it could be an interface implemented on transparent voxels that allow being 'in' the voxel.  Can do a multi-layered render of the voxel at some point to represent the contained voxels... thoughts?  I will assert that from previous experience, I think you'd prefer to keep to a purist approach, and animals will just hop from ground to the top of foliage, and animals can attack animals nearby disregarding height differences.. and then I can't really populate air ... because eventually aroma voxels will exist above fertile land and prevent growth....

Yep, there is the paradigm to keep the rendering of all voxels the same and strictly cubic. That's a choice that will make sense in the future.
That's not something we consider we couldn’t change at all. There is pro and cons in the two ways.
But if we found there is better advantages to change, we'll do it.

In some ways, the "smells" are gas, so like the yellow gas.
Voxel Animals should'nt use the flag 'can player pass through'. When moving, they could either discard "gas" voxels or exchange their positions.
The water is doing that : When moving, a block of water exchange it's position with the gas located in the destination location.
For vegetation, they could simply delete gas voxels in growing over.

Quote
depends on your allocer; most malloc will return the same block as was last freed... so allocating short term storage doesn't fragment.. yes returning into a caller-owned struct solves it.... was more concerned with keeping the function signature the same for quickness; and when not deleted was what was causing my memory error :)  ended up removing that.

well... memory deallocated is defragmented and allowed for reuse; so the things you throw away are collected, so there is garbage collection; just not automagic object reference increment/decrements... and garbage on the stack is collected...

And even so; you still have to intentionally throw away things like Datatables because of the circular references they won't auto implode.... so you should never count on things just going away.

free works kinda like ZMonoSizeMemoryPool::Free such that when released, it's immediately reused for new mallocs...
I find it's better to do a slight more work, and do 2 comparisons in the free list to order free blocks from least memory address to most; further reducing fragmentation... also if the allocer has a minimum memory block size there's less chance of having blocks that are not big enough laying around; my MUD terminal (dekware) improved greatly by setting minimum alloc at 60 bytes... at not that much increase in memory usage.
Also block types that are tiny like binary tree nodes come from a pool of structs so there's only a few allocs from physical memory.

so ya; I saw the techniques and recognized their purpose :)

In fact, the problem is like most optimisation problems : there is a limit to what a general approach can do.

As clever as memory manager could become on some systems, these algorithms remains tuned for general case.

That's why the best system memory manager would remain not optimal for all particular cases and particularly for some cases in video games.

There is also intrinsic limitation with C++ : a system memory manager can't defragment two blocs if you keep one in between. Because there is no reference tracking in C++, there is no way to move that memory.

Also, any defragmenting operation means system will take some CPU time to do it.

In fact, most system memory manager use complicated strategy. On the source code of the glibc, we can read that the strategy depends on the block size. The algorithm is explained in the source code. It doesn't fit well all the cases.

That's also mean something we want to avoid : heuristic approach in these algorithms could lead to unpredictable variability between systems and different memory manager.

Garbage collectors do more than simple memory management, they are tracking unused blocks in order to avoid the obligation of explicit memory freeing.

In Blackvoxel, we doesn't ban system memory manager : we use it for all is general, long term and non intensive memory use.

There is two custom allocators in Blackvoxel and there are used depending on the needs. There is one for specific size memory management and one other for more variable size.

Hmm... does the mem pool really help?  Is new and delete not really based on malloc/free?  Glibc usually collects garbage pretty well... I had my own memory allocator that was in the core of my library; still do, just hard to initialize a dynamic program without having initialized memory; and sometimes core debugging becomes impossible....

In my library I made a set allocator which is a linked list of nodes that have a bitmap mask of used mono-sized nodes... also keep a counter of used nodes so can just check if all used, otherwise scan the bits 32 at a time until it's not ~0 ... otherwise allocates a new block of nodes... so all nodes are continuous in memory ...

even if you're recycling previously allocated things, they're still jumbled all over memory....

Yep, the custom allocators in Blackvoxel helps a lot. For both fragmentation and speed.

These are really blazing fast and doesn't cause any fragmentation growing, even with the most intensive use.

As you guessed, it uses underlying system allocation. But the subtlety is that the memory is never returned to the system, but always recycled. So after a little startup time, no system allocation calls are made.

Of course, this approach have also drawbacks. It's not suited for everything, not even in Blackvoxel.

So, memory management is another case of the optimisation problem leading to the best compromise for each particular needs.

Quote
even if you're recycling previously allocated things, they're still jumbled all over memory....

Our goal with fragmentation isn't to avoid it completely or to make things perfect, but rather to avoid weird degenerative problems after some time of gaming.

The other goals are to get it the fastest as it is possible and limit variations between systems.

With our custom memory managers, even with billions of calls, the fragmentation doesn't grow over time and recycling is very fast. That's all what we need... :)

The Blackvoxel Team

d3x0r

  • Jr. Member
  • **
  • Posts: 75
    • View Profile
Re: Custom VoxelTypes
« Reply #6 on: November 14, 2014, 06:12:28 am »
Voxel extensions don't come from pooled memory.
Moving a voxel from one place to another that has extension causes new and delete operators; and the new voxel is not the same as the prior... (maybe there's a copy operator)...

but also there is no 'move voxel to' or 'swap voxel with' which could move the reference to the original voxelExtension.

So motion is (set new voxel, create extension ) (clear old voxel, delete old extension)

olive

  • Administrator
  • Full Member
  • *****
  • Posts: 149
    • View Profile
Re: Custom VoxelTypes
« Reply #7 on: November 15, 2014, 02:56:36 am »
Voxel extensions don't come from pooled memory.

Yes, this must be improved.

At origin, Extensions where used only for some non massively used machines.

All "massive" active stuff uses no extension or only 32 bits of the otherinfo as a direct storage (this is possible).

But semi-massive uses may need extensions. So, the actual system must be improved.

Quote
Moving a voxel from one place to another that has extension causes new and delete operators; and the new voxel is not the same as the prior... (maybe there's a copy operator)...

but also there is no 'move voxel to' or 'swap voxel with' which could move the reference to the original voxelExtension.

So motion is (set new voxel, create extension ) (clear old voxel, delete old extension)

These functions exists in Blackvoxel.

That's the ZWorld::MoveVoxel_Sm() and ZWorld::ExchangeVoxels()

With these functions, extensions are simply moved.

But I'm doing a synthetic simple API for easier active voxels creation. It's now published it on Github(but still unfinished).  :)

The Blackvoxel Team

d3x0r

  • Jr. Member
  • **
  • Posts: 75
    • View Profile
Re: Custom VoxelTypes
« Reply #8 on: November 16, 2014, 12:26:08 am »
A large performance increase can be made in the water processor...

Code: [Select]
// original
                              for(i=0,j=4,vCount=0,WaveCount=0;i<4;i++,j++)
                              {
                                cx = x+bft[i].x ; cy = y+bft[i].y ; cz = z+bft[i].z ; SecondaryOffset[i] = If_x[cx]+If_y[cy]+If_z[cz];St[i] = SectorTable[ Of_x[cx] + Of_y[cy] + Of_z[cz] ]; Vp[i] = &St[i]->Data[ SecondaryOffset[i] ].Data;
                                cx = x+bft[j].x ; cy = y+bft[j].y ; cz = z+bft[j].z ; SecondaryOffset[j] = If_x[cx]+If_y[cy]+If_z[cz];St[j] = SectorTable[ Of_x[cx] + Of_y[cy] + Of_z[cz] ]; Vp[j] = &St[j]->Data[ SecondaryOffset[j] ].Data;
                                if (VoxelTypeManager->VoxelTable[*Vp[i]]->Is_CanBeReplacedBy_Water && VoxelTypeManager->VoxelTable[*Vp[j]]->Is_CanBeReplacedBy_Water) {vCount++; DirEn[i]=true;}
                                else DirEn[i]=false;
                                if (VoxelTypeManager->VoxelTable[*Vp[i]]->Is_CanBeReplacedBy_Water) {WaveCount++;WaveDirEn[i] = true;}
                                else                                                                {WaveDirEn[i] = false;}
                              }

// modified; move the test for (*Vp ) as a common point, then Vp[j] doesn't have to be computed, or tested, because it's an and condition with Vp
Code: [Select]

                              for(i=0,j=4,vCount=0,WaveCount=0;i<4;i++,j++)
                              {
                                cx = x+bft[i].x ; cy = y+bft[i].y ; cz = z+bft[i].z ; SecondaryOffset[i] = If_x[cx]+If_y[cy]+If_z[cz];St[i] = SectorTable[ Of_x[cx] + Of_y[cy] + Of_z[cz] ]; Vp[i] = &St[i]->Data[ SecondaryOffset[i] ].Data;
                                if (VoxelTypeManager->VoxelTable[*Vp[i]]->Is_CanBeReplacedBy_Water )
                                {
                                  cx = x+bft[j].x ; cy = y+bft[j].y ; cz = z+bft[j].z ; SecondaryOffset[j] = If_x[cx]+If_y[cy]+If_z[cz];St[j] = SectorTable[ Of_x[cx] + Of_y[cy] + Of_z[cz] ]; Vp[j] = &St[j]->Data[ SecondaryOffset[j] ].Data;
                                  if( VoxelTypeManager->VoxelTable[*Vp[j]]->Is_CanBeReplacedBy_Water) {vCount++; DirEn[i]=true;}
                                  else DirEn[i]=false;
                                  {WaveCount++;WaveDirEn[i] = true;}  // bad braces
                                }
                                else  {WaveDirEn[i] = false; DirEn[i]=false;}
                              }

50% processing time reduction

olive

  • Administrator
  • Full Member
  • *****
  • Posts: 149
    • View Profile
Re: Custom VoxelTypes
« Reply #9 on: November 18, 2014, 02:25:06 am »
A large performance increase can be made in the water processor...

Code: [Select]
// original
for(i=0,j=4,vCount=0,WaveCount=0;i<4;i++,j++)
                              {
                                cx = x+bft[i].x ; cy = y+bft[i].y ; cz = z+bft[i].z ; SecondaryOffset[i] = If_x[cx]+If_y[cy]+If_z[cz];St[i] = SectorTable[ Of_x[cx] + Of_y[cy] + Of_z[cz] ]; Vp[i] = &St[i]->Data[ SecondaryOffset[i] ].Data;
                                cx = x+bft[j].x ; cy = y+bft[j].y ; cz = z+bft[j].z ; SecondaryOffset[j] = If_x[cx]+If_y[cy]+If_z[cz];St[j] = SectorTable[ Of_x[cx] + Of_y[cy] + Of_z[cz] ]; Vp[j] = &St[j]->Data[ SecondaryOffset[j] ].Data;
                                if (VoxelTypeManager->VoxelTable[*Vp[i]]->Is_CanBeReplacedBy_Water && VoxelTypeManager->VoxelTable[*Vp[j]]->Is_CanBeReplacedBy_Water) {vCount++; DirEn[i]=true;}
                                else DirEn[i]=false;
                                if (VoxelTypeManager->VoxelTable[*Vp[i]]->Is_CanBeReplacedBy_Water) {WaveCount++;WaveDirEn[i] = true;}
else {WaveDirEn[i] = false;}
                              }

// modified; move the test for (*Vp ) as a common point, then Vp[j] doesn't have to be computed, or tested, because it's an and condition with Vp
Code: [Select]

for(i=0,j=4,vCount=0,WaveCount=0;i<4;i++,j++)
                              {
                                cx = x+bft[i].x ; cy = y+bft[i].y ; cz = z+bft[i].z ; SecondaryOffset[i] = If_x[cx]+If_y[cy]+If_z[cz];St[i] = SectorTable[ Of_x[cx] + Of_y[cy] + Of_z[cz] ]; Vp[i] = &St[i]->Data[ SecondaryOffset[i] ].Data;
                                if (VoxelTypeManager->VoxelTable[*Vp[i]]->Is_CanBeReplacedBy_Water )
                                {
                                  cx = x+bft[j].x ; cy = y+bft[j].y ; cz = z+bft[j].z ; SecondaryOffset[j] = If_x[cx]+If_y[cy]+If_z[cz];St[j] = SectorTable[ Of_x[cx] + Of_y[cy] + Of_z[cz] ]; Vp[j] = &St[j]->Data[ SecondaryOffset[j] ].Data;
                                  if( VoxelTypeManager->VoxelTable[*Vp[j]]->Is_CanBeReplacedBy_Water) {vCount++; DirEn[i]=true;}
                                  else DirEn[i]=false;
                                  {WaveCount++;WaveDirEn[i] = true;}  // bad braces
                                }
                                else  {WaveDirEn[i] = false; DirEn[i]=false;}
                              }

50% processing time reduction

Thanks for that!

It seems a very good improvement. :)

The Blackvoxel Team

olive

  • Administrator
  • Full Member
  • *****
  • Posts: 149
    • View Profile
Re: Custom VoxelTypes
« Reply #10 on: November 18, 2014, 02:31:29 am »
...
also; in consideration of making a container for voxels, needed to know what a voxel was, so I reimplemented Sector->Data,OtherInfos,TempInfos as VoxelData *Data;

https://github.com/d3x0r/Blackvoxel/blob/group_voxel_datas/src/ZVoxelSector.h#L203

Hum, I wouldn’t recommend doing this.

The way the storage was made is for memory bandwidth efficiency.

Packing these data will lead to waste an important amount of memory bandwidth.

This is a weird side effect of how modern processors access memory with prefetch mechanisms and important bus width : processors can't fetch only a byte or short.

In practice, in Blackvoxel, the different informations about a voxel are rarely used at the same time. Most massive processing operations are mostly done on one unique field.

With packed informations, the processor will fetch also some adjacent data of other fields. These data won't be used.

So, for this case,  it's better to keep each field in it's own array.  ;)

The Blackvoxel Team

d3x0r

  • Jr. Member
  • **
  • Posts: 75
    • View Profile
Re: Custom VoxelTypes
« Reply #11 on: November 18, 2014, 04:11:21 am »

Hum, I wouldn’t recommend doing this.

The way the storage was made is for memory bandwidth efficiency.

Packing these data will lead to waste an important amount of memory bandwidth.

This is a weird side effect of how modern processors access memory with prefetch mechanisms and important bus width : processors can't fetch only a byte or short.

Sectors are 16384 indexes... voxel types are 2 bytes... so 32k or 8 4k pages.
TempInfos is another short for block temperature; this should probably be in an infos since in general blocks don't change behavior based on tempurature....
OtherInfos is 4/8 bytes to reference voxel instance data; VoxelExtension*... 

all together 341 + 4 bytes to 512 per page..........

total is 32k + 32k + 64k(32 bit)/128k(64 bit)  (I've been running 64 bit build, because I have more sectors of smaller voxels usually)

128k/192k ..  32 or 48 pages (4096 bytes) for a sector...

-------------------
I made a branch at that point... I wasn't sure how much of a performance hit it would be... I'm aware of cache... *see below*

I guess given the defined scope of the project
for the renderer which only needs voxel type, then it needs to only fill 8 pages instead of 48... given no custom render for custom voxels... (color shading)... although maybe renderer uses TempInfos to determine texture... so 16 pages; even if blocks are rarely shaded, so temp isn't checked always... could be less...

voxel reactor uses (tempurature?  does temp get modified except by time and water?  Does it dissapate?  Each voxelType have a thermal coefficient thing? :)  ) and OtherInfos... unless a highly static level is used with non extended voxels... with an active environment, OtherInfo will definatly be cached... so no 8+32.. 40 pages loaded without tempurature... so there's no real savings at this level...

Feature: at a voxel-is-center-of-universe view, if I'm given an offset to my data, to get near voxel's (extended)data... I dunno I guess I still need the sector reference...

so ya... a highly static map benefits from only needing 32k loaded for working with a sector (plus another page for the sector, and another for the voxel type manager) ... but then again in a 1M cache 32 sectors can potentially be loaded... so that's only a few more than the block of 9 around the player at any point... so it still has to scroll through the memory...

....
in a sequence of processing blocks, only 4-6 pages are used ... (the center, left/right) (above and below) (forward and backward) , especially on boundaries of sectors... I dunno; the working set is still the same.... this is tripled with the current scheme... because mirror otherinfo, tempinfo pages may be used... 12-18 working set pages...

it resulted in more efficient assembly because there was only one pointer and other offsets computed from that...in the other place I was looking at I do remember noting that...

It may be arguably better if they were allocated all together... and put all voxeltypes and all tempinfos and all otherinfos together instead of interlaced, but with a single pointer...

What is lost is gained in other ways.... and I don't notice a particular performance hit from this change...

--------------

Once upon a time I got to play with/use a logic analyzer that decoded the pins interfacing from 386 to motherboard... got to see read/write memory to fetch instruction blocks... so there's the clearing of cache on calls and jumps backward... jumps forward are better handled by setting a ignore flag and processing the prefetch cache anyway... kinda like how arm handles short jumps.... but anyway... it's just much wider now... and burst mode...
« Last Edit: November 18, 2014, 04:26:34 am by d3x0r »

olive

  • Administrator
  • Full Member
  • *****
  • Posts: 149
    • View Profile
Re: Custom VoxelTypes
« Reply #12 on: November 20, 2014, 03:37:58 am »


Hum, I wouldn’t recommend doing this.

The way the storage was made is for memory bandwidth efficiency.

Packing these data will lead to waste an important amount of memory bandwidth.

This is a weird side effect of how modern processors access memory with prefetch mechanisms and important bus width : processors can't fetch only a byte or short.

Sectors are 16384 indexes... voxel types are 2 bytes... so 32k or 8 4k pages.
TempInfos is another short for block temperature; this should probably be in an infos since in general blocks don't change behavior based on tempurature....
OtherInfos is 4/8 bytes to reference voxel instance data; VoxelExtension*...

all together 341 + 4 bytes to 512 per page..........

total is 32k + 32k + 64k(32 bit)/128k(64 bit)  (I've been running 64 bit build, because I have more sectors of smaller voxels usually)

128k/192k ..  32 or 48 pages (4096 bytes) for a sector...

-------------------
I made a branch at that point... I wasn't sure how much of a performance hit it would be... I'm aware of cache... *see below*

I guess given the defined scope of the project
for the renderer which only needs voxel type, then it needs to only fill 8 pages instead of 48... given no custom render for custom voxels... (color shading)... although maybe renderer uses TempInfos to determine texture... so 16 pages; even if blocks are rarely shaded, so temp isn't checked always... could be less...

voxel reactor uses (tempurature?  does temp get modified except by time and water?  Does it dissapate?  Each voxelType have a thermal coefficient thing? :)  ) and OtherInfos... unless a highly static level is used with non extended voxels... with an active environment, OtherInfo will definatly be cached... so no 8+32.. 40 pages loaded without tempurature... so there's no real savings at this level...

Feature: at a voxel-is-center-of-universe view, if I'm given an offset to my data, to get near voxel's (extended)data... I dunno I guess I still need the sector reference...

so ya... a highly static map benefits from only needing 32k loaded for working with a sector (plus another page for the sector, and another for the voxel type manager) ... but then again in a 1M cache 32 sectors can potentially be loaded... so that's only a few more than the block of 9 around the player at any point... so it still has to scroll through the memory...

....
in a sequence of processing blocks, only 4-6 pages are used ... (the center, left/right) (above and below) (forward and backward) , especially on boundaries of sectors... I dunno; the working set is still the same.... this is tripled with the current scheme... because mirror otherinfo, tempinfo pages may be used... 12-18 working set pages...

it resulted in more efficient assembly because there was only one pointer and other offsets computed from that...in the other place I was looking at I do remember noting that...

It may be arguably better if they were allocated all together... and put all voxeltypes and all tempinfos and all otherinfos together instead of interlaced, but with a single pointer...

What is lost is gained in other ways.... and I don't notice a particular performance hit from this change...

--------------


The problem appears more clearly when looking at the data needed by each part of Blackvoxel involved in massive processing :

- The renderer doesn't use anything else than VoxelType and FaceCulling info. It will be reduced in the future.

- The MVI mostly use VoxelType data. That may sound surprising, but in fact, most scanned voxels aren't active. Even on active voxels, only few are using Extensions. (Even if it may change depending on voxel nature).

- On the sector loader, all data are needed. But each are processed independently. So here again, individual fields would be betters.

- Some temperature processing is planned to be implemented in the future. Thats why the TempInfo table is here. It will probably use Tempinfo and VoxelType. The cycle would be slower than MVI. Not sure when we will do it.

- Some pressure informations could be added in the future when most processors will have at least 8 true cores and according memory bandwidth.

The idea of accessing different data with an unique pointer could be interesting. And we can certainly implement it cleanly with limited changes. But I could not tell you what would be the order of magnitude of the gains(because of the caches). And not yet thinked how we could keep Valgrind detecting MVI memory error.

Quote
and I don't notice a particular performance hit from this change...

This does not surprise me at all. :)

Some Core i7 have more than 30Gb/s of memory bandwidth.

The core 2 quad is much around 10Gb/s.

Core i3 and recent AMD are in between.

And and old intel atom (Single channel DDR2) in a netbook is around 4Gb/s. (Yes, Blackvoxel can run on it with some setting adjustments).

(Note these numbers can vary slightly depending on sources and processor generations).

So, the idea is to keep memory bandwidth in order to run on modest machines, but also for keeping room for future stuff : I'm affraid moore law is now dead.

What is weird with Memory bandwidth is it's shared nature. All cores share the memory controller. So using too much memory bandwidth on one core can reduce efficiency on other cores.

We often realized during Blackvoxel tuning that some changes could react differently depending on the hardware.

Not easy to minimize these side effects. That' why we ran a lot of test and had to correct a lot of things.


Quote
Once upon a time I got to play with/use a logic analyzer that decoded the pins interfacing from 386 to motherboard... got to see read/write memory to fetch instruction blocks... so there's the clearing of cache on calls and jumps backward... jumps forward are better handled by setting a ignore flag and processing the prefetch cache anyway... kinda like how arm handles short jumps.... but anyway... it's just much wider now... and burst mode...

That's recall me the good old time when we worked with 68000, wire wrapping boards, TTL's circuit logic, Eproms, PIA, ACIA and all these amazing stuff. We did our own computer.

I think you are a good programmer as you have learned how the computer's hardware is working under the hood. That's why you can understand and do optimisations. :)

The Blackvoxel Team